Diffie-Hellman 密钥交换

在前一篇流加密里面介绍到,加密解密的双方需要有一个 key,需要保证不能泄露这个 key。那么双方要如何在不泄露的情况下都知道这个 key 呢。

Diffie-Hellman 密钥交换算法就是为了解决,通信双方,在一个不安全的通信环境里,在双方互相不认识的情况下,最终能协商出一个只有双方知道的值。

在这里恭喜 Diffie 和 Hellman 两人,前两天刚凭借这个密钥交换算法获得了 2015 年度的图灵奖。

Diffie-Hellman 最核心的思想就是利用某些某个方向计算很容易,但是反反向计算非常难的数学。

数学解释

首先,对于 $y \equiv g^x \quad (\bmod p)$ 这个等式中,知道 g、x、p 是很容易计算出 y 来的。但是知道 y、g、p 的情况下,算出 x 来却十分困难。所以,利用这个等式,我们就可以构建一个密钥协商的过程。

首先,通信的双方 Alice 和 Bob 分别选择一个随机数 $r_A$ 和 $r_B$,然后分别计算他们自己的:

$$ m_A = g^{r_A} \quad (\bmod p)$$

$$ m_B = g^{r_B} \quad (\bmod p)$$

然后 Alice 和 Bob 分别把自己算出来的 $m_A$ 和 $m_B$ 发送给对方。在这个发送的过程中,所有的通信数据都可以被 Eve 看到。所以 Eve 是知道 $m_A$ 和 $m_B$ 的。但是由于反方向计算十分困难,所以 Eve 无法反推出 $r_A$ 和 $r_B$。

Alice 和 Bob 分别接收到对方的 $m_B$ 和 $m_A$ 后。在对方发过来的数据的基础上,带入自己的随机数,例如对于 Bob 会计算:

$$ S = (g^{r_A}) ^ {r_B} \quad (\bmod p) $$

对于 Alice 会计算:

$$ S = (g^{r_B}) ^ {r_A} \quad (\bmod p) $$

尽管计算顺序不一样,但是最后的结果是一样的,$(g^{r_B}) ^ {r_A} \quad (\bmod p) = (g^{r_A}) ^ {r_B} \quad (\bmod p)$。这个 S 就是最后协商的密钥。

椭圆曲线

Diffie-Hellman 还可以利用椭圆曲线(Elliptic curve),就是所说的 ECDH。

椭圆曲线密码学(ECC),基于椭圆曲线数学,作为程序员的我并不能看懂。

ECC 相比较而言的优势在于获得相同的安全性的时候,相对于上面的基于离散对数的方式,所需要的 key 的长度更小,所以计算速度会更快。

中间人攻击

Diffie-Hellman 算法并不能识别交换双方的身份。所以在交换密钥的过程中,可能会被中间人攻击。比如 Mallory 在 Alice 和 Bob 中间,分别和 Alice、Bob 进行密钥交换,那么 Mallory 还是可以分别得到两个人的 key。

为了解决这个问题,需要引入证书体系,将在后面介绍。