概述

我们都知道对称加密算法的一大难题是密钥交换问题。在1976年,研究生 Whitefield Diffie 和他的老师 Martin Hellman 提出了一个奇妙的密钥交换协议,称为 Diffie-Hellman 密钥交换协议/算法(Diffie-Hellman Key Exchange Agreement/Algorithm)。这个算法奇妙在并不直接把密钥在网络上传输,而是通信双方互相交换一些可以公开的数据,最终再用这些公开的数据与一些只有自身知道的私密数据共同计算出一个相同的密钥,而攻击者很难从这些公开的数据直接计算出密钥。

算法描述

现在有Alice和Bob两个人,他们需要交换对称密钥用于对称加密。

首先Alice和Bob分别确定两个大素数 $n$ 和 $g$ ,这两个大素数不用保密,可以明文在网络中交换。

Alice再选择另一个大随机数 $x$ ,并用下面的公式计算出一个 $A$ 。 $$ A = g^x mod n $$ 然后Alice将这个 $A$ 发送给Bob,这个过程仍然可以明文传输。

而Bob则选择另一个大随机数 $y$ ,并用下面的公式计算出一个 $B$ 。 $$ B = g^y mod n $$ 然后Bob将这个 $B$ 发送给Alice,这个过程同样明文传输。

此时Alice计算出一个密钥 $K_{1}$ : $$ K_{1} = B^x mod n $$ Bob计算出一个密钥 $K_{2}$ : $$ K_{2} = A^y mod n $$ 此时,可以证明,$K_{1}$ 等于 $K_{2}$ ,且这个值就是最终商定出来的对称密钥。

算法证明

我们需要证明两个东西,一个是为什么 $K_{1} = K_{2}$ ,一个是攻击者为什么不能通过明文传输的 $n$ 、$g$ 、$A$ 、$B$ 求出只有Alice和Bob知道的 $x$ 和 $y$ ,从而无法得到密钥 $K$ 。

首先,由 $B = g^y mod n$ 和 $K_{1} = B^x mod n$ 可求得 $K_{1} = (g^y mod n)^x mod n$ ,由求模的运算法则 $(a ^ b) mod p = [(a mod p)^b] mod p$ ,可将上式化简为 $K_{1} = g^{xy} mod n$ 。类似的,可以求得 $K_{2} = g^{xy}modn$ 。所以 $K_1 = K_2$ 得证。

然后证明另一个问题,这需要用到一点小学三年级就学到过的数学知识:

在有限域中的离散对数的计算难度比同一个域中的指数计算难得多。

好吧,我不知道你看懂这句话了没,反正我是没看懂。总而言之,对于$A = g^x mod n$ 来说,已知 $A$ 、$g$ 、$n$ ,求 $x$ ,在数学上是相当难的一件事,相当复杂,可能需要计算机高速计算很久很久才能求出来。也就是说,这是依靠着计算复杂度来保证着加密的安全。

算法的问题

首先是一个小问题,由上面的描述我们知道,Diffie-Hellman算法求出的密钥可能是一个任意长的值(小于大素数 $n$ ),而很多对称加密算法如DES可能需要的是一个定长的密钥例如56位。这其实很好解决,双方商定一下用求出的密钥中的哪56位即可。

而另一个问题则不容小觑,就是Diffie-Hellman密钥交换算法可能受到中间人攻击(man-in-the-middle attack),如下所述。

中间人攻击是网络安全中非常著名的一种攻击类型。具体来讲,攻击者会分别与一个正常通讯的两端分别创建独立的连接,并中转通讯两端的数据,使通信的两端认为他们正在与正确的对端通信,殊不知整个会话都已经被攻击者完全控制。攻击者可以轻易地拦截通讯双方的通话并插入新内容。

而如果将中间人攻击应用在Diffie-Hellman算法中,就是攻击者分别与Alice和Bob通过算法商定两个不同的密钥,一个用于Alice和攻击者通信,而另一个用于攻击者和Bob通信。在Alice和Bob看来,他们都正确的和对方商定了一个唯一的密钥用于对称加密通信,而事实是整个会话已经被攻击者控制。

这个问题不好解决,需要引入数字签名+数字证书。对于这些技术我写了博客详细阐述,参见 https://laihaodong.cn/2318.htmlhttps://laihaodong.cn/2324.html 。简单来说,Alice 可以在开始 DH 算法之前先发送一个自己的数字签名给 Bob ,这个数字签名由 Alice 的私钥签名,而 Bob 为了验证这个数字签名需要 Alice 的公钥来验证,所以 Alice 同时还得把自己的数字证书发给 Bob ,其中就包含了自己的公钥。这样 Bob 收到数字证书之后,首先可以确定 Alice 的公钥是什么,然后又通过这个公钥验证 Alice 的数字签名,验证成功则说明一定是 Alice 发来的消息,这样就避免了中间人攻击。常见的数字签名有 RSA 数字签名技术。

这里其实又会引出一个问题,既然为了保证 Deffie-Hellman 算法不受中间人攻击引入了 RSA 非对称加密/签名技术,那为什么不干脆直接用RSA非对称加密来交换对称加密的密钥呢?这个知乎问题里有答主提到,其实密钥交换算法有很多种,例如刚才说的RSA密钥交换、DH(Diffie-Hellman)、DHE(EDH,临时DH)、ECDH(椭圆曲线版DH),这些其实都能用,不同之处在于后几种DH的变种支持前向安全(Forward Secrecy,缩写:FS),有时也被称为完美前向安全(英语:Perfect Forward Secrecy,缩写:PFS)。所以现实可能更推荐使用DH及其变种来交换密钥。所谓前向安全,即用于解密的密钥泄露后,即使有之前的密文,也无法恢复出这些密文的原文。对于RSA非对称加密来说,如果私钥泄露了,而且攻击者保存了之前用RSA加密的密文,那么就直接可以还原出之前通信的原文,所以RSA就不支持前向安全。而对于DH而言,其交换密钥的本质并不是加密,而是通过一些可以公开的数据计算出密钥,这样只要在完成DH完成后立刻将中间数据都从内存中清除,理论上就不会被破解,也不存在什么密钥泄露的问题,所以具有前向安全。

Last modification:March 15th, 2020 at 11:56 pm