4.3 Diffie-Hellman密钥交换算法

Diffie-Hellman密钥交换算法是第一个公钥方案，其安全性建立在有限域中计算离散对数的困难性的基础上。Diffie-Hellman密钥交换算法不能用于交换任意信息，它允许两个用户可以通过公开信道安全地建立一个秘密信息，用于后续的通信过程，该秘密信息仅为两个参与者知道。该算法由Diffie和Hellman于1976年公开提出，虽然现在知道早在1970年，英国政府通信总部（GCHQ）通信电子安全局（Communications-Electronics Security Group，CESG）的James Ellis已经秘密地提出了这一概念。该算法在一些商业产品中得到应用，在美国的专利于1997年4月29日到期。

4.3.1 对Diffie-Hellman密钥交换算法的描述

假定A，B双方选择素数p以及p的一个原根a，算法的步骤如下：

（1）用户A选择一个随机数Xa < p，计算Ya = aXa mod p。

（2）用户B选择一个随机数Xb < p，计算Yb = aXb mod p。

（3）每一方保密X值，而将Y值交换给对方。

（4）用户A计算出K = YbXa mod p。

（5）用户B计算出K = YaXb mod p。

（6）这两种计算的结果是相同的，最后双方获得一个共享密钥aXaXbmod p。素数p以及p的原根a可由一方选择后发给对方。

由于Xa和Xb是私有的，攻击者只能通过公开的p，a，Ya和Yb来进行攻击，这样他就必须先计算离散对数：Xa = inda,p（Ya）或Xb = inda,p（Yb），然后才能像用户A或B那样计算出密钥K。

4.3.2 对Diffie-Hellman密钥交换的攻击

虽然攻击者试图计算出用户的私钥是困难的，但Diffie-Hellman密钥交换仍然可以受到一种叫做中间人攻击的攻击，如图4.3所示。中间人攻击的步骤如下：

（1）双方选择素数p以及p的一个原根a（假定O知道）。

（2）A选择Xa<p，计算出Ya = aXa mod p，并把Ya 发给B。

（3）O截获Ya，选择Xo，计算出Yo = aXo mod p，冒充A把Yo发给B。

（4）B选择Xb<p，计算出Yb = aXb mod p，并把Yb发给A。

（5）O截获Yb，冒充B把Yo发给A。

（6）A进行如下计算，（Yo）Xa≡（aXo）Xa≡aXoXa mod p。

（7）B进行如下计算，（Yo）Xb≡（aXo）Xb≡aXoXb mod p。

（8）O完成如下计算，（Ya）Xo≡aXaXo mod p，（Yb）Xo≡aXbXo mod p。

在这种攻击方式中，O无法计算出A和B期望获得的密钥aXaXb mod p，但最后O与A和B分别建立了共享密钥aXaXo mod p和aXbXo mod p，同时，O永远必须实时截获并冒充转发，否则会被发现。