🏠 总目录📚 本教程 13 · 数论工具箱 ← →

密码学与信息安全 · 13

模意义下能做除法吗,什么时候逆元根本不存在?

模运算中的逆元不是对每个数都存在。把余数、互素与群阶先理清,再读公钥密码依赖的困难问题。

读完能判断:从余数、gcd与群阶进入公钥密码假设,分清 CDH/DDH。

📑 本页目录(点开跳转)

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 内置的对拍一下(内置通常更快,但 Python pow 不承诺恒定时间;只用于教学整数运算)
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 "能算":加解密都是模幂,靠平方-乘从不可能变成毫秒级。


🧮 二、最大公因数与逆元

欧几里得算法

信息关系

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,所以解密时可以:

  1. 算 $m_p = c^{d \bmod (p-1)} \bmod p$
  2. 算 $m_q = c^{d \bmod (q-1)} \bmod q$
  3. 用 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 量级换算一次,"穷举为什么不可能"就再也不用背了 ⭐
你不需要的数学 对照 大模型 · 数学地基:那份清单(线代/概率/梯度)和公钥密码几乎零重叠,别把它当前置

✅ 检查点

  1. 模运算的哪个性质让"算 3^1000 mod 7"变得可行?
  2. 快速幂的复杂度是多少?2048 bit 指数大概要多少次乘法?
  3. 模逆元存在的充要条件是什么?怎么求?
  4. 什么是生成元?举一个例子。
  5. 欧拉定理说了什么?φ(pq) 等于多少?
  6. 为什么说 φ(pq) 的式子是"计算私钥的一条已知路径;攻破 RSA 与分解的等价性不能据此断言"?
  7. DLP、CDH、DDH 三者的强弱关系?
  8. 为什么 ElGamal 需要 DDH 而不只是 CDH?
  9. 128-bit 安全需要多长的 RSA 模数?多长的椭圆曲线?为什么差这么多?
👀 答案
  1. 乘法可以随时取余:(a×b) mod n = ((a mod n)×(b mod n)) mod n。所以每步乘完就取余,数永远不超过 n²。
  2. O(log b) 次平方加若干次乘法。2048 bit 指数约 3000 次乘法。
  3. gcd(a, n) = 1(互质)。用扩展欧几里得算法求出满足 ax + ny = gcd(a,n) 的 x,当 gcd=1 时 x 就是逆元。Python 里 pow(a, -1, n)。
  4. 阶等于群大小的元素,即 g, g², ..., g^(p-1) 遍历整个群不重复。例:p=7 时 g=3,因为 3^1..3^6 = {3,2,6,4,5,1} 正好是 {1..6}。
  5. gcd(a,n)=1 ⟹ a^φ(n) ≡ 1 (mod n)。φ(pq) = (p−1)(q−1)。
  6. 因为知道 p、q 就能算 φ;只知道 n=pq 却算不出 φ。这个不对称就是公钥能公开、私钥能保密的全部原因。
  7. DDH 难 ⟹ CDH 难 ⟹ DLP 难。DDH 是最强的假设。
  8. 因为 CDH 只保证算不出 g^ab,而 IND-CPA 要求连分辨都做不到。攻击者可能算不出完整值却能判断"最低位是 1",那就违反 IND-CPA 了。DDH 直接说"分辨不出",正好匹配。(实际后果:Z*_p 上 DDH 是假的,ElGamal 必须在素数阶子群上做。)
  9. RSA 3072 bit,椭圆曲线 256 bit。差这么多是因为分解和 DLP 有亚指数算法(数域筛法),而椭圆曲线上目前只有指数级算法。

本节回顾

⚡ 走神救援

先记住这几件事

下一节 👉 14-RSA.md

条件与依据

φ(pq)=(p−1)(q−1) 需 p、q 是不同素数。Python 的平方乘与内置 pow 都不能当作处理真实私钥的恒定时间实现。RSA 反演的标准困难假设与整数分解的关系不等于已证明等价;参数表是经典安全量级,不代表算法仍获当前协议允许。

官方文档;官方文档

打卡记录保存在你的浏览器里,首页能看到总进度