6. DH密钥交换算法
迪菲－赫尔曼密钥交换（Diffie–Hellman key exchange，简称“D–H”） 是一种安全协议。它可以让双方在完全没有对方任何预先信息的条件下通过不安全信道建立起一个密钥。这个密钥可以在后续的通讯中作为对称密钥来加密通讯内容。 (1)、算法描述 离散对数的概念： 原根：如果g是素数p的一个原根，那么数值： gmodp，g^2 modp，…，g^(p-1) modp 是各不相同的整数，且以某种排列方式组成了从1到p-1的所有整数。 离散对数：如果对于一个整数b和素数p的一个原根g，可以找到一个唯一的指数 i，使得： b =（g的i次方） modp 其中0≦i ≦p-1 那么指数i称为b的以g为基数的模p的离散对数。 Diffie-Hellman 算法的有效性依赖于计算离散对数的难度，其含义是：当已知大素数p和它的一个原根g后，对给定的 b，要计算 i ，被认为是很困难的，而给定 i 计算b 却相对容易。
6.1. D-H算法原理
假如用户Alice和用户Bob希望交换一个密钥。
取素数p和整数g，g是p的一个原根，公开g和p。 A选择随机数a 证明： Alice计算出：K= (B)^ a mod p = (g^b mod p)^ a mod p = (g^b)^ a mod p ，即：Bob计算出： K=(A) ^b mod p = (g^a mod p)^ b mod p = (g^a)^b mod p ，即： 由于a和b是保密的，而第三方只有p、g、A、B可以利用，只有通过取离散对数来确定密钥，但对于大的素数p，计算离散对数是十分困难的。 6.2. D-H算法示例 假如用户Alice和用户Bob希望交换一个密钥。 取一个素数p =97和97的一个原根g=5。 Alice和Bob分别选择秘密密钥a=36和b=58，并计算各自的公开密钥： A=g^a mod p=5^36 mod 97=50 B=g^b mod p=5^58 mod 97=44 Alice和Bob交换了公开密钥之后，计算共享密钥如下： Alice：K=(B) ^a mod p=44^36 mod 97=75 Bob：K=(A) ^b mod p=50^58 mod 97=75 6.3. D-H算法的安全性 当然，为了使这个例子变得安全，必须使用非常大的a, b 以及p， 否则可以实验所有的可能取值。(上例中总共有最多97个这样的值, 就算a和b很大也无济于事)。 如果 p 是一个至少 300 位的质数，并且a和b至少有100位长， 那么即使使用全人类所有的计算资源和当今最好的算法也不可能从g, p和g^(a*b) mod p 中计算出 a*b。 这个问题就是著名的离散对数问题。注意g则不需要很大, 并且在一般的实践中通常是2或者5。 在最初的描述中，迪菲－赫尔曼密钥交换本身并没有提供通讯双方的身份验证服务，因此它很容易受到中间人攻击。 一个中间人在信道的中央进行两次迪菲－赫尔曼密钥交换，一次和Alice另一次和Bob，就能够成功的向Alice假装自己是Bob，反之亦然。而攻击者可以解密（读取和存储）任何一个人的信息并重新加密信息，然后传递给另一个人。因此通常都需要一个能够验证通讯双方身份的机制来防止这类攻击。 有很多种安全身份验证解决方案使用到了迪菲－赫尔曼密钥交换。例如当Alice和Bob共有一个公钥基础设施时，他们可以将他们的返回密钥进行签名。