首页 > 代码库 > Diffie-Hellman密钥交换 -- 浅析

Diffie-Hellman密钥交换 -- 浅析

DH算法,实现在不安全网络中,发收双方安全交换对称密钥的一种方法。这个对称密钥阶段性保存,避免了长期保存带来的风险,发收双方共同持有一个秘密的对称密钥,可以实现端到端的秘密通信。

DH算法基于离散对数的基本原理。涉及的知识有,对数,素数,离散对数等;

对数

对数是17世纪的一项发现,作用是用来降低乘除法的运算难度。采用对数可以用加法来代替乘法,用减法代替除法。1627年开普勒使用对数来整理第谷布拉赫积累的数据,并得出了比他的前辈更精确的天体表,并得出行星沿着椭圆轨道绕太阳运行。

y = a^x     
a的x次幂等于y, 那么x就是以a为底的y的对数, y的对数是x(a为底)
x = log y  

对数的性质
log AB =  log A + log B
log A/B = log A - log B


素数,也叫质数

只能被1,和它自己整除的数,叫做素数。比如 2  3  5  7  11  13  17  19  23 。 欧几里得证明素数是无限的。这个证明很有趣,可以阅读  http://baike.baidu.com/view/333373.htm
少部分的素数可以用 2^p - 1 来表示, 这种数叫梅森素数。截止到2013年2月发现的最大的梅森素数为  p=2^57885161-1, 是第48个梅森素数。梅森素数是否有无限,这个未知。


素数的原根 

P为素数,i j 为整数,其中i≠j且i, j介於1至(P-1)之间。 
对于满足条件任意的 i和j 有   g^i mod P ≠ g^j mod P  ,  则 g就是P的原根 。
简单的说,就是g的1次幂、2次幂到P-1次幂的所有结果对P的余数各不相同。
原根有一个好处就是,满足 g^x mod P = y  ,  x与y 一一对应, 一个x对应一个y, 一个y对应一个x。
原根一般都不是很大, 可以通过暴力的方式来计算得出,也有一些优化算法。


离散对数

P是素数,g是P的原根, x 介於1至(P-1)之间 , 满足
g^x mod P = y
则 x就是y的离散对数 。

在已知g P x的情况下, 计算y,复杂度相对不大,计算机是可以完成的。而反过来,已知y求唯一的x,这个在目前已知的数学理论中是不可行的。通过穷举x来求解,但是计算量太大也是不可行的。


DH算法

DH算法,依据的就是离散对数求解困难的这一数学难题。

用户Ada 和 Babbage开始开一个不安全的网络中交换密钥, 下面算法中大写字母是允许公开的秘密

1 Ada 和 Babbage先协商一个大素数P和这个素数的原根G ,  P G 是允许公开的, 但P一定要足够大;

2 Ada 生成一个随机数x,x要小于P, 然后计算 G^x mod P = X  ,  X是允许公开的,由X是不能得到x的;

3 Babbage生成一个随机数y,y要小于P, 计算 G^y mod P = Y ,  Y允许公开;

4 Ada得到Babbage传递过来的Y, 然后计算 Y^x mod P = k ;

5 Babbage得到Ada传递过来的X,计算 X^y mod P = k* ; 

理论上k与k* 是相同的, 这个就是协商后的密钥,理论上这个密钥是不能通过公开的 P G X Y 运算得到。  


证明 k == k* 
 k = Y^x mod P 
    = (G^y mod P) ^ x  mod P
    = G^yx mod P

k* = X^y mod P
    = (G^x mod P) ^ y mod P 
    = G^xy mod P 

所以 k 与 k* 相同。