XXXX学院课程设计报告DH密钥协商算法课程名称： 密码算法程序设计 学生姓名： 学生学号： 专业班级： 任课教师： 2014年12 月 1日指导老师评阅成绩表学习与工作态度（30%）选题意义（10%）研究水平与设计能力（25%）课程设计说明说（论文）撰写质量（25%）设计创新（10%）总分指导老师签名： 年 月 日课程设计答辩记录及评价表学生讲述情况教师主要提问记录学生回答问题情况答辩评分评分项目分值评价参考标准评分总分优良中及格差选题意义1098764研究水平与设计能力252320181510课程设计说明书（论文）撰写质量252320181510设计创新1098764答辩效果302825221915答辩小组成员签名答辩小组组长签名： 年 月 日课程设计成绩评定表成绩汇总评分项目评分比例分数课程设计总分指导老师评分50%答辩小组评分50%目 录1. 选题背景12. DH密钥协商算法12.1 算法的产生12.2 算法的描述22.3 算法的安全性33.DH密钥协商算法的实现43.1 设计要求43.1.1 功能要求43.2 模块划分及实现53.2.1 小素数试除53.2.2 模重复平方法53.2.3 Miller-Rabin检测算法73.2.4 原根的产生83.2.5 产生随机素数114.测试报告12结 论17参考文献17附源代码181. 选题背景密钥协商实际上是一个协议，它通过两个或多个成员在一个公开的信道上通信联合地建立一个秘密密钥，一般情况下，一个密钥协商方案的密钥是某个函数的值，其输入量由通信双方提供，协商过程是由一系列的顺序步骤完成的。会话密钥由每个协议参与者分别产生的参数通过一定的计算得出。常见的密钥协商协议，如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的一个原根，那么数值：amodp，a2modp，a(p-1)modp是各不相同的整数，且以某种排列方式组成了从1到p-1的所有整数。 2）离散对数：如果对于一个整数b和素数p的一个原根a，可以找到一个唯一的指数i，使得b=(ai)mod p，其中0ip-1，那么指数i称为b的以a为基数的模p的离散对数。2. 算法有效性Diffie-Hellman算法的有效性依赖于计算离散对数的难度，其含义是：当已知大素数p和它的一个原根a后，对给定的b，要计算i，被认为是很困难的，而给定i计算b却相对容易。3. Diffie-Hellman算法：假如用户A和用户B希望交换一个密钥。取素数p和整数a，a是p的一个原根，公开a和p。 1）A选择大的随机数RA(0=RA=p-2)，并计算SA=(aRA) mod p，并且把SA发送给用户B。 2）B选择随机数RB(0=RB=p-2)，并计算SB=(aRB) mod p，并且把SB发送给用户A。 3）A计算密钥的方式是：K=(SB) RA modp，B计算密钥的方式是：K=(SA) RB modp，证明：(SB) RA modp= (aRB modp) RA modp = (aRB) RA modp = (aRA) RBmodp (- 密钥即为 a(RA*RB) modp) =(aRA modp) RB modp = (SA) RB modp由于RA和RB是保密的，而第三方只有p、a、SB、SA可以利用，只有通过取离散对数来确定密钥，但对于大的素数p，计算离散对数是十分困难的。4. 例子：假如用户Alice和用户Bob希望交换一个密钥，取一个素数p=97和97的一个原根a=5，Alice和Bob分别选择秘密密钥RA=36和RB=58，并计算各自的公开密钥： SA=aRA modp=536 mod 97=50 SB=aRB modp=558 mod 97=44Alice和Bob交换了公开密钥之后，计算共享密钥如下： Alice：K=(SB) RA modp=4436 mod 97=75 Bob：K=(SA) RB modp=5058 mod 97=75Diffie-Hellman密钥交换协议的基本模式如图2-1所示：SA=aRA(mod p)用户A 用户BSB=aRB(mod p)图2-1 Diffie-Hellman密钥交换协议的基本模式2.3 算法的安全性当然，为了使这个例子变得安全，必须使用非常大的RA,RB 以及p， 否则可以实验所有的可能取值。(总共有最多97个这样的值, 就算RA和RB很大也无济于事)。 如果p是一个至少 300 位的质数，并且RA和RB至少有100位长， 那么即使使用全人类所有的计算资源和当今最好的算法也不可能从a,p和a(RA*RB) modp中计算出 RA*RB。 这个问题就是著名的离散对数问题。注意g则不需要很大, 并且在一般的实践中通常是2或者5。在最初的描述中，迪菲赫尔曼密钥交换本身并没有提供通讯双方的身份验证服务，因此它很容易受到中间人攻击。 一个中间人在信道的中央进行两次迪菲赫尔曼密钥交换，一次和Alice另一次和Bob，就能够成功的向Alice假装自己是Bob，反之亦然。而攻击者可以解密（读取和存储）任何一个人的信息并重新加密信息，然后传递给另一个人。因此通常都需要一个能够验证通讯双方身份的机制来防止这类攻击。 有很多种安全身份验证解决方案使用到了迪菲赫尔曼密钥交换。例如当Alice和Bob共有一个公钥基础设施时，他们可以将他们的返回密钥进行签名。有攻击的Diffie-Hellman密钥交换协议如图2-2所示： SA=aRA(mod p) SA=aRA(mod p)用户A 攻击者C 用户B SB=aRB(mod p) SB=aRB(mod p)图2-2 有攻击的Diffie-Hellman密钥交换协议3. DH密钥协商算法的实现3.1 设计要求3.1.1 功能要求（1）产生一个奇数p ，判断是否是素数。素数要求介于214-215。先用小于20的素数去试除，再使用Miller-Rabin概率检测算法进行检测；（2）求得模p 的一个原根，要求原根的值介于32-1024之间；（3）输出双方选择的随机数，随机数介于25-27，使用模重复平方法进行计算，输出双方的计算结果；（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_PrimeTable7 = 3, 5, 7, 11, 13, 17, 19 ，用产生的大随机数来除以数组中的元素，若所得余数不为0，则能暂时判断该随机数为素数。具体实现代码如下：int SPrime(int odd)int i, remainder, k = 0;for (i = 0; i7; i+)remainder = odd % S_PrimeTablei;printf(第%d次小素数%d试除的余数为%d.n, i + 1, S_PrimeTablei, remainder);if (remainder = 0)k+;if(!k)printf(小素数试除判断%d是素数。nn,odd);else