【密码学百科】Diffie-Hellman 密钥交换与离散对数问题

一、密钥分发问题

在对称密码学的世界里，加密和解密使用同一把密钥。无论是 AES 还是 ChaCha20，只要通信双方共享一段秘密比特串，就能在公开信道上安全地传输信息。然而，这里隐藏着一个根本性的矛盾：如果 Alice 和 Bob 从未见过面，他们如何在完全公开的信道上协商出一把只有他们自己知道的密钥？

这就是密钥分发问题（key distribution problem）。在互联网出现之前，这个问题的解决方案几乎全部依赖物理手段——外交信使携带密码本、军事人员面对面交接密钥材料。对于需要同时与数百万用户通信的现代网络而言，这种方式显然不可扩展。如果网络中有 \(n\) 个用户，两两之间都需要一把独立的对称密钥，则系统需要管理 \(\binom{n}{2} = n(n-1)/2\) 把密钥，其增长速度为 \(O(n^2)\)。当 \(n\) 达到百万级别时，密钥数量将达到万亿量级，管理成本不可接受。

引入可信第三方（trusted third party）是一种缓解方案。Kerberos 协议便是这一思路的典型代表：所有用户与密钥分发中心（KDC）共享长期密钥，由 KDC 为每次会话签发临时会话密钥。然而，KDC 本身成为了单点故障和高价值攻击目标，且所有用户必须事先与 KDC 建立信任关系，这在全球规模的开放网络中仍然是巨大的部署障碍。

1976 年，Whitfield Diffie 和 Martin Hellman 在划时代的论文《New Directions in Cryptography》中提出了一个看似不可能的方案：两个从未谋面的人，仅通过公开信道的信息交换，就能协商出一个共享秘密，而窃听者即使截获了所有公开传输的数据，也无法计算出这个秘密。这一方案就是 Diffie-Hellman 密钥交换协议（Diffie-Hellman key exchange，简称 DH），它标志着公钥密码学（public-key cryptography）的诞生，彻底改变了密码学的发展方向。

DH 协议的革命性在于它将密钥协商问题从物理安全领域转移到了数学领域。协议的安全性不再依赖信使的忠诚或物理信道的保密性，而是建立在一个精确定义的数学难题——离散对数问题（discrete logarithm problem，简称 DLP）之上。只要这个数学难题在计算上不可行，协议就是安全的。这种将安全性归约到数学假设的思想，成为此后所有公钥密码方案的设计范式。

值得一提的是，英国政府通信总部（GCHQ）的 James Ellis、Clifford Cocks 和 Malcolm Williamson 在 1970 年代初期独立发现了类似的概念，但由于军事保密的原因，这些成果直到 1997 年才被解密公开。因此，公开文献中 Diffie 和 Hellman 的工作仍被视为公钥密码学的开端。

二、DH 协议详解

2.1 协议流程

DH 协议的数学舞台是一个有限循环群（finite cyclic group）。最经典的实例化使用模素数 \(p\) 的乘法群 \(\mathbb{Z}_p^*\) 中的一个阶为 \(q\) 的子群，其中 \(g\) 为该子群的生成元。公开参数 \((p, g)\) 可以由通信双方中的任意一方选择，也可以使用标准化的参数。

协议步骤如下：

1. 参数公开：Alice 和 Bob 就素数 \(p\) 和生成元 \(g\) 达成一致（这些参数是公开的）。
2. Alice 生成私钥：Alice 均匀随机选择 \(a \xleftarrow{\$} \{1, 2, \ldots, p-2\}\)，计算 \(A = g^a \bmod p\)，将 \(A\) 发送给 Bob。
3. Bob 生成私钥：Bob 均匀随机选择 \(b \xleftarrow{\$} \{1, 2, \ldots, p-2\}\)，计算 \(B = g^b \bmod p\)，将 \(B\) 发送给 Alice。
4. 共享秘密计算：Alice 计算 \(s = B^a \bmod p\)；Bob 计算 \(s = A^b \bmod p\)。

2.2 正确性证明

协议的正确性来自模幂运算的交换律：

\[s_{\text{Alice}} = B^a = (g^b)^a = g^{ab} \bmod p\]

\[s_{\text{Bob}} = A^b = (g^a)^b = g^{ab} \bmod p\]

因此 \(s_{\text{Alice}} = s_{\text{Bob}} = g^{ab} \bmod p\)，双方确实计算出了相同的共享秘密。

2.3 直觉理解

一个广为流传的类比是”颜料混合”（paint mixing analogy）。想象 Alice 和 Bob 各自有一种秘密颜色，同时他们公开约定了一种基础颜色。协议过程是：每人将自己的秘密颜色与基础颜色混合，然后将混合结果发送给对方。收到对方的混合色后，再加入自己的秘密颜色。由于颜料混合的顺序不影响最终结果（交换律），双方最终得到相同的颜色。而窃听者虽然知道基础颜色和两个混合色，但由于颜料混合的不可逆性，无法还原出任何一方的秘密颜色，也就无法得到最终的共享颜色。

另一个更贴切的比喻是”电话簿”（phone book analogy）。计算 \(g^a \bmod p\) 就像在电话簿中根据姓名查找电话号码——简单快捷。而从 \(g^a \bmod p\) 反推 \(a\)，就像只知道电话号码去反查姓名——在没有反向索引的情况下，你只能逐页翻阅，这个过程极为缓慢。DH 协议的安全性正是建立在这种计算上的不对称性之上。

2.4 Python 实现

以下是 DH 密钥交换的基本实现：

import secrets
from hashlib import sha256

def generate_dh_params():
    """使用 RFC 3526 的 2048 位 MODP 群参数（截取演示用的较小参数）"""
    # 实际部署应使用 RFC 3526/7919 中定义的标准群
    # 此处为演示使用一个较小的安全素数 p = 2q + 1
    p = 0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C354E4ABC9804F1746C08CA18217C32905E462E36CE3BE39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9DE2BCBF6955817183995497CEA956AE515D2261898FA051015728E5A8AACAA68FFFFFFFFFFFFFFFF
    g = 2
    return p, g

def dh_key_exchange():
    p, g = generate_dh_params()

    # Alice 生成私钥和公钥
    a = secrets.randbelow(p - 2) + 1
    A = pow(g, a, p)

    # Bob 生成私钥和公钥
    b = secrets.randbelow(p - 2) + 1
    B = pow(g, b, p)

    # 双方计算共享秘密
    s_alice = pow(B, a, p)
    s_bob = pow(A, b, p)

    assert s_alice == s_bob, "共享秘密不匹配！"

    # 通过 KDF 派生实际加密密钥
    shared_key = sha256(s_alice.to_bytes(256, 'big')).digest()
    print(f"Alice 公钥: {A}")
    print(f"Bob   公钥: {B}")
    print(f"共享密钥:   {shared_key.hex()}")
    return shared_key

dh_key_exchange()

需要注意的是，实际部署中共享秘密 \(g^{ab}\) 不应直接用作加密密钥，而应通过密钥派生函数（KDF）提取出均匀分布的密钥材料。这是因为 \(g^{ab}\) 作为群元素，其比特分布并不均匀——例如在 \(\mathbb{Z}_p^*\) 中，共享秘密一定小于 \(p\)，因此最高位的分布存在偏差。

三、离散对数问题

3.1 形式化定义

给定有限循环群 \(G = \langle g \rangle\)（由 \(g\) 生成），阶为 \(n\)，以及群元素 \(h \in G\)，离散对数问题要求找到整数 \(x \in \{0, 1, \ldots, n-1\}\) 使得 \(g^x = h\)。记作 \(x = \log_g h\)。

DH 协议的安全性直观上建立在 DLP 的困难性之上：如果攻击者能从 \(A = g^a\) 中高效地计算出 \(a\)，就能利用截获的 \(B = g^b\) 计算 \(s = B^a = g^{ab}\)。然而，DLP 的困难性与 DH 的安全性之间的精确关系比这更为微妙，我们将在第四节讨论。

3.2 朴素算法与 Baby-Step Giant-Step

最朴素的方法是穷举搜索：从 \(x = 0\) 开始逐一尝试，直到 \(g^x = h\)。这需要 \(O(n)\) 次群运算，当群的阶 \(n\) 为 256 位整数时完全不可行。

1971 年 Daniel Shanks 提出的 Baby-step Giant-step（小步大步算法，简称 BSGS）是一种经典的时间-空间折中方法。设 \(m = \lceil\sqrt{n}\rceil\)，算法分两步进行：

1. Baby step（小步）：计算并存储 \(\{(j, g^j) : 0 \le j < m\}\) 到一个哈希表中。
2. Giant step（大步）：令 \(\gamma = g^{-m}\)，依次计算 \(h \cdot \gamma^i\)（\(i = 0, 1, 2, \ldots\)），检查是否在哈希表中出现。

若 \(h \cdot \gamma^i = g^j\)，则 \(h = g^{j + im}\)，即 \(x = j + im\)。算法的时间和空间复杂度均为 \(O(\sqrt{n})\)，这是一个巨大的改进——对于 256 位的群阶，只需要约 \(2^{128}\) 次运算，但仍然是指数级的（相对于比特长度）。

Pollard 的 rho 算法（Pollard’s rho algorithm）在时间上与 BSGS 相当（\(O(\sqrt{n})\) 次群运算），但空间复杂度仅为 \(O(1)\)，在实践中更受青睐。它利用伪随机游走在群中产生碰撞，并结合 Floyd 或 Brent 的环检测算法来找到离散对数。

3.3 Pohlig-Hellman 算法

当群的阶 \(n\) 可以分解为小素因子之积（即 \(n\) 是”光滑数”，smooth number）时，Pohlig-Hellman 算法能够极大地降低 DLP 的难度。

设 \(n = \prod_{i=1}^{k} p_i^{e_i}\)，算法在每个素幂子群 \(\langle g^{n/p_i^{e_i}} \rangle\) 中分别求解规模为 \(p_i^{e_i}\) 的离散对数问题，然后通过中国剩余定理（CRT）组合出完整的解。总复杂度为 \(O\left(\sum_{i=1}^{k} e_i (\log n + \sqrt{p_i})\right)\)，取决于最大的素因子 \(p_i\)。

这一结果对密码参数选择有深远的影响：如果群的阶包含大量小因子，DLP 就变得容易。因此，密码学中使用的群必须具有大的素数阶因子。这也是为什么我们需要”安全素数”——形如 \(p = 2q + 1\) 的素数，其中 \(q\) 也是素数。这时 \(\mathbb{Z}_p^*\) 的阶为 \(p - 1 = 2q\)，最大素因子为 \(q\)，Pohlig-Hellman 算法不会带来实质性的加速。

3.4 指数计算法

在 \(\mathbb{Z}_p^*\) 中，存在比通用算法更强大的攻击：指数计算法（index calculus）。它是专属于有限域的亚指数算法，无法推广到一般的群（例如椭圆曲线群）。

指数计算法的核心思想是：选定一个因子基（factor base）\(\mathcal{B} = \{p_1, p_2, \ldots, p_B\}\)（由前 \(B\) 个小素数组成），收集形如 \(g^{r_i} \bmod p\) 能被因子基完全分解（即 \(\mathcal{B}\)-光滑）的关系式，建立线性方程组，通过求解该方程组得到因子基中每个元素的离散对数，然后利用这些结果计算任意元素的离散对数。

对于一般数域筛法（general number field sieve，GNFS）应用于离散对数时，其复杂度为：

\[L_p\left[\frac{1}{3}, \left(\frac{64}{9}\right)^{1/3}\right] = \exp\left(\left(\frac{64}{9}\right)^{1/3} (\ln p)^{1/3} (\ln \ln p)^{2/3}\right)\]

这是一个亚指数但超多项式的复杂度。对于 1024 位素数，这个复杂度在学术界的高性能计算资源下已经处于可计算的边缘，这也是 2015 年 Logjam 攻击的理论基础（详见第八节）。

指数计算法的存在是椭圆曲线密码学（ECC）兴起的重要原因之一：在椭圆曲线群上，目前没有已知的亚指数算法，因此 ECC 可以用更短的密钥达到同等安全级别。

四、CDH 与 DDH 假设

4.1 计算 Diffie-Hellman 假设

DLP 的困难性是 DH 安全性的充分条件但可能不是必要条件。为了更精确地刻画 DH 协议的安全需求，密码学家定义了两个与 DH 直接相关的计算假设。

计算 Diffie-Hellman 假设（Computational Diffie-Hellman assumption，CDH）：给定群 \(G = \langle g \rangle\)、\(g^a\) 和 \(g^b\)（其中 \(a, b\) 均匀随机选取），没有高效算法能够计算出 \(g^{ab}\)。

形式化地，对于任何概率多项式时间算法 \(\mathcal{A}\)：

\[\Pr[\mathcal{A}(G, g, g^a, g^b) = g^{ab}] \le \text{negl}(\lambda)\]

其中 \(\lambda\) 为安全参数，\(\text{negl}(\cdot)\) 表示可忽略函数。

CDH 直接对应 DH 协议的安全目标：攻击者看到 \(g^a\) 和 \(g^b\)，需要计算 \(g^{ab}\)。如果 CDH 假设成立，攻击者就无法做到这一点。

4.2 判定 Diffie-Hellman 假设

在许多密码方案（如 ElGamal 加密）中，我们需要更强的安全保证：攻击者不仅不能计算 \(g^{ab}\)，甚至不能区分 \(g^{ab}\) 和一个随机群元素。

判定 Diffie-Hellman 假设（Decisional Diffie-Hellman assumption，DDH）：给定 \((g, g^a, g^b, g^c)\)，没有高效算法能够以不可忽略的优势区分 \(c = ab \bmod n\) 和 \(c \xleftarrow{\$} \mathbb{Z}_n\) 这两种情况。

形式化地，以下两个分布在计算上不可区分：

\[(g, g^a, g^b, g^{ab}) \approx_c (g, g^a, g^b, g^c)\]

其中 \(a, b, c\) 均匀随机选取。

4.3 假设之间的层次关系

三个假设之间存在清晰的蕴含关系：

\[\text{DLP 困难} \Longrightarrow \text{CDH 困难} \Longrightarrow \text{DDH 困难}\]

反向是否成立目前尚未证明。具体来说：若 CDH 容易（即能计算 \(g^{ab}\)），则 DLP 不一定容易——理论上可能存在一种方法直接计算 \(g^{ab}\) 而不需要先求出 \(a\) 或 \(b\)。类似地，若 DDH 容易（即能区分 \(g^{ab}\) 和随机元素），也不意味着能够实际计算出 \(g^{ab}\)。

在实践中，对于精心选择的密码学群（如安全素数群的素数阶子群、适当的椭圆曲线群），这三个假设被广泛认为同时成立。

4.4 间隙群与 DDH 的局限

存在一类特殊的群称为间隙群（gap group），在其中 CDH 困难但 DDH 容易。最典型的例子是具有高效配对（pairing）的椭圆曲线群：双线性配对 \(e: G \times G \to G_T\) 允许高效判断 \((g, g^a, g^b, h)\) 中 \(h\) 是否等于 \(g^{ab}\)（通过检验 \(e(g^a, g^b) = e(g, h)\)），但这并不帮助实际计算 \(g^{ab}\)。

更简单的例子是 \(\mathbb{Z}_p^*\) 本身（而非其素数阶子群）。在 \(\mathbb{Z}_p^*\) 中，可以利用 Legendre 符号泄露 \(g^{ab}\) 的二次剩余性质来打破 DDH。具体地说，如果 \(p \equiv 3 \pmod{4}\) 且 \(g\) 是 \(\mathbb{Z}_p^*\) 的生成元，那么 \(g^x\) 是二次剩余当且仅当 \(x\) 是偶数。因此，观察 \(g^a\) 和 \(g^b\) 的二次剩余性就能推断 \(g^{ab}\) 的二次剩余性，从而区分 \(g^{ab}\) 和随机元素。这就是为什么 DH 协议必须在素数阶子群中工作，而不是在整个 \(\mathbb{Z}_p^*\) 中。

五、参数选择与安全性

5.1 安全素数与 Sophie Germain 素数

安全素数（safe prime）是形如 \(p = 2q + 1\) 的素数，其中 \(q\) 也是素数。此时 \(q\) 称为 Sophie Germain 素数。安全素数之所以得名，是因为 \(\mathbb{Z}_p^*\) 的阶 \(p - 1 = 2q\) 仅有很少的因子（1、2、\(q\)、\(2q\)），使得 Pohlig-Hellman 算法无法利用小因子加速。

在使用安全素数时，\(\mathbb{Z}_p^*\) 中阶为 \(q\) 的子群恰好是所有二次剩余组成的集合 \(QR_p\)。通信双方应在这个子群中工作：使用 \(g\) 为该子群的生成元（即 \(g\) 是模 \(p\) 的二次剩余且 \(g \ne 1\)），并验证收到的对方公钥也在这个子群中。

5.2 标准化参数

为避免每次协议执行都生成新的素数（这是一个计算昂贵的过程），业界定义了多组标准化的 DH 参数：

• RFC 3526（2003）：定义了 1536 位到 8192 位的 MODP 群，广泛用于 IKE（Internet Key Exchange）协议。
• RFC 7919（2016）：为 TLS 1.3 定义了命名的有限域 DH 群（ffdhe2048、ffdhe3072、ffdhe4096 等），同时引入了协商机制以防降级攻击。

使用标准化参数的好处是：其安全性已经过广泛审查；通信双方无需额外的参数协商步骤；实现更加简洁，减少出错概率。但正如 Logjam 攻击（第八节）所揭示的，如果大量服务器使用同一组参数，攻击者只需执行一次昂贵的预计算就能攻击所有这些服务器。

5.3 最低参数长度

根据当前的计算能力和算法发展，各标准机构推荐的最低参数长度如下：

NIST SP 800-57 建议 2031 年之后不再使用 2048 位以下的参数。对于长期安全需求，应使用至少 3072 位的参数，或转向椭圆曲线 DH（ECDH）以获得更高的效率。

5.4 群元素验证

接收对方公钥后，必须执行以下验证步骤：

1. 检查 \(1 < A < p\)（排除退化元素 0 和 1，以及非法的过大值）。
2. 检查 \(A^q \equiv 1 \pmod{p}\)（确认 \(A\) 在阶为 \(q\) 的子群中）。

如果使用安全素数 \(p = 2q + 1\)，第二步等价于检查 \(A\) 是否为二次剩余，可以通过计算 Legendre 符号 \(\left(\frac{A}{p}\right) = A^{(p-1)/2} \bmod p\) 来高效完成。省略这些验证将导致小子群攻击（详见第六节）。

六、小子群攻击

6.1 攻击原理

小子群攻击（small subgroup attack）利用了群结构中的低阶元素来提取受害者的私钥信息。当 \(p - 1\) 包含小素因子 \(r\) 时，\(\mathbb{Z}_p^*\) 中存在阶为 \(r\) 的子群。攻击者可以构造一个属于这个小子群的元素，冒充合法的 DH 公钥发送给受害者。

假设攻击者 Eve 向 Alice 发送 \(B' = t\)，其中 \(t\) 的阶为 \(r\)（小素数）。Alice 按照协议计算 \(s = (B')^a = t^a \bmod p\)。由于 \(t\) 的阶为 \(r\)，\(s\) 只取决于 \(a \bmod r\) 的值——即 \(s = t^{a \bmod r} \bmod p\)。由于 \(r\) 很小，\(a \bmod r\) 只有 \(r\) 种可能，Eve 可以穷举所有可能来确定 \(a \bmod r\)。

如果 \(p - 1\) 有多个小素因子 \(r_1, r_2, \ldots\)，Eve 可以针对每个小因子重复此攻击，然后通过中国剩余定理组合出 \(a\) 对更大模数的值，甚至完全恢复 \(a\)。这就是 Lim-Lee 攻击的思想。

6.2 小子群攻击演示

以下 Python 代码演示了小子群攻击的原理：

def small_subgroup_attack_demo():
    """
    演示小子群攻击：当 p-1 含有小因子时，
    攻击者可以通过选择低阶元素提取私钥的部分信息。
    """
    # 选择一个 p 使得 p-1 有小因子
    # p = 467, p-1 = 466 = 2 * 233
    # 这里我们用更能体现攻击的例子
    # p = 1009, p-1 = 1008 = 2^4 * 3^2 * 7
    p = 1009
    g = 11  # 原根

    # Alice 的私钥
    a = 537

    # 攻击者选择阶为 7 的元素
    # g^(1008/7) = g^144 的阶为 7
    r = 7
    t = pow(g, (p - 1) // r, p)
    assert pow(t, r, p) == 1, "t 的阶不是 r"
    assert t != 1, "t 不应为单位元"

    # 攻击者发送 t 作为伪造的公钥
    # Alice 计算 "共享秘密"
    s = pow(t, a, p)

    # 攻击者穷举 a mod r 的值
    recovered = None
    for candidate in range(r):
        if pow(t, candidate, p) == s:
            recovered = candidate
            break

    print(f"素数 p = {p}, p-1 = {p-1} = 2^4 * 3^2 * 7")
    print(f"攻击者使用阶为 {r} 的元素 t = {t}")
    print(f"Alice 的私钥 a = {a}")
    print(f"Alice 计算的 '共享秘密' s = {s}")
    print(f"攻击者恢复: a mod {r} = {recovered}")
    print(f"验证: {a} mod {r} = {a % r}")
    assert recovered == a % r, "攻击失败"
    print("攻击成功！攻击者获得了 a mod r 的值。")

    # 继续攻击：对因子 9 执行同样的攻击
    r2 = 9
    t2 = pow(g, (p - 1) // r2, p)
    s2 = pow(t2, a, p)
    for candidate in range(r2):
        if pow(t2, candidate, p) == s2:
            recovered2 = candidate
            break
    print(f"\n对因子 {r2} 的攻击: a mod {r2} = {recovered2}")
    print(f"验证: {a} mod {r2} = {a % r2}")

    # CRT 组合
    # 已知 a mod 7 和 a mod 9，可以得到 a mod 63
    from math import gcd
    for x in range(r * r2):
        if x % r == recovered and x % r2 == recovered2:
            print(f"\nCRT 组合: a mod {r * r2} = {x}")
            print(f"验证: {a} mod {r * r2} = {a % (r * r2)}")
            break

small_subgroup_attack_demo()

6.3 防御措施

防御小子群攻击的方法有以下几种：

1. 使用安全素数：若 \(p = 2q + 1\)（\(q\) 为素数），则 \(p - 1 = 2q\) 的唯一小因子是 2，小子群攻击的信息泄露量微乎其微。这是最直接也是最常见的防御手段。

2. 子群验证：接收到对方公钥 \(A\) 后，检查 \(A^q \equiv 1 \pmod{p}\)。如果 \(A\) 不在阶为 \(q\) 的子群中，则拒绝该公钥。

3. 私钥防护：将私钥乘以子群阶的因子。具体而言，在计算共享秘密时使用 \(s = A^{ha} \bmod p\)，其中 \(h\) 是群的余因子（cofactor）。对于安全素数，\(h = 2\)，因此 \(s = A^{2a}\) 保证了结果一定落在素数阶子群中。这种技术称为余因子 DH（cofactor DH）。

七、中间人攻击与认证 DH

7.1 中间人攻击

基本 DH 协议的一个根本缺陷是缺乏身份认证。协议保证了窃听者无法计算共享秘密，但无法防止主动攻击者（active attacker）冒充通信一方。

中间人攻击（Man-in-the-Middle attack，MITM）的过程如下：

1. Alice 向 Bob 发送 \(g^a\)，但被 Eve 截获。Eve 生成自己的随机数 \(e_1\)，将 \(g^{e_1}\) 转发给 Bob。
2. Bob 向 Alice 发送 \(g^b\)，同样被 Eve 截获。Eve 生成 \(e_2\)，将 \(g^{e_2}\) 转发给 Alice。
3. Alice 认为自己在与 Bob 通信，实际上她与 Eve 共享密钥 \(g^{a \cdot e_2}\)。Bob 认为自己在与 Alice 通信，实际上他与 Eve 共享密钥 \(g^{b \cdot e_1}\)。
4. Eve 可以解密 Alice 发来的消息，读取内容，然后用与 Bob 的共享密钥重新加密后转发，反向亦然。整个过程对 Alice 和 Bob 完全透明。

这一攻击表明：没有认证的密钥交换是毫无意义的。攻击者可以让双方各自以为建立了安全信道，实际上所有通信都经过攻击者中转。

7.2 Station-to-Station 协议

Station-to-Station（STS）协议是最早的认证 DH 方案之一。其核心思想是：在 DH 交换的基础上，双方各自使用自己的长期签名密钥对交换的公钥进行签名，并使用协商出的共享密钥加密签名。

简化的 STS 流程：

1. Alice → Bob：\(g^a\)
2. Bob → Alice：\(g^b, E_{K}(\text{Sig}_{B}(g^b, g^a))\)
3. Alice → Bob：\(E_{K}(\text{Sig}_{A}(g^a, g^b))\)

其中 \(K\) 由 \(g^{ab}\) 派生，\(\text{Sig}_X\) 表示使用 \(X\) 的长期签名私钥签名。每一方收到对方的消息后，先使用共享密钥解密，再验证签名。签名中包含双方的公钥，防止反射攻击（reflection attack）和未知密钥共享攻击（unknown key share attack）。

7.3 与证书体系的集成

在 TLS（Transport Layer Security）协议中，认证 DH 通常通过数字证书实现。服务器持有由可信证书颁发机构（CA）签发的证书，其中包含服务器的公钥和身份信息。TLS 握手中的认证 DH（如 DHE_RSA 或 ECDHE_RSA 密码套件）流程大致如下：

1. 服务器选择 DH 参数 \((p, g)\)，生成临时密钥对 \((b, g^b)\)。
2. 服务器使用其长期 RSA（或 ECDSA）私钥对 \(g^b\) 和握手上下文进行签名。
3. 服务器将 \(g^b\)、签名、以及证书链发送给客户端。
4. 客户端验证证书链的有效性，使用证书中的公钥验证签名，确认 \(g^b\) 确实来自合法服务器。
5. 客户端生成 \((a, g^a)\)，将 \(g^a\) 发送给服务器，双方计算共享秘密。

这里 “E” 代表临时的（ephemeral），意味着每次握手都使用新鲜的 DH 参数，从而提供前向安全性（forward secrecy）：即使服务器的长期私钥将来被泄露，过去的会话也不会被解密。

八、Logjam 攻击与预计算

8.1 攻击背景

2015 年，Adrian 等人发表了论文《Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice》，揭示了一种名为 Logjam 的攻击，它对实际部署的 DH 协议构成了严重威胁。

Logjam 攻击的核心观察是：指数计算法中最耗时的步骤——关系收集和线性代数求解——只依赖群的参数 \((p, g)\)，而与具体的 DH 公钥无关。这意味着，如果大量服务器使用相同的 \((p, g)\)，攻击者只需对这组参数执行一次耗时的预计算，之后就能快速破解任何使用该参数的 DH 交换。

8.2 出口级 DH 的灾难

在 1990 年代美国的密码出口管制政策下，SSL/TLS 协议被迫支持”出口级”密码套件，其中 DHE_EXPORT 使用仅 512 位的 DH 参数。Logjam 论文的作者发现，在 2015 年，攻击者可以在约一分钟内完成 512 位 DLP 的预计算。

更为严重的是，由于 TLS 协议的降级攻击漏洞，即使客户端和服务器都支持更强的密码套件，中间人攻击者也可以篡改握手消息，迫使连接使用 DHE_EXPORT。论文发表时，仍有约 8.4% 的 Alexa 排名前 100 万的 HTTPS 网站支持 DHE_EXPORT，因而容易受到这种攻击。

8.3 1024 位参数的威胁

Logjam 论文进一步指出，对于 1024 位的 DH 参数，预计算所需的资源虽然巨大但并非遥不可及。作者估计，一个拥有数亿美元预算的国家级攻击者（如情报机构）可以完成对特定 1024 位群的预计算。

事实上，Apache 的 httpd 服务器长期使用一组硬编码的 1024 位 DH 参数（即 oakley group 2），大量网站共享相同的参数。论文作者推测，这可能是 2013 年 Snowden 泄露文档中提到的 NSA 大规模解密 VPN 流量能力的技术基础。

预计算的具体数据如下：

8.4 防御与影响

Logjam 攻击推动了以下安全改进：

1. 禁用出口级密码套件：所有主流浏览器和服务器迅速移除了对 DHE_EXPORT 的支持。
2. 最低参数长度提升：浏览器开始拒绝 1024 位以下的 DH 参数，并逐步提升到要求至少 2048 位。
3. TLS 1.3 的设计改进：TLS 1.3 完全移除了对自定义 DH 参数和出口级密码套件的支持，只允许使用 RFC 7919 中定义的命名群和椭圆曲线群。
4. 推广 ECDH：由于椭圆曲线群不存在指数计算法类型的亚指数攻击，ECDH 不受 Logjam 式预计算攻击的影响，进一步加速了从有限域 DH 向 ECDH 的迁移。

Logjam 攻击是密码学工程的一个深刻教训：理论上安全的参数长度不一定在实践中安全，特别是当参数被广泛共享、协议允许降级、且存在国家级攻击者时。密码系统的安全性取决于其最薄弱的环节。

九、ElGamal 加密与从 DH 到 ECDH

9.1 ElGamal 加密

Taher ElGamal 于 1985 年提出了基于 DH 问题的公钥加密方案。ElGamal 加密可以看作是将 DH 密钥交换的”一半”嵌入到每条加密消息中。

密钥生成：选择群参数 \((G, g, q)\)，随机选取 \(x \xleftarrow{\$} \mathbb{Z}_q\)，计算 \(h = g^x\)。公钥为 \((G, g, q, h)\)，私钥为 \(x\)。

加密：要加密消息 \(m \in G\)，随机选取 \(r \xleftarrow{\$} \mathbb{Z}_q\)，计算密文 \((c_1, c_2) = (g^r, m \cdot h^r)\)。这里 \(g^r\) 相当于发送者的临时 DH 公钥，\(h^r = g^{xr}\) 是临时共享秘密，\(m\) 被该共享秘密”掩盖”。

解密：持有私钥 \(x\) 的接收者计算 \(c_1^x = g^{rx}\)，然后恢复 \(m = c_2 \cdot (c_1^x)^{-1} = m \cdot h^r \cdot g^{-rx} = m\)。

9.2 IND-CPA 安全性

ElGamal 加密在 DDH 假设下满足 IND-CPA（indistinguishability under chosen-plaintext attack，选择明文攻击下的不可区分性）安全。

直觉上，DDH 假设保证了 \((g, g^x, g^r, g^{xr})\) 与 \((g, g^x, g^r, g^c)\) 不可区分（其中 \(c\) 随机选取）。因此密文 \((g^r, m \cdot g^{xr})\) 与 \((g^r, m \cdot g^c)\) 不可区分。由于 \(g^c\) 是随机群元素，\(m \cdot g^c\) 完美地隐藏了 \(m\)，攻击者无法获得关于 \(m\) 的任何信息。

形式化的安全证明通过构造一系列混合博弈（hybrid games）完成：从真实的加密博弈出发，先用 DDH 假设将 \(g^{xr}\) 替换为随机元素 \(g^c\)，再证明在替换后的博弈中攻击者的优势为零。两步之间的不可区分性保证了总体优势可以忽略。

需要注意的是，基本 ElGamal 方案不满足 IND-CCA（选择密文攻击下的不可区分性）安全。攻击者可以对密文 \((c_1, c_2)\) 进行可延展性攻击：将 \(c_2\) 乘以任意群元素 \(g^t\) 得到 \((c_1, c_2 \cdot g^t)\)，这是 \(m \cdot g^t\) 的有效加密。要达到 CCA 安全，需要使用 Cramer-Shoup 方案或对 ElGamal 应用 Fujisaki-Okamoto 变换等技术。

9.3 ElGamal 签名

ElGamal 还提出了基于离散对数的签名方案，它是后来 DSA（Digital Signature Algorithm）和 Schnorr 签名的前身。

ElGamal 签名的过程如下：要对消息 \(m\) 签名，选择随机数 \(k\)（与 \(p-1\) 互素），计算 \(r = g^k \bmod p\)，然后求解 \(s\) 使得 \(m \equiv xr + ks \pmod{p-1}\)。签名为 \((r, s)\)。验证者检查 \(g^m \equiv h^r \cdot r^s \pmod{p}\)。

ElGamal 签名方案中随机数 \(k\) 的安全性至关重要。如果 \(k\) 被重复使用，攻击者可以从两个使用相同 \(k\) 的签名中提取出私钥 \(x\)。这正是 2010 年 Sony PlayStation 3 签名密钥泄露事件的技术原因——Sony 在 ECDSA 签名中使用了固定的 \(k\) 值。

9.4 从有限域 DH 到椭圆曲线 DH

经典 DH 协议工作在有限域 \(\mathbb{F}_p\) 的乘法群上，而椭圆曲线 DH（Elliptic Curve Diffie-Hellman，ECDH）将相同的协议框架搬到了椭圆曲线群上。协议的数学结构完全类似，只是将群运算从模乘法替换为椭圆曲线上的点加法：

ECDH 的核心优势在于安全效率比。由于椭圆曲线离散对数问题（ECDLP）目前没有已知的亚指数算法，最佳攻击仍然是 Pollard rho 的 \(O(\sqrt{n})\) 通用方法。因此，256 位的椭圆曲线群提供约 128 位的安全级别，等价于 3072 位的有限域 DH。在计算效率和带宽消耗上，ECDH 的优势显而易见：密钥长度更短（256 位对 3072 位）、计算速度更快、通信开销更小。

在现代实践中，ECDH 已经成为主流选择。TLS 1.3 默认使用基于椭圆曲线的密钥交换（如 X25519 或 P-256），有限域 DH 的使用场景已显著缩小。本系列的下一篇文章将深入探讨椭圆曲线密码学的数学基础和安全分析。

有限域 DH 与 ECDH 参数对照

以下表格并排对比了主流有限域 DH 群与椭圆曲线 DH 方案的关键参数：

笔者认为，从有限域 DH 迁移到 ECDH 的意义远不止效率提升。从安全架构的角度看，这一迁移消除了一整类攻击面——小子群攻击。在有限域 DH 中，\(\mathbb{Z}_p^*\) 的阶 \(p-1\) 可能包含多个小素因子，如果参数选择不当或群元素验证被遗漏，攻击者可以利用小阶子群逐步提取私钥信息（如本文第六节所述）。这种攻击的防御依赖于正确选择安全素数并严格执行子群验证——而历史反复证明，“依赖实现者不犯错”是最脆弱的安全策略。相比之下，X25519 的设计在协议层面就消除了这一问题：余因子为 8 的 Curve25519 通过余因子清除（cofactor clearing）使得任何 32 字节输入都是合法的公钥，实现者根本没有机会忽略群元素验证——因为不需要验证。这正是”让正确的实现成为最简单的实现”这一密码学工程原则的典范。

一个经常被忽视的观点是，Diffie-Hellman 论文（1976）的意义远不止于一个具体的密钥交换协议——它是一场智识上的革命。在此之前，密码学的基本公理是”安全通信需要预先共享秘密”，这被所有密码学家视为不言自明的前提。Diffie 和 Hellman证明了两个从未接触的人可以在完全公开的信道上建立共享秘密，这在当时的密码学界看来几乎等同于数学上的不可能。这种”推翻基本公理”的思维方式——不是在既有框架内优化，而是质疑框架本身的前提——正是 Diffie-Hellman 论文被冠以”New Directions”这一标题的深层原因。对于今天的研究者而言，这提供了一个永恒的启示：密码学中最深刻的突破，往往不是来自更巧妙的算法，而是来自对”什么是不可能的”这一问题的重新审视。

从工程实践来看，Logjam 攻击最深层的教训不在于弱参数本身——512 位 DH 不安全在 2015 年早已是常识——而在于预计算表的摊销效应。指数计算法中最昂贵的步骤（关系收集和线性代数求解）只取决于群参数 \((p, g)\)，与具体的 DH 公钥无关。这意味着，如果十万台服务器共享同一组 1024 位 DH 参数，攻击者对这组参数的一次预计算投资（可能耗资数亿美元）就可以摊销到十万次破解中，每次破解的边际成本降到分钟级。这将一个”每次连接”的攻击转变为一种”投资一次、收割全部”的大规模监控能力——而这恰恰是情报机构的威胁模型。Logjam 论文的作者甚至推测，这可能就是 Snowden 文档中提到的 NSA 大规模解密 VPN 流量能力的技术基础。对于系统架构师而言，这里的教训远超密码学：任何被广泛共享的安全参数——无论是 DH 群、证书、还是密钥——都隐含着一种摊销经济学，攻击者投资的回报率与共享该参数的系统数量成正比。

然而，有限域 DH 的学习价值不可替代。它的数学结构更为直观，安全分析的技术（CDH、DDH、指数计算法等）在概念上更容易理解，且许多椭圆曲线密码学的安全证明都是对有限域 DH 中相应证明的直接推广。理解有限域 DH 是深入学习现代公钥密码学的坚实基础。

密码学百科系列 · 第 16 篇

← 上一篇：RSA | 系列目录 | 下一篇：椭圆曲线密码学 →