Diffie-Hellman密钥交换.doc

Diffie-Hellman密钥交换算法及其优化首次发表的公开密钥算法出现在Diffie和Hellman的论文中,这篇影响深远的论文奠定了公开密钥密码编码学。由于该算法本身限于密钥交换的用途,被许多商用产品用作密钥交换技术,因此该算法通常称之为Diffie-Hellman密钥交换。这种密钥交换技术的目的在于使得两个用户安全地交换一个秘密密钥以便用于以后的报文加密。Diffie-Hellman密钥交换算法的有效性依赖于计算离散对数的难度。简言之,可以如下定义离散对数:首先定义一个素数p的原根,为其各次幂产生从1到p-1的所有整数根,也就是说,如果a是素数p的一个原根,那么数值amodp,a2modp,...,ap-1modp是各不相同的整数,并且以某种排列方式组成了从1到p-1的所有整数。对于一个整数b和素数p的一个原根a,可以找到惟一的指数i,使得b=aimodp其中0≤i≤(p-1)指数i称为b的以a为基数的模p的离散对数或者指数。该值被记为inda,p(b)。基于此背景知识,可以定义Diffie-Hellman密钥交换算法。该算法描述如下:1、有两个全局公开的参数,一个素数q和一个整数a,a是q的一个原根。2、假设用户A和B希望交换一个密钥,用户A选择一个作为私有密钥的随机数XA<q,并计算公开密钥YA=aXAmodq。A对XA的值保密存放而使YA能被B公开获得。类似地,用户B选择一个私有的随机数XB<q,并计算公开密钥YB=aXBmodq。B对XB的值保密存放而使YB能被A公开获得。3、用户A产生共享秘密密钥的计算方式是K=(YB)XAmodq。同样,用户B产生共享秘密密钥的计算是K=(YA)XBmodq。这两个计算产生相同的结果:K=(YB)XAmodq=(aXBmodq)XAmodq=(aXB)XAmodq(根据取模运算规则得到)=aXBXAmodq=(aXA)XBmodq=(aXAmodq)XBmodq=(YA)XBmodq因此相当于双方已经交换了一个相同的秘密密钥。4、因为XA和XB是保密的,一个敌对方可以利用的参数只有q、a、YA和YB。因而敌对方被迫取离散对数来确定密钥。例如,要获取用户B的秘密密钥,敌对方必须先计算XB=inda,q(YB)然后再使用用户B采用的同样方法计算其秘密密钥K。Diffie-Hellman密钥交换算法的安全性依赖于这样一个事实:虽然计算以一个素数为模的指数相对容易,但计算离散对数却很困难。对于大的素数,计算出离散对数几乎是不可能的。下面给出例子。密钥交换基于素数q=97和97的一个原根a=5。A和B分别选择私有密钥XA=36和XB=58。每人计算其公开密钥YA=536=50mod97YB=558=44mod97在他们相互获取了公开密钥之后,各自通过计算得到双方共享的秘密密钥如下:K=(YB)XAmod97=4436=75mod97K=(YA)XBmod97=5058=75mod97从|50,44|出发,攻击者要计算出75很不容易。下图给出了一个利用Diffie-Hellman计算的简单协议。假设用户A希望与用户B建立一个连接,并用一个共享的秘密密钥加密在该连接上传输的报文。用户A产生一个一次性的私有密钥XA,并计算出公开密钥YA并将其发送给用户B。用户B产生一个私有密钥XB,计算出公开密钥YB并将它发送给