Lecture 6: RSA（RSA 公钥密码）

目录 · ← l6 · l8 →

Lecture 6: RSA（RSA 公钥密码）

概述

本讲把前五讲积累的模运算工具箱——欧几里得算法、费马小定理 (Fermat’s Little Theorem)、中国剩余定理 (Chinese Remainder Theorem)——一次性投入一个真实且有巨大历史影响的工程问题：如何让两个从未见过面的人在不安全信道上安全通信。答案是 RSA 公钥密码体制 (public-key cryptosystem)，由 Rivest、Shamir、Adleman 于 1970 年代提出。

本讲的核心是一个正确性定理：$D(E(x)) \equiv x \pmod N$。它的证明出奇地短，但用到了全部关键零件：$ed \equiv 1 \pmod{(p-1)(q-1)}$ 的分解、费马小定理、以及「分别验证模 $p$ 与模 $q$、再合并」这一 CRT 式思路。证明中最需要小心的是 $\gcd(x,N) \ne 1$ 的边界情形——此时费马小定理的前提不成立，必须单独处理。

本讲还讨论为什么安全（依赖大整数分解的困难性，且这不是一个已被证明的定理，而是一个被广泛相信的假设）以及为什么教科书式 RSA 直接拿来用是不安全的（确定性加密 + 可乘性）。

核心概念的直观解释

密码学的基本舞台

• 定义：设 Alice 想在不安全信道（如互联网）上把消息 $x$（写作比特串，视作整数）发送给 Bob。Alice 对 $x$ 施加加密函数 (encryption function) $E$，把 $E(x)$ 发出去；Bob 收到后施加解密函数 (decryption function) $D$，恢复 $x$，即要求 $D(E(x)) = x$。信道上还坐着一个窃听者 Eve（”sniffer”），她能看到 $E(x)$。
• 直观解释（”它是什么意思？”）：把消息想象成写在一张明信片上的内容。Eve 是邮局里偷看明信片的人。加密就是把内容写进一个数字锁箱：任何人都能把箱子锁上（因为锁是公开的），但只有 Bob 手里那把钥匙能打开。Eve 可以随便拿走一万个锁好的箱子，也砸不开。
• 具体示例：Alice 要发 $x = 13$。她查到 Bob 的公开信息 $(N,e) = (55,3)$，算出 $E(13) = 13^3 \bmod 55 = 52$，把 $52$ 发出去。Bob 用自己的私钥 $d = 27$ 算出 $52^{27} \bmod 55 = 13$，拿到消息。Eve 只看到 $52$。

私钥密码 vs 公钥密码

• 定义：私钥密码体制 (private-key protocol) 要求 Alice 与 Bob 事先见面，共同约定一本秘密密码本（这本书同时扮演 $E$ 与 $D$ 的角色）。公钥密码体制 (public-key protocol) 中，每个人持有一对密钥：公钥 (public key) 全世界都能查，私钥 (private key) 只有本人知道。Alice 用 Bob 的公钥加密，Bob 用自己的私钥解密。
• 直观解释：私钥体制像两个人共享同一把抽屉钥匙：要共享，就得先见一面把钥匙递过去——可是如果两人隔着半个地球，递钥匙的通道本身可能就是不安全的。公钥体制解决的是密钥分发难题 (key distribution problem)。注意这里有一层看似矛盾的地方：Eve 和 Bob 都能看到 $E(x)$，凭什么 Bob 能解密而 Eve 不能？答案在于 Bob 手里有 Eve 没有的额外信息（$p, q, d$），所以两人并不对称。
• 具体示例：一个班 100 人要两两私密通信。私钥体制需要 $\binom{100}{2} = 4950$ 把共享密钥，且每把都要安全送达。公钥体制每人只需生成一对密钥，公开 100 个公钥即可，任何人都能从公开目录取用。

单向函数 (one-way function)

• 定义：一个函数 $f$ 称为单向的，如果正向计算容易（多项式时间可算），但逆向求值困难（已知 $y = f(x)$ 求 $x$ 无已知高效算法）。RSA 中候选的单向函数是 $f(x) = x^e \bmod N$。
• 直观解释：把一摞纸撕成碎片很容易，把碎片拼回去极难；把两种颜料混成一种颜色很容易，把混合色拆回两种原色极难。注意这里”容易/困难”是计算复杂度意义上的，不是”理论上不可能”——碎纸片理论上都能拼回去，只是组合太多。
• 具体示例：取 $N = 55, e = 3$。正向：$13 \mapsto 13^3 \bmod 55 = 52$，两个乘法搞定。逆向：已知 $52$，要找出满足 $x^3 \equiv 52 \pmod{55}$ 的 $x$。最笨的办法是把 $x = 0,1,\dots,54$ 全试一遍（$55$ 次）。当 $N$ 有 512 比特时，$N \approx 10^{154}$，试遍是不可能的。

模幂运算与快速幂的必要性

• 定义：$E(x) \equiv x^e \pmod N$，$D(y) \equiv y^d \pmod N$。计算 $x^y \bmod N$ 的反复平方法 (repeated squaring) 在讲次 4 已给出：把 $y$ 按二进制展开，递归地算 $x^{\lfloor y/2 \rfloor}$，再平方并按需乘一个 $x$。
• 直观解释：不要把 $x$ 乘 $y - 1$ 次（$y$ 可能有 $10^{154}$ 那么大，宇宙寿命也乘不完）。快速幂利用”平方能把指数翻倍”这一点，把代价从指数级降到线性于 $y$ 的比特数：算 $x^{2^{512}}$ 只需要 512 次平方，而不是 $2^{512}$ 次乘法。
• 具体示例：算 $52^{27} \bmod 55$。$27 = 11011_2$，只需 4 次平方 + 4 次乘法（共 8 次模乘），而不是 26 次乘法。

欧拉函数 (Euler’s totient function) 与欧拉定理

• 定义：对正整数 $n$，$\varphi(n)$ 表示 $\{1, 2, \ldots, n\}$ 中与 $n$ 互质的整数个数。当 $N = pq$（$p \ne q$ 为质数）时，$\varphi(N) = (p-1)(q-1)$。欧拉定理 (Euler’s theorem)：若 $\gcd(a, N) = 1$，则 $a^{\varphi(N)} \equiv 1 \pmod N$。
• 直观解释：$\varphi(N)$ 数的是模 $N$ 的乘法世界里”有逆元”的元素个数——即模 $N$ 的可逆元群 (group of units) 的大小。欧拉定理说：在这个群里，任何元素的 $\varphi(N)$ 次幂都回到单位元 1。费马小定理正是 $N = p$（质数）、$\varphi(p) = p - 1$ 的特例，所以欧拉定理是费马小定理的推广。
• 具体示例：$N = 55 = 5 \cdot 11$。$\varphi(55) = 4 \cdot 10 = 40$。与 $55$ 互质的数有 $1,2,3,4,6,7,8,9,12,\ldots$，共 40 个。取 $a = 13$：$13^{40} \bmod 55 = 1$。但取 $a = 5$（$\gcd(5,55) = 5 \ne 1$）：$5^{40} \bmod 55 = 45 \ne 1$——条件不可省。

数字锁 (digital lock)

• 定义：RSA 的核心机制是 Bob 构造一个”只能用自己的钥匙打开的公开锁”。锁本身 = 公钥 $(N, e)$；钥匙 = 私钥 $d$。
• 直观解释：这解释了为什么 RSA 表面上看不可能是对的。Eve 和 Bob 都能拿到 $E(x)$，看似同一起跑线；但 Bob 额外持有 $(p, q)$，从而能算出 $d$。Eve 想算出 $d$，就得先分解 $N$ 拿到 $p, q$——这是她与 Bob 唯一的、也是决定性的差距。
• 具体示例：Bob 选 $p = 5, q = 11$，算出 $N = 55$，公开 $(55, 3)$，锁就挂出去了。私钥 $d = 27$ 锁在抽屉里。Eve 知道 55，也知道 55 = 5 × 11（小数字好分解），所以她真的能攻破这个小例子——这正是为什么实际中 $N$ 要有几百比特。

完整证明与推导（核心）

定理 6.1（RSA 正确性 / RSA Correctness）：设 $p \ne q$ 为质数，$N = pq$，$e$ 满足 $\gcd(e, (p-1)(q-1)) = 1$，$d \equiv e^{-1} \pmod{(p-1)(q-1)}$。定义 $E(x) \equiv x^e \pmod N$，$D(y) \equiv y^d \pmod N$。则对每一个 $x \in \{0, 1, \ldots, N-1\}$，

证明策略：直接用分情形证明 (proof by cases)，配合费马小定理。思路分三步：

1. 用 $d$ 的定义把指数 $ed$ 写成 $1 + k(p-1)(q-1)$，于是 $x^{ed} - x$ 可以提出公因子 $x$；
2. 证明 $x^{ed} - x$ 同时被 $p$ 与 $q$ 整除。这里必须分两种情形：$p \nmid x$ 时用费马小定理，$p \mid x$ 时因为 $x$ 本身就是因子而”平凡成立”；
3. 用 $p, q$ 为质数这一事实，从”被 $p$ 整除且被 $q$ 整除”推出”被 $pq = N$ 整除”。

选这个策略的理由：费马小定理只在模质数且底数与模数互质时成立，而我们的目标是模合数 $N = pq$。把合数拆成两个质数分别处理，是把已知工具接到新问题上的标准手法（也是 CRT 的精神）。

逐步推导：

第 1 步：把指数改写成方便的形式。

因为 $d$ 是 $e$ 模 $(p-1)(q-1)$ 的逆元，由逆元定义

按同余的定义，存在整数 $k$ 使得

这里的 $k$ 是非负整数：因为 $e, d \ge 1$ 所以 $ed \ge 1$，故 $k(p-1)(q-1) = ed - 1 \ge 0$；又 $(p-1)(q-1) > 0$，所以 $k \ge 0$。

于是对任意整数 $x$：

第 2 步：证明 $x\left(x^{k(p-1)(q-1)} - 1\right)$ 被 $p$ 整除。

情形 A：$p \nmid x$（$x$ 不是 $p$ 的倍数）。

此时 $x \not\equiv 0 \pmod p$。因为 $p$ 是质数，模 $p$ 的非零元素全都与 $p$ 互质，即 $\gcd(x, p) = 1$。费马小定理（定理 6.4，见下）给出

两边同时取 $k(q-1)$ 次幂：

（这一步用的是”同余式可以两边同时乘方”：若 $u \equiv v \pmod p$，则 $u^m \equiv v^m \pmod p$，对 $m \ge 0$ 归纳可证。当 $k = 0$ 时 $k(q-1) = 0$，$x^0 = 1$，断言同样成立。）

于是 $x^{k(p-1)(q-1)} - 1 \equiv 1 - 1 \equiv 0 \pmod p$。这个因子被 $p$ 整除，所以整个乘积 $x\left(x^{k(p-1)(q-1)} - 1\right)$ 也被 $p$ 整除。

情形 B：$p \mid x$（$x$ 是 $p$ 的倍数）。

此时 (6.3) 的右边显含因子 $x$，而 $x$ 本身被 $p$ 整除，所以整个表达式被 $p$ 整除。这里完全不需要费马小定理——这正是证明最需要小心的”边界情形”。

两种情形穷尽了所有 $x$，因此 $x^{ed} - x$ 恒被 $p$ 整除。

第 3 步：对 $q$ 做完全对称的论证。

把上面每一步中的 $p$ 换成 $q$、把 $p - 1$ 换成 $q - 1$，逐字成立（$x^{k(p-1)(q-1)} = \left(x^{q-1}\right)^{k(p-1)}$，故情形 A 中用费马小定理模 $q$；情形 B 中 $q \mid x$ 时同样平凡）。结论：$x^{ed} - x$ 也被 $q$ 整除。

第 4 步：合并到模 $N$。

$p \mid (x^{ed} - x)$ 且 $q \mid (x^{ed} - x)$，其中 $p \ne q$ 均为质数，所以 $x^{ed} - x$ 是 $p$ 的倍数也是 $q$ 的倍数。因为 $p \neq q$ 均为质数，$pq$ 的质因数分解就是 $p \cdot q$，所以 $pq \mid (x^{ed} - x)$。

（这一步靠的是唯一分解 / 质数性质：若 $\gcd(p,q) = 1$，$p \mid m$ 且 $q \mid m$，则 $pq \mid m$。证明：$m = pa$，又 $q \mid pa$，而 $\gcd(q,p)=1$，由欧几里得引理 $q \mid a$，所以 $a = qb$，$m = pqb$。）

即 $x^{ed} - x \equiv 0 \pmod N$，也就是 $(x^e)^d \equiv x \pmod N$。这正是 (6.1) 所想证的，定理成立。$\blacksquare$

【证明机制解说】：这个证明最关键的一步是 (6.3) 的因式分解 $x^{ed} - x = x\left(x^{k(p-1)(q-1)} - 1\right)$。为什么必须提出公因子 $x$？因为费马小定理有前提 $\gcd(x,p) = 1$，当 $x$ 是 $p$ 的倍数时这个前提失效。而”提出 $x$”这一手恰好让 $p \mid x$ 的情形自动成立——这就是所谓“免费”地覆盖了边界情形。

第二个关键点是从模 $p$ 与模 $q$ 拼回模 $N$。我们从来没有直接计算 $x^{ed} \bmod N$（指数 $ed$ 可能有几百比特，直接算毫无直觉），而是分别在两个质数模下验证一个整除性陈述，最后靠 “$p,q$ 互质 ⟹ 乘积整除” 合并。这就是中国剩余定理的核心思想，只不过这里用的是它在整除语言下的等价形式。

第三个值得品味的地方是：整个证明只用到 $ed \equiv 1 \pmod{(p-1)(q-1)}$ 这一条关于 $d$ 的信息，没有用到 $d$ 具体是多少。这意味着任何满足 $ed \equiv 1 \pmod{(p-1)(q-1)}$ 的 $d$ 都能工作——例如 $d = 27$ 和 $d = 67$ 都是合法的私钥（$3 \cdot 67 = 201 \equiv 1 \pmod{40}$）。CS70 约定取 $1 \le d < (p-1)(q-1)$ 的那个代表元以保证唯一性。

证明的整体决策结构（ASCII 图）

下面这张图把整个证明的”分支树”画出来。它清楚显示：每个 $x$ 都要在两个质数模下各走一次二分支，共 4 条路径，而每一条路径的最后一步都是”$p$ 与 $q$ 都整除 ⟹ $N$ 整除”。

                        目标：证明 N | (x^{ed} - x)，其中 ed = 1 + k(p-1)(q-1)
                                              │
                    ┌─────────────────────────┴─────────────────────────┐
                    │  先提出公因子：  x^{ed} - x = x · ( x^{k(p-1)(q-1)} - 1 )
                    └─────────────────────────┬─────────────────────────┘
                                              │
        ┌─────────────────────────────────────┴─────────────────────────────────────┐
        │                                                                           │
   【模 p 这一侧】                                                            【模 q 这一侧】（完全对称）
        │                                                                           │
   ┌────┴─────┐                                                              ┌─────┴─────┐
   │          │                                                              │           │
 p ∤ x      p | x                                                          q ∤ x       q | x
   │          │                                                              │           │
   │          │                                                              │           │
 用 FLT     "平凡"                                                        用 FLT      "平凡"
 x^{p-1}≡1   x 本身是                                                  x^{q-1}≡1    x 本身是
   │        因子，                                                        │         因子，
   ▼        整个乘积被 p 整除                                             ▼        整个乘积被 q 整除
 x^{k(p-1)(q-1)}                                                       x^{k(p-1)(q-1)}
   = (x^{p-1})^{k(q-1)} ≡ 1                                              = (x^{q-1})^{k(p-1)} ≡ 1
   │                                                                     │
   ▼                                                                     ▼
 p | (x^{ed} - x)                                                       q | (x^{ed} - x)
   │                                                                     │
   └─────────────────────────────────┬───────────────────────────────────┘
                                     │
                     p, q 均为质数且 p ≠ q  ⇒  gcd(p,q) = 1
                     由欧几里得引理 / 唯一分解：p|m 且 q|m ⇒ pq | m
                                     │
                                     ▼
                        N = pq | (x^{ed} - x)   即   x^{ed} ≡ x (mod N)
                                     │
                                     ▼
                             D(E(x)) ≡ x  (mod N)   ✔ 对所有 x ∈ {0,…,N-1}

图中要注意的一点：FLT 用于”底数与模互质”的那一支，另一支靠因式分解里显含的因子 $x$ 平凡解决。这就是定理 6.1 与定理 6.5 共享的骨架——区别只在于前者用”整除”语言、后者用”同余 + CRT 唯一性”语言收尾。

定理 6.2（欧拉定理 / Euler’s Theorem）：设 $N$ 为正整数，$a$ 为整数且 $\gcd(a, N) = 1$。则

证明策略：用双射 + 乘积相等 (bijection and product comparison) 的手法——这正是费马小定理证明的推广。核心观察是：把可逆元集合整体乘以 $a$，得到的还是同一个集合（只是元素次序被打乱），所以”两个集合的所有元素之积”相等。

逐步推导：

令 $U = \{r \in \{1, 2, \ldots, N\} : \gcd(r, N) = 1\}$，按定义 $\vert U\vert = \varphi(N)$。注意 $N \notin U$（除非 $N = 1$，此处假设 $N \ge 2$），且 $1 \in U$。

第一步：定义映射 $\mu: U \to U$，$\mu(r) = ar \bmod N$（取 $1$ 到 $N$ 之间的代表元）。验证它是 $U$ 到 $U$ 的映射（良定义）。

设 $r \in U$。则 $\gcd(a, N) = 1$ 且 $\gcd(r, N) = 1$。若质数 $s \mid \gcd(ar, N)$，则 $s \mid ar$ 且 $s \mid N$；因 $s$ 为质数，$s \mid a$ 或 $s \mid r$。若 $s \mid a$ 则 $s \mid \gcd(a,N) = 1$，矛盾；若 $s \mid r$ 则 $s \mid \gcd(r,N) = 1$，矛盾。故 $\gcd(ar, N) = 1$。又 $\gcd$ 在模 $N$ 下不变（$r^{\prime} \equiv r \pmod N \Rightarrow \gcd(r^{\prime},N) = \gcd(r,N)$），所以 $\mu(r) \in U$。

第二步：证明 $\mu$ 是单射。

设 $\mu(r_1) = \mu(r_2)$，即 $a r_1 \equiv a r_2 \pmod N$。由讲次 5 的结论，$\gcd(a, N) = 1$ 时 $a$ 有模 $N$ 的乘法逆元 $a^{-1}$。两边乘 $a^{-1}$ 得 $r_1 \equiv r_2 \pmod N$，即 $r_1 = r_2$（两者都在 $\{1,\ldots,N\}$ 内）。

第三步：由有限集上的单射推出双射，再比较乘积。

$U$ 是有限集，单射 $\mu: U \to U$ 必为双射。因此 $\{\mu(r) : r \in U\}$ 作为多重集与 $U$ 完全相同，两边元素的乘积在模 $N$ 下相等：

第四步：约掉 $\prod_{r \in U} r$。

每个 $r \in U$ 都有模 $N$ 的逆元，所以乘积 $P = \prod_{r \in U} r$ 也有逆元 $P^{-1} \bmod N$（有限个可逆元之积仍可逆，归纳可证）。两边乘 $P^{-1}$：

【证明机制解说】：和费马小定理的证明是同一台机器，只是把”模质数的非零元素 $\{1,\ldots,p-1\}$”换成了”所有可逆元 $U$”。两个证明都用同一个技巧：用一个乘法动作把集合置换到自己身上，然后比较整体乘积。这个技巧在群论里叫”拉格朗日定理”的证明，在 CS70 里你只需要记住这个置换 + 乘积的模式。

系理 6.3（$\varphi(pq) = (p-1)(q-1)$）：若 $p \ne q$ 为质数，则 $\varphi(pq) = (p-1)(q-1)$。

证明：在 $\{1, 2, \ldots, pq\}$ 中，与 $pq$ 不互质的数恰好是被 $p$ 或 $q$ 整除的数。被 $p$ 整除的有 $q$ 个（$p, 2p, \ldots, qp$），被 $q$ 整除的有 $p$ 个（$q, 2q, \ldots, pq$），两者交集是被 $pq$ 整除的数，只有 $pq$ 本身，共 1 个。由容斥原理，

所以

定理 6.4（费马小定理 / Fermat’s Little Theorem，讲次 5 回顾）：设 $p$ 为质数，$a \in \{1, 2, \ldots, p-1\}$。则

证明策略：与定理 6.2 同一手法，但集合取 $\{1, \ldots, p-1\}$，并注意到 $a, 2a, \ldots, (p-1)a \bmod p$ 正好是这个集合的一个置换。

逐步推导：

第一步：$a, 2a, \ldots, (p-1)a$ 在模 $p$ 下两两不同，且都不为 $0$。

若 $ia \equiv ja \pmod p$ 且 $1 \le i < j \le p-1$，则 $p \mid (j-i)a$。因为 $p$ 是质数且 $p \nmid a$（$1 \le a \le p-1$），必有 $p \mid (j-i)$。但 $0 < j - i < p$，不可能。所以互不相同。又 $p \nmid ia$（$p \nmid i$ 且 $p \nmid a$），故模 $p$ 不为 $0$。

第二步：$S = \{1, \ldots, p-1\}$ 与 $S^{\prime} = \{a, 2a, \ldots, (p-1)a \bmod p\}$ 作为集合相同。

$S^{\prime}$ 是 $S$ 中 $p-1$ 个互不相同的非零元素构成的子集，而 $\vert S\vert = p - 1$，所以 $S^{\prime} = S$（只是次序不同）。

第三步：比较两边所有元素之积。

因为集合相同，两式左边相等模 $p$，故 $(p-1)! \equiv a^{p-1}(p-1)! \pmod p$。

第四步：约掉 $(p-1)!$。

$(p-1)!$ 的每个因子都在 $\{1,\ldots,p-1\}$ 中，都与 $p$ 互质，所以 $(p-1)!$ 可逆。两边乘其逆元得 $a^{p-1} \equiv 1 \pmod p$。$\blacksquare$

定理 6.5（RSA 正确性的 CRT 证明）：在定理 6.1 的设定下，$x^{ed} \equiv x \pmod N$。

证明策略：不用”整除”语言，而是显式地在模 $p$ 与模 $q$ 下分别算出同余式，再用中国剩余定理的唯一性把两个解合并。这比利诱解法更贴近 CRT 的”坐标视角”。

逐步推导：

第一步：模 $p$ 下计算。

• 若 $x \not\equiv 0 \pmod p$：由费马小定理 $x^{p-1} \equiv 1 \pmod p$，故 $(x^{p-1})^{k(q-1)} \equiv 1$，于是 $x^{ed} \equiv x \pmod p$。
• 若 $x \equiv 0 \pmod p$：(6.4) 最左端 $x^{ed}$ 含因子 $x$，故 $x^{ed} \equiv 0 \equiv x \pmod p$，直接观察即得。

所以恒有 $x^{ed} \equiv x \pmod p$。

第二步：对称地，$x^{ed} \equiv x \pmod q$。

第三步：合并。 记 $a_1$ 为 $x \bmod p$，$a_2$ 为 $x \bmod q$。同余方程组

由中国剩余定理（$\gcd(p,q) = 1$）在模 $pq = N$ 下有唯一解。而 $y \equiv x^{ed}$ 与 $y \equiv x$ 都满足这个方程组，故它们在模 $N$ 下相等：

【证明机制解说】：这个证明把 CRT 的”唯一性”当成了武器。注意它其实没有构造解，只是说”两个候选解满足同一个模 $p$ 同余与同一个模 $q$ 同余，所以必然相同”——唯一性就是用来做这种”等号传递”的。对 $x = 15$ 这个具体例子（情形 $p \mid x$、$q \nmid x$）验算：$x^{ed} = 15^{81}$，$15^{81} \bmod 5 = 0 = 15 \bmod 5$（平凡情形），$15^{81} \bmod 11 = 4 = 15 \bmod 11$（费马情形）。用 CRT 从 $(0 \bmod 5, 4 \bmod 11)$ 重建，在 $0$ 到 $54$ 中唯一满足的是 $15$。两个同余条件被同时满足的唯一 $y$ 就是 $15$ 本身。

反例 6.6（$\gcd(x, N) \ne 1$ 时费马小定理的前提确实会失效）

定理 6.1 的证明之所以要分两种情形，是因为”若 $x$ 是 $p$ 的倍数则 $x^{p-1} \equiv 1 \pmod p$”这句话是假的。取 $p = 5$：$x = 5$ 时 $5^4 = 625$，而 $625 \bmod 5 = 0 \ne 1$。所以情形 B 不能归约到情形 A，必须靠”提出公因子 $x$”独立处理。

同理，欧拉定理（定理 6.2）的条件 $\gcd(a, N) = 1$ 也不可省。取 $N = 55, a = 5$：$\varphi(55) = 40$，而 $5^{40} \bmod 55 = 45 \ne 1$。把 $\gcd$ 条件去掉，欧拉定理就崩了。

反例 6.7（$e$ 必须与 $\varphi(N)$ 互质）

RSA 要求 $e$ 与 $(p-1)(q-1)$ 互质，因为解密密钥 $d$ 定义为 $e$ 的模 $\varphi(N)$ 逆元，而逆元存在当且仅当互质（讲次 5 定理）。取 $p = 5, q = 11$，$\varphi(N) = 40$，若误取 $e = 5$：$\gcd(5, 40) = 5 \ne 1$，$5d \bmod 40$ 的取值只能落在 $\{0, 5, 10, 15, 20, 25, 30, 35\}$ 里，永远取不到 1，所以不存在任何 $d$。

更糟的是，加密本身还会变得不可逆。取 $x = 2$：$E(2) = 2^5 \bmod 55 = 32$。在 $d = 1, 2, \ldots, 39$ 中逐一验算 $32^d \bmod 55$，没有任何一个 $d$ 能还原出 2。同理 $x = 3$：$E(3) = 3^5 \bmod 55 = 23$，同样无 $d$ 可解。所以 $e$ 的选择不是”看起来差不多就行”，互质是硬性要求。

与经典问题的联系

问题实际背景

Alice 和 Bob 想在不安全信道上私密通信，且从未见过面（无法预先共享密钥）。Eve 可以监听并截获所有密文 $E(x)$。目标是：即使 Eve 拿到了 $E(x)$、公钥 $(N,e)$、以及任意多条其他密文，她也无法得知 $x$。

数学建模

RSA 把这个问题建模成模算术中的一个”可逆但不可逆向求值”的映射：

方案设计

1. 密钥生成 (key generation)：
   1. 随机选取两个大质数 $p \ne q$（实际各约 512 比特），令 $N = pq$。
   2. 计算 $\varphi(N) = (p-1)(q-1)$。
   3. 选取 $e$ 使 $\gcd(e, \varphi(N)) = 1$（常用 $e = 3$ 或 $e = 65537$）。
   4. 用扩展欧几里得算法计算 $d \equiv e^{-1} \pmod{\varphi(N)}$。
   5. 公开 $(N, e)$，销毁 $p, q, \varphi(N)$ 的痕迹，保密 $d$。
2. 加密：$E(x) \equiv x^e \pmod N$（用快速幂）。
3. 解密：$D(y) \equiv y^d \pmod N$（用快速幂）。

完整通信流程（ASCII 图）

            ┌──────────────────────── 公开目录 (Eve 也能看) ────────────────────────┐
            │                     Bob 的公钥  (N, e)                              │
            └───────────────────────────────┬─────────────────────────────────────┘
                                            │  Alice 读取
   ┌──────────────┐                         ▼                          ┌──────────────┐
   │    Alice     │        y = x^e mod N  （密文）                     │     Bob      │
   │  明文 x       │ ────────────────────────────────────────────────►  │ 私钥 d       │
   │              │         不安全信道                                 │ 保存 p, q    │
   └──────────────┘                                                    └──────┬───────┘
                                            ▲                                 │
                                            │  Eve 只能看到  (N, e, y)         │ x = y^d mod N
                                            │  想拿到 x 必须先分解 N = p·q     ▼
                                     ┌──────┴───────┐                  恢复明文 x
                                     │     Eve      │
                                     │  窃听者      │   已知 (N,e,y)，求 x：
                                     │              │   ① 穷举 x          → 需要 ~N 次尝试
                                     └──────────────┘   ② 分解 N 得 p,q   → 无已知多项式算法
                                                          再求 d = e^-1 mod (p-1)(q-1)

完整小数字手算演示（官方 Note 的算例，逐步展开）

取 $p = 5$，$q = 11$。

第一步：算 $N$ 与 $\varphi(N)$。

第二步：选 $e$。 取 $e = 3$。检查 $\gcd(3, 40) = 1$ ✔。

第三步：算 $d \equiv 3^{-1} \pmod{40}$。 用扩展欧几里得算法：

所以 $d \equiv -13 \equiv 40 - 13 = 27 \pmod{40}$。验算：$3 \times 27 = 81$，$81 \bmod 40 = 1$ ✔。

Bob 的公钥是 $(55, 3)$，私钥 $d = 27$。

第四步：加密 $x = 13$。

\(13^2 = 169, \qquad 169 \bmod 55 = 169 - 3 \times 55 = 169 - 165 = 4.\) \(13^3 = 13^2 \times 13 = 169 \times 13 = 2197, \qquad 2197 \bmod 55 = 2197 - 39 \times 55 = 2197 - 2145 = 52.\)

所以 $y = E(13) = 52$。Alice 把 $52$ 发出去。

第五步：解密 $y = 52$，算 $52^{27} \bmod 55$（用反复平方法）。

$27$ 的二进制是 $11011_2$。按从低位到高位扫描：

得到 $D(52) = 13$，正是原始消息 $x$ ✔。

第六步：验证全消息空间。 对 $x = 0, 1, 2, \ldots, 54$ 全部 55 个值逐一验算 $D(E(x))$，结果全部等于 $x$，无反例。几个含边界情形的例子：

注意 $x = 15$ 时 $E(15) = 20$ 而 $E(25) = 5$——加密可以”乱序”，解密仍然准确。这直观地显示了 $E$ 是整个 $\{0,1,\ldots,54\}$ 上的双射，包括那些与 $55$ 不互质的元素。（注意 $E$ 不是 $\mathbb{Z}/55$ 的加法群同态，也不是乘法群 $(\mathbb{Z}/55)^*$ 上的置换——它是定义域和值域都为整个 $\mathbb{Z}/55$ 的双射，把 $\gcd(x,55) \ne 1$ 的那些点也一并映射到别的点上。）

第七步：$ed = 81 = 1 + k(p-1)(q-1)$ 中的 $k$。

所以 $ed = 1 + 2 \times 4 \times 10 = 81$，与定理 6.1 第 1 步的形式一致。

为什么安全：依赖大整数分解的困难性

RSA 的安全性建立在这样一个基本假设 (basic assumption) 上：

已知 $N$、$e$ 与 $y \equiv x^e \pmod N$，不存在求 $x$ 的高效算法。

Eve 的两条已知攻击路线：

1. 穷举 $x$：对每个候选 $x$ 检查 $x^e \equiv y \pmod N$ 是否成立。需要约 $N$ 次尝试。当 $N$ 是 512 比特的数（$N \approx 2^{512} \approx 1.34 \times 10^{154}$）时完全不可行。
2. 分解 $N$：先求出 $p, q$，再算 $\varphi(N) = (p-1)(q-1)$，再算 $d = e^{-1} \bmod \varphi(N)$，就得到私钥。这条路线需要高效地把 $N$ 分解为质因数，而这一问题被广泛相信对大整数没有多项式时间算法。

必须强调：RSA 的安全性没有被形式化证明。它依赖两个假设：(i) 攻破 RSA 本质上等价于分解 $N$；(ii) 分解 $N$ 是困难的。两者都是”被广泛相信”而非”已被证明”。

这里有一个极具讽刺意味也极具启发性的对比：判定一个数是否质数有高效算法（$O((\log n)^k)$，多项式于比特数），但已知 $n$ 是合数却找不到它的因子。RSA 的全部可行性就架在这个区分上——Bob 能高效造出 $N = pq$，但没人能高效拆开它。

质数如何生成

• 质数定理 (Prime Number Theorem)：令 $\pi(n)$ 表示不超过 $n$ 的质数个数。对所有 $n \ge 17$， \(\pi(n) \ge \frac{n}{\ln n}, \qquad \text{且} \quad \lim_{n \to \infty} \frac{\pi(n)}{n / \ln n} = 1.\)
• 怎么用：取 $n = 2^{512}$，则 $2^{512}$ 以下大约 $\frac{2^{512}}{512 \ln 2}$ 个数是质数，比例约 $\frac{1}{512 \ln 2} \approx \frac{1}{355}$。也就是说每 355 个 512 比特的数里就有一个质数。所以 Bob 只需随机抽 512 比特的奇数，做素性测试，平均试约 355 个就能找到一个质数——快得可以忽略不计。
• $n \ge 17$ 时 $\pi(n) \ge n/\ln n$ 这个下界是个”够用就好”的粗糙界限：实际 $\pi(100) = 25 > 100/\ln 100 \approx 21.7$，$\pi(1000) = 168 > 144.8$，$\pi(10000) = 1229 > 1085.7$，$\pi(100000) = 9592 > 8685.9$。定理只说 $n/\ln n$ 是下界，并不声称它精确（$\pi(n)$ 通常更大）。

$e$ 的选取：为什么常用 65537

$e$ 的选取要同时满足：$\gcd(e, \varphi(N)) = 1$，且 $e$ 的二进制表示里 1 的个数尽量少（快速幂的乘法次数正比于 1 的个数）。

• $e = 3$：只有 2 个 1，最快。但小指数有额外风险：实际实现中若不做填充，当 $x$ 很小时 $x^3 < N$ 可能成立，于是 $x^3 \bmod N = x^3$ 原样保留，攻击者直接在整数上开立方根就恢复了 $x$（这就是”低指数攻击”）。
• $e = 65537 = 2^{16} + 1$：二进制是 $10000000000000001_2$，只有 2 个 1，所以快速幂只需 16 次平方 + 1 次乘法，几乎和 $e = 3$ 一样快；同时 $65537$ 本身是质数，只要 $p - 1$ 与 $q - 1$ 都不是 $65537$ 的倍数（正常随机选大质数时几乎必然如此），就自动有 $\gcd(65537, \varphi(N)) = 1$。这是当今最通行的选择。

实用考虑：快速幂与运行代价

RSA 里 Alice 与 Bob 各自只需要做两件非平凡的事：

1. Bob 找两个大质数（用素性测试 + 随机采样，如上）。
2. Alice 算 $x^e \bmod N$，Bob 算 $y^d \bmod N$（用反复平方法）。

代价分析：$e, d < N$，故 $e, d$ 的比特数为 $O(\log N)$；反复平方的乘法次数是 $O(\log N)$；每次乘法是 $O(\log N)$ 比特的数相乘，用小学竖式乘法需 $O((\log N)^2)$ 次位运算（CS170 会讲更快的算法）。所以总代价

这是关于 $\log N$ 的多项式——所以哪怕 $N$ 有几百比特，任何袖珍计算设备都能在瞬间完成加密解密。而 Eve 要做的分解，被认为需要远超全世界所有最先进计算机联合起来的算力。

教科书 RSA 为什么不安全（必须加随机填充）

上面的方案被称为教科书 RSA (textbook RSA)——它证明了数学上的可逆性，但作为密码系统是不安全的，有两个致命缺陷：

缺陷 1：确定性加密 (deterministic encryption)。 同一明文 $x$ 永远加密成同一个密文 $x^e \bmod N$。于是 Eve 不需要解密也能获得信息：她可以预先建一张”常见明文 → 密文”的表（例如所有可能的”是/否”、所有小额转账金额、所有人的名字）。看到密文，查表即得明文。这违反现代密码学要求的语义安全性 (semantic security)。

缺陷 2：可乘性 (multiplicative malleability)。 因为 $E$ 就是模 $N$ 的幂运算，它保持乘法结构：

验算（$N = 55, e = 3$）：

这个性质让攻击者在不知道明文的情况下伪造出有意义的新密文：给定 $E(x)$，他能构造 $E(2x) = E(x) \cdot E(2)$。在拍卖、转账等场景里这是灾难性的——攻击者可以把”转账 100 元”的密文改成”转账 200 元”的密文，而收方解密后完全无法察觉。

解法：加密前对明文做随机化的填充 (padding)——在明文里混入足够长的随机比特（如 OAEP），使得 (i) 同一明文的两次加密产生不同密文，破坏确定性；(ii) 明文结构被随机数掩盖，破坏可乘性的可利用性。填充后的方案才叫 PKCS#1、RSA-OAEP，是实际部署的版本。

与其他讲次的关联

• 讲次 4（Modular Arithmetic，模运算）：RSA 的加密 $x^e \bmod N$ 与解密 $y^d \bmod N$ 完全建立在同余语言上。讲次 4 的”乘法次序无关、可以随时约减”是我们在第 2 步里把 $x^{ed}$ 拆成 $\left(x^{p-1}\right)^{k(q-1)}$ 并逐层约减 $(p-1)$ 次幂的依据；讲次 4 的反复平方法 (mod-exp) 则是 RSA 能实用的全部技术基础，本讲的 $52^{27}$ 手算表格就是用它的 5 步跟踪。此外，讲次 4 的”$x$ 有模 $m$ 逆元 $\iff \gcd(m,x) = 1$”直接决定了 $e$ 必须与 $\varphi(N)$ 互质。
• 讲次 5（Euclid, FLT, CRT）：
  • 扩展欧几里得算法 (Extended Euclid) 是计算 $d \equiv e^{-1} \pmod{(p-1)(q-1)}$ 的工具。本讲 $d = 27$ 的求法就是 $\gcd(3,40) = 1 = 40 - 13 \times 3$，读出 $b = -13 \equiv 27$。
  • 费马小定理 (FLT) 是定理 6.1 第 2 步情形 A 的唯一工具，也是定理 6.5 第一步的依据。
  • 中国剩余定理 (CRT) 在定理 6.5 里以”唯一性”的面目出现；讲次 5 的”基向量”视角（$b_1 \equiv (1 \bmod p, 0 \bmod q)$）正好解释了为什么模 $p$ 与模 $q$ 上各满足一个同余就能唯一确定模 $pq$ 的解。本讲里 $\varphi(pq) = (p-1)(q-1)$ 的证明则用了讲次 5/14 的容斥计数。
  • 讲次 5 的唯一分解 / 欧几里得引理（$p \mid ab, p$ 质数 $\Rightarrow p \mid a$ 或 $p \mid b$）在定理 6.1 第 4 步”$p,q$ 互质 ⟹ $pq \mid m$”中发挥作用。
• 讲次 3（Induction，归纳法）：定理 6.2 第 4 步”有限个可逆元之积仍可逆”以及”同余式两边可同时乘方”都靠对个数做简单归纳。
• 讲次 2（Proof Techniques II，分情形/反证）：定理 6.1 的核心结构就是分情形证明（$p \mid x$ vs $p \nmid x$），而 $\varphi$ 的存在性讨论与唯一性论证（定理 6.5 第三步）用的是反证/唯一性论证。
• 讲次 7（Polynomials，多项式）：多项式上的单向函数构造（如 $P(x)$ 求根困难）与 RSA 共享同一套”正向易、逆向难”的设计哲学；本讲末尾提到的随机填充之所以能破坏确定性，靠的正是下一讲的”用有限域上的随机点定义对象”的思想。
• 讲次 20（Expectations & Linearity，哈希与负载均衡）：本讲的”随机采样质数、平均试 355 个成功”正是”随机化算法 + 期望分析”的典型应用，其期望值计算与讲次 20 的期望线性性一脉相承。

关键要点

1. 密钥生成三步：$N = pq$（$p \ne q$ 为大质数）→ $\varphi(N) = (p-1)(q-1)$ → 取 $\gcd(e, \varphi(N)) = 1$，算 $d \equiv e^{-1} \pmod{\varphi(N)}$。公钥 $(N,e)$ 公开，$p,q,d$ 保密。
2. 加解密：$E(x) \equiv x^e \pmod N$，$D(y) \equiv y^d \pmod N$。正确性的形式化陈述是 $(x^e)^d \equiv x \pmod N$ 对所有 $x \in \{0,\ldots,N-1\}$ 成立。
3. 正确性证明的黄金链条：$ed \equiv 1 \pmod{(p-1)(q-1)}$ ⟹ $ed = 1 + k(p-1)(q-1)$ ⟹ 提出公因子 $x$ 得 $x^{ed} - x = x\left(x^{k(p-1)(q-1)} - 1\right)$ ⟹ 分情形证它被 $p$ 整除（$p \nmid x$ 用 FLT；$p \mid x$ 靠 $x$ 本身是因子）⟹ 对称得被 $q$ 整除 ⟹ $pq = N$ 整除它。
4. 边界情形的处理口诀：”能被费马就费马，不能费马就提因子“。$\gcd(x,N) \ne 1$ 时费马小定理前提失效，靠因式分解中显含的 $x$ 平凡解决。
5. 安全性的确切边界：RSA 的安全性未被证明，它依赖”分解大整数是困难的”这一广泛相信但未证明的假设。有高效素性测试，但没有已知的高效分解算法——RSA 就架在这个不对称上。
6. 教科书 RSA 必须加填充：确定性（同明文同密文 ⟹ 字典攻击）与可乘性（$E(x_1)E(x_2) = E(x_1x_2)$ ⟹ 密文可被篡改）是两个必须靠随机填充修补的结构性缺陷。

常见误区与注意事项

1. 误以为”定理对所有 $x$ 成立”就无需求证边界情形。官方 Note 特别把消息空间写作”除 $0$ 和 $1$ 之外的模 $N$ 的数”（因为 $0$ 与 $1$ 加密后就是自己，不承载信息），但定理 7.1 的陈述是对所有 $x \in \{0,1,\ldots,N-1\}$，且证明确实覆盖了 $0$ 与 $1$（$x=0$：$p \mid 0$ 且 $q \mid 0$，两分支都走情形 B）。不要把”消息集合”与”定理成立的范围”混为一谈。

2. 把费马小定理的条件写漏。费马小定理是”对质数 $p$ 和 $a \in \{1,\ldots,p-1\}$ 有 $a^{p-1} \equiv 1 \pmod p$”，不是对所有模数成立，也不是对任意 $a$ 成立（$a \equiv 0 \pmod p$ 时 $a^{p-1} \equiv 0$）。RSA 证明中 $p \mid x$ 的情形正是这个条件失效的地方。

3. 忘记”$e$ 必须与 $\varphi(N)$ 互质”是硬要求。$d$ 定义为 $e$ 的模 $\varphi(N)$ 逆元，而逆元存在当且仅当 $\gcd(e, \varphi(N)) = 1$。取 $e = 5, \varphi(N) = 40$ 时，$5d \bmod 40$ 永远取不到 1，且加密变得不可逆（$E(2) = 32$ 在任何 $d$ 下都解不回 2）。

4. 把 $\varphi(N)$ 与 $N-1$ 混淆。$\varphi(N) = (p-1)(q-1) = N - p - q + 1$，比 $N - 1$ 小得多（$N = 55$ 时是 40 而不是 54）。$d$ 是模 $\varphi(N)$ 的逆元，不是模 $N$ 的，也不是模 $N-1$ 的。写成 $\bmod (N-1)$ 会导致解密失败。

5. 误把”$d$ 唯一”理解成”$d$ 只有一个数值”。$d$ 只在模 $\varphi(N)$ 意义下唯一。$N = 55$ 时 $d = 27$ 与 $d = 67$ 都是合法私钥（$3 \times 67 = 201 \equiv 1 \pmod{40}$）。实现中取 $1 \le d < \varphi(N)$ 的代表元只是为了确定化。

6. 认为”$N$ 公开所以 $p,q$ 也就暴露了”。$N$ 公开不等于分解可行。对 512 比特的 $p,q$，$N$ 有约 1024 比特，而分解被认为没有多项式时间算法。同时要注意 $p$ 与 $q$ 不能太接近（见下一条）——否则有专门的快速分解法。

7. 忽略 $p$ 与 $q$ 的选取细节。若 $p$ 与 $q$ 太接近，费马分解法 (Fermat factorization) 会瞬间拆开 $N$：它利用 $N = pq = \left(\frac{p+q}{2}\right)^2 - \left(\frac{p-q}{2}\right)^2$，从 $a = \lceil \sqrt{N} \rceil$ 起逐一测试 $a^2 - N$ 是否为完全平方。差额越小，需要的步数越少（约 $\frac{(\sqrt{q} - \sqrt{p})^2}{2}$ 步）。实测：$p = 1000003, q = 1000033$（差 30）时费马法第 0 步就成功；而 $p = 3, q = 1000003$ 时需约 498270 步才拆开。所以 RSA 实现必须保证 $\vert p - q\vert $ 足够大（通常要求 $p,q$ 长度相同但差值也很大），同时还要避开”$p-1$ 或 $q-1$ 只有小质因子”的弱质数。

思考题（带答案）

Q1. 取 $p = 7$，$q = 13$，$e = 5$。（a）求 $N$ 与 $\varphi(N)$；（b）求私钥 $d$；（c）对 $x = 10$ 完成一次加密与解密，逐步写出中间值；（d）验证 $x = 14$ 的情况（注意 $14 = 2 \times 7$，是 $p$ 的倍数），说明定理 6.1 的哪个分支在处理它。

Q2. 有人提出一个”简化版 RSA”：取 $N = pq$ 后，不用 $\varphi(N) = (p-1)(q-1)$，而是直接令 $d \equiv e^{-1} \pmod{N-1}$。请用 $p = 5, q = 11, e = 3$ 构造一个具体的失败例子，并解释这个方案在哪个环节崩掉。

Q3. 攻击者 Eve 截获了 Bob 公钥 $(N, e) = (55, 3)$ 下同一个明文 $x$ 的两次密文，分别是 $y_1 = 52$ 与 $y_2 = 8$。已知 $x$ 是 $\{2, 3, \ldots, 54\}$ 中的某个整数。（a）判断这两次密文是否可能来自同一个明文，并说明这是教科书 RSA 的什么缺陷；（b）如果 $x_1 = 13$ 对应 $y_1 = 52$，且 Eve 还截获了另一条密文 $y_3$，她能伪造出 $E(x_1^2)$ 吗？给出具体计算。