Diffie–Hellman 密钥协商算法详解

月半兄

2020-11-01 (Updated: 2020-12-28)

算法, 网络安全

简介

迪菲－赫尔曼（Diffie–Hellman）密钥协商是在美国密码学家惠特菲尔德·迪菲和马丁·赫尔曼的合作下发明的，发表于 1976 年。它是第一个实用的在非保护信道中创建共享密钥方法。

描述了这个算法的美国专利第 4,200,770 号，已经于 1997 年 4 月 29 日后过期，专利文件表明了 Hellman、Diffie 和 Merkle 是算法的发明者。

解决的问题

DH 算法可以在一个不安全的信道上建立安全连接，从而解决的不安全信道上信息安全交换的问题。

算法流程与数学原理

DH 算法通过公共信道交换一个信息，就可以创建一个可以用于在公共信道上安全通信的共享秘密（shared secret）。

假设 Client_A 与 Client_B 在不安全的信道上交换信息，他们通过 DH 算法协商出一个密钥，具体流程如下:

Client_A 与 Client_B 确定算法协商使用质数 p 的整数模 n 乘法群以及其原根 g
Client_A 生成随机数 $a \in [1, p-1]$ ，计算 $A = g^a \mod p$ ，将 A 发送给 Client_B
Client_B 生成随机数 $b \in [1, p-1]$ ，计算 $B = g^b \mod p$ ，将 B 发送给 Client_A
Client_A 计算 $s = B^a \mod p = g^{ba} \mod p$
Client_B 计算 $s = A^b \mod p = g^{ab} \mod p$

通过上述过程，Client_A 与 Client_B 得到了一个安全的共享密钥 s。

下图描述了整个协商的过程，可以辅助理解算法流程:

Client_A 与 Client_B 算出 s 相等的数学证明

我们需要证明 Client_A 计算的 s 等于 Client_B 计算的 s，下面对于 Client_A 计算 s 的过程进行分析。

首先对于 B 可做如下变换

$\begin{aligned}g^b \mod p &= B \g^b &= kp + B, (k \in N) \B &= g^b - kp, (k \in N)\end{aligned}$

则 Client_A 计算 s 的过程可做如下变换

$\begin{aligned}s &= B^a \mod p \&= (g^b - kp)^a \mod p \&= (\binom{a}{0}g^{ba}(-kp)^0 + \binom{a}{1}g^{b(a-1)}(-kp) + \binom{a}{2}g^{b(a-2)}(-kp)^2 + … + \binom{a}{a}g^0(-kp)^a) \mod p \\end{aligned}$

上述展开使用到二项式定理，其中每个形如 $\binom{a}{k}$ 的项称作二项式系数的特定正整数，其等于 ${\frac {a!}{k!(a-k)!}}$ 。除了第一项外，其余所有项都有 kp 因子参与乘积，因此其结果 mod p 后均等于 0，等式可以变换为。

$\begin{aligned}s &= (\binom{a}{0}g^{ba}(kp)^0) \mod p \&= g^{ab} \mod p\end{aligned}$

至此，完成对 Client_A 计算 s 的公式推导，对于 Client_B 计算 s 的过程可由同样方式推导为 $g^{ab} \mod p$ ，因此 Client_A 计算的 s 等于 Client_B 计算的 s。

g 的取值范围

DH 算法定义 质数 p 的整数模 n 乘法群以及其原根 g，参考关于原跟、整数模n乘法群的数学定义可以知道，原根 g 的取值范围其实是通过 p 计算得出，且范围一定在 [1, p-1] 内。

a, b 的取值范围

如果 a、b 取值大于等于 p，则以 a 为例，我们做如下分析。

首先我们将 a 分解为 j 个 (p-1) 项，加一个余数项 k，即：

$a = (p-1)j + k \quad (j \in N, k \in [1, p-1])$

则 $g^a$ 可以做如下变换：

$\begin{aligned}g^a &= g^{(p-1)j+k} \&= g^{(p-1)j}\cdot g^k \&= (g^{(p-1)j} \mod p ) \cdot (g^k \mod p) \&= ((g^{(p-1)})^j \mod p ) \cdot (g^k \mod p) \&= ((g^{(p-1)} \mod p)^j \mod p ) \cdot (g^k \mod p) \&= ((1)^j \mod p ) \cdot (g^k \mod p) \&= (1 \mod p ) \cdot (g^k \mod p) \&= 1 \cdot (g^k \mod p) \&= g^k \mod p \\end{aligned}$

上述等式变化使用到的数学原理包括：

模除中的恒等式、乘法分配律、幂运算。
费马小定理，对于整数 g，质数 p，有 $g^p \mod p = g \mod p$ 。若 g 不是 p 的倍数，有 $g^{p-1} \mod p = 1$ 。

综上，我们可以得出结论，当 a 的值大于等于 p 时， $g^a$ 的计算结果范围与 $a \in [1, p-1]$ 时的计算结果范围相同。用数学表示为以下结论，集合 A 与集合 B 相等。

$\begin{aligned}A &= { g^a, a \in N, a \geq p } \B &= { g^a, a \in N, a \in [1, p-1] } \A &= B\end{aligned}$

考虑到 DH 算法的安全性主要由 p 与 g 的取值确定（参考下一节安全性分析），且高阶幂运算本身具有一定的性能损耗，因此我们对 a、b 的取值范围限定在 $[1, p-1]$ 。

安全性分析

如果有中间人 Client_C 可以获取到 Client_A 与 Client_B 交换的所有信息，它仍然无法推导出密钥 s。对于 Client_A，Client_B，Client_C 在整个密钥协商过程中，能获取到的信息如下表展示。可以看到，Client_C 可以拦截到传输过程中的 p, g, A, B，但由于不知道 a, b，无法最终计算出 s。

信息	Client_A	Client_B	Client_C
p	✔️	✔️	✔️
g	✔️	✔️	✔️
a	✔️	❌	❌
b	❌	✔️	❌
A = g^a mod p	✔️	✔️	✔️
B = g^b mod p	✔️	✔️	✔️
s = A^b mod p	❌	✔️	❌
s = B^a mod p	✔️	❌	❌

中间人如果想要计算出 s，必须先计算出 a 或 b，也就是求解离散对数问题 $Ind_{g}A \equiv a {\pmod {m}}$ 或 $Ind_{g}B \equiv b {\pmod {m}}$ 。

离散对数问题被认为是一个难解的数学问题，公钥密码学中几个重要算法的基础，是假设寻找离散对数的问题解，在仔细选择过的群中，并不存在有效率的求解算法。

p 的安全范围

如果 p 的取值范围过小，DH 算法的安全性就会大打折扣，参考下面这个示例。

假如我们选择 p = 7，g = 3。随机数 a = 2，b = 5，则整个 DH 协商过程如下：

Client_A 计算 $A = 3^2 \mod 7 = 2$ ，将 A 发送给 Client_B
Client_B 计算 $B = 3^5 \mod 7 = 5$ ，将 B 发送给 Client_A
Client_A 计算 $s = 5^2 \mod 7 = 4$
Client_B 计算 $s = 2^5 \mod 7 = 4$

中间人拦截到 p = 7，g = 3，A = 2，B = 5。中间人只需要遍历 a 的取值范围 [1, 6]，并分别计算 $A = g^a \mod p$ 直到算出一个值，等于拦截到的 A 值，也就是 2，则中间人就算出了 a，从而可以通过 $s = B^a \mod p$ 计算出 s。

进一步分析所有 $g^a$ 的结果，对于 $a \in [1, 6]$ ，其计算结果如下。可以看出来，一共只有 6 种值，因此中间人可以很容易通过枚举 a 的方式碰撞出 a 的值。

$a$	$g^a \mod p$
1	3
2	2
3	6
4	4
5	5
6	1

因此我们在选择时，必须选择一个足够大的质数 p，以保证 a，b 的选择范围足够大，无法被轻易碰撞出来。一般来说，128 bit 的质数 p 在现有硬件算力的环境下是足够安全的。

在实际的操作中，一个索菲热尔曼素数 q 可以用来计算素数 p = 2q + 1，这样的 p 称为安全素数，因为使用它之后 G 的阶只能被 2 和 q 整除。

除此之外，根据上面的分析，我们也应该尽量选择足够大的数来作为随机数 a 和 b，以防止暴力破解。一般选择一个足够大的素因子以防止使用 Pohlig–Hellman 算法来得到 a 或 b。

对于使用索菲热尔曼素数 q 来计算 p 的场景，维基百科同样提到了下面这段有关 g 的安全取值的描述。（限于个人技术水平，没搞懂原理)

g 有时被选择成 G 的 q 阶子群的生成元，而不是 G 本身的生成元，这样 $g^a$ 的勒让德符号将不会显示出 a 的低位。

身份验证

DH 密钥交换本身并没有提供通讯双方的身份验证服务，因此它很容易受到中间人攻击。一个中间人在信道的中央进行两次 DH 密钥交换，一次和 A 另一次和 B，就能够成功的向 A 假装自己是B，反之亦然。中间人者可以解密（读取和存储）任何一个人的信息并重新加密信息，然后传递给另一个人。通常需要一个能够验证通讯双方身份的机制来防止这类攻击，比如一个公钥基础设施。

简介