Week 28 复习 — 密码学数学速查

日期: 2026-11-04 方向: 密码学数学 阶段: Phase 4 - 密码学数学基础 (Day 181-194) 标签: #密码学 #数学速查 #群论 #有限域 #椭圆曲线 #pairing

---

今日目标

---

一、知识图谱（数学到协议的链路）

群论 (Day 181)
   ├─ 循环群、生成元、阶
   ├─ Lagrange / Fermat / Euler 定理
   └─ 子群 / 陪集
        ↓
有限域 (Day 182)
   ├─ F_p (素域)
   ├─ F_{p^n} (扩域, 不可约多项式)
   └─ Frobenius 自同构 x↦x^p
        ↓
椭圆曲线 (Day 183)
   ├─ Weierstrass: y² = x³ + ax + b
   ├─ 点加法 / 标量乘法 / 无穷远点
   └─ Hasse: |#E - (p+1)| ≤ 2√p
        ↓
主流曲线对比 (Day 184)
   ├─ secp256k1, Curve25519: 无 pairing, 128-bit
   ├─ BN254: pairing, ~100-bit (deprecated)
   └─ BLS12-381: pairing, 128-bit (主流)
        ↓
双线性配对 (Day 185)
   ├─ e: G1 × G2 → GT, e(aP, bQ) = e(P,Q)^{ab}
   ├─ Tate / Weil / Optimal Ate
   └─ Miller loop O(log r) + final exp
        ↓
困难问题 (Day 186)
   ├─ DLP / CDH / DDH / BDH / SXDH
   ├─ Pollard rho O(√n) / NFS L_p(1/3)
   └─ Shor 量子破 → PQC
        ↓
应用层
   ├─ ECDSA, Schnorr, EdDSA → 签名
   ├─ ECDH → 密钥交换
   ├─ BLS → 聚合签名 (Eth2)
   ├─ KZG → 多项式承诺 (Plonk, EIP-4844)
   └─ Groth16 → SNARK

---

二、定理速查表

---

三、群速查

---

四、椭圆曲线公式速查

y² = x³ + a·x + b   (Weierstrass)

加: P + Q = R, P=(x1,y1), Q=(x2,y2)
  λ = (y2-y1)/(x2-x1)         if P ≠ Q
  λ = (3x1²+a)/(2y1)          if P = Q (doubling)
  x3 = λ² - x1 - x2
  y3 = λ(x1 - x3) - y1

特殊:
  P + (-P) = O                   (无穷远点)
  -P = (x, -y)
  P + O = P

标量乘 kP: double-and-add, O(log k)
  R = O
  for bit in bits(k) MSB→LSB:
    R = 2R
    if bit: R = R + P

---

五、Pairing 公式速查

双线性: e(aP, bQ) = e(P, Q)^{ab}
非退化: e(g1, g2) ≠ 1
可计算: Miller loop O(log r) + final exp

Tate:  e_T(P, Q) = f_{r,P}(Q)^{(p^k-1)/r}

类型:
  Type I  (G1 = G2):     DDH 容易
  Type II (G2 → G1 hom): 中间
  Type III (G1, G2 不同): SXDH (DDH 在两边都难) ← 主流

应用:
  BLS sig:  e(σ, G2) = e(H(m), pk)
  KZG:      e(π, [τ-z]_2) = e(C - [y]_1, G2)
  Groth16:  e(A,B) = e(α,β) e(L,γ) e(C,δ)

---

六、攻击速查

L_q(α, c) := exp(c (log q)^α (log log q)^{1-α})

L_q(1/3) ≪ L_q(1/2) ≪ L_q(1)=q
  ↑ NFS    ↑ index    ↑ rho

---

七、安全等级速查（NIST）

---

八、曲线对比速查

---

九、协议 → 数学映射

---

十、概念自测（30 题，闭卷）

1. 群的四条公理是？
2. 写出 Lagrange 定理。
3. $\varphi(12) = ?$
4. 为什么 $(\mathbb{Z}/12)^*$ 不是循环群？
5. Fermat 小定理 vs Euler 定理区别？
6. 6 元有限域存在吗？为什么？
7. 写 $\mathbb{F}_4$ 的 4 个元素。
8. Frobenius 自同构是什么？
9. secp256k1 的 $p, a, b$ 是？
10. Hasse 定理给出什么界？
11. EC 点加法 doubling 公式？
12. 无穷远点 $\mathcal{O}$ 的几何意义？
13. ECDSA 签名公式？
14. 比较 secp256k1 vs Curve25519。
15. 嵌入度的定义？
16. 为什么 $k=12$ 是 sweet spot？
17. BLS12-381 与 BN254 的优劣？
18. Pairing 的双线性是什么？
19. Type I/II/III pairing 的区别？
20. Miller loop 复杂度？
21. Final exponentiation 的作用？
22. BLS 签名验证公式？
23. KZG 验证公式？
24. DLP / CDH / DDH 的强弱？
25. Pollard rho 复杂度？
26. NFS 复杂度记号 $L_p(1/3)$ 是什么？
27. Shor 算法破什么？
28. 后量子密码基于什么困难问题？
29. RSA-2048 ≈ ECC-?
30. small subgroup attack 怎么发生？怎么防？

答案：复习 Day 181-186。每题应能在 30 秒内答出关键点。

---

十一、Bitcoin 安全的"一页数学"

目标：能否用 A4 纸说服别人 Bitcoin 私钥安全？

1. 群：secp256k1 上 EC 点群 $G = \langle G_0 \rangle$，$|G| = n \approx 2^{256}$，$n$ 大素数。

2. 困难问题：ECDLP — 给 $G_0, P = kG_0$，求 $k$。

3. 通用攻击：Pollard rho，复杂度 $\sqrt n \approx 2^{128}$ 群操作。

4. 特殊攻击免疫：

• Index calculus：不存在（EC 无 factor base）
• MOV：嵌入度 $\sim 2^{255}$，不可约简
• Smart anomalous：$#E \ne p$
• Pohlig-Hellman：$n$ 素数

5. 量子威胁：Shor 多项式破，但需 ~$10^7$ 逻辑量子比特，目前 ~$10^3$ 物理。

6. 实现攻击：

• 侧信道：用 Montgomery ladder + RFC 6979 nonce
• 故障注入：硬件防护

7. 估算：$2^{128}$ ops × $10^{-12}$ s/op = $3 \times 10^{19}$ 秒 ≈ $10^{12}$ 年。即使银河级算力（$10^{20}$ ops/s）仍需 $10^9$ 年。

结论：Bitcoin 私钥（256-bit, 选自 $[1, n)$）在经典计算下安全到宇宙年龄结束。

---

十二、面试题（综合）

Q1: 现场推导：为什么 Schnorr 签名比 ECDSA 简洁？

答：

• ECDSA：$s = k^{-1}(H(m) + rd)$，验证用模逆 + EC scalar mul
• Schnorr：$s = k + H(R || m) \cdot d$，验证 $sG = R + H(R||m) \cdot pk$
• Schnorr 线性于密钥 $\Rightarrow$ 可聚合（MuSig）；ECDSA 因模逆不可线性聚合
• Schnorr 安全证明严格（在 ROM 下基于 DLP）；ECDSA 证明依赖 GGM
• BIP-340 在比特币 Taproot 引入 Schnorr 是大升级

Q2: 为什么 KZG 需要 trusted setup？

答：KZG 承诺 $C = [p(\tau)]_1 = p(\tau) G_1$，需要预先生成 ${G_1, [\tau]_1, [\tau^2]_1, \dots, [\tau^d]_1, G_2, [\tau]_2}$。$\tau$ 是 toxic waste，泄露则任何人能伪造证明。MPC ceremony（Powers of Tau）让多人协作生成，只要有一人诚实丢弃份额，整体安全。

Q3: 解释 BLS 聚合签名的安全证明思路。

答：

• 单签名安全：在 random oracle 模型 + co-CDH 假设下，BLS 安全归约到 co-CDH（给 $g_1^a, g_2$ 求 $g_2^a$）
• 聚合：$\sigma = \sum \sigma_i$，验证 $e(\sigma, g_2) = \prod e(H(m_i), pk_i)$
• Rogue key attack：恶意 $pk' = pk^* - \sum_{i\ne *} pk_i$ 让聚合证明任意消息
• 修复：proof-of-possession（每个 pk 注册时附自签名）或 BLS-MuSig 风格 weight

Q4: 用 5 行解释为什么 secp256k1 选 $a=0$。

答：(1) Doubling 公式 $\lambda = 3x^2/(2y)$ 少一个加法；(2) Koblitz 曲线性质，有 endomorphism $\phi(x,y) = (\beta x, y), \beta^3 = 1$；(3) GLV 分解让标量乘 25% 加速；(4) 点压缩简化；(5) 历史选择，已固化在比特币。

Q5: 在量子时代 Bitcoin 应该怎么升级？

答：

• 签名：用 PQC 签名替换 ECDSA。候选：SPHINCS+（hash-based, 大）、Dilithium（lattice, 中）、Falcon（lattice, 高效但浮点）
• 过渡方案：Hybrid 签名（同时 ECDSA + PQC，兼容性 + 安全双保）
• 存款 vs 转账：签名只在花费时暴露公钥，所以 P2PKH 地址在量子破解后仍安全（只要私钥未用过）；但用过的地址 (P2PK) 暴露 pubkey，量子可破
• 实施：BIP soft fork 加 PQC opcode，钱包逐步迁移

---

十三、明日预告

Day 188: 数论基础 — 模运算、欧拉定理、CRT、二次剩余、Miller-Rabin 素性测试。这些是上面所有数学的"地基"，今天复习已用到，明天系统化。

核心问题：如何在 1 秒内判定一个 1024-bit 数是否素数？

参考文献：

• 复习 Day 181-186 的全部参考。
• Galbraith, Mathematics of Public Key Cryptography, Ch. 1-14.
• NIST SP 800-57: Recommendation for Key Management.