1977年，三位麻省理工学院的教授——罗纳德·李维斯特、阿迪·萨莫尔和伦纳德·阿德曼——终于找到了一个实用的公钥加密算法。他们以姓氏的首字母命名为RSA。这个算法的数学原理虽然深刻，但核心思想却简单到可以用小学数学来解释。
RSA的钥匙是怎么造出来的？
想象一下，你有一个巨大的数字保险箱，但保险箱的锁有点特别：它有两把钥匙，一把是公开的锁（公钥），任何人都可以用它来锁上箱子；另一把是私密的钥匙（私钥），只有你能打开箱子。而且，这两把钥匙是由一对特殊的数字组成的。
RSA的钥匙生成过程分为四步：
第一步：选两个质数
你偷偷选出两个很大的质数，比如质数p和q。质数是只能被1和自身整除的数，比如2、3、5、7、11……在真实世界中，这两个质数可能有几百位长，但在我们的例子里，我们选小的：p = 61，q = 53。
第二步：计算乘积n
把这两个质数乘起来：n = p × q。在我们的例子里，n = 61 × 53 = 3233。这个n就是公钥和私钥的一部分，可以公开。
第三步：计算欧拉函数φ(n)
欧拉函数φ(n)表示小于n且与n互质的正整数的个数。对于质数乘积，有一个简单公式：φ(n) = (p-1) × (q-1)。在我们的例子里，φ(3233) = 60 × 52 = 3120。
第四步：选择加密指数e和解密指数d
选择一个小于φ(n)且与φ(n)互质的整数e，比如e = 17。然后计算一个d，使得 e × d ≡ 1 (mod φ(n))，也就是 e × d 除以 φ(n) 余1。在我们的例子里，我们需要找到一个d，使得 17 × d ≡ 1 (mod 3120)。计算可得 d = 2753（因为 17 × 2753 = 46801，46801 ÷ 3120 = 15 余 1）。
现在，我们的钥匙就做好了：
- 公钥：数字对 (n, e) = (3233, 17)
- 私钥：数字对 (n, d) = (3233, 2753)
你可以把公钥贴在墙上，让全世界都知道。而私钥中的d必须严加保密，绝不能泄露。
怎么用RSA加密？
假设你的朋友鲍勃想给你发一条秘密消息，他知道你的公钥是 (3233, 17)。他先把消息转换成数字，比如他要发送字母“A”，我们可以把它变成数字2（A=1，B=2，但为了简单，我们直接用一个小数字）。
加密的公式很简单：密文 = 明文的e次方，然后除以n取余数。
写成数学公式：c = m^e mod n
用我们的例子，m = 2，e = 17，n = 3233：
- 先计算 2^17 = 131072
- 然后除以3233取余数：131072 ÷ 3233 = 40 余 ？我们算一下：3233 × 40 = 129320，131072 - 129320 = 1752。所以密文 c = 1752。
鲍勃把数字1752发给你。即使被窃听者伊芙截获了1752，她也无法还原出原来的2，因为她没有你的私钥d。
怎么用RSA解密？
你收到1752后，用自己的私钥 (n, d) = (3233, 2753) 进行解密。公式是：明文 = 密文的d次方，然后除以n取余数。
m = c^d mod n
计算 1752^2753 除以3233的余数……这看起来可怕，但计算机可以快速完成（实际上利用模重复平方算法）。结果应该是 2。验证一下：2^17 mod 3233 = 1752，而1752^2753 mod 3233 应该还原为2。
神奇的事情发生了：经过这么一大圈复杂的运算，我们又回到了最初的数字2。
为什么RSA能行？
这背后有一个深刻的数学定理——欧拉定理：如果 a 和 n 互质，那么 a^φ(n) ≡ 1 (mod n)。在我们的加密过程中，我们构造了 e 和 d 使得 e×d = 1 + k×φ(n)。所以：
c^d ≡ (m^e)^d = m^(e×d) = m^(1 + k×φ(n)) = m × (m^φ(n))^k ≡ m × 1^k = m (mod n)
这就解释了为什么加密后能解密回来——只要m小于n且与n互质（实际上不互质时也能工作，但证明稍复杂）。
用颜料混合来比喻
如果你觉得数学还是有点抽象，这里有一个经典的比喻：想象你要配一种颜色。你有两桶颜料，一桶黄色，一桶蓝色。你把它们混合起来，得到了绿色。现在，如果有人给你绿色颜料，让他找出原来的黄色和蓝色——几乎不可能，因为混合是单向的，你无法从结果反推出成分。
在RSA里，n = p×q 就像那桶绿色颜料。p和q是黄色和蓝色，而n是混合后的颜色。任何人都知道n，但想从n分解出p和q，就像从绿色反推出黄色和蓝色——极其困难。而正是这个困难，构成了RSA的安全基石。
为什么RSA安全？
RSA的安全性建立在大数分解的困难性上。给定一个足够大的合数n（比如2048位，大约600多位十进制数），即使使用世界上最快的超级计算机，分解它也需要数百年甚至更长的时间。只要没有人能分解n，就无法从公钥 (n, e) 推导出私钥d（因为需要知道p和q才能计算φ(n)）。
当然，随着计算能力的提升，密钥长度也需要不断增加。今天，安全RSA至少需要2048位，而许多机构已经要求使用3072位或更高。
一个完整的小例子
让我们用一个极小的例子来完整走一遍（注意：这么小的数字在实际中完全不安全，仅用于演示）：
- p = 3, q = 11 → n = 33, φ(n) = 2 × 10 = 20
- 选择 e = 3（与20互质）
- 计算 d：3 × d ≡ 1 mod 20 → d = 7（因为 3×7=21，21 mod 20 = 1）
- 公钥 (33, 3)，私钥 (33, 7)
假设明文 m = 4（必须小于33）：
- 加密：c = 4^3 mod 33 = 64 mod 33 = 31
- 解密：m = 31^7 mod 33 = ？
计算 31^2 = 961 mod 33 = 961 - 33×29 = 961 - 957 = 4，然后 31^4 ≡ 4^2 = 16 mod 33，31^7 = 31^4 × 31^2 × 31 ≡ 16 × 4 × 31 = 1984 mod 33 = 1984 - 33×60 = 1984 - 1980 = 4。果然回到了4。
现实中的RSA
在实际应用中，RSA的密钥长度至少是2048位，这意味着n是一个600多位的十进制数。而加密的消息通常不会直接使用RSA加密，因为RSA很慢。在HTTPS中，RSA主要用于交换一个临时生成的对称密钥，然后用那个对称密钥（如AES）来加密真正的数据。这就是我们将在6.5节讨论的混合加密。
RSA的诞生，让公钥密码学从理论走向了实践。它至今仍是互联网上应用最广泛的非对称加密算法，守护着每一次网上支付、每一次安全登录。下一节，我们将介绍另一种更高效的非对称加密——椭圆曲线密码，它用更短的钥匙提供了同等级别的安全。