两个陌生人约定一个秘密密钥，而他们的每句话谁都听得见。这怎么可能？其中的陷阱又在哪里？
爱丽丝和鲍勃从未见过面。他们唯一的交流方式，伊芙都能听到每一句话。他们能不能现在就当着她的面，约定一个伊芙无法得知的密码？
直觉给出的回答是坚决的“不能”。鲍勃知道的一切都是通过公共信道得到的，所以伊芙也都知道。鲍勃从哪里能得到她没有的东西呢？
几千年来情况确实如此。任何密码，从凯撒密码到 DES，都要求事先通过可靠途径把密钥送到双方手中：信使、外交邮袋、当面交接。就连 1963 年开通的莫斯科—华盛顿热线，用的也是一次性密钥纸带，由双方通过大使馆互相传递。需要秘密通信的人越多，这套物流就越沉重。
先说清楚它是什么。迪菲-赫尔曼不是密码算法，而是一种密钥协商协议。它不加密任何东西，只是让爱丽丝和鲍勃得到同一个秘密密钥。之后再由普通的密码（例如 AES）用这个密钥加密通信内容。
整个协议依靠的只有一件事：一种容易做、却难以撤销的运算。最简单的办法是先用颜料来想象它。
有一种人人都知道的公共颜料。爱丽丝和鲍勃各自往里加入自己的秘密颜料，然后公开交换混合物。接着每人把自己的秘密颜料加进对方的混合物。两人罐子里最终是同一种颜色，而伊芙虽然看到了两份混合物，却无法从中提取出秘密颜料。
这是简化：真实的颜料混合物在实验室里其实是可以分开的。所以协议用的是数字而不是颜料。
在真正的协议里，“混合”指的是模幂运算：把一个数乘方，再把结果除以模数 p，只保留余数。例如 30 mod 23 = 7，因为 30 = 1 · 23 + 7。下面每一步先给出一般形式，再给一个能心算的小例子。游戏默认用的也是这些数，而且在游戏里可以更改。
爱丽丝和鲍勃公开约定两个数。p 是模数，一个很大的素数：在真实系统中长达 2048 位甚至更长，也就是至少有 617 位十进制数字。g 是要被乘方的底数，选取时要让 g 的各次幂给出尽可能多的不同余数（详见“给好奇的你”）。现成的 p 和 g 组合通常取自标准。所有人都知道它们，包括伊芙：这不是泄密，本来就是这样设计的。
例子：p = 23，g = 5。
每人随机选一个秘密数：爱丽丝选 a，鲍勃选 b。在真实协议中，这些数长达数百位，每次新连接都重新选取。秘密数不发给任何人：它们就是“秘密颜料”。
例子：a = 2，b = 3。
爱丽丝计算 A = ga mod p，鲍勃计算 B = gb mod p。这就是“把自己的颜料和公共颜料混合”。A 和 B 通过信道公开传送，伊芙看得到。
例子：A = 5² mod 23：5² = 25 = 1 · 23 + 2，所以 A = 2。B = 5³ mod 23：先算出完整的幂 5³ = 125，再做带余除法 125 = 5 · 23 + 10，所以 B = 10。
爱丽丝把收到的 B 取自己的秘密次方：s = Ba mod p。鲍勃对 A 做同样的事：s = Ab mod p。两人得到的数相同，尽管密钥本身从未经过信道。在真实系统中，s 和 p 一样长，之后再从它派生出对称密码的密钥。
例子：爱丽丝得到 10² = 100 = 4 · 23 + 8，鲍勃得到 2³ = 8（小于 23，不用再除）。两人都得到 s = 8。
B 就是 gb，所以爱丽丝得到 Ba = gb·a，鲍勃得到 Ab = ga·b。交换因数的顺序，乘积不变，正如颜料的混合与先后顺序无关。而除以 p 取余可以在任何一步进行，结果都不变。一般公式：s = Ba = Ab = gab mod p。
1976 年 11 月，斯坦福大学的惠特菲尔德·迪菲和马丁·赫尔曼发表了论文《New Directions in Cryptography》（密码学的新方向）。文章开头写道：“今天，我们正站在密码学革命的边缘。”时机恰到好处：计算机开始联网，要为每一对想通信的人派信使送密钥，已经不可能了。这个想法受到了拉尔夫·默克尔工作的影响，他当时独立地寻找公开约定密钥的方法。后来赫尔曼提议把这个协议称为迪菲-赫尔曼-默克尔密钥交换。
这个想法当时已呼之欲出。在英国政府通信总部（GCHQ），詹姆斯·埃利斯早在 1970 年就描述了“非秘密加密”，1974 年马尔科姆·威廉森找到了本质上相同的协议。这些工作一直是机密，直到 1997 年才公开。所以协议以公开发表它的人命名；2015 年，迪菲和赫尔曼因公钥密码学获得了图灵奖。
如今，这种交换几乎在每一条安全连接中默默运行：
每一次 TLS 1.3 连接都从迪菲-赫尔曼交换开始，通常在椭圆曲线 X25519 上进行。秘密数字为每次连接重新选取，用完即删：即使服务器日后被攻破，旧的对话也无法解密。这一性质称为前向保密（forward secrecy）。
Signal 和 WhatsApp 通过多次迪菲-赫尔曼交换来约定聊天密钥。Telegram 的 MTProto 协议也建立在这种交换之上。
远程登录服务器和安全隧道也用同样的方式得到会话密钥。之后这个密钥用对称密码（例如 AES）来加密数据。
说起迪菲-赫尔曼，总会提到 RSA。两者都诞生于 20 世纪 70 年代，都使用公开数和秘密数，也都在做模幂运算，所以很容易混淆。但它们做的事情不同。迪菲-赫尔曼什么也不加密：它让两个人一起得出共同的密钥。RSA 则是一把锁：鲍勃事先把锁发出去，任何人都能用它锁上一封信，而只有鲍勃能打开。
| 问题 | 迪菲-赫尔曼 | RSA |
|---|---|---|
| 做什么 | 两个人协商出共同的秘密密钥 | 为某一个收件人锁上信件；签名也用同样的方法 |
| 谁必须参与 | 双方同时参与：各自加入自己的秘密数 | 只有发送者：鲍勃的锁人人都有，鲍勃本人可以不在线 |
| 信道里传的是什么 | 公开数 A 和 B；密钥本身从不出现在信道里 | 锁上的信 c |
| 密钥用多久 | 每次对话都用新的秘密数 | 一把锁用好几年 |
| 依靠什么 | 很难由公开数求出秘密数（离散对数） | 很难把 n 分解成两个素数 |
| 比喻 | 两个人一起调的颜料 | 一把打开的挂锁 |
俄罗斯认证的密码保护工具用 VKO 算法生成共同密钥。它记载于标准化建议 R 50.1.113-2016 中，运行在签名标准 GOST R 34.10-2012 规定的 256 位或 512 位椭圆曲线上。思路和游戏里一样：每一方都有一个秘密数和由它算出的公开数；每一方把自己的秘密数和对方的公开数结合起来，双方得到同一个结果。
与教科书方案相比有两点不同。计算中会混入一个公开传送的随机数 UKM，这样同一对长期密钥每次都能产生新的共同密钥。而且结果不直接使用，而是先经过哈希函数 Streebog（GOST R 34.11-2012）。得到的密钥再用 Kuznyechik 或 Magma 加密数据。俄罗斯的 TLS 密码套件中也使用 VKO。
在 Ludus Lab 的交互式演示中，你用小数字亲手走完整个协议。伊芙看到的和你一样多，所以你可以检验她在哪里缺少信息、又在哪里获胜。值得一试的有：
三者遵循同一个模式：秘密数、公开数、共同秘密。区别在于计算是在哪个“世界”里进行的：
| 参数 | 经典 DH | ECDH (X25519) | VKO（GOST） |
|---|---|---|---|
| 在哪里计算 | 模素数 p 的余数 | Curve25519 曲线上的点 | GOST R 34.10-2012 曲线上的点 |
| 数的长度 | 2048–4096 位 | 255 位 | 256 或 512 位 |
| 大致安全强度 | 2048 位时 ≈ 112 位 | ≈ 128 位 | ≈ 128 或 ≈ 256 位 |
| 共同秘密如何处理 | 密钥派生函数（TLS 中为 HKDF） | 密钥派生函数（TLS 中为 HKDF） | 结合公开的 UKM 做 Streebog 哈希 |
| 年份 | 1976 | 2006（D. 伯恩斯坦） | 2016 |
| 标准 | RFC 3526, RFC 7919 | RFC 7748 | R 50.1.113-2016（RFC 7836） |
| 发布机构 | IETF | IETF | TC 26、俄罗斯联邦技术监管与计量局 |
伊芙比简单穷举聪明。对于模 p 的离散对数，有一种巧妙的方法：数域筛法。正因如此，2048 位的 p 提供的安全强度大约只相当于 112 位的对称密钥，远不是 2048 位。在椭圆曲线上还不知道这样的技巧：最好的方法也需要大约完整穷举量的平方根，所以 256 位的曲线就足以提供约 128 位的安全强度。这就是转向椭圆曲线的原因：密钥更短，计算更快。
2015 年，研究人员展示了 Logjam 攻击。许多服务器使用相同的 512 位和 1024 位标准 p，其中一些还因旧的“出口”规定而接受 512 位。对固定的 p，最繁重的那部分计算可以事先一次做完，之后就能很快求出所有使用这个 p 的连接的密钥。对 512 位，这项准备工作用了大约一周；对 1024 位，估计一个国家有能力完成。此后 1024 位的群被淘汰：如今 p 至少取 2048 位，或者改用椭圆曲线。
运行肖尔算法的量子计算机能很快解决离散对数问题，无论是模 p 还是在椭圆曲线上。这样的机器目前还不存在，但今天被录下的流量将来可能被解密。因此从 2024 年起，浏览器开始在 X25519 之外加上后量子机制 ML-KEM（FIPS 203 标准）：密钥由两部分组成，要得到它，必须把两部分都攻破。
g 模 p 的各次幂应当取遍尽可能多的不同余数。在本文的例子（g = 5、p = 23）中，它们恰好给出 1 到 22 的全部 22 个数：这样的 g 叫作原根。但如果取 g = 22，幂就会交替出现：22、1、22、1……于是 A 只可能是两个数之一，伊芙试两次就够了。所以游戏只允许选择“好的” p 和 g 组合。
这是简化：在真实系统中，g 往往不是原根，而是某个素数阶巨大子群中的元素（例如 p = 2q + 1，其中 q 也是素数）。重要的不是 g 的幂覆盖一切，而是它们的数量多到天文数字，并且不存在能让伊芙钻空子的小子群。
现在你知道了两个人怎样当众约定一个秘密，也知道了为什么如果有人能够介入，这还远远不够
在演示中，你将混合颜料，在灯板上数清幂，扮演伊芙，看看她的攻击在哪里失败、又在哪里得手