密码学数学基础 笔记 9：从离散对数与 Diffie–Hellman 问题出发，理解密钥交换和 ElGamal 加密，再推导 BSGS、Pollard rho、Pohlig–Hellman 与指标演算法

离散对数与密码学应用

上一篇用阶刻画模幂的周期，用原根生成全部可逆剩余类，并用指标把乘法转换成指数的加法。现在把计算方向反过来：知道底数 $g$ 和结果 $h=g^x$，如何求指数 $x$？

这个问题就是离散对数问题。它既能用于构造密码协议，也能把前面学过的线性同余、CRT 和素因数分解重新串起来，形成求解离散对数的算法

离散对数与 Diffie–Hellman 问题

设 $G=\langle g\rangle$ 是一个 $N$ 阶有限循环群，采用乘法记号。给定 $h\in G$，求

$$\boxed{g^x=h,\qquad0\leq x<N}$$

称为离散对数问题（DLP），记 $x=\log_g h$。讲义把一般循环群上的版本记作 GDLP，本文统一用 DLP

若 $G=\mathbb F_p^*$ 且 $g$ 是模 $p$ 的原根，那么 $N=p-1$。若 $g$ 只生成其中一个子群，则 $N=\operatorname{ord}_p(g)$，所有指数按 $N$ 取模

给定 $x$，重复平方只需 $O(\log N)$ 次群运算就能计算 $g^x$。反方向的困难程度则取决于群的阶与元素的表示方式。离散对数虽然满足对数法则，却没有实数对数的单调性，不能通过比较 $g^x$ 与 $h$ 的大小来二分搜索

三种不同的任务

在同一个循环群中，需要区分：

讲义中的 DHP 对应这里的 CDH。若能求离散对数，就能从 $g^a$ 恢复 $a$，再计算 $(g^b)^a$；若能计算 CDH，就能将结果与 $T$ 比较，完成 DDH 判定。因此，按“能用右侧算法求解左侧问题”的方向写，

$$\boxed{\mathrm{DDH}\leq_P\mathrm{CDH}\leq_P\mathrm{DLP}}$$

这些归约不能直接反向使用。特别是，“离散对数难”并不足以单独证明一个加密方案不会泄露明文信息

Diffie–Hellman 密钥交换

先取素数 $p$，并在 $\mathbb F_p^*$ 中选择一个大素数阶子群 $G=\langle g\rangle$，记 $|G|=q$。公开参数为 $p,q,g$

Alice 随机选择秘密指数 $a\in\{1,\ldots,q-1\}$，Bob 独立随机选择 $b\in\{1,\ldots,q-1\}$。二人执行：

正确性只依赖指数法则：

$$\boxed{B^a=(g^b)^a=g^{ab}=(g^a)^b=A^b}$$

被动窃听者看到 $p,q,g,A,B$，若要直接恢复 $S$，面对的正是 CDH 问题。实际协议再把共享值和会话信息送入密钥派生函数，得到后续对称加密使用的密钥

一个小例子

取 $p=23$、$q=11$、$g=2$，有 $\operatorname{ord}_{23}(2)=11$。Alice 取 $a=6$，Bob 取 $b=7$，则

$$A=2^6\bmod23=18,\qquad B=2^7\bmod23=13$$

两人分别算得

$$13^6\equiv18^7\equiv6\pmod{23}$$

因此共享值为 $6$。这些小参数只用于展示计算，后面介绍的算法可以轻易求出秘密指数

身份认证为什么仍然必要

上述等式保证双方在接收到真实公开值时得到同一个结果，但公开值本身没有绑定身份。主动攻击者可以截获 $A,B$，分别替换成自己的公开值，从而与 Alice、Bob 各建立一份共享秘密，再转发双方消息

因此完整协议还需要认证交换内容，例如用签名和证书绑定身份与会话，并验证收到的元素确实属于预期子群。这里只完成了密钥交换的数学构造

ElGamal 公钥加密

Diffie–Hellman 让双方协商共享值。ElGamal 则将这个共享值用作掩码，使发送方能够加密指定消息

仍在 $q$ 阶子群 $G=\langle g\rangle$ 中工作。Alice 选择私钥 $a$，发布公钥

$$A=g^a$$

Bob 要发送群元素 $m\in G$，为每次加密独立选择新的随机指数 $k\in\{1,\ldots,q-1\}$，计算

$$\boxed{c_1=g^k,\qquad c_2=mA^k}$$

密文为 $(c_1,c_2)$。本文的群运算都可实现为模 $p$ 乘法

Alice 收到后，计算

$$\boxed{m=c_2(c_1^a)^{-1}}$$

因为 $c_1^a=g^{ak}=A^k$，所以

$$c_2(c_1^a)^{-1}=m\,g^{ak}(g^{ak})^{-1}=m$$

接着前面的参数计算

继续取 $p=23$、$g=2$、$a=6$、$A=18$。Bob 发送 $m=8\in G$，取 $k=7$，得到

$$c_1=13,\qquad A^k\equiv6\pmod{23},\qquad c_2\equiv8\cdot6\equiv2\pmod{23}$$

Alice 算出 $c_1^a\equiv6$，而 $6^{-1}\equiv4\pmod{23}$，于是

$$m\equiv2\cdot4\equiv8\pmod{23}$$

一个群元素的明文对应两个群元素的密文，因此按相同编码长度计，密文约膨胀为两倍。任意文本还需要编码或结合混合加密，不能直接把任意整数都当作子群中的消息

恢复明文与 CDH 的联系

已知 $A=g^a$ 和 $c_1=g^k$，若能解决 CDH，就能得到 $g^{ak}$ 并消去掩码，因此 CDH 算法可以解密 ElGamal

反过来，假设有一个能对任意公钥、任意有效密文恢复明文的算法。给定 CDH 挑战 $A=g^a$、$B=g^b$，把 $A$ 当作公钥，把

$$(c_1,c_2)=(B,1)$$

交给该算法。它恢复出的明文是 $m=(g^{ab})^{-1}$，取逆元就得到 $g^{ab}$。这是讲义中“解密与 Diffie–Hellman 的联系”的具体归约

这里讨论的是完整恢复明文。若要证明密文连部分消息信息也不泄露，需要更强的判定型假设：在 $G$ 中 DDH 困难时，$g^{ak}$ 对观察者表现为随机掩码，从而得到 ElGamal 的选择明文安全性，相关论证见 Boneh 对 DDH 的讨论

这个区别也能与上一篇的二次剩余联系起来。若在整个 $\mathbb F_p^*$ 中取原根 $g$，则 $g$ 是二次非剩余，因而

$$\left(\frac{g^a}{p}\right)=(-1)^a$$

公开值的 Legendre 符号会暴露指数的奇偶性，进而确定掩码 $g^{ak}$ 的 Legendre 符号，并从 $c_2=m g^{ak}$ 推出 $m$ 的 Legendre 符号。因此整个乘法群上的离散对数困难，并不能保证上述加密具有语义安全性，这也是选择合适子群的原因之一

随机指数与密文的代数结构

若两个消息复用了同一个 $k$，就复用了同一个掩码，导致

$$\frac{c_2}{c_2'}=\frac{m}{m'}$$

知道其中一个明文即可求出另一个。因此每次加密都需要新的随机指数

此外，任意 $t\in G$ 都可以把密文变为 $(c_1,tc_2)$，使解密结果变成 $tm$。这种乘法结构可以用于同态计算，也说明基础 ElGamal 可被修改，不能直接满足选择密文安全性

求离散对数：先区分三类算法

下面统一考虑 $G=\langle g\rangle$、$|G|=N$、$h=g^x$：

• 通用算法：只使用群运算与元素比较，包括穷举、BSGS 和 Pollard rho
• 利用群阶分解的算法：Pohlig–Hellman 将问题分解到素数阶子群
• 利用元素表示的算法：指标演算法在有限域中寻找光滑数关系

这些算法的差异在于使用了哪些额外结构。下面的复杂度主要按群运算次数计；若要得到比特复杂度，还要计入每次群运算和查表的成本

穷举与 Baby-step Giant-step

穷举搜索

依次计算 $1,g,g^2,\ldots$，直到遇到 $h$。每次只需把上一次结果乘以 $g$，因此最多需要 $O(N)$ 次群运算，保存常数个群元素即可

但输入长度约为 $\log N$，所以 $O(N)$ 对输入长度而言是指数级，而非多项式级

把一个指数拆成两部分

取 $n=\lceil\sqrt N\rceil$，把未知数写成

$$x=in+j,\qquad0\leq i,j<n$$

于是

$$g^x=h\quad\Longleftrightarrow\quad g^j=hg^{-in}$$

这给出 Baby-step Giant-step（BSGS，小步大步）算法：

1. 存储 $g^j$ 与对应的 $j$，其中 $0\leq j<n$
2. 从 $h$ 出发，反复乘以 $g^{-n}$，计算 $hg^{-in}$
3. 若查到 $hg^{-in}=g^j$，则输出 $x\equiv in+j\pmod N$

因为每个 $0\leq x<N$ 都有这样的分解，两组值一定存在交点。用哈希表查找，在通常的期望常数时间查表模型下，算法需要 $O(\sqrt N)$ 次群运算和 $O(\sqrt N)$ 个表项；若用排序与二分查找，比较成本会带来额外的对数因子

一个 BSGS 例子

求 $2^x\equiv13\pmod{23}$。在 $G=\langle2\rangle$ 中 $N=11$，取 $n=4$。小步表为

$$\begin{array}{c|rrrr} j&0&1&2&3\\\hline g^j&1&2&4&8 \end{array}$$

$2^4\equiv16$，而 $16^{-1}\equiv13\pmod{23}$。大步先得到 $13$，再得到

$$13\cdot2^{-4}\equiv13\cdot13\equiv8\pmod{23}$$

它与小步 $g^3$ 相同，所以 $i=1,j=3$，得到

$$\boxed{x=1\cdot4+3=7}$$

BSGS 用存储空间把线性搜索降到了平方根规模

Pollard rho：少存储的碰撞搜索

Pollard rho 同样通过碰撞恢复指数，但不存储整张表。核心是维护形如

$$X_i=g^{\alpha_i}h^{\beta_i}$$

的迭代序列，并同步记录已知的 $\alpha_i,\beta_i\pmod N$

怎样保持指数可追踪

将群元素按某个确定规则分成三类，分别执行乘以 $g$、平方或乘以 $h$。每一步的更新为

分类必须只由当前群元素决定，这样相同元素之后会沿着相同路径前进。初始化可随机选择 $\alpha_0,\beta_0$，并计算 $X_0=g^{\alpha_0}h^{\beta_0}$

碰撞给出线性同余

如果某次遇到

$$g^{\alpha_i}h^{\beta_i}=g^{\alpha_j}h^{\beta_j}$$

代入 $h=g^x$，就得到

$$\boxed{(\beta_j-\beta_i)x\equiv\alpha_i-\alpha_j\pmod N}$$

若系数与 $N$ 互素，直接求逆元恢复 $x$。若最大公因数为 $d>1$，按线性同余方程的方法求出 $d$ 个候选，再代入 $g^x=h$ 验证；若碰撞只给出 $0\equiv0$，或候选太多，则更换随机游走重新开始

对于素数阶群，只要 $\beta_j\not\equiv\beta_i\pmod N$，系数就可逆，这使碰撞恢复尤其方便

为什么叫 rho

有限集合上的确定迭代最终进入循环，路径由一段尾巴和一个环组成，形状类似希腊字母 $\rho$。使用 Floyd 判圈法，只保存两个状态：一个每轮前进一步，另一个前进两步，直到二者相遇

若迭代具有随机映射式的混合行为，生日碰撞估计给出约 $O(\sqrt N)$ 的期望时间，Floyd 实现只保存常数个群元素与指数。这个时间估计依赖随机游走模型，任意选取的分段函数都不能自动保证同样的效果

Pohlig–Hellman：分解指数所在的模数

即使模数 $p$ 是素数，指数也生活在模 $N$ 的空间里。当 $g$ 是原根时，$N=p-1$ 通常可以继续分解

假设已知

$$N=\prod_{i=1}^t q_i^{e_i}$$

其中 $q_i$ 是不同素数。Pohlig–Hellman 的目标是先求 $x\pmod{q_i^{e_i}}$，再用 CRT 拼回 $x\pmod N$

投影到素数幂阶子群

令

$$g_i=g^{N/q_i^{e_i}},\qquad h_i=h^{N/q_i^{e_i}}$$

根据幂的阶公式，$g_i$ 的阶恰为 $q_i^{e_i}$，且

$$g_i^x=h_i$$

在这个子群求出离散对数 $y_i$ 后，就知道

$$x\equiv y_i\pmod{q_i^{e_i}}$$

各模数两两互素，CRT 唯一确定 $x\pmod N$。正确性也可以直接理解为：真实指数满足每个局部条件，因此重构出的指数必然与真实指数模 $N$ 同余

素数幂阶还可以逐位拆开

设某个局部问题为 $u^x=v$，其中 $u$ 的阶为 $q^e$。将 $x$ 写为 $q$ 进制展开

$$x=x_0+x_1q+\cdots+x_{e-1}q^{e-1},\qquad0\leq x_j<q$$

记 $\gamma=u^{q^{e-1}}$，它的阶为 $q$。先将等式两边提升到 $q^{e-1}$ 次幂，得到

$$\gamma^{x_0}=v^{q^{e-1}}$$

高位贡献都变成了单位元，留下一个阶为 $q$ 的离散对数问题

假设已经求出前 $j$ 位，并记 $s_j=\sum_{k=0}^{j-1}x_kq^k$，则消去这些低位再乘幂：

$$\boxed{\gamma^{x_j}=(vu^{-s_j})^{q^{e-1-j}}}$$

右边等于 $u^{(x-s_j)q^{e-1-j}}$，其中比第 $j$ 位更高的项都含有 $q^e$，所以只留下 $\gamma^{x_j}$。重复 $e$ 次，就将一个阶为 $q^e$ 的问题化成 $e$ 个阶为 $q$ 的问题

若素数阶问题用平方根算法求解，整体群运算复杂度为

$$\boxed{O\!\left(\sum_{i=1}^t e_i(\log N+\sqrt{q_i})\right)}$$

这里假设群阶分解已知，CRT 的整数运算另计，标准算法与分析可参见 Handbook of Applied Cryptography 第 3 章

一个按群阶拆分的例子

求 $2^x\equiv37\pmod{61}$。上一篇已知 $2$ 的阶为 $60=4\cdot3\cdot5$，分别投影得到

以上均按 $61$ 取模，其中 $11^3\equiv50$、$9^4\equiv34$。CRT 合并为

$$\boxed{x\equiv39\pmod{60}}$$

代回验证 $2^{39}\equiv37\pmod{61}$，与目标一致

群阶的分解为什么影响安全性

Pohlig–Hellman 表明，$N$ 很大并不代表问题困难。如果 $N$ 的素因子都很小，即使某些素数出现很高次幂，也可以逐位求解

因此用于密码学的循环群通常选择大素数阶 $q$。例如取安全素数 $p=2q+1$，再使用阶为 $q$ 的子群，就避免了群阶被分解成许多小素数阶问题

但这只处理了群阶分解带来的攻击。在有限域中，还需要考虑利用元素表示的算法

指标演算法：寻找光滑数关系

BSGS、rho 与 Pohlig–Hellman 只要求能够执行群运算。指标演算法（index calculus）进一步使用有限域元素的整数代表元及其因数分解

以下取 $G=\mathbb F_p^*$，$g$ 是原根，故指数模数为 $p-1$。选择一个上界 $B<p$，将所有不超过 $B$ 的素数组成因子基

$$\mathcal B=\{\ell:\ell\leq B,\ \ell\text{ 为素数}\}$$

若一个正整数的全部素因子均不超过 $B$，称其为 $B$-光滑数。例如 $360=2^3\cdot3^2\cdot5$ 是 $5$-光滑数，而 $14=2\cdot7$ 不是

第一阶段：预计算因子基的对数

随机选择指数 $i$，计算 $g^i\bmod p$ 的最小正整数代表元。若它恰好是 $B$-光滑数，就得到

$$g^i\equiv\prod_{\ell\in\mathcal B}\ell^{u_\ell}\pmod p$$

两边取离散对数，转化为

$$\boxed{i\equiv\sum_{\ell\in\mathcal B}u_\ell\log_g\ell\pmod{p-1}}$$

未知量是各个因子基元素的对数。收集足够多有效关系，就能求解这些未知量

“关系足够多”要求它们提供足够独立的信息，不能只数方程条数。另外，$p-1$ 通常为合数，非零系数未必可逆，消元时不能无条件相除；可以分解指数模数，在局部模数下求解，再用 CRT 合并

第二阶段：把目标转到因子基

预计算完成后，给定目标 $h$，随机寻找 $k$，使 $hg^{-k}\bmod p$ 的整数代表元是光滑数：

$$hg^{-k}\equiv\prod_{\ell\in\mathcal B}\ell^{v_\ell}\pmod p$$

于是

$$\boxed{\log_g h\equiv k+\sum_{\ell\in\mathcal B}v_\ell\log_g\ell\pmod{p-1}}$$

右侧全部已知。恢复指数后，再计算 $g^x$ 验证。只要模数、底数和因子基相同，第一阶段的结果还可以复用于多个目标

讲义中的完整例子

取 $p=18443$、原根 $g=37$、因子基 $\{2,3,5\}$，求

$$37^x\equiv211\pmod{18443}$$

讲义收集了四条光滑关系：

$$\begin{aligned} 37^{12708}&\equiv2^3\cdot3^4\cdot5,\\ 37^{11311}&\equiv2^3\cdot5^2,\\ 37^{15400}&\equiv2^3\cdot3^3\cdot5,\\ 37^{2731}&\equiv2^3\cdot3\cdot5^4 \end{aligned} \pmod{18443}$$

记 $L_2=\log_{37}2$、$L_3=\log_{37}3$、$L_5=\log_{37}5$，转化为

$$\begin{aligned} 3L_2+4L_3+L_5&\equiv12708,\\ 3L_2+2L_5&\equiv11311,\\ 3L_2+3L_3+L_5&\equiv15400,\\ 3L_2+L_3+4L_5&\equiv2731 \end{aligned} \pmod{18442}$$

指数模数 $18442=2\cdot9221$，其中 $9221$ 是素数。在两个模数下分别求解，得到

$$\begin{aligned} (L_2,L_3,L_5)&\equiv(1,0,1)\pmod2,\\ (L_2,L_3,L_5)&\equiv(5733,6529,6277)\pmod{9221} \end{aligned}$$

CRT 合并为

$$(L_2,L_3,L_5)\equiv(5733,15750,6277)\pmod{18442}$$

现在寻找目标的光滑表示，得到

$$211\cdot37^{-9549}\equiv2^5\cdot3^2\cdot5^2\pmod{18443}$$

因此

$$\begin{aligned} x&\equiv9549+5L_2+2L_3+2L_5\\ &\equiv9549+5\cdot5733+2\cdot15750+2\cdot6277\\ &\equiv8500\pmod{18442} \end{aligned}$$

最终验证

$$\boxed{37^{8500}\equiv211\pmod{18443}}$$

这个例子将“模幂关系—线性同余—CRT—目标对数”完整连接了起来

光滑性带来的复杂度取舍

因子基越大，随机代表元越容易光滑，但未知对数也越多，线性代数阶段随之增大。指标演算法需要在收集关系和求解方程之间取得平衡

常用记号为

$$L_p[\alpha,c]=\exp\!\left((c+o(1))(\ln p)^\alpha(\ln\ln p)^{1-\alpha}\right)$$

讲义给出的基础指标演算估计处于 $L_p[1/2,c]$ 的次指数规模；数域筛思想在相应有限域中可进一步达到 $L_p[1/3,c]$ 类型的规模。这些估计依赖具体算法与光滑性启发式，不能理解成任意群上的统一复杂度

关键在于：光滑性是整数代表元的性质。任意循环群并不自动具有这样的因子分解结构，所以指标演算法不能仅凭群的阶就原样移植过去

如何比较这些算法

这些方法还可以组合：先用 Pohlig–Hellman 拆分群阶，再在局部子群中使用 BSGS 或 rho。评估参数时，也要同时考虑群阶和具体表示，而不能只看模数或指数有多少位

抽象同构为什么不等于计算一样困难

任何 $N$ 阶循环群都与加法群 $\mathbb Z/N\mathbb Z$ 同构：

$$\mathbb Z/N\mathbb Z\longrightarrow G,\qquad x\longmapsto g^x$$

离散对数要求计算这个映射的逆。但如果直接在加法群中工作，以生成元 $a$ 为底的“离散对数”只是在解

$$ax\equiv b\pmod N$$

因为 $a$ 是生成元，$\gcd(a,N)=1$，所以扩展欧几里得算法立即给出

$$x\equiv a^{-1}b\pmod N$$

两个群的抽象结构相同，并不意味着能高效计算任意给定表示之间的同构。密码学所使用的，正是特定表示下正向运算与反向求解之间的计算差异