鲍勃把给他写信用的密钥直接登在报纸上。怎样让这把密钥能锁上信，却打不开？
鲍勃希望任何人都能给他写密信，哪怕是从没见过的人。他在报纸上登出一把密钥：“给我写信，请用它加密”。伊芙也看报纸。有没有可能，伊芙手里拿着同一把密钥，却仍然读不了任何一封寄给鲍勃的信？
听起来像胡话。在所有熟悉的密码里，从凯撒密码到 AES，同一把密钥既能上锁也能开锁。知道怎么加密的人，也就知道怎么解密：把一切倒过来做就行。公开这样的密钥，就等于公开秘密本身。
1976 年，迪菲和赫尔曼展示了两个人怎样当众约定一个共同密钥。但每换一个通信对象都得重新约定，而且双方必须同时在线。在同一篇论文里，他们还描述了一个更好的梦想：一种有两把不同密钥的密码——公开的用来上锁，私有的用来开锁。他们并不知道怎样造出它。
RSA 是一种公钥密码：鲍勃有两把密钥，而且它们不同。公钥他发给所有人，私钥不给任何人看。日常生活里也有同样的东西——挂锁。
鲍勃把打开的挂锁发给所有人，钥匙留在自己手里。爱丽丝把信放进箱子，扣上鲍勃的锁：这一步不需要钥匙。箱子通过普通邮寄送到鲍勃那里。伊芙也有鲍勃的锁，但锁只能扣上。
简化说明：真正的挂锁可以用开锁工具撬开。RSA 的数字锁也有“撬锁工具”——分解 n，但面对巨大的数字它就失灵了。
RSA 上锁用的运算和迪菲-赫尔曼一样：把数字取若干次方，再取除法的余数。新东西在别处：模数 n 由鲍勃自己用两个秘密素数组成，正是它们让他能算出钥匙。下面的例子都用游戏里的数字，其中 n = 33。
鲍勃随机选两个素数 p 和 q——只能被 1 和自身整除的数。在真正的密钥中，每个都长达 1024 位甚至更长，约 309 位十进制数。它们的乘积 n = p × q 他发给大家，p 和 q 本身则保密。两个数相乘很容易；从乘积反推出它由哪两个素数构成，在数字巨大时就很难。
例子：p = 3，q = 11，n = 3 × 11 = 33。
鲍勃算出 φ = (p − 1)(q − 1)，并选出锁的次方 e——一个与 φ 没有公因数的数。在真正的密钥中几乎总是 e = 65537。他再由 e 和 φ 求出钥匙的次方 d：使 e · d 除以 φ 余 1 的那个数。公钥是数对 (n, e)，私钥是 d。要求出 d 得知道 φ，要求出 φ 得知道 p 和 q。
例子：φ = 2 × 10 = 20，e = 3，d = 7，因为 3 · 7 = 21 = 1 · 20 + 1。
信就是一个小于 n 的数 m：文字要先转换成数字。爱丽丝拿到鲍勃的公钥，算出 c = me mod n。这就是“扣上锁”。次方要分步算：乘一次，取余数；再乘一次，再取余数。结果和一次算完整个次方相同，但数字不会变大。否则，面对 65537 次方和几百位长的数字，任何计算机都吃不消。数 c 公开发送：没有 d 它毫无用处。
例子：m = 4。4 × 4 = 16；16 × 4 = 64 = 1 · 33 + 31。所以 c = 31。
鲍勃把 c 取自己秘密的 d 次方，用同一个模数，得到原来的 m。没有任何新的运算：方法相同，只是次方不同。
例子：分步计算 317 mod 33：31 · 31 = 961 → 4；4 · 31 = 124 → 25；25 · 31 = 775 → 16；16 · 31 = 496 → 1；1 · 31 = 31；31 · 31 = 961 → 4。鲍勃得到 m = 4。
爱丽丝把 m 取 e 次方，鲍勃再把结果取 d 次方。合起来就是 me·d。而鲍勃选的 e · d 恰好比 φ 的某个倍数多 1。模 n 的余数有一个性质（欧拉定理）：这样的次方会让任何数回到原位。所以 cd = me·d = m mod n。可以这样想象：锁把 0 到 n − 1 的数字像一副牌那样洗乱，每个数字都有自己的位置；钥匙沿着同样的线走回去。
例子：3 · 7 = 21 = 1 · 20 + 1，而 421 mod 33 = 4。
麻省理工学院的罗纳德·里维斯特、阿迪·沙米尔和伦纳德·阿德曼花了一年时间，寻找迪菲和赫尔曼梦想中的那种函数。里维斯特和沙米尔提出方案，阿德曼负责把它们攻破。1977 年 4 月，一个基于两个素数的可行方案诞生了；RSA 就是三人姓氏的首字母。同年 8 月，马丁·加德纳在《科学美国人》上介绍了这种密码，并出了一道题：一个 129 位的数，以及用它加密的一句话，奖金 100 美元。直到 1994 年才被解开：约 600 名志愿者通过互联网花了八个月分解这个数。那句话原来是“The Magic Words are Squeamish Ossifrage”。
在这件事上，英国的政府通信总部（GCHQ）同样抢先一步。1973 年，年轻的数学家克利福德·考克斯读了同事詹姆斯·埃利斯关于“非秘密加密”的笔记，一个晚上就找到了同样的双素数方案——比里维斯特、沙米尔和阿德曼早了将近四年。麻省理工学院的 RSA 专利在美国一直有效到 2000 年 9 月，此后这个算法就可以自由使用了。
RSA 至今仍在你身边工作，只是如今它签名的时候比加密的时候多：
大多数网站的证书都用 RSA 签名，浏览器用这个签名来确认密钥确实属于这个网站。而用 RSA 传送连接密钥的做法在 TLS 1.3 中被禁止了：这如今是迪菲-赫尔曼交换的任务。
第一次连接时，服务器或路由器会显示其公钥的指纹，这往往是一把 RSA 密钥。设备用它证明你正在和它本身通话，而不是和冒充者。
PGP 邮件、程序和更新的签名、带芯片的银行卡——凡是需要在从未见过作者的情况下确认作者的地方。
两种算法都属于公钥密码学，也都在做模幂运算，所以常被混淆。区别在于它们做什么。在迪菲-赫尔曼交换中，爱丽丝和鲍勃互换公开数，各自在自己这边算出共同密钥。那里什么也不加密，而且双方必须同时参与。在 RSA 中，鲍勃早已把锁发给了所有人：爱丽丝拿起锁，自己就能把信锁上，哪怕鲍勃此刻不在线。
| 问题 | RSA | 迪菲-赫尔曼 |
|---|---|---|
| 用来做什么 | 为某一个收件人锁上信，或者给自己的信签名 | 让两个人得到一个共同密钥，之后用它加密通信 |
| 对方必须在线吗 | 不必：爱丽丝手里已经有鲍勃的锁 | 必须：每人都要加入自己的秘密数 |
| 发送的是什么 | 信本身，用锁锁好 | 只有公开数；信和密钥都不在信道里 |
| 密钥 | 鲍勃的锁和钥匙能用好几年 | 每次对话都重新选秘密数 |
| 伊芙面对的难题 | 把 n 分解成两个素数 | 由公开数求出秘密数（离散对数） |
| 比喻 | 一把打开的挂锁 | 两个人一起调的颜料 |
俄罗斯标准里根本没有 RSA。签名按 GOST R 34.10-2012 在椭圆曲线上进行，共同密钥则用 VKO 生成（见关于迪菲-赫尔曼的文章）。这里的公钥是曲线上的一个点，而不是两个素数的乘积，所以没有什么可分解的。安全性依靠的是另一个难题——离散对数。
在 GOST 中，也不习惯直接用公钥锁信：公钥只用来签名和生成共同密钥，信随后用对称密码加密。其实 RSA 的世界里做法几乎一样：RSA 通常锁的不是信本身，而是一把随机的 AES 密钥。
不过，RSA 在俄罗斯每天都能见到。普通浏览器不懂 GOST，所以就连俄罗斯数字发展部的国家认证中心自 2022 年起为网站签发的证书，也是用 RSA 签名的。为了 GOST 连接，这个认证中心另有一条证书链，但这样的网站只能在支持 GOST 的浏览器里打开，例如 Yandex 浏览器。
在游戏里，你会亲手组装密钥，锁上并打开一封信，然后扮演伊芙试着破解它。可以这样做：
两种方案都有一对密钥——公钥和私钥，但背后的难题不同，能做的事情也不同：
| 参数 | RSA | GOST R 34.10-2012 |
|---|---|---|
| 密钥由什么组成 | 两个大素数及其乘积 | 一个秘密数和椭圆曲线上的一个点 |
| 难题 | 因数分解 | 曲线上的离散对数 |
| 约 128 位安全强度所需的密钥长度 | 3072 位 | 256 位 |
| 能做什么 | 加密（配合 OAEP）和签名 | 签名；共同密钥用 VKO |
| 年份 | 1977 | 2012（之前是 GOST R 34.10-2001） |
| 标准 | PKCS #1 (RFC 8017) | GOST R 34.10-2012（RFC 7091），TC 26 |
RSA 的数字是用同样的数域筛法分解的，它也威胁着迪菲-赫尔曼，所以安全强度也一样：2048 位大约相当于 112 位的对称密钥，要达到 128 位则需要 3072 位。纪录是这样增长的：RSA-129（426 位）在 1994 年被分解，RSA-768 在 2009 年，RSA-250（829 位）在 2020 年。离 2048 位还差得很远，但如今短于 2048 位的密钥已被视为不安全。
65537 = 216 + 1 是素数，而且它的二进制只有两个 1，所以锁上一封信只需 17 次乘法。如果不加随机性，用很小的 e（比如 3）是危险的：当 m3 小于 n 时，除法什么也没改变，伊芙只要对 c 开立方根就行。游戏里 m = 2 和 3 就能看到这一点：23 = 8 小于 33，于是 c = 8。
2012 年，两个研究小组从互联网上收集了数百万把 RSA 公钥，并两两比较。结果发现数万把密钥有共同的素因数，主要出现在路由器、网络摄像头等设备上：它们在第一次开机后立刻生成密钥，那时还没有足够好的随机性。如果两个 n 共用一个 p，用欧几里得算法一瞬间就能找到它，两把密钥都会被攻破。素数不仅要巨大，还必须真正随机。
量子计算机上的肖尔算法分解 n 的速度，和它解决迪菲-赫尔曼问题一样快。对 RSA 来说，最重要的是签名，而替代方案已经准备好了：后量子签名标准 ML-DSA（FIPS 204）和 SLH-DSA（FIPS 205）。后者有趣之处在于，它只依靠哈希函数，完全不用数论。
现在你知道了怎样用人人都有的密钥锁上一封信，也知道了为什么光靠分解的困难还不够
在游戏里，你会选择自己的素数，造出锁的纸带，并看到伊芙怎样不经任何分解就读到信