DH密钥协商算法报告文档之欧阳美创编Word文档格式.docx
《DH密钥协商算法报告文档之欧阳美创编Word文档格式.docx》由会员分享，可在线阅读，更多相关《DH密钥协商算法报告文档之欧阳美创编Word文档格式.docx（29页珍藏版）》请在冰点文库上搜索。
7
6
4
研究水平与设计能力
25
23
20
18
15
课程设计说明书（论文）撰写质量
设计创新
答辩效果
30
28
22
19
答辩小组成员签名
答辩小组组长签名：
课程设计成绩评定表
成绩汇总
比例
分数
课程设计总分
指导老师评分
50%
答辩小组评分
1.选题背景
密钥协商实际上是一个协议，它通过两个或多个成员在一个公开的信道上通信联合地建立一个秘密密钥，一般情况下，一个密钥协商方案的密钥是某个函数的值，其输入量由通信双方提供，协商过程是由一系列的顺序步骤完成的。
会话密钥由每个协议参与者分别产生的参数通过一定的计算得出。
常见的密钥协商协议，如IKE。
密钥协商协议的生成方式则可分为证书型和无证书型。
证书型是指在会话密钥的产生过程中，由一个可信的证书中心（CA）给参与密钥协商的各方各分发一个证书，此证书中含有此方的，ID及其他信息。
证书型密钥协商协议的优点是提供认证，目前PKI（公钥密码体制）广泛部署，比较成熟，应用面广，且由PKG管理公私钥对有利于统一管理，缺点是计算代价大，需要一个可信的CA，同时证书还需要维护。
无证书型是指各方在进行会话密钥的协商过程中不需要证书的参与，这是目前密钥协商协议的主流种类，优点是不需要CA的参与，减少了计算量，尤其是在低耗环境下应用的更多，同时安全性也不比证书型弱。
几乎没有明显的缺点，只是设计一个安全的更加低耗的无证书密钥协商方案不是很容易。
现有的流行的密钥协商协议，都使用了Diffie-Hellman，它们基本上可以看成是Diffie-Hellman的扩展。
也就是说，群组密钥协商协议可以理解成如何使用Diffie-Hellman来实现群的密钥交换。
2.DH密钥协商算法
2.1算法的产生
Diffie-Hellman密钥交换协议是第一个被提出的密钥协商方案，是美国斯坦福大学的W.Diffie和M.E.Hellman于1976年提出的，它是第一个发表的公钥密码体制，Diffie-Hellman算法的唯一目的就是使两个用户能安全的交换密钥，从而得到一个共享的会话密钥（秘密密钥）。
需要注意的是，该算法本身不能用于加密解密，只能用于密钥的交换，双方确定要用的密钥后，要使用其他对称密钥操作加密算法实际加密和解密消息。
2.2算法的描述
1.离散对数的概念：
1）原根：
如果a是素数p的一个原根，那么数值：
a
mod
p，a^2
p，…，a^（p-1）
p是各不相同的整数，且以某种排列方式组成了从1
到p-1
的所有整数。
2）离散对数：
如果对于一个整数b和素数p的一个原根a，可以找到一个唯一的指数i，使得b
=（a^i）modp，其中0≦i≦p-1，那么指数i称为b的以a为基数的模p的离散对数。
2.算法有效性
Diffie-Hellman
算法的有效性依赖于计算离散对数的难度，其含义是：
当已知大素数p和它的一个原根a后，对给定的b，要计算
i
，被认为是很困难的，而给定
计算b
却相对容易。
3.Diffie-Hellman算法：
假如用户A和用户B希望交换一个密钥。
取素数p和整数a，a是p的一个原根，公开a和p。
1）A选择大的随机数RA（0<
=RA<
=p-2），并计算SA=（a^RA）modp，并且把SA发送给用户B。
2）B选择随机数RB（0<
=RB<
=p-2），并计算SB=（a^RB）modp，并且把SB发送给用户A。
3）A计算密钥的方式是：
K=（SB）^RAmod
p，B计算密钥的方式是：
K=（SA）^RBmod
p，
证明：
（SB）^RAmod
p
=（a^RBmod
p）^RAmod
p
=（a^RB）^RAmod
=（a^RA）^RBmod
（--密钥即为a^（RA*RB）mod
p）
=（a^RAmod
p）^RBmod
=（SA）^RBmod
由于RA和RB是保密的，而第三方只有p、a、SB、SA可以利用，只有通过取离散对数来确定密钥，但对于大的素数p，计算离散对数是十分困难的。
4.例子：
假如用户Alice和用户Bob希望交换一个密钥，取一个素数p
=97和97的一个原根a
=5，Alice和Bob分别选择秘密密钥RA=36和RB=58
，并计算各自的公开密钥：
SA=a^RAmod
=5^36mod97=50
SB=a^RBmod
=5^58mod97=44
Alice和Bob交换了公开密钥之后，计算共享密钥如下：
Alice：
p=44^36mod97=75
Bob：
p=50^58mod97=75
Diffie-Hellman密钥交换协议的基本模式如图2-1所示：
图2-1Diffie-Hellman密钥交换协议的基本模式
2.3算法的安全性
当然，为了使这个例子变得安全，必须使用非常大的RA,
RB以及p，否则可以实验所有的可能取值。
（总共有最多97个这样的值,就算RA和RB很大也无济于事）。
如果
是一个至少300位的质数，并且RA和RB至少有100位长，那么即使使用全人类所有的计算资源和当今最好的算法也不可能从a,
p和a^（RA*RB）mod
中计算出RA*RB。
这个问题就是著名的离散对数问题。
注意g则不需要很大,并且在一般的实践中通常是2或者5。
在最初的描述中，迪菲－赫尔曼密钥交换本身并没有提供通讯双方的身份验证服务，因此它很容易受到中间人攻击。
一个中间人在信道的中央进行两次迪菲－赫尔曼密钥交换，一次和Alice另一次和Bob，就能够成功的向Alice假装自己是Bob，反之亦然。
而攻击者可以解密（读取和存储）任何一个人的信息并重新加密信息，然后传递给另一个人。
因此通常都需要一个能够验证通讯双方身份的机制来防止这类攻击。
有很多种安全身份验证解决方案使用到了迪菲－赫尔曼密钥交换。
例如当Alice和Bob共有一个公钥基础设施时，他们可以将他们的返回密钥进行签名。
有攻击的Diffie-Hellman密钥交换协议如图2-2所示：
图2-2有攻击的Diffie-Hellman密钥交换协议
3.DH密钥协商算法的实现
3.1设计要求
3.1.1功能要求
（1）产生一个奇数p，判断是否是素数。
素数要求介于2^14-2^15。
先用小于20的素数去试除，再使用Miller-Rabin概率检测算法进行检测；
（2）求得模p的一个原根，要求原根的值介于32-1024之间；
（3）输出双方选择的随机数，随机数介于2^5-2^7，使用模重复平方法进行计算，输出双方的计算结果；
（4）网络传输方面，可以是C/S模式，也可以是B/S模式；
（5）输出最后协商的密钥；
3.1.2输出要求
（1）输出奇数的产生过程，用函数实现产生满足要求的奇数；
（2）输出用小素数试除的判断过程，并输出每次试除之后的余数，用函数实现一次试除并返回试除之后的余数；
（3）Miller-Rabin概率检测算法运行5次，输出检测过程及结果。
用函数实现一次Miller-Rabin概率检测算法并返回检测结果；
（4）如果不是奇素数，输出下一个奇数产生的规则；
（5）输出产生模
的一个原根的过程；
（6）输出使用模重复平方法进行计算的过程和结果。
3.2模块划分及实现
3.2.1小素数试除
算法描述：
小素数试除主要是用随机产生的数来试除小于20的素数，以此简单判定该随机数是否是素数。
实现方式：
以本次程序编写为例，取小素数数组S_PrimeTable[7]={3,5,7,11,13,17,19}，用产生的大随机数来除以数组中的元素，若所得余数不为0，则能暂时判断该随机数为素数。
具体实现代码如下：
intSPrime（intodd）
{
inti,remainder,k=0;
for（i=0;
i<
7;
i++）
remainder=odd%S_PrimeTable[i];
printf（"
第%d次小素数%d试除的余数为%d.\n"
i+1,S_PrimeTable[i],remainder）;
if（remainder==0）
k++;
}
if（!
k）
小素数试除判断%d是素数。
\n\n"
odd）;
else
小素数试除判断%d不是素数。
return!
k;
3.2.2模重复平方法
模重复平方法是对大整数模m和大整数e计算b^e（modm）。
在本次设计中，模重复平方法主要使用在米勒检测算余值部分、求原根部分、SA和SB的计算以及最后密钥的计算过程中，
其中，SA和SB的计算以及最后密钥的计算要求输出计算过程。
（为了界面显示美观，在此写了两个模重复平方算法的代码，思路相同，只是在其中一个函数中写了输出计算过程，该函数用来计算SA和SB以及最后的密钥。
）
令a=1，并将十进制数e写成二进制，若二进制数值为1，则计算a≡（a*b）modn,b≡（b*b）modn；
若二进制数值为0，则计算a≡amodn,b≡（b*b）modn。
最后a即为最终计算结果。
intMoChongFu（intm,inte,intn）
intbinary[22];
intcount=0,i;
inta=1,b;
b=m;
do{
binary[count]=e%2;
e=e/2;
count++;
}while（e!
=0）;
for（i=0;
i<
count;
i++）
if（binary[i]==1）
a=（a*b）%n;
b=（b*b）%n;
//printf（"
a=%d,b=%d\n"
a,b）;
if（binary[i]==0）
a=a;
returna;
3.2.3Miller-Rabin检测算法
米勒检测在本次设计中主要用来检测在小素数判定了之后的随机数是否是素数。
将待检测的数n写成n-1=2s*t，选取随机数a，计算b≡atmodn。
若bmodn≡1，则n是素数。
否则，做如下循环，循环次数为1—s：
如果bmodn≡-1，则b是素数，否则，b≡b*bmodn。
intmilejiance（intodd）
ints=0,i,count=0;
inta,b,t,num;
num=odd-1;
while
（1）
if（num%2==0）
s++;
num=num/2;
t=num;
break;
将%d写成%d-1=2^%d*%d\t\t\n"
odd,odd,s,t）;
a=rand（）%（odd-3）+2;
产生的随机数a是：
%d\n"
a）;
b=MoChongFu（a,t,odd）;
第1次算出的余值是：
b）;
if（b%odd==1||b==（odd-1））
return1;
s;
b=（b*b）%odd;
第%d次算出的余值为%d\n"
i+2,b）;
if（b==（odd-1））
return0;
3.2.4原根的产生
要求一个素数一定范围内的原根，应该先求该素数的最小原根。
根据定理：
设m>
1，m的欧拉函数a所有不同素因数是q1,q2,…，qk，则g是模m的一个原根的充要条件是g^（a/qi）!
=1（modm）,i=1,2，…k
先求大素数的欧拉函数的素因数a[n]，并通过素因数求得g的指数c[n]，接着验证g^c[n]是否同余于1，对g=2,3…，逐个验算，直到算出最小的g值满足g^c[n]均不同余于1，那么g便是大素数m的最小原根，因为当c[n]遍历欧拉函数a的简化剩余系时，g^c[n]遍历模m的所有原根，所以可以通过欧拉函数的简化剩余系求得满足要求的原根。
intyuangen（intyy）
intn=2,g=0,q,k,j=0,a[10];
inti=0,l=0;
intgg;
intc[10];
intcount=0,flag=0;
q=yy-1;
while
（1）
if（q%n==0）
a[j]=n;
j++;
q=q/n;
n++;
if（q<
n）
模%d的欧拉函数分解质因数为：
\n"
yy）;
for（n=0;
n<
j;
++n）
%d"
a[n]）;
）;
所以指数为：
"
c[n]=（yy-1）/a[n];
c[n]）;
for（g=2;
;
g++）
if（MoChongFu（g,c[n],yy）==1）
%d^%d=%dmod%d\n"
g,c[n],MoChongFu（g,c[n],yy）,yy）;
gotocd;
gg=g;
所以%d是最小原根。
gg）;
gotoab;
cd:
;
ab:
for（g=3;
if（（yy-1）%g!
=0）
k=MoChongFu（gg,g,yy）;
if（k>
32&
&
k<
1024）
取介于2^5到2^10之间的一个原根值为：
%d\n\n"
k）;
returnk;
3.2.5产生随机素数
使用srand（）和rand（）函数产生随机数n，然后通过判断n%2是否为0来判断产生的是否是奇数。
intS_PrimeTable[7]={3,5,7,11,13,17,19};
//产生一个随机数
intRandom_Odd（）
intodd=0;
while
（1）
srand（time（NULL））;
odd=rand（）%（16385）+16384;
if（odd%2!
=0）
//printf（"
odd）;
returnodd;
4.测试报告
产生奇素数，用小素数试除并且输出试除的余数，再进行Miller-Rabin检测，若Miller-Rabin检测没有通过，则输出产生下一个随机数的规则并继续产生下一个随机数，直至产生满足条件的奇素数，如图4-1、4-2所示：
图4-1产生随机数并用小素数试除
图4-2米勒检测过程
代码调试的最终结果如图4-3、图4-4、图4-5、图4-6、图4-7、图4-8所示：
图4-3产生随机数并用小素数试除
图4-4米勒检测过程
图4-5大素数的欧拉函数分解质因数
图4-6求原根并计算各自的密钥
图4-7模重复平方法计算过程
图4-8计算共同密钥
结论
本文是在学习了相关C语言知识、密码学及相关信息安全数学知识之上进行的设计，本设计采用C语言实现，实现了DH密钥协商算法，用户A和用户B通过自己选取的随机数和公开的大素数通过离散对数的某些算法求得密钥，并相互交换密钥，通过交换得来的密钥产生共同的密钥。
由于学生水平有限，在程序可读性和规范性上有着一定的欠缺，略显不足，而在实现功能上也显得不是很完善，需要在进一步的学习中得到提升。
在编写程序的过程中遇到了一些不可避免的错误和问题，但是都通过书本以及同学的帮助得以及时将这些问题解决，此次设计对我的逻辑性理解和编程能力都有一定的提高。
参考文献
[1]谭浩强.C程序设计[M].北京：
清华大学出版，1999.12
[2]张仕斌.应用密码学[M].西安：
西安电子科技大学出版，2009.12
[3]陈恭亮.简明信息安全数学基础[M].北京：
高等教育出版社，20011.1
附源代码
#include<
stdio.h>
time.h>
math.h>
stdlib.h>
intRandom_Odd（）;
intSPrime（intodd）;
intMoChongFu（intm,inte,intn）;
intMoChongFua（intm,inte,intn）;
intmilejiance（intodd）;
intyuangen（intyy）;
intmain（void）
intyy=0;
intA,B,Key,Key1,Key2;
intSA,SB;
inti,flag1,flag2;
do
q:
**********************\n\n\n"
while（yy==Random_Odd（））;
yy=Random_Odd（）;
产生的随机数是:
flag1=!
SPrime（yy）;
5;
flag2=!
milejiance（yy）;
if（flag2）
第%d次米勒检测未通过。
i+1）;
因为第%d次米勒检测没有通过，所以随机数%d不是素数，\n产生下一个随机数，先用小素数试除，再进行5次米勒检测，如果小素数试除通过并且5次都通过，则说明该随机数是大素数。
i+1,yy）;
gotoq;
第%d次米勒检测通过。
while（flag1||flag2）;
gg=yuangen（yy）;
A=rand（）%（96）+32;
B=rand（）%（96）+32;
Alice选择的随机数A是：
A）;
Bob选择的随机数B是：
B）;
计算SA=（gg^A）modyy:
SA=MoChongFua（gg,A,yy）;
计算SB=（gg^B）modyy:
SB=MoChongFua（gg,B,yy）;
所以SA和SB分别是：
%d,%d\n\n"
SA,SB）;
计算Key1=（SB^A）modyy:
Key1=MoChongFua（SB,A,yy）;
计算Key2=（SA^B）modyy:
Key2=MoChongFua（SA,B,yy）;
所以：
Key1=%d,Key2=%d\n\n"
Key1,Key2）;
if（Key1==Key2）
Key=Key1;
所以共同密钥Key是：
Key）;
odd=rand（）%（16384）+16384;
//如果是素数的话返回1
inti,r,k=0;
r=odd%S_PrimeTable[i];
i+1,S_PrimeTable[i],r）;
if（r==0）
intMoChongFua（intm,inte,intn）
升级会员 