Diffie-Hellman算法

blowingwind

Diffie-Hellman 算法描述： 目前被许多商业产品交易采用。HD 算法为公开的密钥算法，发明于1976年。该算法不能用于加密或解密，而是用于密钥的传输和分配。
     DH 算法的安全性体现在：在有限域上计算离散对数非常困难。
     离散对数 ：定义素数p的原始根（primitive root）为这样一个数，它能生成1~p-1所有数的一个数。现设a为p的原始根，则
a mod p, a2 mod p,…,ap-1 mod p
   两两互不相同，构成一个1~p-1的全体数的一个排列。对于任意数b及素数p的原始根a,可以找到一个唯一的指数i，满足
b=ai mod p, 0
   则称指数i为以a为底、模P的b的离散对数。
算法描述：
假如Alice 和 Bob在不安全的网络上进行协商共同的密码：
1.Alice和Bob先说好一个大素数p和它的原始根a
2.Alice随机产生一个数x， 计算X=ax mod p, 然后把X发给Bob；
3.   Bob秘密产生一个随机数y，计算Y=ay mod p, 然后把Y发给Alice；
4.Alice计算k=Yx mod p;
5.Bob计算k*=Xy mod p;

因为
k=Yx mod p= (ay) x mod p=(a x)y mod p=X y mod p= k*
   所以  k= k*。
不安全线路上的窃听者只能得到a、p、X、Y,除非能计算离散对数x和y，否则将无法得到密钥ｋ。因此，k为Alice和Bob独立计算出的密钥。

缺点：DH密钥交换算法易受到中间人攻击。
中间人攻击 描述：
（1）                       Alice 公开发送值a和p给Bob,攻击者Carol截获这些值，随即把自己产生的公开值发给Bob。
（2）                       Bob 公开发送值a和p给Alice,又被 Carol截获，随即把自己产生的公开值发给Alice。
（3）                       Alice 和Carol计算出两人之间的共享密钥k1。
（4）                       Bob 和Carol计算出两人之间另一个的共享密钥k2。
受到中间人Carol攻击后，Alice用密钥k1给Bob发送消息，Carol截获后用k1解密就可读取消息，然后将获得的明文消息用k2加密（加密前对消息可能做某些修改，即主动攻击），然后发给Bob。对Bob发给Alice的消息，Carol用同样的手法读取和修改。
造成中间人攻击得逞的原因是：DH密钥交换算法不进行认证对方。利用数字签名可以解决中间人攻击的缺陷。


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/15071/showart_1316640.html