原根论文：Diffie-Hellman密钥交换算法及其实现.doc

原根论文:Diffie-Hellman密钥交换算法及其实现     摘要:Diffie-Hellman密钥交换算法是在通信前双方交换公钥产生密钥的一种方法。关键词:原根;公钥;密钥 Diffie-HellmanKeyExchangeAlgorithmandImplementation YaoYe1,SongShiyao2 (,Shenyang110161,China;,Shenyang110122,China) Abstract:Diffie-municationbeforethepublictogeneratekeys. Keywords:Primitiveroots;Publickey;Key Diffie-Hellman密钥交换算法(Diffie-HellmanKeyExchangeAlgorithm)是消息在传输过程中,为应对网络的不安全因素而进行的简单密钥交换,通信双方只能使用该算法计算出密钥对,而不能进行消息的加密和解密。而消息的加密与解密只能通过其他算法实现。一、算法原理 Diffie-Hellman算法主要是根据离散对数计算的难度来实现的,即定义两个数,一个是素数p(因为验证是素数的时间较长,所以素数的选择可以从已经经过证明的大素数中选取),或是选择相对素数(就是很可能是素数的数);另一个是其原根a(所谓原根,就是a^imodp的结果两两不同,其中1 b=aimodp其中0≤i≤(p-1) 指数i也因此被称为b的以a为基数的模p的离散对数或者指数。在算法描述中被记为Inda,p(b)。 Diffie-Hellman算法的计算过程: (一)用户A和B希望在传输消息之间达成共识,产生一个双方认可的公共密钥,由用户A选择一个素数p(这里以p=97为例,97不是素数,仅仅是作为一个相对素数来选择),和它的一个原根a(这里a=5),另一个是小于p的随机数RA(假设RA=36)作为私有密钥,通过计算公式: XA=aRAmodp=536mod97=50mod97=50 得到公共密钥,这时用户A将计算结果XA(XA=50)公开传送至用户B。(二)同样的方法,用户B也选择一个小于素数p(p=97)的随机数RB(RB=58)作为私有密钥,通过计算公式: XB=aRBmodp=558mod97=44mod97=44 得到公共密钥,这时用户B也将计算结果XB(XB=44)公共传送至用户A。(三)用户A得到XB后,与己方产生的随机数RB一起通过计算公式: K=(XB)RAmodp=4436mod97=75mod97=75 得到共享密钥。而用户B得到XA后,与己方产生的随机数RA一起通过计算公式: K=(XA)RBmodp=5058mod97=75mod97=75 (四)由此可见,用户A与用户B双方计算产生相同的结果,相当于双方已经交换了一个相同的密钥。传输消息的过程中,p、a、XA和XB几个参数是公开传递的,但是传输双方各自拥有一个安全随机数(RA和RB)密钥,因此第三方要想获得密钥,必须通过双方公开的参数p、a、XA和XB,采取离散对数的方法来确定密钥。例如,要获取用户A的密钥RA,必须计算 RA=Inda,,