RSA 为什么能解密：欧拉定理与中国剩余定理

全文分三层：

1. 通俗理解：公钥、私钥、"单向门"
2. 实际用处：HTTPS 证书、签名，以及几个经典翻车
3. 数学原理：欧拉定理、为什么 $ed \equiv 1$、CRT 加速，附手算例子

第一层：通俗理解

1.1 一把谁都能锁、只有你能开的挂锁

RSA 的公钥像一把打开着的挂锁：你可以复制几万把发给全世界，任何人都能用它把箱子锁上。但钥匙只有你有，所以锁上的箱子只有你能打开。

1.2 单向门：乘起来容易，拆开难

RSA 的安全性来自一件很朴素的事：

• 两个 300 位的素数 $p, q$ 乘起来，电脑一眨眼就算完；
• 但给你乘积 $n = pq$，让你把 $p, q$ 找回来，目前最快的经典算法也要算到天荒地老。

私钥 $d$ 是用 $p$ 和 $q$ 算出来的。外人只知道 $n$，拆不开 $n$，就算不出 $d$。这种"一个方向容易、反方向很难，但有暗门（$p, q$）就容易"的结构，叫陷门单向函数。

1.3 为什么"乘方再乘方"能回到原点

想象一个钟面，但不是 12 格，而是很多格。你从 $m$ 出发，每次乘以 $m$ 往前走。走了恰好 $\varphi(n)$ 步之后，一定会回到 $1$；再多走一步，就回到 $m$ 本身。

RSA 选的 $e$ 和 $d$ 满足 $e \cdot d = 1 + k\varphi(n)$，所以"先走 $e$ 倍，再走 $d$ 倍"等于绕了 $k$ 整圈再多走一步，刚好回到 $m$。外人不知道一圈有多长（$\varphi(n)$），所以不知道该走多少步回去。

第二层：实际用处

2.1 加密和签名

• 加密：用别人的公钥锁，只有对方能开。实际中 RSA 只用来加密一把随机的 AES 密钥（"数字信封"），大数据交给 AES。
• 签名：反过来，用自己的私钥"锁"一份文件的哈希值，所有人都能用公钥打开验证。打得开，就说明一定是私钥持有者签的。

HTTPS 证书、软件更新签名、PGP 邮件、SSH 登录，几十年来大多用 RSA。现在新系统更多换成了椭圆曲线（见《椭圆曲线》），因为同样安全时密钥短得多：

2.2 几个经典翻车

第三层：数学原理

3.1 密钥生成

1. 选两个大素数 $p, q$，令 $n = pq$；
2. 计算 $\varphi(n) = (p-1)(q-1)$，这是 $\{1, \dots, n\}$ 中与 $n$ 互素的数的个数；
3. 选 $e$ 满足 $\gcd(e, \varphi(n)) = 1$（常用 $e = 65537$）；
4. 用扩展欧几里得算法求 $d \equiv e^{-1} \pmod{\varphi(n)}$。

公钥 $(n, e)$，私钥 $d$。

3.2 欧拉定理：拉格朗日定理的推论

$\mathbb{Z}_n^\times$（模 $n$ 的可逆元）在乘法下是一个有限群，阶为 $\varphi(n)$。由拉格朗日定理，每个元素的阶整除群的阶，所以

$$a^{\varphi(n)} \equiv 1 \pmod n,\qquad \gcd(a, n) = 1.$$

这就是欧拉定理；$n = p$ 为素数时它就是费马小定理 $a^{p-1} \equiv 1$。

3.3 为什么解密正确

由 $ed = 1 + k\varphi(n)$，

$$c^d = (m^e)^d = m^{1 + k\varphi(n)} = m \cdot \big(m^{\varphi(n)}\big)^k \equiv m \cdot 1^k = m \pmod n.$$

3.4 CRT 加速

由中国剩余定理，$\mathbb{Z}_n \cong \mathbb{Z}_p \times \mathbb{Z}_q$ 是环同构。所以可以把 $c^d \bmod n$ 拆成两半分别算：

$$m_p = c^{\,d \bmod (p-1)} \bmod p,\qquad m_q = c^{\,d \bmod (q-1)} \bmod q,$$

再把 $(m_p, m_q)$ 拼回模 $n$ 的唯一解。指数可以先模 $p-1$ 缩小，也是费马小定理的功劳。模数位数减半，乘法便宜约 4 倍，指数位数也减半，整体快 3 到 4 倍。

3.5 手算例子

总结