前置知识

相关文章

蓝图 · 291 字 · 1 分钟阅读

Diffie-Hellman:让 RSA 成为可能的密钥交换

在 Rivest、Shamir、Adleman 造出那把锁之前,Whitfield Diffie 和 Martin Hellman 已经证明了这把锁可以存在。他们 1976 年的论文才是公钥密码学真正的起点。

目录
  1. TL;DR
  2. 问题:两个陌生人,一个秘密
  3. 共享颜料的类比
  4. 数学
  5. 为什么离散对数难
  6. Diffie-Hellman 不是 RSA
  7. “临时”的小把戏:前向保密
  8. 椭圆曲线 Diffie-Hellman
  9. Diffie-Hellman 唯一做不到的
  10. Diffie-Hellman 真正证明了什么

#TL;DR

1976 年 11 月,Whitfield Diffie 和 Martin Hellman 发表了 “New Directions in Cryptography” —— 这篇论文证明了:两个从未见过面的陌生人,可以通过一条公开信道,在不让窃听者学到任何秘密的情况下,共同约定一个共享秘密。一年后 Rivest、Shamir 和 Adleman 发表了 RSA——第一套实用的公钥加密系统。但是 Diffie 和 Hellman 才是先证明了”这件事可以做”的人,他们的密钥交换协议至今仍是 TLS、SSH 和 Signal 用来建立会话密钥的原语。五十年后,论文里的算法被升级到跑在椭圆曲线上,但那个诀窍是一样的。

#问题:两个陌生人,一个秘密

假设你我想交换加密消息。我们需要一个共享密钥——某串字节,只有我们俩知道,别人都不知道。1976 年前唯一存在的对称加密,假设这个密钥已经存在。

那我们是怎么拿到它的?

在 Diffie-Hellman 之前有两种答案:

  1. 我们当面见,把密钥写在一张纸、一个 U 盘、或一张打孔卡上交给对方。
  2. 我们信任一个信使——通常是政府——替我们传密钥。

这两种都不能规模化。一家银行要和一百万客户交换加密消息,它寄不出一百万个信封。两位 ARPANET 研究员要私下通信,也不可能先互相坐飞机过去。密钥分发问题是网络规模下密码学的根本障碍,20 世纪大半时间里,密码学家把它当作前提条件,而不是可以用数学解决的事情。

Diffie 和 Hellman 用数学解决了它。

#共享颜料的类比

在写方程之前,有个标准的讲法:想象你我各有一罐完全一样的颜料,我们想通过一条公开信道约定一个共享颜色——任何颜料寄送都要经过一个仓库,那儿有个窃听者可以偷看。

我们这样做:

  1. 公开约定一个起始颜色——比如黄色。全世界都知道我们从黄色开始。
  2. 我私下选一个颜色——蓝色。我把黄 + 蓝混成绿色,把绿色那罐寄给你。
  3. 你私下选一个颜色——红色。你把黄 + 红混成橙色,把橙色那罐寄给我。
  4. 我收到你的橙色。 我再混入自己的蓝色,得到(橙 + 蓝)= 棕色。
  5. 你收到我的绿色。 你再混入自己的红色,得到(绿 + 红)= 棕色。

我们俩都得到了棕色。仓库里的窃听者看到的是黄色、绿色、橙色——但要调出棕色,至少需要一种私密颜色,而这些他从没见过。

这个把戏依赖于混合颜料的两个性质:

  • 混合容易 — 给你两种颜色,几秒钟就混好。
  • 分离很难 — 给你一种混好的颜色,要还原出原始成分基本是不可能的。

这就是一个单向函数。Diffie 和 Hellman 的洞察是:模幂运算具有同样的性质,你可以在它上面搭出真正的协议。

#数学

Diffie-Hellman 用”在一个大素数模下的整数”替代了”颜料”。

公共参数(所有人都知道):
  p = 一个大素数
  g = 模 p 乘法群的生成元  (实践中 g=2 或 g=5)

Alice 的秘密:  a (随机数,保密)
Bob 的秘密:    b (随机数,保密)

Alice 发送:    A = g^a mod p
Bob 发送:      B = g^b mod p

Alice 计算:    s = B^a mod p  =  (g^b)^a mod p  =  g^(ab) mod p
Bob 计算:      s = A^b mod p  =  (g^a)^b mod p  =  g^(ab) mod p

两人都得到 s。攻击者有 p、g、A、B——但没有 a 或 b。

共享秘密是 g^(ab) mod p。Alice 和 Bob 各自把对方的公开值升到自己的私钥指数上计算它。他们得到同一个数,是因为模幂在指数上可交换:(g^a)^b = (g^b)^a = g^(ab)。

p = 23     # 玩具素数——真实 Diffie-Hellman 使用 2048+ 位的素数
g = 5

# Alice 选一个秘密
a = 6
A = pow(g, a, p)  # 5^6 mod 23 = 8

# Bob 选一个秘密
b = 15
B = pow(g, b, p)  # 5^15 mod 23 = 19

# 公开信道:Alice → Bob 发 A=8;Bob → Alice 发 B=19

# Alice 计算共享秘密
s_alice = pow(B, a, p)  # 19^6 mod 23 = 2

# Bob 计算共享秘密
s_bob = pow(A, b, p)    # 8^15 mod 23 = 2

assert s_alice == s_bob == 2

窃听者看到 p=23、g=5、A=8、B=19。要算出共享秘密,他得拿到 Alice 的私密 a 或 Bob 的私密 b。从 A = g^a mod p 反推 a 就是离散对数问题——这就是这个方案安全性的来源。

#为什么离散对数难

给你 a、g、p,计算 g^a mod p 很快——即便对 2048 位的数也只要几毫秒,因为平方-乘法可以在大约 log(a) 次乘法内完成。

反过来——给你 g^a mod p,要反推 a——就是离散对数问题,在经典计算机上没有已知算法能高效求解。

对一般素数域来说,最好的算法属于一般数域筛家族,它们的运行时间随 p 的大小亚指数增长。对一个 2048 位的素数来说,计算代价和分解一个 2048 位 RSA 密钥差不多——远远超出任何已知系统的能力。

离散对数和大整数分解不是同一个问题,但它们都属于同一类密码学假设:经典上被认为很难、但在跑 Shor 算法的量子计算机面前会垮掉的问题。正是这个共同的弱点,让后量子过渡同时影响 RSA 和经典 Diffie-Hellman。

#Diffie-Hellman 不是 RSA

有一个微妙的点容易让人绊倒:Diffie-Hellman 并不加密任何东西。它是一个密钥协商协议——跑完之后 Alice 和 Bob 共享一个秘密。他们拿这个秘密去做什么是另一回事。

实际上,这个共享秘密会被送进一个密钥派生函数(比如 HKDF),产出一个或多个对称密钥,这些密钥会被拿去做真正的会话加密,比如 AES-GCM。

相比之下,RSA 既可以加密(用对方的公钥加密数据),也可以签名(用自己的私钥签名)。RSA 做的事更多,Diffie-Hellman 更窄:它被优化来专门做”建立一个共享对称密钥”这一件事。

事实上,Diffie-Hellman 在实践中比 RSA 老得更好,原因正是如此。现代协议几乎从不直接用 RSA 加密通信数据——RSA 对大量数据加密来说太慢,RSA 用于密钥运输的角色已经被基于 Diffie-Hellman 的密钥协商取代了。现代 TLS 用 ECDHE(椭圆曲线 Diffie-Hellman,临时)握手来派生会话密钥,RSA 只用在服务器证书的签名上(用来证明服务器身份)。

#“临时”的小把戏:前向保密

如果 Alice 和 Bob 一直使用长期不变的 DH 私钥,那么将来窃得其中一把私钥的攻击者,就能解密他们之前录下的每一条会话。这叫前向保密失败。

修法是临时 Diffie-Hellman(DHE 或 ECDHE)。Alice 和 Bob 为每一次会话生成全新的随机 a 和 b,派生完会话密钥后立刻扔掉,绝不写到磁盘上。攻击者以后即便偷到他们的长期身份密钥,也没法解密旧会话——那些临时的 a 和 b 已经永远消失了。

现代 TLS 默认坚持使用临时密钥协商。ECDHE 里的 “E” 代表 “ephemeral”(临时),在 TLS 1.3 里这不可选。

#椭圆曲线 Diffie-Hellman

经典 Diffie-Hellman 在”模大素数的整数乘法群”里操作。椭圆曲线 Diffie-Hellman(ECDH)在”椭圆曲线上点的群”里跑一模一样的协议。

诀窍是在椭圆曲线上,离散对数问题按位看似乎更难。一条 256 位的 ECDH 密钥,安全性大致相当于 3072 位的经典 DH 密钥。这意味着 ECDH 的密钥和消息小得多,在移动设备、嵌入式系统,以及任何每个字节都要省的协议里非常重要。

选哪条曲线很重要:Curve25519(Daniel J. Bernstein 设计)是多数现代协议事实上的默认曲线,因为它快、实现规则简单,避免了早期曲线允许的几类微妙 bug。Signal、WireGuard、现代 SSH、TLS 1.3、基于 Noise 的协议,都用 Curve25519 做密钥协商。

椭圆曲线的数学是另一个大话题,RSA 那篇有所提及。这里关键是:Diffie-Hellman 的协议是一样的——同样的握手、同样的数学结构、同样的安全论证——只是换了个群。

#Diffie-Hellman 唯一做不到的

Diffie-Hellman 在两方之间建立共享秘密,但它做不到告诉你你和谁建立了那个秘密。

如果 Mallory 坐在连接中间,她可以把 Diffie-Hellman 协议跑两遍——一次和 Alice、一次和 Bob——最后分别和两人各共享一把不同的密钥。Alice 以为自己在和 Bob 聊,Bob 以为自己在和 Alice 聊。Mallory 在中间转发每一条消息,一边解密一边重新加密,一路把所有内容都读掉。

这就是中间人攻击,也是为什么裸的 Diffie-Hellman 从不在实战中被单独使用。你需要身份认证——某种方法来证明你收到的那份公开值真的来自你想与之对话的那一方。

解决这个问题的正是数字签名。在 TLS 里,服务器出示一张由受信任 CA 签发的证书,客户端验证这个签名,然后双方才跑 Diffie-Hellman,并且对收到的公开值的真实性有信心。两个原语互补:Diffie-Hellman 建立密钥;签名认证身份。

#Diffie-Hellman 真正证明了什么

RSA 那篇把 Diffie-Hellman 的论文称作”概念优雅且可证明可行”。那种表述低估了 1976 年 11 月发生的事。这篇论文:

  • 引入了公钥密码学的概念。 在这篇论文之前,学术界根本没有”加密和解密用不同密钥”这样一个概念。Diffie 和 Hellman 给这件事命了名,并证明它在数学上是自洽的。
  • 给出两大问题之一(密钥协商)的可工作协议。 他们还没办法用一个单独的原语同时做到加密和签名——那是 RSA 的贡献——但他们已经证明了密钥分发问题可以被解决。
  • 把密码学变成了公开的学术主题。 在 1976 年之前,严肃的密码研究基本全是保密的。Diffie-Hellman 这篇论文,就是这个领域从政府跨进公开科学的那一刻。

一年后 Rivest、Shamir 和 Adleman 用一个完整的公钥加密系统完成了这场接力。但他们是站在 Diffie 和 Hellman 结果之上的——而且现代协议又绕回来找回了 Diffie-Hellman:今天公共互联网上的多数会话密钥,是从椭圆曲线 Diffie-Hellman 握手里出来的,不是从 RSA 加密里。这个原语已经比它那位更年轻、更有名的表亲活得更久了。对于一个”只不过是商量一个数字”的协议来说,这已经很不赖了。