Diffie-Hellman（迪菲-赫尔曼）秘钥交换

你的名字 2022-09-22 13:54 294阅读 0赞

[https://www.captainbed.net/lee244868149/][https_www.captainbed.net_lee244868149]

Diffie-Hellman算法是Whitefield Diffie和Martin Hellman在1976年公布的一种秘钥交换算法，它是一种建立秘钥的方法，而不是加密方法，所以秘钥必须和其他一种加密算法结合使用。这种秘钥交换技术的目的在于使两个用户安全的交换一个秘钥一遍后面的报文加密。

![20160630145752325][]

Diffie-Hellman密钥交换算法的有效性依赖于计算离散对数的难度。简言之，可以如下定义离散对数：首先定义一个素数p的原根，为其各次幂产生从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<=p-1**

指数i称为b的以a为基数的模p的离散对数或者指数。该值被记为inda ,p(b)。

基于此背景知识，可以定义Diffie-Hellman密钥交换算法。该算法描述如下：

1、有两个全局公开的参数，一个素数q和一个整数a，a是q的一个原根。

2、假设用户A和B希望交换一个密钥，用户A选择一个作为私有密钥的随机数XA<q，并计算公开密钥YA=a^XA mod q。A对XA的值保密存放而使YA能被B公开获得。类似地，用户B选择一个私有的随机数XB<q，并计算公开密钥YB=a^XB mod q。B对XB的值保密存放而使YB能被A公开获得。

3、用户A产生共享秘密密钥的计算方式是K = (YB)^XA mod q。同样，用户B产生共享秘密密钥的计算是K = (YA)^XB mod q。这两个计算产生相同的结果：

![20160630151113124][]

K = (YB)XA mod*q*

= (*a*XB mod*q*)XA mod *q*

= (*a*XB)XA mod*q* （根据取模运算规则得到）

= ***a*XBXA mod*q***

= (*a*XA)XB mod*q*

= (*a*XA mod*q*)XB mod *q*

= (YA)XB mod*q*

*所以 (YB)XA modq = K =(YA)XB modq*

因此相当于双方已经交换了一个相同的秘密密钥。

4、因为XA和XB是保密的，一个敌对方可以利用的参数只有q、a、YA和YB。因而敌对方被迫取离散对数来确定密钥。例如，要获取用户B的秘密密钥，敌对方必须先计算

XB = inda ,q(YB)

然后再使用用户B采用的同样方法计算其秘密密钥K。

Diffie-Hellman密钥交换算法的安全性依赖于这样一个事实：虽然计算以一个素数为模的指数相对容易，但计算离散对数却很困难。对于大的素数，计算出离散对数几乎是不可能的。

下面给出例子。密钥交换基于素数q = 97和97的一个原根a = 5。A和B分别选择私有密钥XA = 36和XB = 58。每人计算其公开密钥

YA = 536 = 50 mod 97

YB = 558 = 44 mod 97

在他们相互获取了公开密钥之后，各自通过计算得到双方共享的秘密密钥如下：

K = (YB)XA mod 97 = 4436 = 75 mod 97

K = (YA)XB mod 97 = 5058 = 75 mod 97

从|50，44|出发，攻击者要计算出75很不容易。

当然，为了使这个例子变得安全，必须使用非常大的XA, XB 以及p， 否则可以实验所有的可能取值。(总共有最多97个这样的值, 就算XA和XB很大也无济于事)。  
如果 p 是一个至少 300 位的质数，并且XA和XB至少有100位长， 那么即使使用全人类所有的计算资源和当今最好的算法也不可能从a, p和a^(XA\*XB) mod p 中计算出 XA\*XB。  
这个问题就是著名的离散对数问题。注意g则不需要很大, 并且在一般的实践中通常是2或者5

![20160630151605318][]

假设用户A希望与用户B建立一个连接，并用一个共享的秘密密钥加密在该连接上传输的报文。

1.用户A产生一个一次性的私有密钥x，并计算出公开密钥R1并将其发送给用户B。

2.用户B产生一个私有密钥y，计算出公开密钥R2并将它发送给用户A作为响应。必要的公开数值q和a都需要提前知道。另一种方法是用户A选择q和a的值，并将这些数值包含在第一个报文中。

3.A用户将接收到的R2||x||p 计算出秘钥K，B用户将接收到的R1||y||p 也计算出秘钥K，这相当于A和B交换了秘钥K。

![20160630152303703][]

下面再举一个使用Diffie-Hellman算法的例子。假设有一组用户（例如一个局域网上的所有用户），每个人都产生一个长期的私有密钥XA，并计算一个公开密钥YA。这些公开密钥数值，连同全局公开数值q和a都存储在某个中央目录中。在任何时刻，用户B都可以访问用户A 的公开数值，计算一个秘密密钥，并使用这个密钥发送一个加密报文给A。如果中央目录是可信任的，那么这种形式的通信就提供了保密性和一定程度的鉴别功能。因为只有A和B可以确定这个密钥，其它用户都无法解读报文（保密性）。接收方A知道只有用户B才能使用此密钥生成这个报文（鉴别）。

当然还有其他类型的秘钥交换结构，比如无线路由器中的802.1x Enrollee --- AP --- registrar可能会使用到两个秘钥K1，K2：

![20160630155329291][]

Diffie-Hellman算法具有两个吸引力的特征：

1、仅当需要时才生成密钥，减小了将密钥存储很长一段时间而致使遭受攻击的机会。

2、除对全局参数的约定外，密钥交换不需要事先存在的基础结构。

然而，该技术也存在许多不足：

1、没有提供双方身份的任何信息。

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

3、没办法防止重演攻击。

4、容易遭受中间人的攻击。第三方C在和A通信时扮演B；和B通信时扮演A。A和B都与C协商了一个密钥，然后C就可以监听和传递通信量。中间人的攻击按如下进行：

（1）B在给A的报文中发送他的公开密钥。

（2）C截获并解析该报文。C将B的公开密钥保存下来并给A发送报文，该报文具有B的用户ID但使用C的公开密钥YC，仍按照好像是来自B的样子被发送出去。A收到C的报文后，将YC和B的用户ID存储在一块。类似地，C使用YC向B发送好像来自A的报文。

（3）B基于私有密钥XB和YC计算秘密密钥K1。A基于私有密钥XA和YC计算秘密密钥K2。C使用私有密钥XC和YB计算K1，并使用XC和YA计算K2。

（4）从现在开始，C就可以转发A发给B的报文或转发B发给A的报文，在途中根据需要修改它们的密文。使得A和B都不知道他们在和C共享通信。

Oakley算法是对Diffie-Hellman密钥交换算法的优化，它保留了后者的优点，同时克服了其弱点。

Oakley算法具有五个重要特征：

1、它采用称为cookie程序的机制来对抗阻塞攻击。

2、它使得双方能够协商一个全局参数集合。

3、它使用了现时来保证抵抗重演攻击。

4、它能够交换Diffie-Hellman公开密钥。

5、它对Diffie-Hellman交换进行鉴别以对抗中间人的攻击。

Oakley可以使用三个不同的鉴别方法：

1、数字签名：通过签署一个相互可以获得的散列代码来对交换进行鉴别；每一方都使用自己的私钥对散列代码加密。散列代码是在一些重要参数上生成的，如用户ID和现时。

2、公开密钥加密：通过使用发送者的私钥对诸如ID和现时等参数进行加密来鉴别交换。

3、对称密钥加密：通过使用某种共享密钥对交换参数进行对称加密，实现交换的鉴别。

这种算法的关键是在这个式中

**b=ai mod p, 0<=i<=p-1**

如果知道a, i, p可以很方便的算出b的值，但是知道b, a, p的情况下想要算出i的值却非常难。所以如果只要突破这个点，就需要能在足够短的时间内算出i的值是多少。我相信不久的将来，随着量子计算机的发展，破解这种加密方式将不再是问题，任何一种依靠计算复杂度来保证数据安全性的加密方式都将会被淘汰，应运而生的将是更加先进可靠的加密方式。

[https_www.captainbed.net_lee244868149]: https://www.captainbed.net/lee244868149/
[20160630145752325]: /images/20220721/58637207b8f14a28a1a1b476a1bed78a.png
[20160630151113124]: /images/20220721/e8c5244637b446a99747a2a2078820c3.png
[20160630151605318]: /images/20220721/ef69e455116647a88f9fb2cfb1c9c128.png
[20160630152303703]: /images/20220721/2b042befc96848618f9469ad6bb975d4.png
[20160630155329291]: /images/20220721/e46f7ee01c2d47af8301646e541891ca.png