RSA 的安全性并非建立在某种未知的魔法之上，而是基于一个我们目前认为“困难”的数学问题，其核心巧妙地将数论中的几个概念结合在了一起。

核心数学思想

RSA 的公钥密码体系基于一个根本性的不对称性：

• 正向计算容易：将两个大质数 pp 和 qq 相乘，得到 n=p×qn=p×q。

• 逆向计算极其困难：在只知道 nn 的情况下，将其分解回原始的 pp 和 qq。这被称为“大整数质因数分解问题”。

整个 RSA 协议都是围绕着这个核心不对称性构建的。

---

一、构建基石：必需的数学概念

要理解 RSA，必须掌握以下四个关键概念：

1. 欧拉函数 φ(n)

• 定义：对于正整数 nn，φ(n)φ(n) 表示小于等于 nn 的正整数中，与 nn 互质（最大公约数为1）的数的个数。

• 关键结论：

  • 如果 n=pn=p 是一个质数，则 φ(p)=p−1φ(p)=p−1。

  • 如果 n=p×qn=p×q，且 pp 和 qq 都是质数，则 φ(n)=φ(p)×φ(q)=(p−1)(q−1)φ(n)=φ(p)×φ(q)=(p−1)(q−1)。这是 RSA 的基石公式之一。

2. 模反元素（乘法逆元）

• 定义：在模 mm 的意义下，如果一个整数 aa 与另一个整数 bb 满足 a×b≡1(modm)a×b≡1(modm)，则称 bb 是 aa 的模 mm 的乘法逆元，记作 b≡a−1(modm)b≡a−1(modm)。

• 存在条件：aa 与 mm 必须互质（即 gcd⁡(a,m)=1gcd(a,m)=1）。

3. 欧拉定理

• 定理：如果正整数 aa 与 nn 互质，那么 aφ(n)≡1(modn)aφ(n)≡1(modn)。

• 它是 RSA 加解密能够成立的根本保证。

---

二、RSA 算法详述：从密钥生成到加解密

现在，我们将这些数学概念组合起来，一步步构建 RSA。

第一步：密钥生成

这是最核心的一步，由接收者（比如 Bob）完成。

1. 选择两个大质数：随机选择两个非常大且不同的质数 pp 和 qq。

   • 安全性：pp 和 qq 必须足够大，使得从 nn 分解出 pp 和 qq 在计算上不可行。

2. 计算模数 nn：计算 n=p×qn=p×q。

   • nn 将被用于公钥和私钥中，并且会公开。攻击者只知道 nn。

3. 计算欧拉函数 φ(n)φ(n)：计算 φ(n)=(p−1)(q−1)φ(n)=(p−1)(q−1)。

   • 这是最关键的秘密！ 知道 nn 的人无法计算出 φ(n)φ(n)，除非他能分解 nn。这个秘密值 φ(n)φ(n) 在生成密钥后必须立即被安全地丢弃。

4. 选择公钥指数 ee：选择一个整数 ee，满足 1<e<φ(n)1<e<φ(n)，且 gcd⁡(e,φ(n))=1gcd(e,φ(n))=1（即 ee 与 φ(n)φ(n) 互质）。

   • ee 通常选择一个较小的质数，如 65537 (0x10001)，以提升加密效率。这个 ee 将成为公钥的一部分。

5. 计算私钥指数 dd：计算 dd，使得 ee 是 dd 关于模 φ(n)φ(n) 的乘法逆元。即：

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

   • 这意味着存在一个整数 kk，使得 e×d=k×φ(n)+1e×d=k×φ(n)+1。

   • dd 可以通过扩展欧几里得算法高效地计算出来。这个 dd 是私钥，必须严格保密。

最终，我们得到：

• 公钥：(e,n)(e,n) - 可以公开给任何人。

• 私钥：(d,n)(d,n) - 由接收者秘密保存。

第二步：加密

假设发送者（比如 Alice）想给 Bob 发送一条加密消息 MM（在计算机中，MM 是一个数字）。

1. Alice 获取 Bob 的公钥 (e,n)(e,n)。

2. 她将明文 MM 转化为一个整数，满足 0≤M<n0≤M<n。

3. 她计算密文 CC：

   C≡Me(modn)C≡Me(modn)

4. 将密文 CC 发送给 Bob。

第三步：解密

Bob 收到密文 CC 后，使用自己的私钥 (d,n)(d,n) 进行解密。

1. 他计算：

   M‘≡Cd(modn)M‘≡Cd(modn)

2. 我们将证明，计算出的 M’M’ 就是原始的明文 MM。

---

三、核心：为什么解密是正确的？

这是最精彩的部分，它完美地展示了数学的严谨与优美。

证明： 我们需要证明 Cd(modn)=MCd(modn)=M。

我们从加密过程知道 C≡Me(modn)C≡Me(modn)。将其代入解密公式：

Cd≡(Me)d≡Me×d(modn)Cd≡(Me)d≡Me×d(modn)

根据密钥生成过程，我们有 e×d≡1(modφ(n))e×d≡1(modφ(n))，即 e×d=k×φ(n)+1e×d=k×φ(n)+1（对于某个整数 kk）。

所以：

Me×d≡Mk×φ(n)+1(modn)Me×d≡Mk×φ(n)+1(modn)≡(Mφ(n))k×M(modn)≡(Mφ(n))k×M(modn)

现在，我们分两种情况讨论：

情况一：MM 与 nn 互质（即 gcd⁡(M,n)=1gcd(M,n)=1）
这是最直接应用欧拉定理的情况。
根据欧拉定理：Mφ(n)≡1(modn)Mφ(n)≡1(modn)。
因此：

(Mφ(n))k×M≡(1)k×M≡M(modn)(Mφ(n))k×M≡(1)k×M≡M(modn)

得证。

情况二：MM 与 nn 不互质（即 gcd⁡(M,n)≠1gcd(M,n)=1）
在实际中，由于 M<nM<n 且 n=p×qn=p×q，MM 与 nn 不互质意味着 MM 是 pp 或 qq 的倍数。我们假设 MM 是 pp 的倍数（即 M=t×pM=t×p），但与 qq 互质（因为如果同时是 pp 和 qq 的倍数，则 M≥nM≥n，这与 M<nM<n 矛盾）。

1. 根据欧拉定理，因为 MM 与 qq 互质：

   Mφ(q)≡Mq−1≡1(modq)Mφ(q)≡Mq−1≡1(modq)

2. 由于 φ(n)=(p−1)(q−1)φ(n)=(p−1)(q−1)，我们计算 Me×dMe×d 模 qq：

   Me×d=Mk×φ(n)+1=Mk×(p−1)(q−1)+1Me×d=Mk×φ(n)+1=Mk×(p−1)(q−1)+1=(Mq−1)k×(p−1)×M=(Mq−1)k×(p−1)×M≡(1)k×(p−1)×M≡M(modq)≡(1)k×(p−1)×M≡M(modq)

   所以，Me×d≡M(modq)Me×d≡M(modq)。

3. 因为 MM 是 pp 的倍数，显然有：

   Me×d≡0≡M(modp)Me×d≡0≡M(modp)

4. 现在我们得到两个同余式：

   • Me×d≡M(modp)Me×d≡M(modp)

   • Me×d≡M(modq)Me×d≡M(modq)
     根据中国剩余定理，因为 pp 和 qq 互质，这必然意味着：

   Me×d≡M(modp×q)Me×d≡M(modp×q)

   即：

   Me×d≡M(modn)Me×d≡M(modn)

结论：无论在哪种情况下，解密运算 Cd(modn)Cd(modn) 都能准确地恢复出原始明文 MM。