覆盖经典 DH 与 ECDH 的数学原理、正确性证明、安全假设（DLP/CDH/DDH），以及主要离散对数攻击（Pohlig–Hellman、BSGS、Pollard ρ、Index Calculus / NFS-DL）之公式推导与复杂度评估。默认群记为 $G=\langle g\rangle$ 为循环群，阶为 $|G|=N$。
1. 群与离散对数问题（DLP）
- 设定：给定循环群 $(G,\cdot)$ 与生成元 $g\in G$。对任意 $y\in G$，若存在 $x\in\{0,\dots,N-1\}$ 使 $y=g^x$，称 $x=\log_g y$ 为 $y$ 关于 $g$ 的离散对数。
- 离散对数问题（DLP）：输入 $g,y$，求 $x$ 使 $g^x=y$。
- 计算 Diffie–Hellman（CDH）：输入 $g^a,g^b$，计算 $g^{ab}$。
- 判定 Diffie–Hellman（DDH）：判定三元组 $(g^a,g^b,g^c)$ 是否满足 $c\equiv ab\ (\bmod N)$。
典型安全层级：$\text{DLP}\Rightarrow \text{CDH}\Rightarrow \text{DDH}$（可由反设/归约说明），但一般不可反向。
2. 经典 Diffie–Hellman（DH）与正确性
2.1 协议定义（素域版本）
令 $p$ 为大素数，$G=\mathbb{Z}_p^\times$ 中选一阶为大素数 $q\mid (p-1)$ 的子群，$g$ 为其生成元。
- Alice 取随机 $a\xleftarrow{\$}{1,\dots,q-1}$，发送 $A=g^a\pmod p$。
- Bob 取随机 $b\xleftarrow{\$}{1,\dots,q-1}$，发送 $B=g^b\pmod p$。
双方计算共享密钥：
$$ K_A=B^a\equiv g^{ba}\equiv g^{ab}\pmod p,\qquad K_B=A^b\equiv g^{ab}\pmod p. $$
正确性证明：群运算交换律与幂的结合性即给出 $B^a=(g^b)^a=g^{ba}=g^{ab}=(g^a)^b=A^b$。
实用中对 $K=g^{ab}$ 进行密钥派生：$k=\operatorname{KDF}(\operatorname{enc}(K))$。
2.2 安全（基于 DDH 的不可区分性）
若 DDH 成立，则 $g^{ab}$ 在对手眼中与 $g^c$（随机 $c$）不可区分：
$$ \left|\Pr[\mathcal{D}(g^a,g^b,g^{ab})=1]-\Pr[\mathcal{D}(g^a,g^b,g^c)=1]\right|\le\varepsilon(\lambda), $$
从而 $k=\operatorname{KDF}(g^{ab})$ 近似均匀（在随机预言模型 / 合适的 KDF 假设下）。
MITM 警示：DH 本身不认证身份，需与签名/证书绑定（如 TLS 的 (EC)DHE）。
3. 椭圆曲线 Diffie–Hellman（ECDH）
令 $E/\mathbb{F}_p$ 为椭圆曲线，基点 $G\in E(\mathbb{F}_p)$ 的阶为素数 $n$，余因子 $h=\#E/n$ 很小（通常 $h\in\{1,2,4,8\}$）。
- Alice 取 $a\xleftarrow{\$}[1,n-1]$，发 $A=aG$。
- Bob 取 $b\xleftarrow{\$}[1,n-1]$，发 $B=bG$。
- 共享点：$S=aB=bA=abG$。共享密钥可取 $K=\operatorname{KDF}(\operatorname{enc}(x(S)))$。
正确性：来自群法则的结合律：$a(bG)=(ab)G=b(aG)$。
余因子清除（cofactor clearing）：若接收方仅验证点在曲线上而未验证阶，可取 $S'=h\cdot(aB)$ 以免小子群攻击；更好做法是验证对端公钥阶为 $n$。
4. 参数与实现要点
- 素域 DH：选 $p=2q+1$ 安全素数，$g$ 生成阶 $q$ 子群；指数 $a,b$ 从 $[1,q-1]$ 均匀取；验证对端 $A,B\in\langle g\rangle$。
- ECDH 曲线：选 $n$ 为大素数阶，如 NIST P-256、secp256k1、Curve25519（Montgomery 形式用 X25519）。
- 前向保密：使用临时密钥（DHE/ECDHE），每次会话独立 $a,b$。
- 边信道：指数/标量运算使用恒定时间算法（如 Montgomery ladder）。
5. 离散对数攻击与公式推导
5.1 Pohlig–Hellman（$N$ 可分解时）
设 $|G|=N=\prod_{i=1}^t p_i^{e_i}$。目标：解 $g^x=y$。令
$$ N_i=\frac{N}{p_i^{e_i}},\qquad g_i=g^{N_i},\quad y_i=y^{N_i}. $$
则 $\langle g_i\rangle$ 的阶为 $p_i^{e_i}$，问题化为在每个 $\langle g_i\rangle$ 中求 $x\bmod p_i^{e_i}$。写 $x$ 的 $p_i$-进展开
$$ x\equiv x_{i,0}+x_{i,1}p_i+\cdots+x_{i,e_i-1}p_i^{e_i-1}\ (\bmod\ p_i^{e_i}). $$
按位递推：令
$$ y_{i,0}=y_i,\qquad y_{i,j}=y_i\cdot g^{-\sum_{k=0}^{j-1}x_{i,k}p_i^{k}}\ (j\ge1), $$
两侧取 $(p_i^{e_i-j})$-次幂得
$$ (y_{i,j})^{p_i^{e_i-j-1}}=g_i^{x_{i,j} p_i^{e_i-j-1}}, $$
右侧仅剩一个 $p_i$-阶子群，故可枚举 $x_{i,j}\in\{0,\dots,p_i-1\}$ 解之。最后用 CRT 合并所有模 $p_i^{e_i}$ 的解得到 $x\pmod N$。
复杂度：$\tilde O\left(\sum_i e_i(p_i+\log N)\right)$（主因在小素数上极快），因此若 $N$ 含小素因子则 DLP 很弱。
5.2 Baby-Step Giant-Step（BSGS）
对素数阶 $N$ 的群，设 $m=\lceil\sqrt N\rceil$。将 $x$ 写作 $x=im+j$（$0\le i,j<m$）。有：
$$ g^{im}=y\cdot g^{-j}. $$
算法：
- 预计算并存表（baby steps）：$T[j]=g^j$（$0\le j<m$）。
- 计算 $\gamma=g^{-m}$，遍历 $i=0,1,\dots,m-1$（giant steps），寻找 $y\cdot\gamma^i\in T$。匹配到即得 $x=im+j$。
复杂度：时间、空间均为 $O(\sqrt N)$。
5.3 Pollard ρ for DLP（随机游走）
构造状态 $X_k=g^{a_k}y^{b_k}$ 的伪随机迭代：
$$ (a_{k+1},b_{k+1},X_{k+1})=F(a_k,b_k,X_k)\ (\bmod N), $$
例如将群划分为 3 类并定义
$$ F(X)=\begin{cases} (gX,\ a+1,\ b), & X\in S_1,\\ (X^2,\ 2a,\ 2b), & X\in S_2,\\ (yX,\ a,\ b+1), & X\in S_3. \end{cases} $$
当出现碰撞 $X_i=X_j$（$i\ne j$）时，有
$$ g^{a_i-a_j}=y^{b_j-b_i}=g^{x(b_j-b_i)}\Rightarrow x\equiv (a_i-a_j)(b_j-b_i)^{-1}\ (\bmod N). $$
期望步数 $\approx\sqrt{\pi N/2}$，空间 $O(1)$。实践中用 Floyd/Brent 判圈 或 distinguished points 并行化。
5.4 Index Calculus / NFS-DL（有限域上子指数）
在 $\mathbb{F}_p^\times$ 上：
- 选 因子基 $\mathcal{B}=\{\text{小素数}\}$。
采样随机 $a,b$，若 $g^a y^b$ 在 $\mathcal{B}$ 上"可分解"，得到关系
$$ a+b x\equiv \sum_{q\in\mathcal{B}} e_q\log_g(q)\ (\bmod p-1). $$
- 累积到线性独立方程后线性代数求出 $\log_g(q)$；最后做一次 个别离散对数 得 $x$。
复杂度为子指数级，常用 $L$-记号：
$$ L_Q[\alpha,c]=\exp\left((c+o(1))(\log Q)^{\alpha}(\log\log Q)^{1-\alpha}\right). $$
对 $\mathbb{F}_p$ 的最优算法（数域筛 NFS-DL）满足
$$ \text{复杂度}\approx L_p\left[\tfrac13,\left(\tfrac{64}{9}\right)^{1/3}\right]. $$
这解释了为何有限域 DH 需要比 ECC 更长的参数以达到同等安全级别。
5.5 椭圆曲线上 DLP（ECDLP）与特殊攻击
- 对一般曲线，最佳算法仍为 $\tilde O(\sqrt n)$ 的 Pollard ρ，因此 ECC 用更短密钥 达到同等安全。
- MOV/FR 攻击：将 ECDLP 嵌入到 $\mathbb{F}_{p^k}^\times$ 的 DLP，需避开小嵌入度 $k$ 的不安全曲线（如超奇异曲线）。
- 异常曲线/弱曲线：应使用标准安全曲线并验证参数。
5.6 小子群/同态泄露攻击（安全性工程）
若对端发来元素 $H$ 落在阶为 $r$ 的小子群，协商结果 $K=H^a$ 亦落在小子群；攻击者可用枚举恢复 $a\bmod r$，对多组不同 $r$ 结合 CRT 还原 $a$。
防护：
- 选素数阶子群（$q$ 为大素），并验证公钥阶；
- ECC 中进行阶验证或做 cofactor clearing（$S'=h\cdot S$）。
6. 例题与推导
例 1（DH 计算）
取 $p=23$, $g=5$。Alice: $a=6\Rightarrow A=5^6\equiv8$。Bob: $b=15\Rightarrow B=5^{15}\equiv19$。共享：
$$ K_A=B^a\equiv 19^6\equiv 2\ (\bmod 23),\quad K_B=A^b\equiv 8^{15}\equiv 2\ (\bmod 23). $$
例 2（Pohlig–Hellman 具体化）
设 $N=2^3\cdot5$，$g$ 为阶 $N$ 元，给定 $y=g^x$。对 $p=2$ 与 $p=5$ 分别求 $x\bmod 8$、$x\bmod 5$，再用 CRT 合并得 $x\bmod 40$。逐位求解时使用上节公式确定 $x_{j}$。
例 3（BSGS 推导）
令 $m=\lceil\sqrt N\rceil$，预计算 $g^j$ 并哈希到表。令 $\gamma=g^{-m}$。若存在 $i,j$ 使
$$ y\cdot\gamma^i=g^j\Rightarrow g^{im}=y\cdot g^{-j}, $$
则 $x=im+j$。不存在时继续增加 $i$ 直至匹配。
7. 复杂度与安全等效位强度（粗略对应）
- 有限域 DH（$\mathbb{F}_p^\times$）：以 NFS-DL 为主导，$p$ 需更大（如 $p$ 3072-bit ≈ ECC 256-bit）。
- ECC：依赖 Pollard ρ 的 $\tilde O(\sqrt n)$，256-bit 素数阶提供 $\approx 128$ 位安全。
8. 实现检查清单（工程）
- [ ] 选素数阶子群 / 验证对端公钥阶与合法性（on-curve、非无穷远点）。
- [ ] 使用临时密钥（(EC)DHE）获得前向保密；每会话新随机数。
- [ ] 指数/标量长度与均匀性：$a,b\xleftarrow{\$}[1,q-1]$。
- [ ] KDF：对 $g^{ab}$ 的编码输入 HKDF / KDF；关联协商上下文（抗反射/绑架）。
- [ ] 恒定时间实现与随机化防侧信道；必要时启用 blinding。
9. 公式速查（Cheat Sheet）
- $\text{CDH}:\ \text{given } g^a,g^b\ \Rightarrow\ g^{ab}.\quad \text{DDH}:\ \text{distinguish } (g^a,g^b,g^{ab}) \text{ vs } (g^a,g^b,g^c).$
Pohlig–Hellman：$x\bmod p^e$ 逐位公式
$$ (y\cdot g^{-\sum_{k=0}^{j-1}x_k p^k})^{N/p^j}=g^{x_j N/p}\ (0\le j<e). $$
- BSGS：$m=\lceil\sqrt N\rceil$，找 $i,j$ 使 $y g^{-im}=g^j\Rightarrow x=im+j$。
- Pollard ρ：碰撞给出 $x\equiv (a_i-a_j)(b_j-b_i)^{-1}\ (\bmod N)$。
- Index Calculus（$\mathbb{F}_p$）：关系 $a+b x\equiv\sum e_q\log_g q\ (\bmod p-1)$。