离散对数与困难问题 — DLP / CDH / DDH / BDH / 攻击算法

日期: 2026-11-03 方向: 密码学数学 阶段: Phase 4 - 密码学数学基础 (Day 181-194) 标签: #密码学 #DLP #CDH #DDH #Pollard #NFS

---

今日目标

---

一、动机

公钥密码安全 = 「某个群里某问题难」的假设。攻击者最强武器是 算法：

• 朴素穷举：$O(n)$
• 通用攻击：$O(\sqrt n)$（Pollard rho, BSGS）
• 群结构攻击：Pohlig-Hellman 约简到子群 DLP
• 特殊群攻击：index calculus / NFS（仅适用 $\mathbb{F}p^*$, $\mathbb{F}{2^n}^*$, ...）

理解这些算法 → 理解为什么 ECC 256-bit ≈ RSA 3072-bit。

---

二、问题层级

2.1 离散对数问题 (DLP)

定义：给定循环群 $G = \langle g \rangle$ 阶 $n$，给 $h \in G$，求 $x \in \mathbb{Z}/n\mathbb{Z}$ 使 $g^x = h$。

记 $x = \log_g h$。

2.2 计算 Diffie-Hellman (CDH)

定义：给 $g, g^a, g^b$，计算 $g^{ab}$。

关系：DLP 易 ⇒ CDH 易（先求 $a$ 再算 $g^a)^b$）。反向未证明（"CDH = DLP" 是开放问题）。

2.3 决策 Diffie-Hellman (DDH)

定义：区分 $(g, g^a, g^b, g^{ab})$ 和 $(g, g^a, g^b, g^c)$（$c$ 随机）。

关系：DDH 易 ⇒ CDH 易（？不一定）；CDH 易 ⇒ DDH 易（显然）。

强弱顺序：DDH ≤ CDH ≤ DLP（左易者右也易）。

2.4 Bilinear DH (BDH)

定义 (Type III pairing $e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$)：给 $g_1, g_1^a, g_1^b, g_2, g_2^a, g_2^b$，计算 $e(g_1, g_2)^{abc}$（其中 $c$ 也给）。

变种：

• co-CDH: 给 $g_1^a, g_2$，求 $g_2^a$
• SXDH: DDH 在 $\mathbb{G}_1$ 和 $\mathbb{G}_2$ 都难（最强可用假设）
• q-Strong DH: 给 $g, g^a, g^{a^2}, \dots, g^{a^q}$，求 $(c, g^{1/(a+c)})$（KZG / BLS short sig 需要）

2.5 RSA 假设

定义：给 $N = pq$（$p, q$ 大素数）, $e$, $y = x^e \mod N$，求 $x$。

关系：因子分解易 ⇒ RSA 易（求 $\varphi(N)$ 后 $d = e^{-1}$）。反向未证。

---

三、攻击算法

3.1 朴素穷举：$O(n)$

枚举 $i$ 算 $g^i$ 比较 $h$。$n = 2^{256}$ 时不可行。

3.2 Baby-Step Giant-Step (BSGS)

算法 (Shanks 1971)：

1. $m = \lceil \sqrt n \rceil$
2. Baby: 表 ${(g^j, j) : j = 0, \dots, m-1}$
3. Giant: 计算 $h \cdot g^{-im}$ for $i = 0, 1, \dots, m-1$，查表
4. 命中 $j = $ baby index，$i = $ giant index → $x = i \cdot m + j$

复杂度：时间 $O(\sqrt n)$，空间 $O(\sqrt n)$。

3.3 Pollard's Rho

算法 (Pollard 1978)：

1. 定义随机函数 $f: G \to G$（用三分法）
2. 找 $f$ 的循环：$x_i = x_{2i}$（Floyd / Brent 检测）
3. 推 $x = \log h$

复杂度：时间 $O(\sqrt n)$，空间 $O(1)$。实际首选攻击通用群。

并行 Pollard rho（van Oorschot-Wiener）可 $O(\sqrt n / k)$ 时间用 $k$ 处理器。

3.4 Pohlig-Hellman

思想：若 $n = \prod p_i^{e_i}$，DLP in $G$ 约简到 DLP in $p_i$ 子群（CRT 合并）。

复杂度：$O(\sum e_i \sqrt{p_i})$。

含义：群阶必须有大素因子！若 $n$ 全是小素因子组合，密码瞬间破。 → secp256k1 选 $n$ 是大素数本身（$h=1$）。

3.5 Index Calculus（仅特殊群）

适用：$\mathbb{F}_p^*$ 和某些群（需"smooth" 元素和"factor base"）。

思想：

1. 选小素数 factor base ${p_1, \dots, p_k}$
2. 找许多 $g^a \mod p$ 是 smooth（只用 base 因子）
3. 取对数得线性方程组
4. 解出每个 $\log p_i$
5. 任意目标 $h$ 凑成 smooth $h \cdot g^r$ 即可

复杂度：$L_p(1/2)$（亚指数）。

关键事实：在 EC 群上不存在 index calculus（无 factor base 概念）。所以 ECDLP 仍是 $O(\sqrt n)$。

3.6 数域筛 NFS（最强 $\mathbb{F}_p$ 攻击）

复杂度 (GNFS)： $$L_p\left(\frac{1}{3}, \sqrt[3]{\frac{64}{9}}\right) = \exp\left(c (\log p)^{1/3} (\log\log p)^{2/3}\right)$$

实际安全：

• $\log p = 1024$：约 80-bit 安全（已破，2009 RSA-768）
• $\log p = 2048$：约 112-bit 安全
• $\log p = 3072$：约 128-bit 安全

Tower NFS / extended NFS 攻击 $\mathbb{F}_{p^k}^*$（Kim-Barbulescu 2016），让 BN254 跌出 128-bit。

3.7 量子攻击 — Shor 算法

Shor (1994)：量子计算机多项式时间解 DLP 和因子分解。

含义：未来量子机器一旦达 ~10000 logical qubit，所有 ECC + RSA 都被破。后量子密码 (PQC) 必须基于格、哈希、码、多变量等"非 DLP/IF" 困难问题。

---

四、ECDLP 安全性分析（secp256k1 例）

4.1 通用攻击

群阶 $n \approx 2^{256}$。

• BSGS: $2^{128}$ 时间 + $2^{128}$ 空间（空间不可行）
• Pollard rho: $2^{128}$ 时间 + $O(1)$ 空间。目前最强通用攻击。

并行 rho 用 $2^{40}$ 机器：$2^{88}$ 步骤 / 机器，仍需 $\sim 10^{19}$ 年。

4.2 群结构攻击

$n$ 是 256-bit 大素数 ⇒ Pohlig-Hellman 不适用（无小子群）。

4.3 特殊曲线攻击

• MOV reduction: 嵌入度 $k$ 太小（$\le 6$）的曲线被打到 $\mathbb{F}_{p^k}^*$ 用 NFS。secp256k1 嵌入度 ~$2^{255}$，免疫。
• Anomalous curve: $#E(\mathbb{F}_p) = p$ 的曲线被 Smart 攻击多项式破。secp256k1 $#E \ne p$。
• GHS / Weil descent: 二进制曲线某些参数被打。secp256k1 在素域，不适用。

4.4 实现攻击（侧信道）

• 时序、缓存、功率、EM
• 防御：恒定时间 Montgomery ladder、scalar blinding、加法链 unification

---

五、代码：BSGS 与 Pollard Rho

"""
Day 186: DLP 攻击算法实现 (小群验证)
"""
from collections import defaultdict


def bsgs(g: int, h: int, p: int, n: int) -> int:
    """
    Baby-Step Giant-Step 解 g^x = h mod p, x ∈ [0, n)
    时间 O(√n), 空间 O(√n)
    """
    m = int(n ** 0.5) + 1

    # baby steps: 表 g^j -> j
    table = {}
    cur = 1
    for j in range(m):
        if cur not in table:  # 取最小 j
            table[cur] = j
        cur = (cur * g) % p

    # giant steps: 计算 h * (g^(-m))^i
    g_inv_m = pow(g, -m, p)
    cur = h
    for i in range(m):
        if cur in table:
            return i * m + table[cur]
        cur = (cur * g_inv_m) % p
    raise ValueError("DLP not found")


def pollard_rho(g: int, h: int, p: int, n: int) -> int:
    """
    Pollard Rho DLP, 时间 O(√n), 空间 O(1)
    解 g^x = h mod p, x ∈ [0, n)
    """
    def f(x, a, b):
        s = x % 3
        if s == 0:   return (x * x) % p, (2*a) % n, (2*b) % n
        elif s == 1: return (x * g) % p, (a + 1) % n, b
        else:        return (x * h) % p, a, (b + 1) % n

    x, a, b = 1, 0, 0
    X, A, B = 1, 0, 0  # 兔子 (跑两倍快)

    for i in range(1, n):
        x, a, b = f(x, a, b)
        X, A, B = f(*f(X, A, B))
        if x == X:
            # x = g^a h^b, X = g^A h^B → g^(a-A) = h^(B-b)
            r = (B - b) % n
            if r == 0:
                raise ValueError("retry with different f")
            r_inv = pow(r, -1, n)
            return ((a - A) * r_inv) % n
    raise ValueError("rho failed")


# ============ 演示 ============
if __name__ == "__main__":
    # 小群: F_607, g=2 (607 是素数, ord(2)=303)
    p, g = 607, 2
    n = 303  # ord(g) - 实际 (Z/607Z)* 阶 = 606, 但 g=2 阶 303

    # 实际算: 用整个 (Z/p)* 阶 p-1
    n = p - 1

    # 选秘密 x = 100
    x_true = 100
    h = pow(g, x_true, p)
    print(f"已知: g={g}, h={h}, p={p}, 求 x")

    x_bsgs = bsgs(g, h, p, n)
    print(f"BSGS 解出 x = {x_bsgs}, g^x mod p = {pow(g, x_bsgs, p)}")

    x_rho = pollard_rho(g, h, p, n)
    print(f"Rho 解出 x = {x_rho}, g^x mod p = {pow(g, x_rho, p)}")

    # 大群: 256-bit 时, BSGS 需 2^128 内存 (不可行)
    # Rho 需 2^128 时间 (单机不可行)
    print(f"\n256-bit 群 (secp256k1): Pollard rho 需 ~2^128 ≈ 3.4e38 操作")
    print(f"  按 10^9 ops/sec, 单机需 ~10^22 年; 银河级算力 ~10^12 年")

输出：

已知: g=2, h=405, p=607, 求 x
BSGS 解出 x = 100, g^x mod p = 405
Rho 解出 x = 100, g^x mod p = 405

---

六、密码学应用关联

---

七、真实参数与安全级别

等价安全表（NIST SP 800-57）

已破的 DLP

EC 上 ECDLP 已破（专为破解设计的曲线）

---

八、常见陷阱

1. 小子群攻击假设忽视：DLP 假设强调"$n$ 大且素"。若群结构有小因子，Pohlig-Hellman 直接攻破。
2. DDH 在 pairing 群中可能失效：Type I 配对让 DDH 容易，所以协议必须显式声明假设 (CDH/Gap-DH/SXDH)。
3. GNFS 复杂度的误解："2048-bit RSA 安全"基于 $L_p(1/3)$ 估算；若 NFS 改进到 $L_p(1/4)$，2048 立即危险。RSA 比 ECC 更脆弱于算法进步。
4. 量子时间表的误判：常说"30 年后量子破 ECC"。但密钥需要长期保密的协议（如签名）今天就该考虑 PQC 迁移（harvest now, decrypt later）。
5. Anomalous 曲线：$#E(\mathbb{F}_p) = p$ 的曲线（"trace 1"）被 Smart 1999 多项式时间破。生成曲线必须验证 $#E \ne p$。
6. Frey-Ruck 攻击：嵌入度 $k$ 的小但非 1 的曲线，把 ECDLP 转 $\mathbb{F}_{p^k}^*$ DLP。secp256k1 免疫（$k$ 巨大）。

---

九、关键速查

算法复杂度表

假设强弱

$$\text{DDH} \le \text{CDH} \le \text{DLP}$$ （左侧难度 ≤ 右侧）

---

十、面试题

Q1: 比较 BSGS 与 Pollard rho 的取舍。

答：

• BSGS：时间 $O(\sqrt n)$，空间 $O(\sqrt n)$。$n=2^{256}$ 时空间 $2^{128}$ 字 ≈ $10^{30}$ TB，不可行。
• Pollard rho：时间 $O(\sqrt n)$，空间 $O(1)$。$n=2^{256}$ 时间 $2^{128}$ 操作，全球算力 $\sim 10^{20}$ ops/sec 也需 $10^{18}$ 年。

实际通用 ECDLP 攻击用并行 rho（distinguished points 方法），单机内存极小。

Q2: 解释为什么 RSA-2048 与 ECC-256 等价安全。

答：

• RSA-2048: 因子分解 $N \sim 2^{2048}$, GNFS 复杂度 $L_N(1/3) \approx 2^{112}$（实际 ~112 bit）
• ECC-256: ECDLP $n \sim 2^{256}$, Pollard rho $\sqrt n \approx 2^{128}$

二者都达 ~112-128 bit 安全。ECC 更紧凑因为没有亚指数攻击。

Q3: 量子计算机来了，哪些假设倒下？

答：

• 倒下：DLP（含 ECDLP）、因子分解 → Shor 多项式时间破
• 存活：基于 hash（SHA-256、Merkle 签名）、格（LWE、SIS、NTRU）、码（McEliece）、多变量、isogeny
• 影响：今天的签名/加密都靠 ECDLP/RSA → 必须迁 PQC（NIST 已选 Kyber/Dilithium/Falcon/SPHINCS+）

但量子破解需要 ~10^7 logical qubits（含纠错），目前 ~1000 物理 qubits（≈ 几十 logical），距离仍远（10-30 年估计）。

Q4: secp256k1 与 BN254 哪个更安全？

答：secp256k1 更安全。

• secp256k1: 通用 rho 攻击 $2^{128}$，无特殊弱点 → 128 bit 安全
• BN254: 嵌入度 12 + Tower NFS → $\mathbb{F}_{p^{12}}^*$ DLP 攻击约 $2^{100}$ → 仅 ~100 bit 安全

但 BN254 用途不同（pairing-friendly，必需嵌入度小），secp256k1 不能做 pairing。所以「更安全 ≠ 更好」，看应用。

Q5: q-strong DH 假设是什么？哪些协议用？

答：q-Strong DH (Boneh-Boyen 2004)：给 $g, g^a, g^{a^2}, \dots, g^{a^q}$，求一对 $(c, g^{1/(a+c)})$ for $c \in \mathbb{Z}_p \setminus {-a}$。

用处：

• KZG 多项式承诺（$\tau$ 是 trusted setup 的 toxic waste）
• BBS+ 签名 / anonymous credentials
• Groth16 (一部分)

风险：$q$ 越大假设越强；$q=2^{40}$ 时实证攻击效率高于 $\sqrt n$ rho（Cheon 2006 攻击）。所以 trusted setup 大小有限制。

---

十一、明日预告

Day 187: Week 28 复习 — 把 Day 181-186 的群论 / 有限域 / 椭圆曲线 / pairing / 困难问题整合成"密码学数学速查"（cheatsheet 格式）。

核心问题：拿一张 A4 纸能否承载证 Bitcoin 安全的全部数学？

参考文献：

• Pollard, "Monte Carlo methods for index computation (mod p)", 1978.
• Pohlig & Hellman, IEEE Trans. Inf. Theory 1978.
• Lenstra et al, "The Number Field Sieve", 1993.
• Shor, "Algorithms for Quantum Computation", FOCS 1994.
• Galbraith, Mathematics of Public Key Cryptography, Ch. 13-14.