Diffie-Hellman算法

一、原理分析

离散对数问题

假定 a, p 均是素数，下面两个集合相等，证明过程请参考 Cryptography and Network Security 第八章：

1	{ a^1 mod p, a^2 mod p, ..., a^(p-1) mod p } = {1, 2, ... , p-1 } {} 表示集合

上述式子可概括成以下三点，对于 1 <= x,y <= p - 1，有：

a^x mod p 一定属于 {1, 2, …, p -1 }
如果 x != y，则 a^x mod p != a^y mod p
对于 1 <= b <= p - 1，一定存在唯一的 1 <= x <= p-1，使得 b = a^x mod p

第三点在求解上有这么一个特点：已知 x 求 b 非常容易，已知 b 求 x 非常困难，特别当 p 很大时，求解的复杂度非常高，所以它又被称为离散对数问题 (Discrete logarithm)，它是 DH 算法能够安全交换密钥的基础！

求模公式

假设 q 为素数，对于正整数 a,x,y，有：

1	(a^x mod p)^y mod p = a^(xy) mod p

证明如下：

令 a^x = mp + n， 其中 m, n 为自然数， 0 <= n < p，则有
C = (a^x mod p)^y mod p
  = ((mp + n) mod p)^y mod p
  = n^y mod p
  = (mp +n)^y mod p
  = a^(xy) mod p

下面进入正题：假设A和B之间相互通信，他们之间进行以下操作：

57646804789

双方同时选取素数a和p，A选择一个数Xa，进行运算得到Ya，同理，B选择一个数Xb，计算得到Yb，这是A和B分别得到彼此的密文，再运用自己的私钥进行解密，得到K，如果K相同，说明消息准确，反之有误。

下面证明，A 和 B 计算出来的密钥 K 相同。

A计算K时：
K = Yb^Xa mod p
  = (a^Xb mod p)^Xa mod p
  = a^(Xa * Xb) mod p          根据上述求模公式
B计算K时：
K = Ya^Xb mod p
  = (a^Xa mod p)^Xb mod p
  = a^(Xa * Xb) mod p

上面一共出现了 a, p, Xa, Ya, Xb, Yb, K 共 7 个数，其中：

公开的数：a, p, Ya, Yb
非公开数：Xa, Xb, K

通常情况下，a一般是2或者5，比较小，但是呢，p的取值是非常大的，至少是几百位，Xa和Xb的取值也是非常大的，其复杂度至少为O(p^0.5)，对于攻击者来说，已知Ya，a和p的情况下，求解出Xa，几乎不可能(爆破也很难)，同理Xb的求解也一样，也就是说密钥K的求解变的相当困难，侧面可以证明DH算法可以保证通信双方在透明的信道中安全的交换密钥：

57646870389