从欧拉定理到RSA算法：非对称加密的数学原理（三）
RSA算法的完整构造与实例验证
引言
经过前两篇的铺垫，我们已经掌握了通向 RSA 算法的全部数学钥匙：欧拉定理揭示了模幂运算的周期性归一性质，其变形 $a^{k\varphi(n)+1} \equiv a \pmod{n}$ 保证了”加密—解密”这对操作的可逆性，而模反元素则提供了配对公钥指数 $e$ 与私钥指数 $d$ 的工具。本篇将把这些数学零件组装成一台完整的加密引擎，系统呈现 RSA 算法的密钥生成、加密与解密流程，并通过经典数字实例验证其正确性，最后剖析其安全性根基。
一、RSA 密钥生成的六步法
RSA 算法的安全性建立在大整数分解难题之上，其密钥生成过程可以分解为六个步骤。我们以爱丽丝（Alice）生成密钥对为例，逐步展开。
1.1 第一步：选取两个不等的大质数 $p$ 和 $q$
爱丽丝随机选择两个不相等的质数 $p$ 和 $q$。在本例中，她选择 $p = 61$，$q = 53$。
在实际工程应用中，这两个质数必须足够大——现代标准通常要求至少 512 位（约 155 位十进制数），常用 2048 位甚至 3072 位。为确保安全性，$p$ 和 $q$ 最好大小相近，且 $(p-1)$ 和 $(q-1)$ 中至少有一个大的质因数。质数的选取通常借助伪随机数生成器配合 Miller-Rabin 素性判定法完成。
1.2 第二步：计算模数 $n = p \times q$
爱丽丝将两个质数相乘：
$$n = p \times q = 61 \times 53 = 3233$$
这个 $n$ 就是 RSA 加密和解密时用到的模数，也是公钥和私钥的公共组成部分。$n$ 的二进制位数就是 RSA 密钥的长度——$3233$ 写成二进制是 $110010100001$，共 12 位，因此这是一个 12 位的密钥。实际应用中，RSA 密钥一般为 1024 位，重要场合则为 2048 位。
关键原则：$p$ 和 $q$ 必须严格保密，一旦泄露，整个密钥体系即告崩溃。
1.3 第三步：计算欧拉函数 $\varphi(n)$
根据欧拉函数的性质，当 $n = pq$（$p, q$ 为不同质数）时：
$$\varphi(n) = (p - 1)(q - 1)$$
爱丽丝计算：
$$\varphi(3233) = (61 - 1) \times (53 - 1) = 60 \times 52 = 3120$$
这里正是前两篇反复强调的欧拉函数发挥作用的关键节点——只有知道 $p$ 和 $q$，才能轻松算出 $\varphi(n)$。$\varphi(n)$ 同样必须严格保密，因为它是连接公钥 $e$ 与私钥 $d$ 的桥梁。
1.4 第四步：选择公钥指数 $e$
爱丽丝在 $1$ 到 $\varphi(n)$ 之间随机选择一个整数 $e$，要求 $e$ 与 $\varphi(n)$ 互质，即：
$$1 < e < \varphi(n), \quad \gcd(e, \varphi(n)) = 1$$
她选择了 $e = 17$（因为 $\gcd(17, 3120) = 1$）。
在实际工程中，$e$ 通常固定选择 $65537$（即 $2^{16} + 1$），这是因为它兼具计算效率与安全性。早期曾使用 $e = 3$ 或 $e = 17$，但小 $e$ 在某些场景下存在安全漏洞。
1.5 第五步：计算私钥指数 $d$
这一步是密钥生成的核心。我们需要求解 $e$ 对 $\varphi(n)$ 的模反元素 $d$，使得：
$$e \times d \equiv 1 \pmod{\varphi(n)}$$
即：
$$ed - 1 = k \cdot \varphi(n)$$
等价于求解二元一次不定方程：
$$ex + \varphi(n)y = 1$$
已知 $e = 17$，$\varphi(n) = 3120$，方程为 $17x + 3120y = 1$。利用扩展欧几里得算法，可求得一组整数解 $(x, y) = (2753, -15)$。
验证：
$$17 \times 2753 = 46801 = 15 \times 3120 + 1 \quad \checkmark$$
因此，私钥指数 $d = 2753$。
1.6 第六步：封装公钥与私钥
至此，所有计算完成：
- 公钥：$(n, e) = (3233, 17)$ —— 可以公开给任何人
- 私钥：$(n, d) = (3233, 2753)$ —— 必须严格保密
在实际应用中，公钥和私钥的数据通常采用 ASN.1 格式表达。
二、加密与解密过程
2.1 加密（使用公钥）
假设鲍勃（Bob）要向爱丽丝发送加密信息。明文 $M$ 必须满足 $0 < M < n$（若 $M$ 较长则需分块加密）。
加密公式：
$$C \equiv M^e \pmod{n}$$
其中 $C$ 为密文。鲍勃使用爱丽丝的公钥 $(3233, 17)$ 加密，假设明文 $M = 123$：
$$C = 123^{17} \bmod 3233 = 855$$
鲍勃将密文 $C = 855$ 发送给爱丽丝。即使密文在传输过程中被截获，攻击者也无法从中还原出明文。
2.2 解密（使用私钥）
爱丽丝收到密文后，使用自己的私钥 $(3233, 2753)$ 解密。
解密公式：
$$M \equiv C^d \pmod{n}$$
代入计算：
$$M = 855^{2753} \bmod 3233 = 123$$
明文被完美还原！
三、数学正确性的证明
为什么解密一定能还原明文？让我们从数学上严格证明。
3.1 核心推导
将加密结果代入解密公式：
$$C^d \equiv (M^e)^d \equiv M^{ed} \pmod{n}$$
根据密钥生成第五步，$ed \equiv 1 \pmod{\varphi(n)}$，即存在整数 $k$ 使得：
$$ed = k \cdot \varphi(n) + 1$$
因此：
$$M^{ed} = M^{k\varphi(n) + 1} = M \cdot \left(M^{\varphi(n)}\right)^k$$
3.2 应用欧拉定理
若 $M$ 与 $n$ 互质，根据欧拉定理：
$$M^{\varphi(n)} \equiv 1 \pmod{n}$$
代入上式：
$$M^{ed} \equiv M \cdot 1^k \equiv M \pmod{n}$$
解密成功！
3.3 当 $M$ 与 $n$ 不互质时
实际上，即使 $M$ 与 $n$ 不互质（因为 $n = pq$，这意味着 $M$ 是 $p$ 或 $q$ 的倍数），解密依然成立。这可以通过中国剩余定理（CRT）证明，此处从略。在实际应用中，由于 $n$ 极大（2048 位以上），随机选取的 $M$ 与 $n$ 不互质的概率微乎其微。
四、多组实例验证
为增强说服力，我们再列举几组经典算例。
4.1 算例一：$p = 3, q = 11$
| 参数 | 计算 | 结果 |
|---|---|---|
| $n$ | $3 \times 11$ | $33$ |
| $\varphi(n)$ | $2 \times 10$ | $20$ |
| $e$ | 选 $7$（与 $20$ 互质） | $7$ |
| $d$ | $7d \equiv 1 \pmod{20}$ | $3$ |
| 加密 $M = 5$ | $5^7 \bmod 33$ | $C = 14$ |
| 解密 $C = 14$ | $14^3 \bmod 33$ | $M = 5$ ✓ |
此例来自经典教材习题。
4.2 算例二：$p = 7, q = 11$
| 参数 | 计算 | 结果 |
|---|---|---|
| $n$ | $7 \times 11$ | $77$ |
| $\varphi(n)$ | $6 \times 10$ | $60$ |
| $e$ | 选 $17$ | $17$ |
| $d$ | $17d \equiv 1 \pmod{60}$ | $53$ |
| 加密 $M = 8$ | $8^{17} \bmod 77$ | $C = 57$ |
| 解密 $C = 57$ | $57^{53} \bmod 77$ | $M = 8$ ✓ |
该算例展示了稍大模数下的运算。
4.3 算例三：$p = 5, q = 11$
| 参数 | 计算 | 结果 |
|---|---|---|
| $n$ | $5 \times 11$ | $55$ |
| $\varphi(n)$ | $4 \times 10$ | $40$ |
| $e$ | 选 $3$ | $3$ |
| $d$ | $3d \equiv 1 \pmod{40}$ | $27$ |
| 加密 $M = 9$ | $9^3 \bmod 55$ | $C = 14$ |
| 解密 $C = 14$ | $14^{27} \bmod 55$ | $M = 9$ ✓ |
注意：这里 $e = 3$ 虽然在理论上可行，但在实际工程中因安全性问题已不推荐使用。
五、RSA 的安全性分析
5.1 攻击者的视角
假设攻击者截获了密文 $C$，并且知道公钥 $(n, e)$。他要还原明文 $M$，必须先求得私钥 $d$。
由 $ed \equiv 1 \pmod{\varphi(n)}$ 可知，求 $d$ 必须知道 $\varphi(n)$；而由 $\varphi(n) = (p-1)(q-1)$，求 $\varphi(n)$ 必须知道 $p$ 和 $q$；而由 $n = pq$，求 $p$ 和 $q$ 必须对 $n$ 做质因数分解。
5.2 大整数分解难题
当 $n$ 足够大时（2048 位或以上），大整数分解在计算上是不可行的。截至 2008 年，世界上还没有任何可靠的攻击 RSA 算法的方式。目前人类破解的最长 RSA 密钥是 RSA-768（768 位二进制，232 位十进制），耗费了巨大的计算资源。
对于 2048 位的 RSA 密钥，分解 $n$ 所需的时间远超宇宙年龄，这就是 RSA 安全性的物理保障。
5.3 陷门函数
RSA 的数学构造正是一个典型的陷门单向函数（Trapdoor One-Way Function）：
- 正向容易：已知 $M, e, n$，计算 $C = M^e \bmod n$ 很快（快速模幂算法）
- 逆向困难：已知 $C, e, n$，求 $M$ 等价于求解离散对数，极其困难
- 陷门信息：私钥 $d$（或等价地，$p$ 和 $q$）是”陷门”，拥有它就能轻松解密
5.4 六个数字的保密层级
在 RSA 密钥生成过程中，一共出现六个关键数字：
| 数字 | 是否公开 | 说明 |
|---|---|---|
| $p$ | 绝密 | 质因数之一 |
| $q$ | 绝密 | 质因数之一 |
| $n$ | 公开 | $n = pq$，公钥与私钥的组成部分 |
| $\varphi(n)$ | 绝密 | 欧拉函数值 |
| $e$ | 公开 | 公钥指数 |
| $d$ | 绝密 | 私钥指数 |
公钥用到了两个数（$n$ 和 $e$），其余四个数字都不公开。其中最关键的是 $d$，一旦泄露就等于私钥泄露。
六、工程实际与教学演示的差异
6.1 质数规模
教学演示中使用 2 位小质数（如 $p = 61, q = 53$），实际工程中使用 2048/4096 位超大质数（$p, q$ 各 1024 位以上），$n$ 为 2048/4096 位。
6.2 公钥指数 $e$ 的选择
工程中固定使用 $e = 65537$（二进制 $10000000000000001$），兼顾安全性和运算速度，避免小 $e$（如 $3, 7$）的安全漏洞。
6.3 填充方案
实际应用中，RSA 必须结合填充方案（如 OAEP），否则会遭受选择明文攻击等结构性攻击。直接对原始消息做 RSA 运算是不安全的。
6.4 性能优化
为提升解密效率，实际私钥通常还包含基于中国剩余定理（CRT）的预计算参数 $d_p, d_q, q^{-1} \bmod p$，可使解密速度提升约 4 倍。
七、小结
在本篇中，我们完成了从欧拉定理到 RSA 算法的最后一步：
- 密钥生成六步法：选质数 $p, q$ → 算 $n$ → 算 $\varphi(n)$ → 选 $e$ → 求 $d$ → 封装密钥对
- 加解密公式：$C = M^e \bmod n$，$M = C^d \bmod n$
- 正确性根源：$ed = k\varphi(n) + 1$ 触发欧拉定理的还原性质
- 安全性根基：大整数分解难题构成陷门单向函数
至此，从欧拉定理到 RSA 算法的完整数学链条已然贯通。RSA 的精妙之处在于：它将一个古老的数论定理（欧拉定理）与现代计算复杂性理论（大数分解难题）巧妙结合，构建出了人类历史上最具影响力的公钥加密体制。
然而，RSA 并非永恒的安全港湾。随着量子计算的发展，Shor 算法能够在多项式时间内分解大整数，RSA 的安全性面临根本性挑战。未来的密码学世界，或许将属于抗量子的后量子密码学算法。但无论如何，RSA 算法所展现的数学之美与工程之巧，将永远是密码学史上的一座丰碑。
全系列完结
参考文献：本系列文章参考了多篇网络资源，在此一并致谢。