IT 论文精读 · PAPER 40

RSA 公钥密码体制

Rivest, Shamir, Adleman · MIT · CACM 1978

这篇论文干了什么？

你在浏览器地址栏见过那把小锁、在网上付过款、发过一条没人能偷看的消息——这些背后几乎都站着 RSA。1977 年，MIT 的三个人（Rivest、Shamir、Adleman）造出了第一套真正能用的「公开锁、私藏钥」加密法：锁可以到处发、钥匙只有你有。今天全球的 HTTPS、数字签名、安全支付，源头都能追到这一篇。

旧世界的痛

在它之前，加密像一把普通的锁：锁门和开门用的是同一把钥匙。于是有个死结——你想给一个陌生人发密信，得先想办法把那把钥匙安全地交到他手上；可要是你们之间已经有条安全通道能传钥匙，那还加什么密？「想安全通信，得先安全通信」，鸡生蛋、蛋生鸡。全世界几亿对陌生人两两之间都得预先偷偷换钥匙，根本转不动。

那个点子

RSA 把一把钥匙拆成了两半：一把公开锁、一把私藏钥，而且锁上的只能用钥开、不能用锁再开回去。你把公开锁像发名片一样满世界散出去；任何人想给你发密信，就用你的锁把消息「咔哒」锁进盒子——但锁上之后连他自己也打不开了，只有攥着私藏钥的你能打开。从此两个素不相识的人，不用事先换任何秘密，也能安全通信。死结解开了。

它凭什么锁得住？

秘密藏在一个小学生都懂、却难倒最快超级计算机的算术事实里：把两个很大的质数乘起来，一瞬间就算完；可给你那个乘积，让你反推是哪两个质数乘出来的，几乎没人算得动。就像把两种颜料一搅就成新色、想再分开却无从下手。

你的「公开锁」本质上就是那个巨大的乘积；你的「私藏钥」就是那对只有你知道的质数。别人拿乘积能把消息搅乱（上锁），但没有那对质数就理不清、还原不回来（开锁）。数字越大越安全——如今用的数字大到，就算全世界的电脑一起算到宇宙尽头也拆不开。

反过来用，就是签名

这套锁钥还能倒着玩：你用私藏钥给一份文件「盖个章」，别人用你满世界发的公开锁一验，就能确认「这真是你盖的、且一个字没被改过」——因为只有你有那把私钥。这就是数字签名，网上合同、软件更新、证书全靠它证明「我是我」。

一句话记住

把钥匙拆成「公开锁 + 私藏钥」，锁能随便发、只有你能开——靠的是「两个大质数相乘容易、把乘积拆回质数极难」。陌生人不用先换秘密就能安全通信，倒过来用还能签名。代价是它算得慢（只用来锁一把小钥匙），而且未来的量子计算机可能把它拆开。

想看公钥/私钥的数据流图、真实公式和那道「陷门」的原理？ → 切到精读版

一句话

RSA 给出了第一套实用的公钥密码体制：每人有一对钥匙——公开的 (n, e) 和私藏的 d；任何人都能用你的公钥加密或验签，只有你能用私钥解密或签名。它把「加密」实现成一次模幂运算 c = m^e mod n，其安全性建立在大整数分解极难这一假设上：知道公钥 n 却算不出私钥 d，因为那需要先把 n 分解成两个大质数。这一篇把 Diffie–Hellman 一年前提出的公钥「概念」第一次落地成可算的算法。

Glossary · 术语表

密码学（cryptography）：研究怎样把消息变成只有指定对象能读懂的乱码、以及怎样验证消息真伪的学问。
对称密码（symmetric cipher）：加密和解密用同一把密钥的传统体制（如今天的 AES）；快，但通信双方必须先偷偷共享这把密钥。
公钥密码（public-key cryptography）：每人一对钥匙——公钥公开、私钥自留；用一把加密、另一把才能解，双方无需预先共享秘密。RSA 是它的第一个实用实现。
质数 / 素数（prime）：只能被 1 和自己整除的整数，如 2、3、5、61。任何整数都能唯一地拆成若干质数相乘。
整数分解（factoring）：把一个大整数拆回「哪几个质数相乘得到它」。正着乘很快，反着拆极慢——RSA 的命根子。
模运算 / 取模（mod）：「除法只留余数」的算术，像时钟绕圈——15 mod 12 = 3。绕圈会把结果搅乱、藏住原数。
模幂（modular exponentiation）：算 m^e mod n，即「m 自乘 e 次，再对 n 取余」。有快速算法，几百位大数也能秒算。
单向 / 陷门函数（trapdoor one-way function）：正着算容易、倒着推极难，但掌握一个秘密（陷门）就能轻松倒推的运算。RSA 的私钥就是那道陷门。
数字签名（digital signature）：用私钥给消息盖的「电子章」，任何人用对应公钥可验证它确实出自本人、且未被篡改。

坐标

作者是 Ron Rivest、Adi Shamir、Leonard Adleman，三人当时都在 MIT；论文 1977 年写成、1978 年 2 月发表于《Communications of the ACM》。它直接接续 Diffie 与 Hellman 1976 年的《New Directions in Cryptography》——那篇提出了「公钥」和「数字签名」的设想与密钥交换，却没给出一个能同时做加密和签名的完整方案；RSA 正是把这个设想第一次变成可算的算法。三人因此获 2002 年图灵奖。（后来解密的档案显示，英国 GCHQ 的 Clifford Cocks 早在 1973 年就秘密想出了等价方案，但因保密未能公开、也未影响历史进程。）

问题与动机

1976 年之前，所有密码都是对称的：锁门与开门同一把钥匙。这带来两个绕不过去的难题。

第一是密钥分发：要和某人保密通信，你俩得先共享一把密钥；可这把密钥本身怎么安全送达？若已有安全通道传它，又何必加密——鸡生蛋的死结。而且 N 个人两两通信需要约 N²/2 把不同密钥，规模一大就管理不动。第二是数字签名：现实里签名/盖章能证明「这是我发的、没被改」，可对称密码里双方共享同一把钥匙，谁都能伪造对方，无法向第三方证明到底是谁签的。

Diffie–Hellman 指出了出路——把加解密的能力拆成不对称的两半，并给出了在公开信道上协商共享密钥的方法；但他们没有造出一个能直接加密任意消息、又能签名的具体体制。缺的那块拼图，就是一个合适的陷门单向函数：正着谁都能算（人人能加密），倒着只有持私钥者能算（唯我能解密）。RSA 补上了它。

核心思想 / 方法

陷门单向函数：把「难」变成安全的地基

公钥密码要成立，需要一个这样的运算：给了公钥，人人都能正着算（加密）；但想倒着还原（解密），除非握有私钥这道「陷门」，否则难到不可行。RSA 找到的陷门，就藏在「乘法易、分解难」的鸿沟里——把两个大质数相乘一瞬完成，把乘积拆回质数却让最强的算法与硬件都望而却步。

图 1 · 陷门：p、q 相乘得 n 一瞬完成，反过来把 n 分解回 p、q 极难——落差越大越安全，而知道 p、q 的人（持私钥者）能绕过这道难关。

造钥匙：从两个质数到一对公私钥

密钥生成分四步，每一步都只是初等数论：

① 随机取两个大质数 p、q，相乘得 n = p·q（叫模数，几百位十进制数）。
② 算 φ(n) = (p−1)(q−1)（欧拉函数，直觉上是「1 到 n 里与 n 互质的个数」；知道 p、q 才算得出它）。
③ 挑一个与 φ(n) 互质的公开指数 e（常用 65537）。
④ 求 d，使 e·d ≡ 1 (mod φ(n))——即 d 是 e「关于 φ(n) 的逆」，用扩展欧几里得算法秒算。

于是：公钥 = (n, e)，公开发布；私钥 = d（连同 p、q）自己藏好。要点在于：d 由 e 和 φ(n) 决定，而 φ(n) 又要靠 p、q 才能算出；旁人只看得到 n，想得到 φ(n) 就得先把 n 分解——这正是难题所在。

加密与解密：一趟模幂来回

把消息编码成一个比 n 小的数 m。加密就是一次模幂：c = m^e mod n（用公钥把 m 搅成密文 c）。解密是另一次模幂：m = c^d mod n（用私钥把 c 还原回 m）。两把指数 e、d 像一对互逆的旋钮，先拧 e 再拧 d，正好转回原样。

它为什么转得回来？因为一个数论事实保证了 m^(e·d) ≡ m (mod n)——由于当初就让 e·d ≡ 1 (mod φ(n))，先 e 次方再 d 次方等于绕模 n 转了整整一圈又回到 m（背后是欧拉定理 / 费马小定理；推导可略，直觉就是「e 和 d 在模 φ(n) 的意义下互相抵消」）。攻击者看得到 (n, e, c)，想解出 m 就得知道 d；想知道 d 就得知道 φ(n)；想知道 φ(n) 就得把 n 分解成 p、q——绕来绕去都撞回那道分解难题。

举个真实小例子（数字小仅为演示，实际要几百位）：取 p=61、q=53，则 n=3233、φ(n)=3120；取 e=17，算得 d=2753（因 17×2753=46801=15×3120+1）。加密 m=65：65^17 mod 3233 = 2790；解密 2790^2753 mod 3233 = 65，分毫不差地转回。

图 2 · 加密/解密：发送方用「我」公开的 (n,e) 把 m 搅成密文 c；c 在公开信道上传输，偷看者缺私钥 d 还不出 m；只有握 d 的我能算 c^d mod n 还原 m。

倒过来用：数字签名

RSA 的对称之美在于两把钥匙可以互换角色。签名时反着来：作者用私钥算 s = m^d mod n 给消息盖章，任何人用其公钥算 s^e mod n 若还原出 m，就证明「这确实出自私钥持有者、且内容未被改动」——因为只有他有 d，别人伪造不出能通过验证的 s。这第一次让可公开验证、又无法抵赖的电子签名成为可能。（实际系统里先对消息做哈希再签，并加规范填充，见下文局限。）

关键结果

作为一篇 1978 年的算法论文，它的「结果」不是跑分，而是给出并论证了方案本身可行且安全：正确性由 m^(e·d) ≡ m (mod n) 严格保证；安全性归结为「无有效算法能从 n 分解出 p、q，或直接从公钥求私钥」。作者估算，用当时的分解算法，破解一个约 200 位十进制（≈664 比特） 的 n 需要天文级的时间。他们还在文末抛出著名的 RSA-129 挑战（一个 129 位十进制数），悬赏分解——这道题直到 1994 年才被上千台机器协作攻克，反过来印证了「分解确实很难，只是随算力增长安全边界要不断上调」。今天的实用密钥已普遍用 2048 比特及以上。

为什么重要 / 影响

RSA 把公钥密码从「一个漂亮设想」变成了可部署的工程现实，直接支撑起现代数字社会的信任骨架：HTTPS/TLS 里浏览器与网站的握手、数字证书与证书颁发机构（CA）、PGP 邮件加密、代码与软件更新签名、乃至早期的电子商务与网银，长期都以 RSA 为核心。它把「加密」和「签名」这两件此前需要预共享秘密或当面公证才能做的事，变成了任何两个陌生实体在开放网络上就能完成的操作。三位作者不仅拿下图灵奖，还创办了 RSA 公司，把这套算法推向了整个产业。可以说，没有它，就没有今天可以放心付款、登录、通信的互联网。

局限与批评

慢，不适合加密大数据：模幂比对称密码慢几个数量级，所以现实中几乎从不用 RSA 直接加密正文，而是混合加密——用 RSA 加密一把随机的对称密钥，正文再交给 AES 之类快速算法。
「教科书 RSA」不安全，必须加填充：直接 m^e mod n 是确定性的（同一明文永远得同一密文，可被字典比对），且具可乘性（c₁·c₂ 对应 m₁·m₂ 的密文，可被恶意利用）。真实系统必须用规范填充（加密用 OAEP、签名用 PSS）；历史上 Bleichenbacher 对旧填充 PKCS#1 v1.5 的攻击就曾大面积中招。
实现处处是坑：质数生成随机性不足、多个密钥共用素因子、小指数无填充（Coppersmith / Håstad 广播攻击）、以及计时/侧信道，都能让数学上安全的 RSA 在工程上被攻破。
安全性只是「假设」而非证明：整数分解至今没被证明一定很难，也没被证明「破 RSA 必须先分解」；一旦分解出现突破，RSA 即告危。
量子计算的达摩克利斯之剑：Shor 算法（1994）表明足够大的量子计算机能高效分解大整数，从而彻底攻破 RSA——这正是当下后量子密码（PQC）迁移的直接动因。
并非最早：GCHQ 的 Cocks 早在 1973 年已私下得到等价构造，只是因保密未公开——RSA 是独立且第一个公开的发明。

要点

① 一句话：第一套实用公钥体制——公钥 (n,e) 人人可加密/验签，私钥 d 只有你能解密/签名。

② 痛点：对称密码有「密钥分发」死结（想安全通信得先安全通信）和「无法向第三方证明谁签的」；RSA 用不对称的两把钥匙破局。

③ 陷门：安全靠「大质数相乘易、把乘积分解回质数极难」；知道 p、q 的人能绕过难关。

④ 造钥：n=p·q、φ=(p−1)(q−1)、选 e、求 d≡e⁻¹ (mod φ)；d 要靠 φ、φ 要靠 p、q。

⑤ 收发：加密 c=m^e mod n、解密 m=c^d mod n，靠 m^(ed)≡m (mod n)（欧拉/费马）转得回来。

⑥ 反用即签名：私钥盖章 s=m^d mod n、公钥验 s^e mod n，可公开验证、不可抵赖。

⑦ 影响：HTTPS/TLS、数字证书、PGP、软件签名的地基；三人获 2002 图灵奖。

⑧ 局限：慢（故混合加密）；裸用不安全需 OAEP/PSS 填充；实现多坑；安全性只是假设；Shor 算法下量子计算机可破，正推动后量子迁移。