DH密钥协商算法报告文档.doc

XXXX学院课程设计报告DH密钥协商算法课程名称： 密码算法程序设计 学生姓名: 学生学号: 专业班级： 任课教师: 214年12 月 1日指导老师评阅成绩表学习与工作态度(30%）选题意义(%)研究水平与设计能力(25%)课程设计说明说（论文)撰写质量(2)设计创新(1%）总分指导老师签名: 年 月 日课程设计答辩记录及评价表学生讲述情况教师主要提问记录学生回答问题情况答辩评分评分项目分值评价参考标准评分总分优良中及格差选题意义098764研究水平与设计能力2523201811课程设计说明书（论文)撰写质量232181510设计创新10864答辩效果3答辩小组成员签名答辩小组组长签名： 年 月 日课程设计成绩评定表成绩汇总评分项目评分比例分数课程设计总分指导老师评分5%答辩小组评分50目录1、 选题背景、 D密钥协商算法12、1算法得产生1、2 算法得描述22、3算法得安全性33、密钥协商算法得实现43、1 设计要求43、1、1 功能要求43、2 模块划分及实现53、2、1小素数试除5、2、 模重复平方法5、3 Mile-Rbin检测算法7、2、4 原根得产生83、2、5 产生随机素数114、测试报告2结 论17参考文献17附源代码11、 选题背景密钥协商实际上就是一个协议,它通过两个或多个成员在一个公开得信道上通信联合地建立一个秘密密钥,一般情况下,一个密钥协商方案得密钥就是某个函数得值,其输入量由通信双方提供,协商过程就是由一系列得顺序步骤完成得。会话密钥由每个协议参与者分别产生得参数通过一定得计算得出。常见得密钥协商协议,如E。密钥协商协议得生成方式则可分为证书型与无证书型。证书型就是指在会话密钥得产生过程中，由一个可信得证书中心(CA)给参与密钥协商得各方各分发一个证书,此证书中含有此方得公钥，D及其她信息。证书型密钥协商协议得优点就是提供认证,目前PKI(公钥密码体制)广泛部署,比较成熟,应用面广,且由P管理公私钥对有利于统一管理,缺点就是计算代价大,需要一个可信得CA,同时证书还需要维护。无证书型就是指各方在进行会话密钥得协商过程中不需要证书得参与,这就是目前密钥协商协议得主流种类，优点就是不需要得参与,减少了计算量，尤其就是在低耗环境下应用得更多,同时安全性也不比证书型弱。几乎没有明显得缺点，只就是设计一个安全得更加低耗得无证书密钥协商方案不就是很容易。现有得流行得密钥协商协议,都使用了iffe-Hellmn,它们基本上可以瞧成就是iieHellman得扩展。也就就是说,群组密钥协商协议可以理解成如何使用Difie-Hema来实现群得密钥交换。2、 H密钥协商算法、1 算法得产生Diffe-Helman密钥交换协议就是第一个被提出得密钥协商方案，就是美国斯坦福大学得W、ifie与M、Hellman于96年提出得，它就是第一个发表得公钥密码体制,Diie-lan算法得唯一目得就就是使两个用户能安全得交换密钥，从而得到一个共享得会话密钥(秘密密钥)。需要注意得就是,该算法本身不能用于加密解密,只能用于密钥得交换, 双方确定要用得密钥后,要使用其她对称密钥操作加密算法实际加密与解密消息。2、2 算法得描述1、离散对数得概念： 1)原根:如果a就是素数p得一个原根,那么数值:amdp,a2dp,a(p-)modp就是各不相同得整数,且以某种排列方式组成了从到p-1得所有整数。 2)离散对数：如果对于一个整数与素数p得一个原根a,可以找到一个唯一得指数i,使得b（)mod p,其中0ip-1,那么指数i称为得以a为基数得模p得离散对数。2、 算法有效性ifi-Hlman算法得有效性依赖于计算离散对数得难度,其含义就是:当已知大素数p与它得一个原根a后,对给定得b,要计算i,被认为就是很困难得,而给定i计算却相对容易。、Dfie-Helman算法：假如用户A与用户B希望交换一个密钥。取素数p与整数a，a就是p得一个原根,公开a与。 1)A选择大得随机数R(=RA=p-2)，并计算SA=（aRA）modp，并且把SA发送给用户B。 2）选择随机数RB(0=RB=2),并计算S(aRB） mo p,并且把B发送给用户A。 3)A计算密钥得方式就是:K=(S) RA mp，计算密钥得方式就是：K=(SA) modp,证明：(SB） RAod=(aRmp) A mod =(aB)RA mo = (aRA) odp（-密钥即为 a(RA*RB)mod） (aRA mod) RB mdp =(SA) Bmodp由于RA与B就是保密得,而第三方只有p、a、SB、可以利用,只有通过取离散对数来确定密钥,但对于大得素数p,计算离散对数就是十分困难得。4、例子：假如用户Alic与用户ob希望交换一个密钥,取一个素数p=97与97得一个原根a=,Alce与Bo分别选择秘密密钥A6与R=，并计算各自得公开密钥: SA= mdp=36 o 9750 SB=RB modp558mod 97Aice与Bb交换了公开密钥之后,计算共享密钥如下： Aice:=(SB) RA mdp=436mo 775 Bo:K（A)RB md505 mod 977Diffie-Hellma密钥交换协议得基本模式如图2-1所示:SA=aRA(mod p)用户A 用户BSB=aRB(mod p)图2-1Dffe-ella密钥交换协议得基本模式、3 算法得安全性当然,为了使这个例子变得安全,必须使用非常大得RA，RB 以及, 否则可以实验所有得可能取值。(总共有最多9个这样得值, 就算RA与R很大也无济于事)。 如果p就是一个至少 30 位得质数,并且RA与RB至少有00位长,那么即使使用全人类所有得计算资源与当今最好得算法也不可能从,p与a（*RB) modp中计算出 R*RB。 这个问题就就是著名得离散对数问题。注意则不需要很大, 并且在一般得实践中通常就是或者5。在最初得描述中,迪菲-赫尔曼密钥交换本身并没有提供通讯双方得身份验证服务，因此它很容易受到中间人攻击。 一个中间人在信道得中央进行两次迪菲赫尔曼密钥交换，一次与Aie另一次与Bb，就能够成功得向Alice假装自己就是Bb，反之亦然。而攻击者可以解密(读取与存储）任何一个人得信息并重新加密信息,然后传递给另一个人。因此通常都需要一个能够验证通讯双方身份得机制来防止这类攻击。 有很多种安全身份验证解决方案使用到了迪菲-赫尔曼密钥交换。例如当Aic与Bo共有一个公钥基础设施时,她们可以将她们得返回密钥进行签名。有攻击得DiffieHllman密钥交换协议如图2-2所示: SA=aRA(mod p) SA=aRA(mod p)用户A 攻击者C 用户B SB=aRB(mod p) SB=aRB(mod p)图2- 有攻击得Diff-ellman密钥交换协议3、 DH密钥协商算法得实现3、 设计要求3、1、 功能要求(1)产生一个奇数p ,判断就是否就是素数。素数要求介于1-215。先用小于20得素数去试除,再使用Mier-abi概率检测算法进行检测;（2)求得模 得一个原根,要求原根得值介于32-102之间;(3)输出双方选择得随机数，随机数介于5-2,使用模重复平方法进行计算,输出双方得计算结果；(4）网络传输方面,可以就是S模式,也可以就是B/S模式;（5)输出最后协商得密钥; 3、1、 输出要求()输出奇数得产生过程，用函数实现产生满足要求得奇数；（)输出用小素数试除得判断过程，并输出每次试除之后得余数,用函数实现一次试除并返回试除之后得余数;（3）Millr-Rabi概率检测算法运行5次,输出检测过程及结果。用函数实现一次ier-Rai概率检测算法并返回检测结果;()如果不就是奇素数,输出下一个奇数产生得规则;（）输出产生模得一个原根得过程;（)输出使用模重复平方法进行计算得过程与结果。3、 模块划分及实现3、2、1 小素数试除算法描述:小素数试除主要就是用随机产生得数来试除小于20得素数，以此简单判定该随机数就是否就是素数。实现方式:以本次程序编写为例,取小素数数组SPrimeTable7 3，5, 7, 11，1,17, 19 ,用产生得大随机数来除以数组中得元素,若所得余数不为0,则能暂时判断该随机数为素数。具体实现代码如下:int SPrime（int dd）it i, remine， k 0;for(i = 0； i; +)ir = odd % S_rimeTablei；pintf（第%d次小素数d试除得余数为%、, i+ , _Prmaei, remainder);i (remaide= 0）+；i(!)printf(小素数试除判断%d就是素数。nn,d);elsepritf(小素数试除判断%d不就是素数。nn,d);retr !k;3、2、2 模重复平方法算法描述： 模重复平方法就是对大整数模m与大整数e计算be(mo )。在本次设计中,模重复平方法主要使用在米勒检测算余值部分、求原根部分、SA与SB得计算以及最后密钥得计算过程中，其中，SA与SB得计算以及最后密钥得计算要求输出计算过程。(为了界面显示美观,在此写了两个模重复平方算法得代码,思路相同,只就是在其中一个函数中写了输出计算过程,该函数用来计算S与S以及最后得密钥。)实现方式:令=1，并将十进制数e写成二进制，若二进制数值为1,则计算a(*b)md ,(bb)mod n；若二进制数值为0,则计算a od ，b(b*b)mo 。最后a即为最终计算结果。具体实现代码如下:int MohongFu（intm, in ,in n) i biy；i con=，i;it a=1,b; b=m；d binyou=e%;e=/2;cout+;whl（e！=0);or（i=；iount;+)if(bnary=1)a=(b)；b=(*b)； rtf（a=，%dn,a，b)；if(iai=)a;=（*b）n; /rnf（a=%d, b=%d,b)；rtun ;3、2、3 iller-Rain检测算法算法描述:米勒检测在本次设计中主要用来检测在小素数判定了之后得随机数就是否就是素数。实现方式：将待检测得数写成n1=2*t，选取随机数,计算batmod 。若b mod n1，则n就是素数。否则,做如下循环,循环次数为1:如果b mo n-,则b就是素数,否则,bb*b modn。具体实现代码如下:in mlejiance(intodd)s=0,count;t a,b，,um;num=odd-;wil(1) i(num2=0)s;nm=um/2;elsenum；brek；pritf(将d写成d1=2%d*%ttn,odd,odd，s，t);ard()%(odd3)+2;prntf(产生得随机数就是:%n,a);b=MoCongFu(a,t,odd);pntf(第1次算出得余值就是:%d,b）;i（od1|=（dd-1)） return1;for(i=0;+)b=（b*b)%odd;pritf（第%d次算出得余值为% n,i2，b)；if(b=(odd-1）)rern 1;return ; 3、2、 原根得产生算法描述:要求一个素数一定范围内得原根，应该先求该素数得最小原根。根据定理:设m1，得欧拉函数a所有不同素因数就是1,2，qk,则就是模得一个原根得充要条件就是 g(/q)！1(modm),i=1，2,k实现方式: 先求大素数得欧拉函数得素因数，并通过素因数求得g得指数,接着验证cn 就是否同余于1,对=,3,逐个验算,直到算出最小得g值满足均不同余于1,那么便就是大素数m得最小原根,因为当n遍历欧拉函数a得简化剩余系时，gcn遍历模得所有原根,所以可以通过欧拉函数得简化剩余系求得满足要求得原根。具体实现代码如下:int age(nt y)in n=2,g=0,，j=，a1;in i=0，l=0;int g；intc0;in ont，flag=0；q=y-;whe(1)if （q%n=)a=n;j+；q=q/n；n+;if(qn)break;prntf(模d得欧拉函数分解质因数为：n,y);or(n0;nj;+n)rinf(%d ，n);prtf(nn）;prinf（所以指数为:)；fr(n0；nj；+n)c(yy-1)an；ritf(%d ,c);print(n);f(g=2;；g+)fr（n=0;nj；+n)if(ohongFu(g，c,yy)=1)printf(%d%d=%dmod%dn,cn,MoChongFu(g,cn，yy),yy）;gotocd;lspint（%d%d=%dmod%dn，,cn，MongF(,cn,),yy)；gg=; ri(所以d就是最小原根。n,g);got ab;c：;ab:for(g=3；g+)if(（y）%g！=0）=Mohgu(，g,yy)；if(k32&k12）pritf(取介于25到210之间得一个原根值为:)；prntf(dnn,k）；rn k;return 0;3、2、5 产生随机素数算法描述:使用d()与rnd(）函数产生随机数,然后通过判断%2就是否为0来判断产生得就是否就是奇数。具体实现代码如下：intrimeTale7 = , , ,11, 13， 1,9 ;/产生一个随机数ntadom_dd(）int odd = 0;wil (1)ran(tme(NUL）);dd = rnd() %（163)+ 6384;if （d % 2 ！=0)break;pint（%dn, odd);retur odd；、 测试报告产生奇素数，用小素数试除并且输出试除得余数,再进行Mll-Rabi检测,若Miller-Rin检测没有通过,则输出产生下一个随机数得规则并继续产生下一个随机数,直至产生满足条件得奇素数,如图4-1、4-2所示:图 4-1 产生随机数并用小素数试除图4-2米勒检测过程代码调试得最终结果如图4-、图4-4、图4-5、图4-6、图4-7、图-8所示:图4-3 产生随机数并用小素数试除图4 米勒检测过程图- 大素数得欧拉函数分解质因数图6求原根并计算各自得密钥图4-7 模重复平方法计算过程图48计算共同密钥结 论本文就是在学习了相关C语言知识、密码学及相关信息安全数学知识之上进行得设计,本设计采用C语言实现,实现了DH密钥协商算法,用户A与用户通过自己选取得随机数与公开得大素数通过离散对数得某些算法求得密钥,并相互交换密钥,通过交换得来得密钥产生共同得密钥。由于学生水平有限,在程序可读性与规范性上有着一定得欠缺，略显不足,而在实现功能上也显得不就是很完善,需要在进一步得学习中得到提升。在编写程序得过程中遇到了一些不可避免得错误与问题,但就是都通过书本以及同学得帮助得以及时将这些问题解决，此次设计对我得逻辑性理解与编程能力都有一定得提高。参考文献1 谭浩强、C程序设计M、北京：清华大学出版,999、22 张仕斌、 应用密码学、西安：西安电子科技大学出版,009、12 陈恭亮、简明信息安全数学基础、 北京:高等教育出版社,21、附源代码#iclud#incudicldmah、#includeint RaomOdd();nt Srime(nt odd);nt MChonFu（int m,inte,i);int MoChongua(nt , n e,int n);int ieace（t d);int yngen(int y)；intS_PriTble=， , 7， 11， 13, 17,9 ;int mai(od)int y0；int gg；n A,，ey,Ke1,ey2;int A，SB;int ,flg1,flag2；dq:rint(*nnn）;wie（y = Ranom_Odd(); = Ranom_Od()；pint（产生得随机数就是：%dnn,y);fg1!SPrim(y);fr(i=;i;+)fla2=！miliance（);f(flg2）printf（第%d次米勒检测未通过。nn,i1);prntf(因为第%d次米勒检测没有通过，所以随机数%d不就是素数,n产生下一个随机数，先用小素数试除,再进行5次米勒检测,如果小素数试除通过并且5次都通过,则说明该随机数就是大素数。,+1,y);pitf();goo q；elseprintf(第%次米勒检测通过。n，i+1);while（flg1|flag2）;gg=yuagen(yy);san(time(L);A = rd()(9)+32；B = rnd()%(96)3；pint(Alic选择得随机数A就是：%dn,);rit（Bob选择得随机数B就是:nn,B）；rit（计算S=(ggA) dy:);SA=oChogFu(gg,A,y);pinf(n)；pint(计算=(gB） mod y:);=MChogF(g,B，y);pritf（所以A与S分别就是:%d，%dnn,SA,S);prn（计算y1=(B）mod yy：）;Ke1=oChogFua（S,y）;rintf（n)；prtf(计算Key=(SAB) md yy:n)；Ke2=MoChongFa（SA,y)；printf(所以：y1d,Ky=%dn,Ke，ey);if（Ke=Ky）Key=e1;prin(所以共同密钥Ky就是：nn,Key)；reun 0;/产生一个随机数iRanom_()t odd =0;whil ()srd（tim(NULL);od =rd()% (1634) +1634;if (odd % 2 !=)reak;/printf(dn,od)；euod;/如果就是素数得话返回1inPrie（int odd)int i, , k 0;f (i 0; i7; +)r od _Pieablei;prf(第%d次小素数%d试除得余数为%d、n, i 1， S_PrimeTablei, r);if (r =0)k+;i(!k）printf（小素数试除判断%d就是素数。n,od)；elseprf(小素数试除判断%不就是素数。n,d);etr!k;in MChonF(int ， in e，int n) i binary22；intcout=0,i;int a1,b; =；o binarycoun=e2;e=;coun+;whl(e！=);f(=0;icont；+)i(binaryi=1）a=(a*b)%；b=(bb）%;f(bnaryi=0)=a;b=（*)n;etrn a;it MoChonFua(n ,it e,int n） n binary22;icnt0,i;int a=，b; b=;do biaycou=%2;e=e/;con+；wile（e！=);for(i=0;cunt;i+)if（biaryi=)a(b)%n；b=(b*)%n;prif(a=%d,b=%dn，a,);if(bnry=0)a=a;=(bb）%;pr（a=%d， =dn,a,);retun a；/米勒检测inmiejiae(nodd）its=0，,count=;int a,b,t,num;numod-;wl() if（num%2=)s+;nm=nm2;elset=nu;rak;printf(将%d写成d-1=2%d*ttn,dd,odd,s,t)；a=rad（)（odd3)+；pritf(产生得随机数a就是:%n,a);=MhongF(a，t,odd);pinf(第1次算出得余值就是：%d，b);if(b%od=1|b=（od-1)retrn 1;for（i=0;s-1;i+)b=(bb)%odd;prinf(第%次算出得余值为%d n,i+2,b）;if（=(odd-1)rtur 1；rrn 0; /欧拉函数得素因数与两者得商it ygen(int yy)intn=,g=0,q,k，j=0,a10;nt gg;int 10;q=y-1;wl（）if (q%=0)aj;+; wie（)q=/n;whle（！(q%)qq；if(qn)break;pritf（模%得欧拉函数分解质因数为：n,yy);fr(n=0;nj;+）rtf(% ，an）;print(n)；it(所以指数为:);for（n0;n32&104)prinf(取介于25到210之间得一个原根值为：);inf(%dnn,k);retrn k;reur ；