DH密钥交换算法

日志

迪菲－赫尔曼密钥交换（Diffie–Hellman key exchange，简称“D–H”） 是一种安全协议。
它可以让双方在完全没有对方任何预先信息的条件下通过不安全信道建立起一个密钥。这个密钥可以在后续的通讯中作为对称密钥来加密通讯内容。

算法描述

原根：如果a是素数p的一个原根，那么数值：
amodp，a^2 modp，…，a^(p-1) modp
是各不相同的整数，且以某种排列方式组成了从1到p-1的所有整数。

定义2: 假设一个数g对于P来说是原根，那么 g^i mod P 的结果两两不同,且有 1<g<P, 1<i<P,那么g可以称为是P的一个原根
简单来说就是: g^i mod p ≠ g^j mod p （p为素数 Prime Number）, 其中i≠j且i, j介於1至(p-1)之间, 则g为p的原根

离散对数：如果对于一个整数b和素数p的一个原根a，可以找到一个唯一的指数 i，使得：
b =（a的i次方） modp 其中0≦i ≦p-1
那么指数i称为b的以a为基数的模p的离散对数。

Diffie-Hellman 算法的有效性依赖于计算离散对数的难度，其含义是：当已知大素数p和它的一个原根a后，对给定的 b，要计算 i ，被认为是很困难的，而给定 i 计算b 却相对容易。

算法过程

假如用户A和用户B希望交换一个密钥。
取素数p和整数a，a是p的一个原根，公开a和p
A选择随机数 XA<p，并计算 YA=a^XA mod p
B选择随机数 XB<p，并计算 YB=a^XB mod p
每一方都将X保密而将Y公开让另一方得到
A计算密钥的方式是：K=(YB) ^XA modp
B计算密钥的方式是：K=(YA) ^XB modp

证明：

(YB)^ XA mod p = (a^XB modp)^ XA mod p
= (a^XB)^ XA mod p = (a^XA) ^XB mod p    (<-- 密钥即为 a^(XA*XB) mod p)
=(a^XA modp)^ XB mod p= (YA) ^XB mod p

由于XA和XB是保密的，而第三方只有p、a、YB、YA可以利用，只有通过取离散对数来确定密钥，但对于大的素数p，计算离散对数是十分困难的。

例子：
假如用户Alice和用户Bob希望交换一个密钥
取一个素数p =97和97的一个原根a=5

Alice和Bob分别选择秘密密钥XA=36和XB=58，并计算各自的公开密钥：
YA=a^XA mod p=5^36 mod 97=50
YB=a^XB mod p=5^58 mod 97=44

Alice和Bob交换了公开密钥之后，计算共享密钥如下：
Alice：K=(YB) ^XA mod p=44^36 mod 97=75
Bob：K=(YA) ^XB mod p=50^58 mod 97=75

安全性

当然，为了使这个例子变得安全，必须使用非常大的XA, XB 以及p， 否则可以实验所有的可能取值。(总共有最多97个这样的值, 就算XA和XB很大也无济于事)。

如果 p 是一个至少 300 位的质数，并且XA和XB至少有100位长， 那么即使使用全人类所有的计算资源和当今最好的算法也不可能从a, p和 a^(XA*XB) mod p 中计算出 XA*XB。这个问题就是著名的离散对数问题。注意g则不需要很大, 并且在一般的实践中通常是2或者5。

中间人攻击

在最初的描述中，迪菲－赫尔曼密钥交换本身并没有提供通讯双方的身份验证服务，因此它很容易受到中间人攻击。 一个中间人在信道的中央进行两次迪菲－赫尔曼密钥交换，一次和Alice另一次和Bob，就能够成功的向Alice假装自己是Bob，反之亦然。而攻击者可以解密（读取和存储）任何一个人的信息并重新加密信息，然后传递给另一个人。因此通常都需要一个能够验证通讯双方身份的机制来防止这类攻击。

阻塞攻击

DH 是计算密集性的，因此容易遭受阻塞性攻击，即对手请求大量的密钥.受攻击者花费了相对多的计算资源来求解无用的幂系数而不是在做真正的工作