RSA 算法详解

RSA（Rivest-Shamir-Adleman）是目前应用最广泛的非对称加密算法之一。它的核心思想是：两个大质数相乘很容易，但把乘积重新分解回这两个质数却极其困难。

---

一、RSA 算法的运行步骤

RSA 分为三个阶段：密钥生成、加密、解密。

1. 密钥生成

步骤一： 随机选择两个不相等的超大质数 p 和 q。

步骤二： 计算乘积 n：

n = p × q

n 的长度就是密钥长度。实际应用中 n 通常是 2048 位或 4096 位二进制数。

步骤三： 计算 n 的欧拉函数 φ(n)。当 p、q 为质数时：

φ(n) = (p − 1)(q − 1)

步骤四： 随机选择公钥指数 e，满足：

1 < e < φ(n) 且 gcd(e, φ(n)) = 1

即 e 与 φ(n) 互质。

步骤五： 计算 e 对 φ(n) 的模反元素 d（私钥指数），满足：

e · d ≡ 1 (mod φ(n))

等价于 ed = 1 + k · φ(n)，其中 k 为某个整数。

结果：

• 公钥： (n, e) —— 可公开
• 私钥： (n, d) —— 必须保密

2. 加密

将明文数字化为一个小于 n 的非负整数 M，用公钥 (n, e) 加密：

C ≡ M^e (mod n)

3. 解密

收到密文 C 后，用私钥 (n, d) 解密：

M ≡ C^d (mod n)

---

二、手搓一个 RSA

假设要发送明文 M = 4。

第一步：生成钥匙

• 选两个小质数：p = 3，q = 11
• 模数 n = 3 × 11 = 33
• 欧拉函数 φ(n) = (3−1) × (11−1) = 20

第二步：配对公钥和私钥

• 找公钥 e： 选一个和 20 互质的数，取 e = 3。公钥诞生：(n=33, e=3)，可全网公开。
• 找私钥 d： 找到 d 使 3 × d ≡ 1 (mod 20)。3 × 7 = 21 除以 20 余 1，所以 d = 7。私钥诞生：(n=33, d=7)，必须藏好。

第三步：加密

用公钥 (33, 3) 加密明文 M = 4：

C ≡ 4³ (mod 33)
C = 64 mod 33 = 31

密文 C = 31 被发送出去。即使被截获，没有私钥也无法逆推。

第四步：解密

用私钥 (33, 7) 解密密文 C = 31：

M ≡ 31⁷ (mod 33)

利用同余技巧——31 对 33 取模等价于 −2：

(−2)⁷ = −128
−128 mod 33 = (−128 + 132) mod 33 = 4

完美还原 M = 4。

---

三、RSA 算法的正确性证明

RSA 证明的核心目标：解密运算一定能还原出明文。即证明：

M^ed ≡ M (mod n)

上图展示了推导逻辑，下面是逐步拆解。

1. 目标起点

验证解密公式 C^d mod n 的结果，是否等于原明文 M。

2. 代入加密公式

密文来自 C ≡ M^e (mod n)，代入解密公式：

C^d mod n = (M^e mod n)^d mod n

3. 模运算的指数性质

在模运算中，中途取模和最后取模效果相同：

(a mod n)^b mod n = a^b mod n

于是括号内的 mod n 可以"脱掉"，指数 e 和 d 直接相乘，化简为：

M^ed mod n

4. 确立证明目标

解密等价于计算 M^ed mod n，这个结果必须等于 M。因此所有证明最终都指向：

M^ed ≡ M (mod n)

---

从密钥关系入手

公钥 e 和私钥 d 在生成时必须满足：

ed − 1 = k · φ(n) ⇒ ed = k · φ(n) + 1

代入指数得：

M^{k·φ(n) + 1} mod n

现在需要证明：

M^{k·φ(n) + 1} ≡ M (mod n)

---

引入欧拉定理

将指数拆开：

M^{k·φ(n) + 1} = M · M^k·φ(n)

要证明整体等于 M，实际上就是要证明 M^k·φ(n) ≡ 1 (mod n)。

对于 M 和 n 互质的情况，欧拉定理直接给出：

M^φ(n) ≡ 1 (mod n)

于是：

M^k·φ(n) = (M^φ(n))^k ≡ 1^k ≡ 1 (mod n)

代回原式：

M · M^k·φ(n) ≡ M · 1 ≡ M (mod n)

---

当 M 和 n 不互质时

由于 n = pq（两个质数的乘积），M 不互质意味着 M 是 p 或 q 的倍数。利用中国剩余定理可以分情况证明结论依然成立。此处略去细节，感兴趣可查阅 CRT 在 RSA 证明中的应用。

---

总结： RSA 的安全性依赖于大数分解的困难性，而正确性则由欧拉定理和中国剩余定理共同保证。