Diffie–Hellman 与离散对数：为什么要用素数阶子群

一句话版本

两个陌生人在公开信道上各自出一个秘密指数 $a, b$ ，交换 $g^a$ 和 $g^b$ ，就能算出只有彼此知道的共同密钥 $g^{ab}$ 。偷听者要算出它，基本上得先解离散对数：已知 $g^a$ 求 $a$ 。但如果群的阶只有小素因子，Pohlig–Hellman 算法会用中国剩余定理把问题拆成许多小问题逐个击破。所以必须在大素数阶的子群里做。

全文分三层：

通俗理解：混颜料
实际用处：TLS、Signal、VPN，以及 Logjam 攻击
数学原理：循环群、离散对数、Pohlig–Hellman、小步大步，附手算例子

第一层：通俗理解

1.1 混颜料

Alice 和 Bob 想在一个所有人都能偷听的房间里约定一个秘密颜色：

两人公开约定一种公共颜色：黄色；
Alice 偷偷选红色，Bob 偷偷选蓝色；
各自把秘密色混进黄色：Alice 公开"黄+红"（橙），Bob 公开"黄+蓝"（绿）；
Alice 拿到绿，再混进自己的红：黄+蓝+红；Bob 拿到橙，再混进自己的蓝：黄+红+蓝；
两人得到同一种棕色。

偷听者看到了黄、橙、绿，但混好的颜料分不开，所以算不出棕色。

比喻	数学
公共颜色	公开的群和生成元 $g$
秘密颜色	私钥 $a$ 、 $b$
混颜料	求幂 $g^a$
颜料分不开	离散对数难解
共同的棕色	共享密钥 $g^{ab}$

1.2 1976 年的革命

在此之前，两个人要加密通信，必须事先见面交换密钥（外交信使、密码本）。Diffie 和 Hellman 在 1976 年的论文《密码学的新方向》里第一次公开说明：陌生人可以在公开信道上凭空商定密钥。这是公钥密码学的起点，两人因此获得 2015 年图灵奖。（后来解密的档案显示，英国 GCHQ 的 Malcolm Williamson 在几年前已经秘密发现了同样的方法。）

第二层：实际用处

HTTPS（TLS 1.3）：每次握手都用 ECDHE（椭圆曲线上的 DH）临时生成密钥。
前向保密：每次会话用一次性的 $a, b$ ，用完就扔。即使服务器的长期私钥日后泄露，过去的通话记录也解不开。TLS 1.3 强制要求这一点。
Signal 协议：X3DH 握手加"双棘轮"，几乎每条消息都在做新的 DH，密钥不断更新。
VPN（IPsec、WireGuard）、SSH：都用 DH 或 ECDH 协商会话密钥。

Logjam 攻击（2015）

两个问题凑到了一起：

很多服务器仍支持 90 年代美国出口管制留下的 512 位"出口级"DH，攻击者可以诱导连接降级到它；
大量服务器共用同一个素数 $p$ 。离散对数的数域筛法中，最耗时的预计算只取决于 $p$ 。对一个 512 位的 $p$ 预计算一周之后，破解每个连接只要一两分钟。

研究者还估算，国家级机构有能力对几个最常用的 1024 位素数做同样的预计算。从此 1024 位 DH 被淘汰，主流转向 2048 位以上或椭圆曲线。

中间人攻击

纯 DH 不验证对方身份。攻击者可以分别和 Alice、Bob 各做一次 DH，在中间转发并偷看。所以实际协议一定会配合签名或证书（RSA、ECDSA、Ed25519）来确认"跟我握手的确实是对方"。

第三层：数学原理

3.1 协议

公开参数：素数 $p$ ，和 $\mathbb{Z}_p^\times$ 中的元素 $g$ 。

Alice	公开信道	Bob
选秘密 $a$		选秘密 $b$
算 $A = g^a$	$A \to$ $\leftarrow B$	算 $B = g^b$
算 $B^a = g^{ab}$		算 $A^b = g^{ab}$

正确性只用到指数律 $(g^b)^a = (g^a)^b$ 。

3.2 离散对数为什么难

$\mathbb{Z}_p^\times$ 是 $p-1$ 阶循环群（这是有限域乘法群的一般定理）。取生成元 $g$ ，映射

$\mathbb{Z}_{p-1} \to \mathbb{Z}_p^\times,\qquad x \mapsto g^x$

是群同构：左边加法对应右边乘法。正方向用快速幂只要 $O(\log p)$ 次乘法；反方向就是离散对数，没有已知的多项式时间经典算法。

算法	适用于	大致代价
暴力枚举	任何群	$O(n)$
小步大步、Pollard rho	任何群（"通用算法"）	$O(\sqrt{n})$
Pohlig–Hellman	群的阶 $n$ 有小素因子	$O(\sqrt{q})$ ， $q$ 是 $n$ 的最大素因子
指标演算、数域筛	$\mathbb{Z}_p^\times$ （利用整数可分解）	亚指数

椭圆曲线群没有好用的"分解"概念，指标演算类算法不适用，只剩 $O(\sqrt{n})$ 的通用算法。这就是 ECC 密钥能短得多的原因。

3.3 Pohlig–Hellman：为什么要素数阶

假设群的阶 $n = q_1 q_2 \cdots$ 。要解 $g^x = h$ ：

对每个素因子 $q_i$ ，把两边同时取 $n/q_i$ 次方： $(g^{n/q_i})^x = h^{n/q_i}$ 。左边的底数阶只有 $q_i$ ，所以这只是一个 $q_i$ 阶的小离散对数问题，解出 $x \bmod q_i$ ；
用 中国剩余定理 把所有 $x \bmod q_i$ 拼成 $x \bmod n$ 。

代价由最大的素因子决定。所以 $p - 1$ 如果是很多小素数的乘积，离散对数就很容易。对策是选安全素数 $p = 2q + 1$ （ $q$ 也是素数），并且在 $q$ 阶子群里做。

用抽象代数的语言说，这就是 $\mathbb{Z}_n \cong \mathbb{Z}_{q_1} \times \mathbb{Z}_{q_2} \times \cdots$ （ $q_i$ 两两互素时）这个同构的直接应用：大循环群拆成小循环群的直积，难题也被拆碎了。

3.4 手算例子

一次 DH 握手

$p = 23$ ， $g = 5$ （ $\mathbb{Z}_{23}^\times$ 的生成元）。

Alice 选 $a = 6$ ： $A = 5^6 \bmod 23 = 8$
Bob 选 $b = 15$ ： $B = 5^{15} \bmod 23 = 19$
Alice 算 $19^6 \bmod 23 = 2$ ；Bob 算 $8^{15} \bmod 23 = 2$

共享密钥是 $2$ 。（已用 Python 验算。）

Pohlig–Hellman 破解 Alice 的私钥

偷听者知道 $g = 5$ 、 $A = 8$ ，要解 $5^x \equiv 8 \pmod{23}$ 。群的阶 $22 = 2 \times 11$ 。

求 $x \bmod 2$ ：两边取 $11$ 次方。 $5^{11} \equiv 22 \equiv -1$ ， $8^{11} \equiv 1$ 。所以 $(-1)^x = 1$ ， $x$ 是偶数， $x \equiv 0 \pmod 2$ 。

求 $x \bmod 11$ ：两边取 $2$ 次方。 $5^2 = 25 \equiv 2$ ， $8^2 = 64 \equiv 18$ 。要解 $2^y \equiv 18$ ，只需试 $11$ 个值： $2^6 = 64 \equiv 18$ ，所以 $x \equiv 6 \pmod{11}$ 。

CRT 拼起来： $x \equiv 0 \pmod 2$ ， $x \equiv 6 \pmod{11}$ ，得 $x = 6$ 。

原本要试 $22$ 个值，现在只试了 $2 + 11$ 个。规模大时差别是指数级的。（已用 Python 验算。）

3.5 小步大步法（baby-step giant-step）

即使阶是大素数 $n$ ，也能用"空间换时间"做到 $O(\sqrt{n})$ ：令 $m = \lceil \sqrt{n} \rceil$ ，把 $x$ 写成 $x = im + j$ 。

小步：存下 $g^0, g^1, \dots, g^{m-1}$ 这张表；
大步：依次算 $h \cdot g^{-m}, h \cdot g^{-2m}, \dots$ ，每算一个就查表，撞上时 $h g^{-im} = g^j$ ，得 $x = im + j$ 。

这就是为什么 256 位的群只提供 128 位安全： $\sqrt{2^{256}} = 2^{128}$ 。

总结

层次	要点
直觉	颜料混起来容易，分开很难
代数	$x \mapsto g^x$ 是循环群同构，反方向就是离散对数
安全	阶的小素因子会被 Pohlig–Hellman + CRT 拆掉；通用算法也有 $\sqrt{n}$
工程	用安全素数或椭圆曲线；配合签名防中间人；临时密钥保证前向保密