📑 本页目录（点开跳转）
13 · 数论工具箱
⏱ 28 分钟 ｜ 🎁 就四个概念，都是初中数学的延伸
🎯 一句话
公钥密码需要的全部数学，就是这一章的四个概念。 没有微积分，没有线性代数，只有"除法的余数"。
➗ 一、模运算：只关心余数
$$a \equiv b \pmod n \iff n \mid (a-b)$$
💡 人话：a 和 b 除以 n 的余数相同。
17 ≡ 5 (mod 12) ← 时钟：17 点就是 5 点 ⭐
38 ≡ 2 (mod 12)
-1 ≡ 11 (mod 12) ← 负数也一样，往回绕
好消息：加减乘都可以"随时取余"
(a + b) mod n = ((a mod n) + (b mod n)) mod n
(a × b) mod n = ((a mod n) × (b mod n)) mod n
⭐ 实际意义：算 3^1000 mod 7 不需要先算出那个天文数字，
每一步乘完就取余，数永远不会超过 n²
🔨 快速幂：公钥密码的性能基石
要算 a^b mod n，b 可能有 2048 bit
❌ 朴素做法：乘 b 次 → 2²⁰⁴⁸ 次 → 宇宙热寂也算不完
✅ 平方-乘算法：
a^13 = a^(1101₂) = a^8 · a^4 · a^1
→ 只需要【log b】次平方 + 若干次乘法
→ 2048 bit 指数只要约 3000 次乘法 ⭐
def powmod(a, b, n):
r = 1
a %= n
while b > 0:
if b & 1: r = r * a % n # 当前位是 1 就乘上
a = a * a % n # ⭐ 每步平方
b >>= 1
return r
# Python 内置更快（且是恒定时间的）：
pow(a, b, n)
💡 这就是为什么 RSA "能算"：加解密都是模幂，靠平方-乘从不可能变成毫秒级。
🧮 二、最大公因数与逆元
欧几里得算法
gcd(a, b) = gcd(b, a mod b)，直到余数为 0
gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) = 6 ⭐
⭐ 极快：步数是 O(log min(a,b))
⭐ 扩展欧几里得：求模逆元
问题：给定 a 和 n，找一个 x 使得 a·x ≡ 1 (mod n)
（x 叫做 a 的【模逆元】，记作 a⁻¹）
⭐ 存在的充要条件：gcd(a, n) = 1（互质）
扩展欧几里得能同时求出 gcd(a,n) 和满足
a·x + n·y = gcd(a,n) 的 (x, y)
→ 当 gcd = 1 时，那个 x 就是 a⁻¹ ⭐
例：求 3 在 mod 7 下的逆元
3 × 5 = 15 = 2×7 + 1 ≡ 1 (mod 7)
→ 3⁻¹ = 5 ✅
pow(3, -1, 7) # ⭐ Python 3.8+ 直接支持，返回 5
🔗 RSA 的私钥 d 就是这么算出来的：$d = e^{-1} \bmod \varphi(n)$。
👥 三、群、阶、生成元
群：一个集合 + 一个运算，满足封闭、结合律、有单位元、有逆元。
我们只用两个具体的群：
⭐ (Z*_p, ×)：模素数 p 的乘法群
元素 = {1, 2, ..., p-1}（都和 p 互质）
大小 = p - 1
⭐ 椭圆曲线点群（第 16 章）
阶与生成元
元素 g 的【阶】= 最小的正整数 k 使 g^k ≡ 1
⭐ 生成元（原根）：阶 = 群的大小的元素
→ g, g², g³, ..., g^(p-1) 【遍历整个群】，不重复
例：p = 7，g = 3
3¹=3 3²=2 3³=6 3⁴=4 3⁵=5 3⁶=1
→ {3,2,6,4,5,1} = 整个 {1..6} ✅ 3 是生成元
两个必知定理：
| 定理 | 内容 | 用在哪 |
|---|---|---|
| 费马小定理 | p 素数，gcd(a,p)=1 ⟹ $a^{p-1} \equiv 1 \pmod p$ | 素性检验 |
| 欧拉定理 | gcd(a,n)=1 ⟹ $a^{\varphi(n)} \equiv 1 \pmod n$ | ⭐ RSA 的正确性证明 |
欧拉函数 φ(n) = 小于 n 且与 n 互质的数的个数
φ(p) = p - 1 （p 是素数）
φ(pq) = (p-1)(q-1) ⭐ RSA 用的就是这个
🔑 注意 φ(pq) = (p−1)(q−1) 这个式子： 知道 p、q 就能算 φ；只知道 n = pq 却算不出 φ —— 这个不对称就是 RSA 的全部秘密。
📐 中国剩余定理（CRT）—— 让 RSA 解密快 4 倍（想看再点）
若 $n = pq$（p、q 互质），则模 n 的运算可以拆成模 p 和模 q 分别做：
$$x \bmod n \iff (x \bmod p,\; x \bmod q)$$
RSA 私钥持有者知道 p 和 q，所以解密时可以：
- 算 $m_p = c^{d \bmod (p-1)} \bmod p$
- 算 $m_q = c^{d \bmod (q-1)} \bmod q$
- 用 CRT 合并
为什么快：模幂的代价约是 $O(\log^3 n)$， 把位数减半后每次快 8 倍，两次共 4 倍 ⭐
⚠️ 但 CRT 实现有个著名风险：如果计算中出现硬件故障（或被故意注入）， 只需一次错误签名就能分解出 p —— 这叫 Bellcore 攻击。 所以实现必须验证签名结果。
🔒 四、三个困难问题（公钥密码的地基）
| 问题 | 内容 | 谁靠它 |
|---|---|---|
| 整数分解 | 给 n = pq，求 p 和 q | RSA |
| 离散对数 DLP | 给 g 和 $g^x$，求 x | DH、DSA、ElGamal |
| CDH / DDH | 给 $g^a, g^b$，求（或分辨）$g^{ab}$ | DH 密钥交换、ElGamal ⭐ |
⭐ 三个假设的强弱关系：
DDH 难 ⟹ CDH 难 ⟹ DLP 难
（最强） （最弱）
💡 反过来说：能解 DLP 就能解 CDH，能解 CDH 就能解 DDH
所以【基于 DDH 的方案假设最强，但能得到更好的安全性质】
💡 为什么 ElGamal 需要 DDH 而不只是 CDH（想看再点）
CDH 只保证攻击者算不出 $g^{ab}$， 但 IND-CPA 要求他连分辨都做不到（第 8 章）。
如果只有 CDH，攻击者可能算不出完整的 $g^{ab}$， 却仍能判断出"它的最低位是 1" —— 这就足以违反 IND-CPA。
DDH 假设直接说"分辨不出"，正好匹配 IND-CPA 的要求。
⚠️ 实际后果：在 $\mathbb{Z}_p^*$ 上，DDH 其实是假的（勒让德符号可以泄露信息）， 所以 ElGamal 必须在素数阶子群上做，不能在整个 $\mathbb{Z}_p^*$ 上。
📏 五、参数该取多大
| 安全级别 | RSA / DH 模数 | 椭圆曲线 | 对称密钥 |
|---|---|---|---|
| 112 bit | 2048 | 224 | 3DES |
| 128 bit ⭐ | 3072 | 256 | AES-128 |
| 192 bit | 7680 | 384 | AES-192 |
| 256 bit | 15360 | 512 | AES-256 |
🔑 注意 RSA 那一列增长得多快： 要多 64 bit 安全，模数要从 3072 涨到 7680。 这就是椭圆曲线的价值 —— 同等安全下密钥小一个数量级（第 16 章）。
💡 为什么 RSA 这么"低效"：因为存在亚指数的分解算法（数域筛法）， 而椭圆曲线上目前只有指数级的算法。
🔗 和站内其他章的关系
| 概念 | 后面用在哪 |
|---|---|
| 快速幂 | RSA、DH 的每一次运算 |
| 模逆元 | RSA 私钥 d 的计算 |
| 欧拉定理 | RSA 正确性证明 |
| φ(pq)=(p−1)(q−1) | RSA 的全部秘密 ⭐ |
| 生成元 | DH 的公共参数 |
| DDH | ElGamal 的安全依据 |
| 模运算 | 你天天写的 hash(id) % 100万（推荐算法 · 特征工程）就活在 ℤₙ 里，只是从没用过那里的乘法和逆元 |
| 2¹²⁸ 有多大 | 拿 AI 基础设施 · Roofline 与 MFU 里的 TFLOPS 量级换算一次，"穷举为什么不可能"就再也不用背了 ⭐ |
| 你不需要的数学 | 对照 大模型 · 数学地基：那份清单（线代／概率／梯度）和公钥密码几乎零重叠，别把它当前置 |
✅ 检查点
- 模运算的哪个性质让"算 3^1000 mod 7"变得可行？
- 快速幂的复杂度是多少？2048 bit 指数大概要多少次乘法？
- 模逆元存在的充要条件是什么？怎么求？
- 什么是生成元？举一个例子。
- 欧拉定理说了什么？φ(pq) 等于多少？
- 为什么说 φ(pq) 的式子是"RSA 的全部秘密"？
- DLP、CDH、DDH 三者的强弱关系？
- 为什么 ElGamal 需要 DDH 而不只是 CDH？
- 128-bit 安全需要多长的 RSA 模数？多长的椭圆曲线？为什么差这么多？
👀 答案
- 乘法可以随时取余：(a×b) mod n = ((a mod n)×(b mod n)) mod n。所以每步乘完就取余，数永远不超过 n²。
- O(log b) 次平方加若干次乘法。2048 bit 指数约 3000 次乘法。
- gcd(a, n) = 1（互质）。用扩展欧几里得算法求出满足 ax + ny = gcd(a,n) 的 x，当 gcd=1 时 x 就是逆元。Python 里
pow(a, -1, n)。 - 阶等于群大小的元素，即 g, g², ..., g^(p-1) 遍历整个群不重复。例：p=7 时 g=3，因为 3^1..3^6 = {3,2,6,4,5,1} 正好是 {1..6}。
- gcd(a,n)=1 ⟹ a^φ(n) ≡ 1 (mod n)。φ(pq) = (p−1)(q−1)。
- 因为知道 p、q 就能算 φ；只知道 n=pq 却算不出 φ。这个不对称就是公钥能公开、私钥能保密的全部原因。
- DDH 难 ⟹ CDH 难 ⟹ DLP 难。DDH 是最强的假设。
- 因为 CDH 只保证算不出 g^ab，而 IND-CPA 要求连分辨都做不到。攻击者可能算不出完整值却能判断"最低位是 1"，那就违反 IND-CPA 了。DDH 直接说"分辨不出"，正好匹配。（实际后果：Z*_p 上 DDH 是假的，ElGamal 必须在素数阶子群上做。）
- RSA 3072 bit，椭圆曲线 256 bit。差这么多是因为分解和 DLP 有亚指数算法（数域筛法），而椭圆曲线上目前只有指数级算法。
🛑 可以停在这里
⚡ 走神救援
公钥密码需要的全部数学就四个概念。①模运算：只关心余数（17≡5 mod 12，时钟）；⭐加减乘可以随时取余，所以算 a^b mod n 数永远不超过 n²。快速幂（平方-乘）：a^13 = a^8·a^4·a^1，O(log b) 次，2048bit 指数约 3000 次乘法 → 这就是 RSA "能算"的原因（Python 用
pow(a,b,n)，内置且恒定时间）。②模逆元：ax≡1 (mod n)，⭐存在充要条件是 gcd(a,n)=1，用扩展欧几里得求（pow(a,-1,n)）→ RSA 私钥 d 就是这么算的。③群/阶/生成元：只用 Z_p 和椭圆曲线点群；生成元的幂遍历整个群（p=7 时 3 是生成元）。欧拉定理 a^φ(n)≡1，⭐φ(pq)=(p−1)(q−1) —— ⭐⭐知道 p,q 能算 φ，只知道 n=pq 算不出 φ，这个不对称就是 RSA 的全部秘密。（CRT 让 RSA 解密快 4 倍，但有 Bellcore 攻击风险：一次故障签名就能分解 p，实现必须验签。）④三个困难问题：整数分解（RSA）、DLP 给 g,g^x 求 x、CDH/DDH 给 g^a,g^b 求/分辨 g^ab；⭐强弱关系 DDH ⟹ CDH ⟹ DLP。ElGamal 需要 DDH 不只是 CDH，因为 CDH 只保证"算不出"，IND-CPA 要求连"分辨"都做不到（算不出完整值但能判断最低位就够违反了）；⚠️ Z_p 上 DDH 其实是假的，必须在素数阶子群上做。参数：128-bit 安全 = RSA 3072 / ECC 256 / AES-128；⭐差距源于分解和 DLP 有亚指数算法（数域筛法），椭圆曲线目前只有指数级算法。
下一节 👉 14-RSA.md