📑 本页目录（点开跳转）
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²
🔨 快速幂：公钥密码的性能基石
结果对照
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 内置的对拍一下（内置更快，且是恒定时间的）
a, b, n = 123456789, 987654321, 1_000_000_007
print(powmod(a, b, n), pow(a, b, n))
assert powmod(a, b, n) == pow(a, b, n)
💡 这就是为什么 RSA "能算"：加解密都是模幂，靠平方-乘从不可能变成毫秒级。
🧮 二、最大公因数与逆元
欧几里得算法
信息关系
⭐ 扩展欧几里得：求模逆元
因果链
结果对照
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 章）
阶与生成元
结果对照
两个必知定理：
| 定理 | 内容 | 用在哪 |
|---|---|---|
| 费马小定理 | 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 有亚指数算法（数域筛法），而椭圆曲线上目前只有指数级算法。
🛑 可以停在这里
⚡ 走神救援
先记住这几件事
- 模运算、快速幂、逆元与群是后续公钥方案的数学工具。
- 先检查逆元存在条件与运算所在的群，再代入公式。
- 容易正向计算与困难的逆问题形成不对称，但安全还依赖具体参数与假设。
下一节 👉 14-RSA.md