第 14 章

密码学的革命——1976年，为什么公开一把钥匙，反而能保护秘密？

正在加载交互实验…

第一季 · 人类如何驯服数据

历史主线：1969—1997年 · 英国 GCHQ、斯坦福大学、MIT，以及公钥密码学的诞生1974年秋天，美国斯坦福大学。一名留着长发和胡子的年轻研究者，打电话给一位电气工程教授。他已经花费两年时间，到处寻找愿意与他讨论密码学的人。大多数研究人员并不感兴趣。还有一些研究成果属于国家机密，根本无法公开。但这一次，电话那头的教授产生了兴趣。他们约好见面。原本只打算交谈半个小时。结果越谈越兴奋，从下午一直聊到晚上，最后还去了教授家中继续讨论。他们面对一个当时几乎不可思议的问题：如果两个人从未见过面，也没有任何预先共享的秘密，能否通过一条人人都能窃听的通信线路，建立安全的通信？这两个人是 Whitfield Diffie 和 Martin Hellman。他们并不知道，在大西洋彼岸，英国的一批密码研究人员已经秘密探索了类似的思想。更不知道，自己正在参与的研究会成为未来互联网安全通信的重要基础。^{[WIRED][ACM Turing Award]}

第一幕：一个在密码学中持续了数千年的难题

想象你生活在1970年。你需要通过电话线向另一个城市的同事发送机密文件。最直接的办法是加密。例如，你和同事事先约定一个秘密密钥：K发送者使用它加密：

C=E_K(M)

接收者使用同一个密钥解密：

M=D_K(C)

这叫作对称密码（Symmetric Cryptography）。问题是：你们如何安全地交换密钥 K？如果通过普通邮件发送，信件可能被截获。如果通过电话告诉对方，线路可能被监听。如果派专人送过去，就需要安全的运输渠道。于是，一个非常尴尬的悖论出现了：为了安全通信，需要先共享秘密；为了安全共享秘密，又需要安全通信。

传统对称密钥困境

查看 SVG 配图原件

14-002.svg · 点击查看大图

在军事、外交领域，这个问题可以通过密钥管理中心、外交信使或预先分发密钥等方式缓解。但到了1970年代，计算机开始进入大学、企业和金融机构。人们开始设想：如果将来有一百万台计算机需要彼此安全通信，难道还要专门派人给每一对计算机送密钥吗？这不仅昂贵，而且很难管理。因此，密码学迫切需要一种新的思路。

第二幕：1970年，英国的秘密研究——“不需要保密的加密”

故事先不去美国。我们来到英国。1970年前后，在英国政府通信总部 GCHQ 的密码研究体系中，一位研究人员正在思考同样的密钥分发问题。他叫作 James H. Ellis。Ellis 1924年出生于澳大利亚，后来移居英国，1952年进入 GCHQ 工作。他长期从事通信安全和密码研究。传统密码学有一个根深蒂固的认识：加密双方必须共同持有某种秘密。但 Ellis 开始怀疑：秘密是否一定要存在于加密过程本身？假如存在一种数学变换：任何人都可以执行正向运算。但只有掌握某个秘密的人，才能高效完成逆向运算。那么发送者根本不需要知道接收者的秘密。只需要掌握公开的正向规则，就可以把消息加密。接收者则利用自己的秘密信息恢复原文。Ellis 将这种思想称为：Non-Secret Encryption，不保密的加密。这个名字很反直觉。但它恰恰抓住了后来公钥密码学的核心：加密规则可以公开，解密能力却仍然由秘密信息保护。GCHQ 的官方历史确认，Ellis 在1970年前后提出了这一概念。^[GCHQ]

1973年，一名年轻数学家找到具体方法

1973年，另一位 GCHQ 研究人员 Clifford Cocks 进一步取得突破。他发现可以利用大整数分解的困难性，构造满足 Ellis 想法的密码系统。其数学机制与数年后公开发表的 RSA 非常相似。1974年，Malcolm Williamson 又独立研究了与后来 Diffie–Hellman 密钥交换相近的方案。但这一切都属于机密研究。公众和普通学术界根本不知道这些发现。直到1997年，英国方面才公开承认相关早期成果。^{[GCHQ][国家安全局]}这就出现了计算机科学史上非常特殊的一段双线发展：英国密码机构内部已经发现了关键思想，却因为保密无法公开。美国大学的研究者则沿着公开学术研究路线，独立推动了公钥密码学的发展。两条历史路线，最终在几十年后才被人们放到一起理解。

第三幕：1974年，一个研究密码学的年轻人开车穿越美国

Whitfield Diffie

1944年出生 · 密码学研究者他的研究帮助现代密码学从高度保密的专业活动，发展成可以在大学公开讨论、证明和发表的研究领域。

Diffie 年轻时就对计算机、数学和隐私问题产生了浓厚兴趣。在当时，密码学与军事情报机构联系紧密。公开文献很少。一些研究甚至可能涉及政府的保密限制。但 Diffie 相信，随着计算机网络的发展，普通个人和企业也会需要可靠的密码技术。于是，从1972年前后开始，他投入大量时间寻找新的密码方法。他驾驶一辆 Datsun 510 汽车，走访不同研究机构、图书馆和学者。根据1994年《WIRED》对他的采访，他连续约两年四处寻找相关线索。到1974年秋天，他听说斯坦福大学有一位教授也在研究密码学。于是他打了那个电话。^[WIRED]

Martin Hellman：另一个不愿接受传统限制的人

Martin Hellman

1945年出生 · 斯坦福大学电气工程教授长期研究信息论、编码和密码学，也持续关注核安全与国际安全等问题。

Hellman 当时也在尝试将密码学变成公开学术研究的一部分。但研究进展并不轻松。能够公开交流的同行非常少。因此，当 Diffie 出现在他的办公室时，两人很快发现：彼此都已经在思考相近的问题。两人第一次见面，从原本的短谈延续了大半天。此后开始合作。在这段研究过程中，还有一位后来常被忽视的重要人物：Ralph Merkle。他当时是年轻的大学生，研究如何在公开通信环境下建立共享秘密，并提出了 Merkle's Puzzles（Merkle 谜题）的思路。Hellman 后来多次强调，Merkle 对公钥密钥分发思想作出了独立而重要的贡献，因此他更愿意把相关研究称作 Diffie–Hellman–Merkle 的共同成果。^{[amturing.acm.org][www-ee.stanford.edu]}

第四幕：1976年，一个惊人的数学想法——双方都公开数字，却得到相同秘密

1976年，Diffie 和 Hellman 在 IEEE Transactions on Information Theory 发表：New Directions in Cryptography《密码学的新方向》。这篇论文讨论了公钥密码系统、数字签名和密钥分发等重要问题，并给出一种可以通过公开通信建立共同密钥的具体方法。^{[cr.yp.to][IEEE Information Theory Society]}它是现代密码学最重要的公开论文之一。阅读 Diffie 与 Hellman 1976年原始论文 PDF现在，我们来亲手重新发现这个方法。

第一个数学工具：取模运算

你已经在哈希表那一章见过：

a\bmod p

例如：

29\bmod23=6

意思是29除以23，余数为6。现在做一种稍复杂的计算：

5^6\bmod23

虽然：

5^6=15625

但：

15625\bmod23=8

结果仍然只是0到22之间的数字。如果指数继续增大，计算结果虽然可能涉及极大的整数幂，但可以通过模幂算法高效得到。而如果只告诉你最后的余数：

5^x\bmod23=8

你能立刻知道

x

是多少吗？对于23这样的小数，枚举一下就行。但如果模数变成几千比特的大素数，并选择适当的群和参数，逆向求解可能变得极其困难。这类逆向问题与**离散对数问题（Discrete Logarithm Problem）**有关。Diffie–Hellman 进一步依赖这样的思想：即使知道两个公开幂值，要计算双方共享的组合结果，也应当在所选群中计算上不可行。这涉及计算 Diffie–Hellman 假设，而不只是简单地说“所有取模运算都无法逆向求解”。

第五幕：Alice 和 Bob 如何通过公开线路得到同一个秘密？

我们用小数字演示。先公开约定：

p=23,\qquad g=5

这两个数字所有人都知道。包括窃听者 Eve。Alice 私下选择：

a=6

Bob 私下选择：

b=15

两个私人数字不发送给对方。

Alice 计算公开值

A=g^a\bmod p

也就是：

A=5^6\bmod23=8

她把8发送给 Bob。

Bob 计算公开值

B=g^b\bmod p

也就是：

B=5^{15}\bmod23=19

他把19发送给 Alice。现在 Eve 可以看到全部公开信息：

p=23,\quad g=5,\quad A=8,\quad B=19

但没有看到私有指数6和15。接下来发生了真正神奇的事情。

Alice 用 Bob 的公开值，结合自己的秘密

K_A=B^a\bmod p

K_A=19^6\bmod23=2

Bob 用 Alice 的公开值，结合自己的秘密

K_B=A^b\bmod p

K_B=8^{15}\bmod23=2

最终：

\boxed{K_A=K_B=2}

双方得到了同一个秘密数。但从头到尾，没有把这个秘密数通过通信线路直接发送出去。

为什么两个结果必然相同？

因为：

K_A=(g^b)^a\bmod p

K_B=(g^a)^b\bmod p

而：

(g^b)^a=g^{ab}=(g^a)^b

所以：

\boxed{K_A=K_B=g^{ab}\bmod p}

这就是 Diffie–Hellman 的核心。并不是什么神秘技巧。它利用了模幂运算中的数学结构。但其安全性来自正向运算与已知公开信息下的逆向困难性之间的巨大差距。

实验一：你来执行一次密钥交换

Diffie–Hellman 密钥交换实验室

教学参数 p = 23，g = 5

模幂运算

Alice

私钥 a6

公开 A = 5^a mod 23

8

Bob

私钥 b15

公开 B = 5^b mod 23

19

公开交换 8 和 19

Alice 算出的共享秘密

2

Bob 算出的共享秘密

2

双方结果相同

无论怎样调整私人指数，两边都会算出相同的共享数值。注意：实验中的模数23极小，可以轻易被穷举破解，绝不具有实际安全性。

第六幕：一个重大漏洞——如果敌人不只是窃听，而是篡改消息呢？

现在，我们不能只为刚才的数学结果感到高兴。因为还有一个安全问题。假设 Eve 不只是静静监听。她还能够拦截 Alice 和 Bob 的通信，并替换消息。那么会发生什么？Alice 本来想把公开值 A 发送给 Bob。Eve 截获 A，却把自己的公开值 E₁ 发给 Bob。Bob 本来想把 B 发送给 Alice。Eve 截获 B，却把自己的另一个公开值 E₂ 发给 Alice。结果：Alice 与 Eve 建立了一个共享秘密。Bob 与 Eve 建立了另一个共享秘密。Alice 和 Bob 却误以为自己正在与对方安全通信。这叫作：中间人攻击（Man-in-the-Middle Attack）。

查看 SVG 配图原件

14-006.svg · 点击查看大图

所以 Diffie–Hellman 解决的是一个非常重要的数学问题：怎样在公开信道上协商共享秘密。但它本身不能自动证明另一端是谁。真实系统必须加入身份认证，例如数字签名、证书、预共享认证密钥等机制。而这恰好引出了公钥密码学的另一个重要用途：数字签名。

第七幕：1977年，MIT 的三位研究者连续失败42次

1976年，Diffie 和 Hellman 发表论文之后，计算机科学界开始意识到：公钥密码学不仅是一个大胆的设想，而且可能成为现实。但还有一个重要问题。Diffie–Hellman 可以建立共同秘密。能不能设计一种更直接的系统，让任何人使用我的公开密钥加密消息，而只有我能解密？这时，故事来到 MIT。三位研究人员开始探索：Ronald Rivest、Adi Shamir 和 Leonard Adleman。Rivest 与 Shamir 不断提出新的密码方案。Adleman 则尝试攻击它们。结果一次又一次地失败。不过，不是攻击者失败。而是密码设计方案失败。因为 Adleman 总能找到漏洞。

42次失败之后的第43次

根据 Adleman 后来的回忆，以及关于 RSA 早期历史的采访资料，Rivest 与 Shamir 先后提出了42种候选方案，都被 Adleman 找到问题。到了第43种，研究者终于提出了后来成为 RSA 的核心结构。这一次，Adleman 没能像以前那样轻易破坏它。于是三人将方案整理为论文。Rivest 还曾希望按照字母顺序排列作者姓名，但 Adleman 对自己是否应该成为共同作者有过犹豫。最终三人的姓氏依次排列：Rivest、Shamir、Adleman。于是 RSA 诞生了。^{[WIRED][MacTutor History of Mathematics]}1977年4月，MIT 已经发布了相关技术报告。1978年2月，正式论文发表于 Communications of the ACM：A Method for Obtaining Digital Signatures and Public-Key Cryptosystems。^{[dspace.mit.edu][cs.sfu.ca]}阅读 MIT 1977年 RSA 原始技术报告

第八幕：RSA 的数学魔术——把两个素数乘起来

我们现在把 RSA 的原理拆解成最简单的数字实验。首先选择两个素数：

p=61,\qquad q=53

计算：

n=pq=3233

接着计算：

\varphi(n)=(p-1)(q-1)=60\times52=3120

这里

\varphi

是欧拉函数。因为

p

与

q

是不同素数，所以这个公式成立。选择公开指数：

e=17

要求：

\gcd(e,\varphi(n))=1

也就是说，17和3120互质。现在，我们需要找到私钥指数

d

，使：

ed\equiv1\pmod{3120}

可以使用扩展欧几里得算法求解。最终得到：

d=2753

因此：

公钥

(3233, 17)

可以公开给任何人

私钥

(3233, 2753)

必须保密

加密一个数字

假设我们要加密的消息是：

M=65

RSA 加密公式：

C=M^e\bmod n

代入：

C=65^{17}\bmod3233=2790

发送者把2790发送出去。接收者使用私钥：

M=C^d\bmod n

得到：

2790^{2753}\bmod3233=65

原始消息恢复了。

为什么这个过程能够逆转？

因为我们精心选择了

e

和

d

，使它们满足特定模运算关系。根据欧拉定理及相关数论性质，可以证明对于符合 RSA 参数条件的消息：

(M^e)^d\equiv M\pmod n

RSA 利用的关键事实是：知道两个大素数

p,q

，就容易计算

\varphi(n)

和相应的私钥指数。但如果只知道它们的乘积

n=pq

，而

p,q

足够大且随机选取，反向分解在经典计算模型中可能非常困难。RSA 的经典安全设计与整数分解困难性密切相关，但不能把它简化为已经证明“破解 RSA 与分解整数完全等价”。

实验二：RSA 加密与解密

RSA 数学实验室

教学小整数

原始消息 M

65

原始消息

65

公钥加密：M^17 mod 3233

2790

私钥解密：C^2753 mod 3233

65

这些极小参数仅用于解释模运算。真实 RSA 使用强随机生成的大素数、合适的填充方案和成熟的密码库，绝不可直接照搬此演示。

这里还有一个必须特别提醒的安全问题。这种直接执行：

C=M^e\bmod n

的形式叫作教科书式 RSA（Textbook RSA）。它是确定性的，而且具有可利用的代数结构，并不满足现代公钥加密的安全要求。真实 RSA 加密需要安全填充方案，例如 RSA-OAEP。数字签名则需要对应的签名标准，例如 RSA-PSS。因此，你应该把刚才的实验当作理解数论的工具，而不是可以直接部署的软件加密方案。

第九幕：公钥加密、密钥交换与数字签名，究竟有什么区别？

到这里，我们已经认识了两种重要的密码技术。但它们并不是同一回事。

Diffie–Hellman：协商共同秘密

Alice 与 Bob 各自保留私人值。双方交换公开值。最终算出相同的共享秘密。随后，再使用密钥派生函数把共享秘密转换为适合对称加密的密钥材料。实际应用时，通常使用 AES-GCM 或 ChaCha20-Poly1305 等认证加密算法保护后续数据。

RSA：公开加密密钥与私人解密密钥

任何人都可以使用接收者的公钥加密一段适合的密钥材料。只有持有相应私钥的人才能解密。但现代网络协议不一定采用 RSA 密钥传输。以 TLS 1.3 为例，密钥建立使用（椭圆曲线）Diffie–Hellman 或预共享密钥方式，RSA 证书若被使用，其作用是签名认证，而不是直接加密会话密钥。

数字签名：证明是谁发出的消息

现在把目标反过来。不是为了隐藏消息内容，而是为了让接收者能够验证：消息确实来自某个持有私钥的人。而且消息在传输过程中没有被修改。发送者使用私钥生成签名。接收者使用公钥验证签名。但公钥本身也必须和真实身份建立可信绑定。否则，攻击者完全可以拿自己的公钥冒充某个人的公钥。这就是证书体系、证书颁发机构和信任链等机制存在的原因。

技术	解决的问题	关键性质
对称加密	保护大量数据内容	快速，需要共享密钥
Diffie–Hellman	建立共享秘密	不必预先发送共同秘密
公钥加密	让持有私钥的人恢复消息	加密公钥可公开
数字签名	验证消息来源与完整性	签名私钥保密，验签公钥公开

你会发现：公钥密码学的革命，不在于它让计算机第一次能够加密消息。而在于：它改变了密钥必须如何分配，以及身份和信任能够如何建立。

第十幕：1997年，一场迟到了二十多年的历史承认

我们再次回到英国 GCHQ。此前你已经知道：Ellis、Cocks 和 Williamson 在1970年代初期就发现了相关思想。但直到1997年，GCHQ 才公开承认这些早期研究。这导致密码学历史长期存在两套叙事。公开学术研究史，通常从 Diffie、Hellman、Merkle、Rivest、Shamir 和 Adleman 展开。英国内部秘密研究史，则还需要把 Ellis、Cocks 和 Williamson 放到更早的位置。而如果从科学传播和应用发展角度看，两者的贡献又有所不同。英国研究人员进行了重要的早期秘密发现。美国大学研究者则公开发表算法、推动同行审查、形成学术研究体系，并促进了密码技术向广泛应用发展。这也是为什么历史贡献不能简单用“谁第一个想到”来完全衡量。

公钥密码发展时间线

1970年：James Ellis 在英国秘密研究中提出不保密加密的概念。
1973年：Clifford Cocks 研究出与后来的 RSA 数学机制相近的方案。
1974年：Malcolm Williamson 研究了相关密钥协商方法；Ralph Merkle 也独立提出公开密钥分发思路。
1976年：Diffie 与 Hellman 发表《New Directions in Cryptography》。
1977—1978年：MIT 的 RSA 技术报告与正式论文陆续发表。
1997年：英国公开承认 GCHQ 的相关早期成果。

此后，密码学进入一个更开放的时代。2015年度 ACM 图灵奖授予 Diffie 与 Hellman，表彰他们在现代密码学方面作出的重大贡献。^{[awards.acm.org]}与我们此前讲过的 AVL 树、B 树、快速排序、LZ 压缩一样，真正的历史并不是一个人灵光一现之后，世界便立即改变。而是思想提出、数学验证、独立发现、公开发表与工程实践，经过很多年才逐渐汇合。

第十一幕：为什么今天的互联网不直接使用1976年的原始方案？

到了今天，密码系统还面临更多要求。例如：身份认证。会话密钥的前向保密性。抵抗主动中间人攻击。抵抗重放。可靠的随机数生成。密码参数协商。防止侧信道泄漏。以及量子计算带来的潜在威胁。因此，现代 TLS、SSH 和加密通信软件，并不是简单运行几十行 RSA 或 Diffie–Hellman 代码。它们需要完整的协议设计、安全证明与大量工程防护。还有一个重要区别：现代通信通常采用混合加密（Hybrid Encryption）。公钥技术用于身份认证、密钥协商或保护密钥材料。对称加密用于高效保护大量实际数据。原因很简单。公钥运算一般比对称加密昂贵。如果要传输几 GB 的视频或文件，没有必要让每一个字节都经过昂贵的 RSA 运算。更合理的方法是先安全建立会话密钥，再用 AES-GCM 或 ChaCha20-Poly1305 等认证加密方式保护数据。

那量子计算会怎样改变这段历史？

如果未来具备足够规模且容错能力的量子计算机，Shor 算法将对基于整数分解和离散对数困难性的经典公钥密码方案构成严重威胁。因此，密码学已经发展出后量子密码（Post-Quantum Cryptography）方向。但后量子密码并不是“量子加密”，而是在普通计算机上运行、设计目标是抵抗已知经典与量子攻击的密码算法。从1976年的公钥革命，到今天的后量子迁移，密码学研究仍然在继续。

终章挑战：数学上成立，为什么不一定安全？

假设 Alice 和 Bob 完全按照 Diffie–Hellman 的数学公式计算。双方确实得到了同样的密钥。但是 Eve 可以拦截并替换双方发送的公开值。那么，仅靠原始的、未经认证的 Diffie–Hellman，是否能够保证 Alice 真的在与 Bob 通信？

密码学工程师的最后一道问题

可以。只要双方计算结果相同，就能保证身份正确。不可以。还需要认证机制，防止公开值被中间人替换。只要把素数取得足够大，就不需要身份认证。

尾声：密码学革命，真正改变的是信任的结构

1970年，英国研究人员 James Ellis 开始质疑一个传统假设：加密与解密，是否真的必须使用同一个秘密？1973年，Clifford Cocks 找到了关键的数学构造。1974年，Diffie 与 Hellman 相遇，共同推动公开密码学研究。1976年，他们发表一篇改变计算机科学发展方向的论文。随后 MIT 的三位研究者经过数十次失败尝试，提出了 RSA。这些工作最终深刻影响了互联网、电子商务、安全通信和数字签名。但这场革命最深刻的部分并不是某个模运算公式。而是人们发现：即使所有人都能看见算法和公开信息，也可以通过恰当的数学结构，让真正需要保护的秘密保持安全。这也揭示了现代密码学的一条重要原则：算法公开不是安全性的弱点。真正可靠的系统，不应该依赖攻击者不知道算法如何工作，而应该依赖经过广泛研究的数学假设、正确的密钥管理和完整的协议设计。

第十四章知识总结

概念	核心思想
对称密码	双方使用共享秘密保护数据
公钥密码	公开密钥与私人密钥承担不同角色
单向计算	正向容易，逆向计算困难
Diffie–Hellman	通过公开通信协商共享秘密
离散对数	经典有限域密钥交换的重要困难问题
RSA	利用模幂与大整数数论结构
数字签名	证明消息来源并验证完整性
中间人攻击	攻击者替换交换信息，冒充通信双方
混合加密	公钥技术建立信任与密钥，对称加密保护数据

本章历史原始资料

Diffie 与 Hellman（1976）：《New Directions in Cryptography》原始论文 Rivest、Shamir、Adleman（1977）：RSA 原始技术报告英国 GCHQ 官方历史：James Ellis NSA 历史档案：Ellis、Cocks 与 Williamson Martin Hellman 本人撰写的公钥密码发展史回顾

下一章预告

第十五章：一致性哈希——1997年，为什么增加一台服务器，不应该搬迁整个数据库？

1997年，MIT 的研究人员正在思考一个日后会让无数互联网公司头疼的问题。假设有十台缓存服务器。我们按照：

h(key)\bmod10

决定一条数据应该放在哪台服务器上。这种方式简单而高效。但是，如果公司增加第十一台服务器呢？哈希取模变成：

h(key)\bmod11

原本的数据位置大量改变。系统可能不得不搬迁许多缓存记录。于是，David Karger 等研究者提出了后来著名的一致性哈希（Consistent Hashing）方法。下一章，我们要研究：为什么把服务器和数据都映射到一个圆环上，就能让集群扩容时的数据迁移量大幅减少？这个故事还会带我们进入分布式哈希表、缓存系统、负载均衡，以及后来 Amazon Dynamo 等真实工程实践。