跳转到内容
← 返回先驱
密码学1947–约 16 分钟阅读

罗纳德·里维斯特

Ronald Rivest

1977 年 8 月，《科学美国人》（Scientific American）专栏作家 Martin Gardner 在其"数学游戏"专栏里刊登了一道挑战题：破解一段用新密码加密的信息，奖励 100 美元。这段密码来自三位 MIT 教授的最新研究——Rivest、Shamir、Adleman——他们估计，用当时最快的计…

密码学RSA公钥加密图灵奖

1977 年 8 月，《科学美国人》（Scientific American）专栏作家 Martin Gardner 在其"数学游戏"专栏里刊登了一道挑战题：破解一段用新密码加密的信息，奖励 100 美元。这段密码来自三位 MIT 教授的最新研究——Rivest、Shamir、Adleman——他们估计，用当时最快的计算机破解大约需要 4 × 10^16 年。

1994 年 4 月，这道题被解开了。不是因为破解算法被找到，而是因为一支由 Derek Atkins、Arjen Lenstra 等人协调的分布式计算团队，动用了来自全球约 600 名志愿者贡献的约 1600 台计算机，协作计算了 8 个月，把这个 129 位数（RSA-129）分解出来。

Gardner 的那道题验证了一件事：RSA 加密是可以被破解的，但需要极端的计算资源——而这正是它之所以安全的理由。

破除误解：公钥加密不是 RSA 发明的

RSA 算法（1977）是公钥密码的第一个公开实用实现，但公钥密码的概念是 Diffie 和 Hellman 在 1976 年提出的。Diffie-Hellman 密钥交换（DH）比 RSA 早一年，是"两个人通过不安全信道建立共享密钥"这一思想的首次公开发表。

更早的是：英国政府通信总部（GCHQ）的密码学家 Clifford Cocks 在 1973 年就独立发现了与 RSA 等价的算法，但被列为机密，直到 1997 年才解密公开。RSA 是公钥密码的第一个公开发表的实用实现。

Rivest 本人对这段历史非常坦诚，从不声称自己"发明了公钥密码"，而是"和同事实现了 Diffie-Hellman 的愿景"。

现场：MIT 办公室里的一个夜晚

1977 年，Diffie-Hellman 论文发表后不久，MIT 教授 Leonard Adleman 在一次讲座后向他的两位同事 Ron Rivest 和 Adi Shamir 介绍了这个新思想。三人都对公钥密码的具体实现问题着迷：Diffie 和 Hellman 提出了框架，但没有给出一个具体的单向函数。

接下来的数月，Rivest 和 Shamir 每周都提出一个新方案，Adleman 负责找出每个方案的漏洞。1977 年 4 月的一个夜晚，Rivest 在聚会回家后辗转难眠，坐在沙发上开始推导，凌晨写完了 RSA 算法的初稿。第二天清晨，他把手稿交给了 Adleman，Adleman 找不到任何漏洞。

RSA 的数学基础是两个大素数相乘容易，但给定乘积分解回两个素数极难（大整数分解问题，Integer Factorization Problem）：

n=p×qn = p \times q

已知 $n$ 和公钥指数 $e$，加密：c≡me(modn)c \equiv m^e \pmod{n}；已知私钥指数 $d$（由 $p$、$q$ 确定），解密：m≡cd(modn)m \equiv c^d \pmod{n}。

1983 年，MIT 为 RSA 申请了专利（美国专利 4,405,829）；2000 年，专利到期，RSA 算法进入公共领域。

数论基础：为什么这套方案既正确又难破

RSA 的正确性来自一条三百多年前的定理。私钥指数 $d$ 被构造为 $e$ 在模 φ(n)=(p−1)(q−1)\varphi(n) = (p-1)(q-1) 下的乘法逆元，即 ed≡1(modφ(n))ed \equiv 1 \pmod{\varphi(n)}。由欧拉定理，对任意与 $n$ 互素的 $m$ 都有 mφ(n)≡1(modn)m^{\varphi(n)} \equiv 1 \pmod{n}，于是解密运算 cd=medc^d = m^{ed} 恰好绕回 $m$。整个系统的正确性是已证明的数学，不依赖任何经验假设。

RSA 的安全性则完全是另一回事——它押在"大整数分解很难"这个未经证明的经验事实上。看清"难"的形状，才能理解 RSA 的寿命逻辑：

  • 试除法需要检查到 n\sqrt{n} 的所有素数。对 1024 位的 $n$，这是约 25122^{512} 次试除——严格指数级，永远不可行。RSA 在 1977 年的安全裕度就来自这里。
  • 但分解并非真指数难题。筛法家族不断压低复杂度：1980 年代的二次筛法（QS）已经能分解百位级数字（1994 年破解 RSA-129 用的就是它）；1990 年代成熟的通用数域筛法（GNFS）把复杂度压到次指数 exp⁡ ⁣((64/9)1/3(ln⁡n)1/3(ln⁡ln⁡n)2/3)\exp\!\left((64/9)^{1/3} (\ln n)^{1/3} (\ln\ln n)^{2/3}\right)——比任何多项式都增长快，但远慢于真指数。
  • 这条曲线直接写进了公开记录：RSA-768（768 位）2009 年被分解，耗时约 2000 个 CPU 核年；RSA-250（829 位）2020 年被分解，约 2700 核年。每十几年，实际可分解的位数上涨一截，RSA 的推荐密钥长度就跟着从 512 涨到 1024、2048、3072。

这正是"次指数"的工程含义：密钥每加长固定位数，分解成本的增长都超出多项式，防御方始终领先——但领先优势随算法进步和算力增长不断被侵蚀。RSA 的安全不是一堵墙，而是一场需要不断加高堤坝的赛跑。

Rivest 的其他贡献

MD5（1991）和 MD4（1990）：Rivest 设计的消息摘要（哈希）算法，用于数字签名和完整性验证。MD5 的崩塌过程是密码学史上最有教学价值的案例之一——它不是被一击致命的，而是被逐步侵蚀：

  • 2004 年 8 月，中国密码学家王小云及其团队在 CRYPTO 会议的 rump session 上演示了 MD5 的实际碰撞：两个不同的输入产生相同的哈希值。碰撞攻击的全部意义在于"伪造"——如果你能让两份内容不同的文件哈希相同，数字签名和证书体系的基础就松动了。
  • 2008 年，Sotirov、Stevens 等人把碰撞做成了武器：他们构造了一对"选定前缀"碰撞，伪造出一个假冒的 CA（证书颁发机构）证书，证明 MD5 签名在现实 PKI 体系里可以被实际利用，论文标题就叫《MD5 considered harmful today》。
  • 2012 年，矛头指向国家级攻击： Flame 恶意软件被证实利用 MD5 碰撞伪造微软的代码签名证书，让恶意代码在 Windows 更新机制里被当成官方更新安装。理论漏洞由此完成了到真实破坏的闭环。
  • 类似的剧本在 SHA-1 上重演：理论弱点 2005 年起就有预警，但直到 2017 年 2 月，Google 与荷兰 CWI 的研究者才以约 2632^{63} 次运算的成本公开第一个实际碰撞（SHAttered）。从预警到实证，又给了业界十二年——而迁移依然拖沓。

这条时间线的教训写在所有密码标准的迁移指南里：算法的死亡是渐进的，"还没被实际攻破"不等于安全，等实际碰撞出现时再换就已经晚了。MD5 今天仍广泛用于文件完整性校验（碰撞攻击对"防篡改"场景威胁有限），但在一切安全场合均已出局。

RC 系列密码（1987–2003）：Rivest Cipher（RC2、RC4、RC5、RC6）是一系列对称密钥密码，兴衰同样折射了密码工程的时代变迁。RC4 设计于 1987 年，本是 RSA Security 的商业机密，1994 年被匿名者把源码贴到 Cypherpunks 邮件列表后公开流传——它极简（核心算法只有十几行）、极快，被 SSL/TLS、WEP 等协议大量采用。问题出在使用方式与统计偏差两头：2001 年 Fluhrer、Mantin、Shamir（正是 RSA 的 "S"）发表攻击，利用 RC4 密钥调度的弱点——WEP 把 24 位初始向量直接与密钥拼接，恰好落入弱密钥类别，被动监听足够多数据包即可恢复密钥，WEP 由此实质性破产；此后研究者又发现 RC4 输出流的长期统计偏差，2015 年 IETF 以 RFC 7465 在 TLS 中全面禁用 RC4。与流密码 RC4 的没落相对照，Rivest 在分组密码上的设计走向了公开评审：RC5（1994）以参数化的字长、轮数、密钥长度和"数据相关旋转"著称，成为研究差分密码分析的标准样本；RC6（1998）入围 AES 最终五个候选算法，虽未中选，但全程公开接受全球密码学界的攻击检验——这种"放在阳光下让所有人打"的评审模式，本身就是从 RC4 时代的保密设计学到的教训。

选举安全：Rivest 的后期研究转向了电子选举系统的安全性。2006 年，他提出 ThreeBallot 投票系统：每张选票拆成三份，通过密码学式的构造让选民能验证自己的票被正确计数，却无法向他人证明自己投了谁——前者防选举舞弊，后者防买票和胁迫。该系统未实际部署，但它精确刻画了选举验证性的内在矛盾，是"审计导向"（Audit-Based）选举安全流派的奠基性设计，直接影响了后来的端到端可验证投票系统研究。

算法教材：Rivest 是《算法导论》（Introduction to Algorithms，CLRS，与 Cormen、Leiserson、Stein 共著）的联合作者之一。这本书被全球数千所大学用作算法课教材，是计算机科学教育史上最有影响力的教材之一。

2002 年图灵奖

Rivest 与 Adi Shamir 和 Leonard Adleman 共同获得 2002 年 ACM 图灵奖，表彰他们对公钥密码的贡献。值得注意的是，Diffie 和 Hellman 直到 2015 年才获得图灵奖——公钥密码概念的提出者获奖比实现者晚了 13 年，这在图灵奖历史上是罕见的时间差。

Rivest 目前是 MIT 电气工程与计算机科学系 Viterbi 讲席教授，在 MIT 计算机科学与人工智能实验室（CSAIL）的密码与信息安全组工作。

代价与争议

专利与加密民主化：RSA 的专利（1983–2000）使得 RSA 的商业使用需要授权，这在 PGP（Pretty Good Privacy，Phil Zimmermann，1991）首次发布时引发了法律纠纷——PGP 绕过了 RSA 许可证要求，美国政府甚至以"出口加密软件"为由对 Zimmermann 展开调查（后撤销）。这场争论推动了"密码学无国界"运动，也加速了 RSA 专利的最终到期。

量子计算的威胁：RSA 的安全性依赖大整数分解的计算困难性。Shor 算法（1994）证明，量子计算机能在多项式时间内完成大整数分解，从理论上破解 RSA。目前没有足够大的容错量子计算机来执行此任务，但 NIST（美国国家标准与技术研究院）已在 2022 年前后开始标准化后量子密码算法（Post-Quantum Cryptography），以替代 RSA 和椭圆曲线密码。Rivest 对这一议题持续关注，认为量子威胁是"值得认真对待的长期风险"。

跨域连接

  • 数论：这里有一处常被混淆的分界。算法的正确性是定理，安全性只是"目前尚无高效分解算法"这一经验事实——两者的认识论地位完全不同。可检验的后果非常干脆：分解一旦被高效解决，正确性丝毫不受影响，而安全性当场归零。密码系统的寿命押在后一半上。
  • 量子纠错：量子算法把分解归约为求周期，这一步在原理上是多项式的；但要真的跑起来，必须先有足够多的逻辑比特，而逻辑比特要靠大量物理比特纠错合成。于是威胁的时间表由纠错开销决定，而不是由算法决定——后量子迁移的时间窗口，正是从这条开销曲线里估出来的。
  • 选举制度：选举同时要求两条互相冲突的性质：每位选民能验证自己的票被计入，且无法向他人证明自己投了谁——否则买票与胁迫立刻有了验收手段。这把问题从流程改造推向密码学：需要的是可验证但不可转让的凭证。判据也现成——任何能让选民出示证据的方案，都同时造出了胁迫工具。
  • 言论自由：把加密算法当作受管制的军品，与把源代码当作受保护的表达，是两种不相容的定性。争议的实质不是技术，而是同一段文本在两套法律框架下的归类。归类一旦倒向表达一侧，出口管制在事实上就失去了抓手，这也是当年那场纠纷真正的争夺点。
  • 密码学基础：现代安全定义都是相对的——"安全"意味着任何多项式时间的对手成功概率可忽略，因此它必然依赖某个未被证明的困难性假设。学科的进步方式随之确定：不是逐个论证方案不可破，而是把新方案归约到少数几个标准假设上，让风险集中且可被共同盯着。

人物小记：密码学家与公民科学家

Rivest 的职业生涯横跨密码学的商业化（RSA 专利与 RSA Security 公司）和学术化（MIT 教职与开放研究）两个世界，这在密码学界是不常见的双重身份。

他对选举安全的关注体现了一种罕见的视野：密码学不只是网络安全的工具，也可以是民主制度的保障机制。他的 ThreeBallot 系统设计理念是，即使选举官员也不能操控结果，同时选民也无法向他人证明自己投了谁——在数字时代维持匿名投票的技术路径。

RSA Security 公司（Rivest、Shamir、Adleman 1982 年联合创立）在 2006 年被 EMC 以 2.1 亿美元收购，2011 年遭受严重的网络攻击（RSA SecurID 令牌被盗），是互联网安全史上最受关注的安全事件之一，Rivest 亲历了从密码发明到密码体系被攻击的全过程——一种技术史的切身讽刺。

参考文献

  • Rivest, R., Shamir, A., Adleman, L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. CACM 21(2), 1978.（RSA 原始论文）
  • Diffie, W. & Hellman, M. New Directions in Cryptography. IEEE Trans. Info. Theory 22(6), 1976.（公钥密码概念的首次公开发表）
  • Cormen, T., Leiserson, C., Rivest, R., Stein, C. Introduction to Algorithms. 4th ed., MIT Press, 2022.（CLRS，算法课标准教材）
  • NIST. Post-Quantum Cryptography Standardization. nist.gov, 2022.（后量子密码标准化进展）
  • Rivest, R. The MD5 Message-Digest Algorithm. RFC 1321, IETF, 1992.
  • Wang, X. & Yu, H. How to Break MD5 and Other Hash Functions. EUROCRYPT, 2005.（MD5 碰撞攻击的正式论文，2004 年于 CRYPTO 率先披露）
  • Stevens, M., Bursztein, E., Karpman, P., Albertini, A., Markov, Y. The First Collision for Full SHA-1. CRYPTO, 2017.（SHAttered，SHA-1 首个实际碰撞）
  • Sotirov, A., Stevens, M., Appelbaum, J. et al. MD5 Considered Harmful Today. Chaos Communication Congress, 2008.（用 MD5 碰撞伪造 CA 证书）
  • Rivest, R. The ThreeBallot Voting System. MIT CSAIL, 2006.（端到端可验证投票的早期设计）
  • Zimmermann, P. PGP Source Code and Internals. MIT Press, 1995.（密码民主化运动的实践记录）

延伸阅读

  • Singh, S. The Code Book. Doubleday, 1999.（密码学历史叙事，包含 RSA 的故事，适合非专业读者）