Week 29 复习 — 密码学数学完整体系

日期: 2026-11-11 方向: 密码学数学 阶段: Phase 4 - 密码学数学基础 (Day 181-194) 标签: #密码学 #数学复习 #体系整合 #面试

---

今日目标

---

一、Phase 4 数学全景图

Day 181 群论
    ├─ 公理 (封闭/结合/单位/逆) + Lagrange + 循环
    ↓
Day 182 有限域
    ├─ F_p, F_{p^n} = F_p[x]/(f), Frobenius x↦x^p
    ↓
Day 183-184 椭圆曲线
    ├─ y²=x³+ax+b, 点加, double-and-add
    └─ secp256k1 / Ed25519 / BN254 / BLS12-381
    ↓
Day 185 双线性配对
    ├─ e: G1 × G2 → GT, e(aP,bQ) = e(P,Q)^ab
    └─ Tate / Optimal Ate / Miller loop
    ↓
Day 186 困难问题
    ├─ DLP / CDH / DDH / BDH
    └─ Pollard rho √n / NFS L_p(1/3)

(Day 187 Week 28 复习)

Day 188 数论
    ├─ Fermat / Euler / CRT / Tonelli-Shanks
    └─ Miller-Rabin 素性
    ↓
Day 189 多项式 + FFT
    ├─ Lagrange 插值, butterfly O(n log n)
    └─ NTT in F_p with n | p-1
    ↓
Day 190 信息论
    ├─ Shannon 熵, 互信息, OWF, birthday
    ↓
Day 191 复杂度
    ├─ P/NP/IP=PSPACE/PCP/BQP
    └─ ZK in NP, AoK, KoE
    ↓
Day 192 概率
    ├─ Chernoff, negligible, ROM, PRF/PRP, 安全游戏
    ↓
Day 193 困难假设
    ├─ DLog/RSA/LWE/SIS/Isogeny
    └─ Shor → PQC (Kyber/Dilithium/Falcon/SPHINCS+)

(Day 194 Week 29 总复习 ← 今天)

---

二、最重要 30 个公式 / 定理

群论

1. Lagrange: $|H| \mid |G|$
2. Fermat 小: $a^{p-1} \equiv 1 \pmod p$
3. Euler: $a^{\varphi(n)} \equiv 1 \pmod n$
4. CRT: $x = \sum a_i M_i (M_i^{-1} \mod n_i) \mod N$
5. $\mathbb{F}_q^$ 循环, $|F_q^| = q-1$

椭圆曲线

1. Weierstrass: $y^2 = x^3 + ax + b$
2. Hasse: $|#E - (p+1)| \le 2\sqrt p$
3. EC 加法 $\lambda = (y_2-y_1)/(x_2-x_1)$, $x_3 = \lambda^2 - x_1 - x_2$
4. EC doubling $\lambda = (3x^2+a)/(2y)$
5. 标量乘 $kP$ via double-and-add, $O(\log k)$

Pairing

1. 双线性 $e(aP, bQ) = e(P,Q)^{ab}$
2. 嵌入度 $k$: 最小 $i$, $r \mid p^i - 1$
3. Tate: $e_T(P,Q) = f_{r,P}(Q)^{(p^k-1)/r}$
4. BLS 验证: $e(\sigma, G_2) = e(H(m), pk)$
5. KZG: $e(\pi, [\tau-z]_2) = e(C - [y]_1, G_2)$

困难问题

1. Pollard rho $O(\sqrt n)$
2. GNFS $L_p(1/3, \sqrt[3]{64/9})$
3. Pohlig-Hellman $O(\sum \sqrt{p_i})$
4. Birthday $q \approx \sqrt N$ for $P=1/2$
5. Shor: DLP, IF poly-time on QC

FFT / 多项式

1. DFT: $A_k = \sum a_j \omega^{jk}$
2. Cooley-Tukey: $A_k = E_k + \omega^k O_k, A_{k+n/2} = E_k - \omega^k O_k$
3. FFT 复杂度 $O(n \log n)$
4. NTT 条件: $n \mid p-1$
5. Lagrange 插值唯一存在 $n-1$ 次

信息论 / 复杂度 / 概率

1. Shannon 熵 $H(X) = -\sum p_i \log_2 p_i$
2. 互信息 $I(X;Y) = H(X) - H(X|Y)$
3. Markov / Chebyshev / Chernoff
4. IP = PSPACE
5. NP-complete: SAT, 3-SAT, 3-Coloring (任何 NP 归约到)

---

三、协议安全栈映射

Bitcoin / Ethereum 账户层

   ECDSA on secp256k1
        ↓
   ECDLP @ 128-bit
        ↓
   Pollard rho √n
        ↓
   保护: 256-bit 子群 + 大素数 n + cofactor 1

Phase 4 工具用了：群论（循环群）、有限域（$\mathbb{F}_p$）、椭圆曲线（标量乘）、困难问题（ECDLP）、数论（模逆 in 签名）、概率（RFC 6979 nonce 生成）。

Eth2 BLS 签名层

   BLS sig on BLS12-381
        ↓
   pairing e: G1 × G2 → GT
        ↓
   co-CDH 假设 (Type III, SXDH)
        ↓
   保护: 嵌入度 12, 381-bit p, 255-bit r, ~3072-bit F_p^12

用了：所有上述 + pairing + 复杂度（reduction 证明）。

Plonk SNARK 验证层

   Plonk (KZG-based)
        ↓
   多项式承诺 + Schwartz-Zippel
        ↓
   q-strong DH (BLS12-381) + KoE 假设
        ↓
   保护: r-1 含 2^32 → FFT 友好, prover 用 NTT

用了：所有上述 + 多项式 / FFT + 概率（Fiat-Shamir + ROM）+ 复杂度（IP, PCP, AoK）。

Post-Quantum (Dilithium 签名)

   Dilithium (lattice signature)
        ↓
   MLWE + MSIS
        ↓
   worst-case GapSVP / SIVP
        ↓
   保护: 量子下 BKZ-Q 仍 2^O(n)

用了：信息论（rejection sampling）、概率（高斯采样）、数论（多项式环 $\mathbb{Z}_q[X]/(X^n+1)$）、复杂度（QROM 证明）。

---

四、自测 50 题（闭卷 2 小时）

群论与有限域 (1-10)

1. 群的四条公理。
2. 写出 Lagrange 定理及推论。
3. $\varphi(15) = ?$
4. $(\mathbb{Z}/8)^*$ 是循环群吗？阶？
5. Fermat 小定理证明。
6. 6 元域为什么不存在？
7. $\mathbb{F}_4 = \mathbb{F}_2[x] / (?)$
8. Frobenius 自同构的定义。
9. $\mathbb{F}_{p^k}^*$ 阶 = ?
10. 扩域 $\mathbb{F}_{p^2} = \mathbb{F}_p[u] / (u^2 - \beta)$ 中 $\beta$ 必须是？

椭圆曲线 (11-20)

1. secp256k1 的 $p, a, b$ 值？
2. Hasse 定理给出什么界？
3. EC doubling 公式。
4. 无穷远点的射影坐标？
5. Curve25519 余因子是？为什么 clamp 私钥？
6. 嵌入度 $k$ 定义。
7. BN254 vs BLS12-381 安全级别对比。
8. Pairing-friendly 曲线为什么 $k$ 小有风险？
9. ECDSA 签名公式。
10. BIP-340 Schnorr 与 ECDSA 区别？

Pairing (21-25)

1. 双线性的形式定义。
2. Type I/II/III pairing 区别。
3. Tate pairing 公式。
4. Final exponentiation 作用。
5. BLS 签名验证公式。

困难问题 (26-32)

1. DLP / CDH / DDH 强弱关系。
2. Pollard rho 复杂度，为什么内存 $O(1)$？
3. GNFS 复杂度记号？
4. MOV 攻击什么曲线？
5. Shor 算法破什么？
6. RSA-2048 ≈ ECC-? bit。
7. Pohlig-Hellman 在 secp256k1 是否有效？

数论 (33-37)

1. CRT 公式。
2. Carmichael 数为什么躲过 Fermat 测试？
3. Miller-Rabin 单轮误判率上界。
4. Tonelli-Shanks 在 $p \equiv 3 \pmod 4$ 简化形式。
5. RSA-CRT 解密加速比 ~? 倍。

FFT / 多项式 (38-42)

1. DFT 的 inverse 公式。
2. FFT 复杂度证明思路。
3. NTT 在 secp256k1 上能做吗？
4. KZG 承诺公式。
5. Schwartz-Zippel 引理。

信息论 / 复杂度 / 概率 (43-47)

1. 完美保密的等价定义。
2. Birthday $q \approx \sqrt N$ 推导。
3. SHA-256 抗碰撞 / 抗 preimage 安全 bit。
4. P / NP / PSPACE / IP 的关系。
5. ZK 三性质：完整性 / 可靠性 / 零知识，分别是什么？

后量子 (48-50)

1. 为什么 LWE 量子安全？
2. NIST 选定哪 4 个 PQ 算法？
3. Harvest now decrypt later 是什么威胁？

---

五、答案要点（自测后核对）

1. 封闭/结合/单位元/逆元
2. $|H| \mid |G|$；推论 $\text{ord}(a) \mid |G|$
3. $\varphi(15) = 15(1-1/3)(1-1/5) = 8$
4. 否（Klein 四元群）；阶 4
5. Lagrange 推论 + $\mathbb{F}_p^*$ 阶 $p-1$
6. 阶必为素数幂，$6 = 2 \cdot 3$ 不是
7. $\mathbb{F}_2[x] / (x^2+x+1)$
8. $\phi(x) = x^p$，特征 $p$ 域上自同构
9. $p^k - 1$
10. 非二次剩余 (NQR)
11. $p = 2^{256}-2^{32}-977, a=0, b=7$
12. $|#E - (p+1)| \le 2\sqrt p$
13. $\lambda = (3x^2+a)/(2y), x_3 = \lambda^2-2x, y_3 = \lambda(x-x_3)-y$
14. $(0:1:0)$
15. $h=8$；clamp 防 small subgroup attack
16. 最小 $i$ 使 $r \mid p^i - 1$
17. BN254 ~100-bit (post-NFS)；BLS12-381 128-bit
18. MOV 攻击：把 ECDLP 转 $\mathbb{F}_{p^k}^*$ DLP
19. $r = (kG)_x \mod n, s = k^{-1}(H(m)+rd) \mod n$
20. Schnorr 线性 → 可聚合 (MuSig)，证明 tighter
21. $e: G_1 \times G_2 \to G_T$，$e(aP, bQ) = e(P,Q)^{ab}$
22. I: $G_1 = G_2$, II: 单向 hom, III: 不同
23. $e_T(P,Q) = f_{r,P}(Q)^{(p^k-1)/r}$
24. 把元素映入 $\mu_r$，唯一表示
25. $e(\sigma, G_2) = e(H(m), pk)$
26. DDH ≤ CDH ≤ DLP（左易者右也易）
27. 时间 $\sqrt n$；用 Floyd 循环检测，仅记 2 状态
28. $L_p(1/3, \sqrt[3]{64/9})$
29. 嵌入度 $k$ 小（≤ 6）的曲线
30. DLP, ECDLP, factoring（poly time on QC）
31. 128 bit (256 bit ECC)
32. 否；secp256k1 $n$ 是大素数
33. $x = \sum a_i M_i (M_i^{-1} \mod n_i) \mod N$
34. $\lambda(n) \mid n-1$，所有 base 都通过 FLT
35. $\le 1/4$
36. $y = a^{(p+1)/4} \mod p$
37. ~4×
38. $a_j = \frac{1}{n}\sum A_k \omega^{-jk}$
39. $T(n) = 2T(n/2) + cn = O(n\log n)$（Master Theorem）
40. 否；$n-1$ 仅 1 个因子 2
41. $C = [p(\tau)]_1, \pi = [(p(\tau)-y)/(\tau-z)]_1$
42. 非零 $d$ 次多项式在 $|F|^k$ 上随机点零的概率 ≤ $d/|F|$
43. $p(c \mid m) = p(c)$ for all $m, c$（独立）
44. $1 - e^{-q^2/2N} \approx 1/2 \Rightarrow q \approx \sqrt N \ln 2$
45. preimage $2^{256}$, collision $2^{128}$
46. $P \subseteq NP \subseteq PSPACE = IP$
47. Completeness, Soundness, ZK (simulator-existence)
48. Worst-case lattice 量子归约；BKZ-Q 仅 $2^{0.265 n}$
49. ML-KEM (Kyber), ML-DSA (Dilithium), SLH-DSA (SPHINCS+), FN-DSA (Falcon)
50. 攻击者今天截密文存量子机器可用时解密

---

六、Phase 4 数学全景"必背"卡片

Card 1: 椭圆曲线五要素

曲线 E: y² = x³ + ax + b over F_p
  ├─ p (字段大小)
  ├─ a, b (曲线参数)
  ├─ G (生成元)
  ├─ n (子群阶, 大素数)
  └─ h (余因子)

完整安全评估:
  ✓ #E(F_p) 与 p 不同 (anomalous 防)
  ✓ n 大素数 (Pohlig-Hellman 防)
  ✓ 嵌入度 k 巨大 OR k=12 + p 足够大 (MOV 防)
  ✓ 1/h 简单 (subgroup 攻击防)

Card 2: 三种 pairing

Card 3: PQ 算法选择

---

七、综合面试题（Phase 4 总测）

Q1: 完整解释 Bitcoin 私钥的安全建立在什么数学上。

答：

1. 群：secp256k1 上 EC 点群 $E(\mathbb{F}_p)$，子群阶 $n \approx 2^{256}$，大素数
2. 困难问题：ECDLP — 给 $G, P=kG$ 求 $k$
3. 通用攻击：Pollard rho $\sqrt n = 2^{128}$ 操作，$O(1)$ 内存
4. 特殊攻击免疫：
   • 无 index calculus（EC 群结构）
   • 嵌入度大（MOV 不适用）
   • $#E \ne p$（Smart anomalous 不适用）
   • $h=1$（无 small subgroup）
5. 量子威胁：Shor poly 时间，但需 ~$10^7$ 逻辑 qubit
6. 实施安全：RFC 6979 deterministic nonce + Montgomery ladder + 硬件 RNG

经典安全：$2^{128}$ ops × $10^{-12}$ s/op = $10^{19}$ 秒 = 银河算力 $10^9$ 年。

Q2: 解释 Plonk 在 BLS12-381 上的端到端数学栈。

答：

1. 底层字段：$\mathbb{F}_r$，$r \approx 2^{255}$ 大素数，$r-1$ 含 $2^{32}$ 因子（FFT 友好）
2. 多项式：电路约束转为 $\mathbb{F}_r[X]$ 多项式 $a(X), b(X), c(X), Q_L, Q_R, Q_O, Q_M, Q_C$
3. 承诺：KZG 承诺 $C = [p(\tau)]_1 \in \mathbb{G}_1$，依赖 trusted setup
4. 配对：$\mathbb{G}_1 \subset E(\mathbb{F}_p), \mathbb{G}2 \subset E'(\mathbb{F}{p^2}), \mathbb{G}T \subset \mathbb{F}{p^{12}}^*$
5. 验证：$e(\pi, [\tau-z]_2) = e(C-[y]_1, G_2)$ — 双线性 + 同态
6. 可靠性：基于 q-strong DH + KoE 假设；Schwartz-Zippel 给概率界
7. 零知识：Fiat-Shamir 转 NIZK + blinding factors
8. 量子：Shor 破 → 全栈崩；STARK 替代是 PQ 路线

Q3: 推导为什么 Schnorr 签名安全证明用 forking lemma。

答：Schnorr：$\sigma = (R, s), R = kG, s = k + H(R|pk|m) \cdot d$。

Reduction 思路：假设 forger 给出 $(R, s)$。要解 DLP：给 $(G, P=dG)$ 求 $d$。

但 $(R, s)$ 单一不够，因 $s = k + e \cdot d$，$e = H(\cdot)$。一个等式两未知 $k, d$。

Forking：rewind forger，给同一 $R$ 但不同 $H$ 答案 $e_1, e_2$。得 $s_1, s_2$： $$s_1 = k + e_1 d, \quad s_2 = k + e_2 d$$ $$\Rightarrow d = (s_1 - s_2) / (e_1 - e_2)$$

成功率 $\Omega(\epsilon^2 / q)$（Pointcheval-Stern）。所以：

• forger 优势 $\epsilon$ → DLP 解 $\epsilon^2/q$
• 想 DLP 难 ⇒ $\epsilon \le \sqrt{q \cdot \text{negl}}$
• "Loose" reduction，参数需稍大

Q4: 详细对比 LWE / NTRU / Code-based / Hash-based PQ。

答：

总结：Kyber/Dilithium 综合最优，因此 NIST 主选；McEliece 作为"保守"备份；SPHINCS+ 用于不能容忍 lattice 风险的场景（如固件签名）。

Q5: 完整推导：ECDLP 与 RSA factoring 的安全等价。

答：等价定义为"等量子安全"假设。

• RSA-3072：$N \approx 2^{3072}$，GNFS 复杂度 $L_N(1/3, c) \approx 2^{128}$
• ECC-256：$n \approx 2^{256}$，Pollard rho $\sqrt n = 2^{128}$
• 都达 128-bit 经典安全

为什么 ECC 短：

• $\mathbb{F}_p^*$ 上 DLP 有 sub-exponential GNFS, 复杂度 $L_p(1/3) = \exp(O((\log p)^{1/3}))$
• EC 上 ECDLP 仅有 generic $\sqrt n$，无 index calculus
• 同等安全：ECC 字段 256-bit vs RSA 3072-bit，约 12× 更紧

量子下两者皆崩：Shor 复杂度 $O((\log N)^3)$ for IF, $O((\log n)^3)$ for ECDLP。

密钥大小变化：量子安全的 PQ 公钥 (Kyber 1.2KB) 比 ECC 大 30×，但比 RSA 略小。

---

八、Phase 4 完成情况

14 天产出

能力检验

• 能写出群的四条公理 + 在 $(\mathbb{Z}/n)^*$ 上验证
• 能用 Python 实现 $\mathbb{F}p$ 和 $\mathbb{F}{p^2}$ 算术
• 能实现 secp256k1 的完整点加 + 标量乘
• 能区分 4 条主流曲线的安全/性能特点
• 能定义 pairing 并理解 BLS / KZG 验证公式
• 能列举 DLP 攻击算法及复杂度
• 能用 CRT + Miller-Rabin 实现 RSA 密钥生成
• 能写迭代 FFT 多项式乘法
• 能解释 ZK 在复杂度类中位置 + AoK
• 能在 ROM 下做安全归约证明
• 能对比 Kyber / Dilithium / Falcon / SPHINCS+ 取舍

后续 Phase 4 内容方向（Day 195+ 预告）

• Day 195+: SNARK 引擎（R1CS, QAP, Groth16, Plonk, Halo2）
• Day 230+: STARK / FRI / Plonky2 / RISC Zero
• Day 250+: Custom gates, Folding schemes (Nova, ProtoStar)
• Day 270+: Recursive SNARKs, ZK-EVM, accumulation
• Day 290: Phase 4 capstone — 构建一个 mini SNARK system from scratch

---

九、参考书单（Phase 4 总）

Phase 4 论文

• Diffie-Hellman 1976, Miller 1985, Schoof 1985, GMR 1985, Shamir 1992, Regev 2005, Castryck-Decru 2022。

---

十、面试准备 / 求职定位

完成 Phase 4 数学基础后能回答的密码学面试问题：

1. ✅ 解释 BLS / Schnorr / ECDSA 异同
2. ✅ 推导 KZG 验证公式
3. ✅ 比较 BN254 / BLS12-381 安全性
4. ✅ 设计 PQ 迁移方案
5. ✅ 评估 lattice scheme 参数选择
6. ✅ 分析 ZK 协议的可靠性证明

目标公司：Linea, Scroll, zkSync, Aztec, Aleo, Risc Zero, Succinct (ZK protocol engineers/researchers).

接下来 Phase 4 重点：把数学转协议 — Day 195+ 进入 R1CS / QAP / Groth16 / Plonk 实现细节。

---

十一、Phase 4 数学基础完成 ✅

致 14 天后的自己：你现在能从零推导 ECDSA 签名验证，能解释为什么 BLS12-381 嵌入度 12 是 sweet spot，能用 Python 实现 NTT 多项式乘法。这些数学不是工具——它们是 ZK 协议的语言。每次看 Plonk paper，认得里面每个 $\sum, \prod, e(\cdot, \cdot)$ 的来历，是 Phase 4 终极目标。

参考文献：见 Day 181-193 全部参考集合。

Phase 4 数学基础阶段: Day 181-194 完成。

下一阶段: Phase 4 SNARK 工程 (Day 195+)。