前言

上一节的 Diffie-Hellman 依靠离散对数问题，让双方能够在公开信道中建立共享秘密。RSA 走的是另一条路线：它把两个大素数相乘得到公开模数，再利用模运算中一种“容易正向计算、缺少陷门时难以逆转”的结构构造公钥与私钥。

RSA 的公式经常被压缩成两行：

$$C=M^e\mathrm{mod}n$$

$$M=C^d\mathrm{mod}n$$

真正需要理解的并不是背下 $e$、$d$ 和 $n$，而是回答下面几个问题：

• 为什么公钥指数 $e$ 和私钥指数 $d$ 必须互为模逆；
• 为什么模逆不是普通意义上的倒数；
• 为什么先做 $e$ 次幂、再做 $d$ 次幂能够回到原消息；
• 数千位指数为什么仍能高效计算；
• 私钥运算为什么可以借助中国剩余定理加速。

本文从互质、欧拉函数和模逆开始，使用一组可手算的小参数完整生成 RSA 密钥，并把正确性证明、快速模幂和 CRT 加速串成一条主线。文中的小素数只用于教学，绝不能用于真实系统。

Crypto 专栏：https://blog.csdn.net/r_feynman_/category_13190241.html

Crypto 密码解析实战靶场：https://blog.csdn.net/r_feynman_/category_13194584.html

---

一、RSA 建立在哪些数学对象上

1.1 从两个素数得到模数

选择两个不同的大素数 $p$、$q$，计算：

$$n=pq$$

$n$ 称为 RSA 模数。公钥会公开 $n$，私钥则必须保护与 $p$、$q$ 有关的信息。

为什么不直接公开 $p$ 和 $q$？因为知道分解后，就能计算欧拉函数：

$$\phi (n)=\phi (pq)=(p-1)(q-1)$$

进而求出私钥指数。RSA 的陷门正藏在这里：

• 从 $p,q$ 计算 $n$ 很容易；
• 对足够大的合规 RSA 模数，从 $n$ 恢复 $p,q$ 被认为很困难；
• 持有 $p,q$ 的合法用户可以轻松构造私钥。

这里要避免一句过度简化的话：“破解 RSA 等价于分解 $n$。”已知的通用私钥恢复方式确实与分解高度相关，但严谨地说，不能把所有 RSA 安全命题都直接写成已证明的数学等价。工程安全还取决于填充、随机数、密钥长度、实现和协议使用方式。

---

1.2 互质为什么重要

若两个整数 $a,b$ 的最大公约数为 $1$，记作：

$$\gcd (a,b)=1$$

则称 $a$ 与 $b$ 互质。

RSA 选择公钥指数 $e$ 时要求：

$$1<e<\phi (n),\gcd (e,\phi (n))=1$$

这不是形式要求，而是为了保证 $e$ 在模 $\phi (n)$ 意义下存在乘法逆元。若 $e$ 与 $\phi (n)$ 不互质，就无法找到满足要求的私钥指数 $d$。

例如模 $12$ 下，$5$ 存在逆元，因为：

$$5\times 5=25\equiv 1(\mathrm{mod}12)$$

而 $6$ 不存在逆元。因为 $6x$ 永远是 $6$ 的倍数，不可能模 $12$ 余 $1$。

---

1.3 欧拉函数到底在数什么

欧拉函数 $\phi (n)$ 表示 $1$ 到 $n$ 之间与 $n$ 互质的整数个数。若 $p$ 是素数，则：

$$\phi (p)=p-1$$

因为 $1,2,\dots ,p-1$ 都与 $p$ 互质。

若 $p,q$ 是不同素数，则：

$$\phi (pq)=(p-1)(q-1)$$

也可以从排除法理解。在 $1$ 到 $pq$ 的整数中，去掉 $p$ 的倍数和 $q$ 的倍数，再修正被重复排除的 $pq$，最终得到：

$$pq-q-p+1=(p-1)(q-1)$$

RSA 并不是“因为有欧拉函数所以安全”，而是利用了一个不对称性：知道 $p,q$ 时计算 $\phi (n)$ 很容易；只公开 $n$ 时，想得到同样的信息通常要面对大整数分解问题。

---

二、欧拉定理如何支撑 RSA

2.1 欧拉定理

若：

$$\gcd (a,n)=1$$

则欧拉定理给出：

$$a^{\phi (n)}\equiv 1(\mathrm{mod}n)$$

它说明，在模 $n$ 的可逆元素集合中，把元素连续相乘到特定周期后会回到单位元 $1$。

例：取 $(n=6)$，$\phi (6)=2$，模6可逆元为 $1,5$。取 $(a=5)$，$5^2=25\equiv 1(\mathrm{mod}6)$，自乘2次后回到单位元 $1$。

假设某个指数可以写成：

$$ed=1+k\phi (n)$$

对于与 $n$ 互质的消息 $M$，有：

$$M^{ed}=M^{1+k\phi (n)}$$

拆开后得到：

$$M^{ed}=M{\left(M^{\phi (n)}\right)}^k$$

根据欧拉定理：

$$M^{\phi (n)}\equiv 1(\mathrm{mod}n)$$

所以：

$$M^{ed}\equiv M\cdot 1^k\equiv M(\mathrm{mod}n)$$

这正是 RSA 解密正确性的核心。

---

2.2 $ed\equiv 1$ 到底表示什么

RSA 要求：

$$ed\equiv 1(\mathrm{mod}\phi (n))$$

含义不是普通等式 $ed=1$，而是 $ed-1$ 能被 $\phi (n)$ 整除。因此存在整数 $k$，使得：

$$ed-1=k\phi (n)$$

也就是：

$$ed=1+k\phi (n)$$

这一步把“公私钥指数互为模逆”与欧拉定理连接了起来。

---

2.3 消息与 $n$ 不互质怎么办

只用欧拉定理证明时，会带上 $\gcd (M,n)=1$ 的条件。但 RSA 正确性并不只覆盖与 $n$ 互质的消息。

更完整的证明可以分别在模 $p$、模 $q$ 下进行。以模 $p$ 为例：

• 若 $M\equiv 0(\mathrm{mod}p)$，显然 $M^{ed}\equiv M\equiv 0(\mathrm{mod}p)$；
• 若 $M\not\equiv 0(\mathrm{mod}p)$，由费马小定理可得 $M^{p-1}\equiv 1(\mathrm{mod}p)$。

由于 $p-1$ 和 $q-1$ 都整除 $\phi (n)$，可推出：

$$M^{ed}\equiv M(\mathrm{mod}p)$$

同理：

$$M^{ed}\equiv M(\mathrm{mod}q)$$

$p$、$q$ 互质，根据中国剩余定理：

$$M^{ed}\equiv M(\mathrm{mod}pq)$$

即：

$$M^{ed}\equiv M(\mathrm{mod}n)$$

---

2.4 为什么有时使用 Carmichael 函数

工程和标准中也常使用 Carmichael 函数 $\lambda (n)$。对于 RSA 的模数 $n=pq$（两个不同奇素数 $p,q$）：
$$\lambda (n)=\mathrm{lcm}(p-1,q-1)$$

$\mathrm{lcm}$ 代表最小公倍数。相比于欧拉函数

$$\phi (n)=(p-1)(q-1)$$
$\lambda (n)$ 求出的是模 $n$ 所有可逆元统一的最小周期，是比 $\phi (n)$ 更紧、更小的上界。

欧拉定理只能保证：任意可逆元满足 $a^{\phi (n)}\equiv 1(\mathrm{mod}n)$。
而 Carmichael 定理证明：所有可逆元其实不用乘到 $\phi (n)$，只需要乘到 $\mathrm{lcm}(p-1,q-1)$ 就一定回归 $1$。

例：取 $p=7,q=13$，$p-1=6,q-1=12$。$\phi (n)=6\times 12=72$，$\lambda (n)=\mathrm{lcm}(6,12)=12$。模 $n$ 下全部可逆元，12次方就模 $n$ 等于1，无需72次方。

因此工程密钥可以放宽为更优条件：
$$ed\equiv 1(\mathrm{mod}\lambda (n))$$
数学上满足：
$$\lambda (n)\mid \phi (n)$$
也就是说 $\lambda (n)$ 一定是 $\phi (n)$ 的约数。

使用 $\phi (n)$ 计算简单、适合入门推导；使用 $\lambda (n)$ 是 RSA 真实标准采用的规则，更贴合模运算的真实群周期结构。两种写法本质服务同一套 RSA 算法，并不存在两套不同 RSA。

---

三、模逆与扩展欧几里得算法

3.1 模逆不是小数倒数

若整数 $x$ 满足：

$$ax\equiv 1(\mathrm{mod}m)$$

则称 $x$ 是 $a$ 在模 $m$ 下的乘法逆元，记作：

$$x\equiv a^{-1}(\mathrm{mod}m)$$

它表示“找到一个整数，乘上 $a$ 后模 $m$ 余 $1$”，而不是计算实数 $1/a$。

逆元存在的充要条件是：

$$\gcd (a,m)=1$$

RSA 私钥指数正是：

$$d\equiv e^{-1}(\mathrm{mod}\phi (n))$$

---

3.2 Bézout 等式把求逆变成求系数

若：

$$\gcd (a,b)=g$$

则存在整数 $x,y$，使得：

$$ax+by=g$$

当 $g=1$ 时：

$$ax+by=1$$

两边模 $b$：

$$ax\equiv 1(\mathrm{mod}b)$$

因此 $x$ 就是 $a$ 模 $b$ 的逆元。扩展欧几里得算法不仅计算最大公约数，还能把这个 $x$、$y$ 一并求出来。

---

3.3 手算 $17^{-1}\mathrm{mod}3120$

先做欧几里得除法：

$$3120=17\times 183+9$$

$$17=9\times 1+8$$

$$9=8\times 1+1$$

从最后一行反向代回：

$$1=9-8$$

又因为：

$$8=17-9$$

所以：

$$1=2\times 9-17$$

再代入：

$$9=3120-17\times 183$$

得到：

$$1=2\times 3120-367\times 17$$

因此：

$$-367\times 17\equiv 1(\mathrm{mod}3120)$$

$-367$ 是一个逆元代表。把它转换到 $0$ 到 $3119$ 的范围：

$$d=-367+3120=2753$$

验证：

$$17\times 2753=46801=15\times 3120+1$$

所以：

$$17\times 2753\equiv 1(\mathrm{mod}3120)$$

---

四、完整生成一组可手算的 RSA 密钥

4.1 选择素数并计算模数

取教学参数：

$$p=61,q=53$$

模数为：

$$n=pq=61\times 53=3233$$

欧拉函数为：

$$\phi (n)=(61-1)(53-1)=60\times 52=3120$$

---

4.2 选择公钥指数

选择：

$$e=17$$

检查：

$$\gcd (17,3120)=1$$

因此 $17$ 在模 $3120$ 下存在逆元。

真实系统中经常看到：

$$e=65537=2^{16}+1$$

它的二进制中只有两个 $1$，公开运算效率较好，同时避免了过小指数的一些直接风险。但 $65537$ 并不是“自动安全按钮”，密钥生成和填充仍必须正确。

---

4.3 计算私钥指数

上一节已经求出：

$$d=2753$$

于是公钥可以表示为：

$$(n,e)=(3233,17)$$

私钥的核心参数为：

$$(n,d)=(3233,2753)$$

实际私钥通常还保存 $p,q,d_P,d_Q,q_{\text{inv}}$ 等参数，用于 CRT 加速。只保存 $(n,d)$ 在数学上足以执行私钥运算，但不是常见的高效存储形式。

---

4.4 加密和解密一个整数

设编码后的消息整数为：

$$M=65$$

必须满足：

$$0\le M<n$$

加密：

$$C=65^{17}\mathrm{mod}3233=2790$$

解密：

$$M^{\prime }=2790^{2753}\mathrm{mod}3233=65$$

于是：

$$M^{\prime }=M$$

这里的“整数消息”只是 RSA 原语的输入。真实文本、文件和协议消息要先经过严格编码与填充，不能直接把字节串当整数后执行裸 RSA。OAEP 和 PSS 将在下一篇展开。

---

五、快速模幂：大指数为什么算得动

5.1 直接乘 $d$ 次不可行

朴素计算：

$$a^d=\underset{d\text{ 次}}{\underbrace{a\times a\times \cdots \times a}}$$

会产生巨大的中间整数，运算次数也与 $d$ 成正比。RSA 私钥指数通常有上千位，不能这样计算。

快速模幂利用两点：

1. 每一步都立即取模，控制中间数大小；
2. 把指数写成二进制，通过不断平方与选择性相乘完成计算。

---

5.2 平方—乘算法

例如：

$$17=(10001{)}_2=16+1$$

因此：

$$65^{17}=65^{16}\times 65$$

连续平方并取模：

$$65^2\mathrm{mod}3233=992$$

$$65^4\mathrm{mod}3233=992^2\mathrm{mod}3233=1232$$

$$65^8\mathrm{mod}3233=1232^2\mathrm{mod}3233=1547$$

$$65^{16}\mathrm{mod}3233=1547^2\mathrm{mod}3233=789$$

最后：

$$65^{17}\mathrm{mod}3233=789\times 65\mathrm{mod}3233=2790$$

指数有 $t$ 个二进制位时，平方—乘算法只需要 $O(t)$ 次模乘，而不是执行指数数值那么多次乘法。

---

5.3 Python 内置三参数 pow

Python 中应使用：

result = pow(base, exponent, modulus)

不要先计算：

result = (base ** exponent) % modulus

前者直接执行高效模幂，后者可能先构造极大的完整幂。

下面用教学代码复现密钥生成与加解密：

from math import gcd

p = 61
q = 53
n = p * q
phi = (p - 1) * (q - 1)

e = 17
assert gcd(e, phi) == 1

d = pow(e, -1, phi)

message = 65
ciphertext = pow(message, e, n)
recovered = pow(ciphertext, d, n)

print("n =", n)
print("phi(n) =", phi)
print("public key =", (n, e))
print("private exponent d =", d)
print("ciphertext =", ciphertext)
print("recovered =", recovered)

输出：

n = 3233
phi(n) = 3120
public key = (3233, 17)
private exponent d = 2753
ciphertext = 2790
recovered = 65

以上代码只用于理解数学关系，没有安全素数生成、填充、侧信道防护和密钥保护，不能用于生产环境。

---

六、CRT 如何加速私钥运算

6.1 把一次模 $n$ 运算拆成两次小运算

RSA 解密需要计算：

$$M=C^d\mathrm{mod}n$$

因为 $n=pq$，可以分别计算：

$$m_1=C^{d_P}\mathrm{mod}p$$

$$m_2=C^{d_Q}\mathrm{mod}q$$

其中：

$$d_P=d\mathrm{mod}(p-1)$$

$$d_Q=d\mathrm{mod}(q-1)$$

对示例参数：

$$d_P=2753\mathrm{mod}60=53$$

$$d_Q=2753\mathrm{mod}52=49$$

再预计算：

$$q_{\text{inv}}=q^{-1}\mathrm{mod}p=53^{-1}\mathrm{mod}61=38$$

---

6.2 合并两个余数

已知：

$$M\equiv m_1(\mathrm{mod}p)$$

$$M\equiv m_2(\mathrm{mod}q)$$

可以计算：

$$h=q_{\text{inv}}(m_1-m_2)\mathrm{mod}p$$

再得到：

$$M=m_2+hq$$

这个 $M$ 同时满足模 $p$ 和模 $q$ 的两个同余式，因此就是模 $n$ 下的结果。

对于相同安全强度，模 $p$、模 $q$ 的操作数长度约为模 $n$ 的一半。大整数乘法和模幂不是线性成本，因此 CRT 通常能显著加速 RSA 私钥运算。

---

6.3 CRT 既是优化点，也是防护点

CRT 实现若受到硬件故障、电压毛刺或故意注入的计算错误，错误签名可能泄露素因子。典型情况下，攻击者将正确与错误结果做差并计算最大公约数，就可能得到 $p$ 或 $q$。

因此生产实现通常需要：

• 对 CRT 结果进行重新验证；
• 使用指数盲化、消息盲化降低侧信道风险；
• 采用成熟密码库的常数时间实现；
• 不输出能够区分内部失败原因的细粒度错误。

“数学公式正确”只是第一层，安全实现还必须处理故障与侧信道。

---

七、RSA 数学原语的边界

7.1 裸 RSA 是确定性的

固定公钥下，同一个 $M$ 总会得到同一个 $C$：

$$C=M^e\mathrm{mod}n$$

攻击者可以猜测候选消息并自行加密比较，无法达到现代加密要求的语义安全。

---

7.2 RSA 保留乘法结构

若：

$$C_1=M_1^e\mathrm{mod}n,C_2=M_2^e\mathrm{mod}n$$

则：

$$C_1{C}_2\equiv (M_1{M}_2{)}^e(\mathrm{mod}n)$$

这意味着裸 RSA 具有可塑性。攻击者未必知道明文，却可能系统性改变解密结果。

---

7.3 RSA 不能直接加密大文件

RSA 输入整数必须小于 $n$。加入 OAEP 后，可承载消息还要扣除哈希和编码开销。以 2048 位 RSA 和 SHA-256 为例，OAEP 最大明文长度为：

$$256-2\times 32-2=190\text{ 字节}$$

所以实际系统通常使用混合加密：随机生成对称密钥，用 RSA-OAEP 加密这把短密钥，再用 AEAD 加密业务数据。

---

7.4 不要自行实现生产 RSA

安全 RSA 还涉及：

• 高质量素数与随机数生成；
• 密钥长度和参数检查；
• OAEP、PSS 等标准编码；
• 常数时间模幂与盲化；
• CRT 故障检测；
• 统一错误处理和密钥安全存储。

教学实现可以帮助理解公式，但生产系统应使用经过审计的密码库和明确的协议规范。

---

八、总结

RSA 的核心并不是“用公钥加密、私钥解密”这句口号，而是一组相互咬合的数学关系：

1. 选择不同大素数 $p,q$，构造 $n=pq$；
2. 通过 $p,q$ 计算 $\phi (n)=(p-1)(q-1)$；
3. 选择与 $\phi (n)$ 互质的公钥指数 $e$；
4. 计算模逆 $d\equiv e^{-1}(\mathrm{mod}\phi (n))$；
5. 利用 $ed=1+k\phi (n)$ 和欧拉定理说明运算可逆；
6. 使用快速模幂高效处理大指数；
7. 使用 CRT 把私钥运算拆到模 $p$、模 $q$ 下加速。

但这些内容只定义了 RSA 的数学原语。裸 RSA 不随机、具有代数可塑性，也没有规定文本如何编码。下一篇将进入真正可部署的 RSA 方案：加密为什么需要 OAEP，签名为什么需要 PSS，以及“私钥加密就是签名”这句话究竟错在哪里。