L03b Diffie-Hellman:不寄钥匙,各自算出同一把
先补上原根,再一步步走一遍 Diffie-Hellman 密钥交换,看窃听者手里有什么、缺什么,以及暴力解离散对数是怎么回事。
一句话版
Diffie-Hellman(DH)让两个人在一条人人都能偷听的线路上,各自算出同一把密钥。他们从头到尾没有寄过这把钥匙,偷听的人看到了所有来往的数字,却算不出它。
RSA 用「谁都能锁、只有我能开」解决送钥匙,见上一页 L03a-3。这一页换一条路:干脆不送。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| DH | Diffie-Hellman 密钥交换 | 两人在公开信道上各自算出同一把密钥 |
| 原根 g | primitive root | 模 p 下自乘能走遍 1 到 p−1 所有数的那个数 |
| 阶 | order | g 自乘多少次第一次回到 1 |
| 私值 / 公开值 | private / public value | 自己藏着的指数 a / 算出来交给对方的 gᵃ mod p |
| 离散对数 | discrete logarithm | 已知 gᵃ mod p,反推指数 a |
| 共享密钥 | shared secret | 双方各自算出的同一个数 g^(ab) mod p |
一个类比:广场上调颜料
两个人站在广场两头,周围全是看热闹的人。
先当众说好一种底色,比如黄色。这对应公开的 p 和 g。各自偷偷挑一种私藏颜色,Alice 挑红,Bob 挑蓝,谁也不告诉。
Alice 把红混进黄里,Bob 把蓝混进黄里,两桶半成品当众交换。
Alice 拿到 Bob 那桶,再混进自己的红;Bob 拿到 Alice 那桶,再混进自己的蓝。两边最后都是「黄 + 红 + 蓝」,同一种颜色。
围观的人看到了黄色和两桶半成品。要得到最终颜色,他得把红或蓝从半成品里分离出来,这很难。
类比在哪里失效:
- 颜料混了就真分不开。离散对数是「目前没有已知的快办法」,数字取小了照样能算出来,这一页最后就会亲手算一次。
- 广场上要是有人冒充 Bob 跟你换颜料,你分辨不出来。裸 DH 不认证对方身份,攻击者可以站在中间分别和双方各换一次。
从零讲起
1. 先补一块:原根(补充)
它解决什么问题
DH 的第一步要公开一个素数 p 和一个数 g,课件要求 g 是 p 的原根。不懂原根,就看不懂为什么偏偏挑这个 g,也看不懂课件 p = 23、g = 9 那个例子错在哪。
从哪来(补充)
原根是数论里的老概念:g 是模 n 的原根,指 g 的各次幂能取遍所有和 n 互素的余数。一个最小的例子:3 是模 7 的原根,3 的 1 到 6 次幂模 7 依次是 3、2、6、4、5、1,六个余数一个不落。5 是模 23 的原根之一。
出处:Wikipedia: Primitive root modulo n
直觉
拿 g 一次次自乘,每次模 p,记下余数。余数总在 1 到 p−1 之间,迟早会回到 1,然后开始重复。
如果在回到 1 之前,1 到 p−1 每个数都出现过一次,g 就是原根。如果走到半路就回到 1,它只绕了一个小圈,就不是原根。
圈越大,从公开值反推指数越难。所以 DH 想要原根。
一步一步看
目标:在模 23 下分别用 5 和 9 反复相乘,看出 5 走遍 1 到 22 是原根,9 只走一半就回到 1。
-
取 p = 23,看 g = 5。5¹ = 5,5² = 25 mod 23 = 2,5³ = 2 × 5 = 10,5⁴ = 10 × 5 = 50 mod 23 = 4。
-
一直乘下去,每步只要拿上一个余数乘 5 再模 23。第 22 步才回到 1:5²² mod 23 = 1。
-
中间 22 个余数正好是 1 到 22 各出现一次。5 是 23 的原根,阶是 22。
-
换 g = 9:9¹ = 9,9² = 81 mod 23 = 12,9³ = 12 × 9 = 108 mod 23 = 16,9⁴ = 16 × 9 = 144 mod 23 = 6。
-
继续下去,第 11 步就回到 1:9¹¹ mod 23 = 1。之后开始重复,只走遍了一半的数。9 不是 23 的原根,阶是 11。
怎么判断
g 是 p 的原根,等价于:g 的阶等于 p − 1。
意思是:g 要乘满 p − 1 次才第一次回到 1,中途不能提前回到 1。
小数字手算的办法:把 g 一次次乘下去,记录第一次回到 1 是第几步。第几步就是阶。
常见误解
以为 g 不是原根,DH 就算不出一致的密钥
算得出。两边一致只靠 (gᵃ)ᵇ = (gᵇ)ᵃ,这和 g 是不是原根无关。p = 23、g = 9 那个例子两边都得到 9。g 的阶小只是让可能的密钥变少,更容易被暴力试出来。
以为每个小于 p 的数都是原根
不是每个都是。模 23 下 9 就不是,它的阶是 11。挑 g 时要验证。
试一下
2 是模 7 的原根吗?
不是。2¹ = 2,2² = 4,2³ = 8 mod 7 = 1,第 3 步就回到 1,只走过 2、4、1 三个数,阶是 3,不等于 6。
2. Diffie-Hellman 密钥交换
它解决什么问题
Alice 和 Bob 想用对称加密聊天,需要一把共同的密钥。他们之间只有一条会被偷听的线路,事先也没见过面。DH 让他们在这条线路上来回发两个数,就各自得到同一把密钥,而偷听的人得不到。
从哪来(补充)
Whitfield Diffie 和 Martin Hellman 在 1976 年发表了这个方法。Hellman 后来主张也应该署上 Ralph Merkle 的名字,因为公钥分发的想法有他的贡献。英国 GCHQ 的 Malcolm Williamson 更早得到了同样的方法,1997 年才公开。Wikipedia 条目里的示例用的正是 p = 23、g = 5,结果和下面算的一样。
出处:Wikipedia: Diffie–Hellman key exchange
直觉
两个人各藏一个指数。把 g 自乘自己的指数次发给对方,再把对方发来的数自乘自己的指数次。
两边算的都是「g 自乘 a 次,再自乘 b 次」,只是顺序不同,结果当然一样。偷听者只看到「g 自乘 a 次」和「g 自乘 b 次」的结果,两个指数都不知道。
一步一步看
目标:用 p = 23、g = 5 跟着双方各算一遍,看出两边不交换私值也能得到同一个 18。
-
公开约定:p = 23,g = 5。谁都知道。
-
Alice 偷偷选私值 a = 4,算 A = 5⁴ mod 23 = 625 mod 23 = 4。
-
Bob 偷偷选私值 b = 3,算 B = 5³ mod 23 = 125 mod 23 = 10。
-
交换:Alice 把 4 发给 Bob,Bob 把 10 发给 Alice。线路上的人都看得到。
-
Alice 拿 Bob 的 10,自乘自己的 a 次:10⁴ mod 23。10² = 100 mod 23 = 8,8² = 64 mod 23 = 18。
-
Bob 拿 Alice 的 4,自乘自己的 b 次:4³ = 64 mod 23 = 18。
-
两边都是 18,这就是共享密钥 K。
-
把三方手里的东西列成表,就看得出窃听者缺什么:
怎么算
公开值:A = gᵃ mod p,B = gᵇ mod p。 共享密钥:K = Bᵃ mod p = Aᵇ mod p = g^(ab) mod p。
意思是:每人拿对方的公开值,自乘自己的私值次再取模。
为什么两边相等:Bᵃ = (gᵇ)ᵃ = g^(ab),Aᵇ = (gᵃ)ᵇ = g^(ab)。中间每一步都可以先取模再乘,这是上一讲的「乘法可先取模」,所以 (gᵃ mod p)ᵇ 和 g^(ab) 模 p 同余。
课件要求 p 至少 512 bit,这是课件的历史参数,今天的标准组更大。
常见误解
以为 DH 是一种加密算法
它只产出共享密钥 K,本身不加密任何消息。之后的加密还要交给对称算法。课件的公钥应用表里 DH 只有「密钥交换」一项是 Yes。
以为 DH 能防住中间人
裸 DH 不认证对方身份。攻击者站在中间,跟 Alice 换一次、跟 Bob 换一次,就分别和两人各有一把密钥,两边都察觉不到。实际使用要配合签名或证书认证公开值。
试一下
p = 23、g = 5,a = 2、b = 5。求 A、B 和 K。
A = 5² = 25 mod 23 = 2。B = 5⁵:5⁴ = 4,4 × 5 = 20,B = 20。Alice 算 20² = 400 mod 23 = 9;Bob 算 2⁵ = 32 mod 23 = 9。K = 9。
3. 离散对数与暴力攻击
它解决什么问题
窃听者看到了 p、g、A、B。他想要 K。一条路是先从 A = gᵃ mod p 反推出 a,再自己算 Bᵃ。这一节说明这一步为什么难,以及小数字时它怎么被硬算出来。
直觉
正着算 gᵃ mod p 很快,平方-乘几步就完。反过来,给你一个余数,问它是 g 的几次方,没有像平方-乘那样的捷径。最笨的办法是从 1 开始一个个试:g¹、g²、g³……直到撞上这个余数。
p 有几百位时,要试的次数多到算不完。p 只有三位数时,几百次就试出来了。
一步一步看
目标:站在窃听者一边从 k = 1 往上试 3ᵏ mod 353,看出暴力怎样撞出私值,进而算出共享密钥。
-
课件 Exercise-5:公开 p = 353、g = 3,窃听者看到 Y_A = 40、Y_B = 248。
-
从 k = 1 开始算 3ᵏ mod 353:3、9、27、81、243,然后 243 × 3 = 729 mod 353 = 23,接着 69、207……
-
每一步只要拿上一个余数乘 3 再模 353,一直试下去。
-
试到 k = 96 得 131,k = 97 得 131 × 3 = 393 mod 353 = 40。撞上了 Y_A,所以 Alice 的私值是 97。
-
拿到 97,算 248⁹⁷ mod 353 = 160,就得到了共享密钥。
怎么判断
离散对数问题:已知 p、g 和 y = gˣ mod p,求 x。
意思是:给你一个余数,问它是 g 的几次方。
判断一组 DH 参数会不会被暴力试穿,看 p 有多大:要试的次数和 p 同量级。p = 353 时最多试几百次;p 有几百位时,逐个试没有可能。不过还有比逐个试快得多的算法,所以参数大小要按标准选,不能只拿「要试多少次」来估。
常见误解
以为攻破 DH 必须先求出 a
先求 a 是一条攻击路径。攻击者直接从 A、B 求 g^(ab) 是另一个问题,不能说必须先解离散对数。课件讲的是前一条路。
以为课件里的 512 bit 今天还够用
512 bit 的有限域 DH 已经不安全。RFC 7919 规定的标准组从 2048 bit 起。课件的数字是历史参数(补充,出处见本页「课件里的坑」)。
试一下
p = 23、g = 5,窃听者看到 A = 8。用暴力法求 a。
5¹ = 5,5² = 2,5³ = 10,5⁴ = 4,5⁵ = 20,5⁶ = 20 × 5 = 100 mod 23 = 8。a = 6。
把它们串起来
DH 先公开一个素数 p 和它的原根 g。原根保证 g 的幂能走遍 1 到 p−1,可能的值越多,反推越难。
两个人各藏一个指数,交换 g 的幂,再各自把对方的数自乘自己的指数次。两边算的都是 g^(ab),所以结果一致;全过程没有寄过这把钥匙。
窃听者看到了 p、g 和两个公开值,缺的是两个私值。从公开值求私值就是离散对数。数字小的时候逐个试几百次就出来,数字大到几百位时,目前没有已知的快办法。
DH 只负责产出钥匙,不加密、不签名,也不认证对方是谁。下一页退一步看整个公钥体系:加密、签名、密钥交换三件事各用谁的钥匙,以及它凭什么安全。
课件里的坑
- [原根口径] p.27 要求 G 是 P 的原根,但 p.30 的例子取 G = 9,9 在模 23 下阶为 11,不是原根。算法照样算出一致的密钥,被问到「9 是不是 23 的原根」要答不是(p.27、p.30)
- [大小写混用] 课件这几页 P/G 与 p/g 混用,是同一组量(p.27–28)
- [历史参数] p.27 的「P 至少 512 bit」是历史长度,512-bit 有限域 DH 已不安全;参考 RFC 7919(补充)
- [不认证] 课件只讲窃听者,没讲冒充者。裸 DH 不认证对方身份,挡不住中间人(补充)
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写 DH 的四类量各有哪些;再把例 2 不看解答重算一遍,写成「谁算什么、谁发什么」的时序;最后回答 9 是不是 23 的原根,说出理由。
必背
- DH 做密钥协商:交换 gᵃ 与 gᵇ,得到共享秘密 g^(ab) mod p;解离散对数是一条攻击路径,裸 DH 不认证对方身份
- DH 的四类量:公开参数 p、g;私值 a、b;公开值 gᵃ mod p、gᵇ mod p;共享密钥 g^(ab) mod p;窃听者只拿得到前两类公开的
- 两边结果一致靠 (gᵃ)ᵇ = g^(ab) = (gᵇ)ᵃ,中间每步都可以先取模
- g 是 p 的原根:g 的 1 到 p−1 次幂模 p 走遍 1 到 p−1;p = 23 时 5 是原根,9 不是(阶 11)
- Exercise-5:p = 353、g = 3、私值 97 和 233,公开值 40 和 248,共享密钥 160;暴力攻击逐个试 3ᵏ mod 353 直到撞上 40 或 248
课件例题
例 1(课件 p.30–31):P = 23、G = 9 的 DH 交换
题面:公开参数 P = 23、G = 9,Alice 私值 a = 4,Bob 私值 b = 3。算两人的公开值 X、Y 和共享密钥。9 是 23 的原根吗?
提示
9⁴ 可以先算 9² = 81 ≡ 12,再平方。原根的问题看 9 乘几次回到 1。
解答
X = 9⁴ mod 23 = 6561 mod 23 = 6,因为 23 × 285 = 6555。Y = 9³ mod 23 = 729 mod 23 = 16,因为 23 × 31 = 713。
Alice 算 16⁴ mod 23:16² = 256 mod 23 = 3,3² = 9。Bob 算 6³ mod 23 = 216 mod 23 = 9。两边都是 9。
9 不是 23 的原根:9¹¹ ≡ 1 (mod 23),它的阶是 11,幂只走遍一半元素。算法照样算出一致的密钥,被问到要答「不是」。
例 2(课件 p.32):Exercise-3,p = 23、g = 5 的完整交换
题面:p = 23、g = 5,Alice 私值 a = 4,Bob 私值 b = 3。写出完整的密钥交换过程。
提示
按「各算公开值 → 交换 → 各算密钥」三拍写,每拍标清是谁。
解答
| 步骤 | 计算 | 结果 |
|---|---|---|
| Alice 公开值 | A = 5⁴ mod 23 = 625 mod 23(23 × 27 = 621) | 4 |
| Bob 公开值 | B = 5³ mod 23 = 125 mod 23(23 × 5 = 115) | 10 |
| 交换 | Alice 发 4,Bob 发 10 | |
| Alice 算密钥 | 10⁴ mod 23:10² = 100 mod 23 = 8,8² = 64 mod 23 | 18 |
| Bob 算密钥 | 4³ mod 23 = 64 mod 23 | 18 |
共享密钥 K = 18。这次 5 是 23 的原根,阶 22。答题要把「谁发什么、谁算什么」写成时序,只给 18 拿不到过程分。
例 3(课件 p.50):Exercise-5,p = 353、G = 3 的交换与暴力攻击
见下方完整例题。
完整例题
题面(课件 p.50 Exercise-5):p = 353、g = 3,私值 X_A = 97、X_B = 233。走一遍密钥交换,并说明暴力攻击怎么做。
约定:幂用平方-乘,每步模 353;指数拆成 2 的幂相加。
解法:
- A 算 Y_A = 3⁹⁷ mod 353。平方链:3² = 9,3⁴ = 81,3⁸ = 207,3¹⁶ = 136,3³² = 140,3⁶⁴ = 185。97 = 64 + 32 + 1 → 185 × 140 = 25900 mod 353 = 131,131 × 3 = 393 mod 353 = 40。
- B 算 Y_B = 3²³³ mod 353。再算 3¹²⁸ = 185² mod 353 = 337。233 = 128 + 64 + 32 + 8 + 1 → 337 × 185 → 217,× 140 → 22,× 207 → 318,× 3 → 248。
- 交换:A 发 40,B 发 248。
- A 算 K = 248⁹⁷ mod 353:248² = 82,248⁴ = 17,248⁸ = 289,248¹⁶ = 213,248³² = 185,248⁶⁴ = 337 → 337 × 185 = 217,217 × 248 = 53816 mod 353 = 160。B 算 40²³³ mod 353 同样得 160。
- 暴力攻击:已知 p = 353、g = 3、Y_A = 40、Y_B = 248,逐个算 3ᵏ mod 353,k = 97 时撞上 40(或 k = 233 时撞上 248),再算 248⁹⁷ mod 353 就得 160。
要点:这只是解离散对数的一种笨办法;存在远快于逐个枚举的算法,不能用「512-bit 要试 2⁵¹² 次」来证明安全。
答题格式:按「A 算 Y_A / B 算 Y_B / 交换 / 各算 K / 攻击者怎么做」五段写,每段的平方链写出来。
变式题(先自己做)
(1) 改编自课件 p.32:p = 23、g = 5,A 的私值 a = 6,B 的私值 b = 15。求两个公开值和共享密钥 K,并说出窃听者手里有哪四个数。 (2) 改编自课件 p.30:3 是模 7 的原根吗?6 呢? (3) 改编自课件 p.50:p = 23、g = 5,窃听者看到 A = 10、B = 2。用暴力法求出一个私值,再算出 K。
提示
(1) 5² ≡ 2 可以一路翻倍;19 可以写成 −4 再算。(2) 各自乘下去,数几步回到 1。(3) 从 5¹ 开始逐个试,撞上 10 或 2 就停。
判分点与答案(非官方评分标准)
判分点:① (1) 分清私值、公开值、共享密钥,窃听者手里没有 a、b;② (2) 要写出阶;③ (3) 要写出试的过程并验算 K。
(1) 5² = 25 ≡ 2,5⁴ ≡ 4,5⁶ = 5⁴ × 5² ≡ 8,所以 A = 8。5⁸ ≡ 16,5¹⁵ = 5⁸ × 5⁴ × 5² × 5 ≡ 16 × 4 × 2 × 5 = 640 mod 23 = 19 = B。A 算 K = 19⁶ ≡ (−4)⁶ = 4096 mod 23 = 2;B 算 8¹⁵:8² ≡ 18,8⁴ ≡ 2,8⁸ ≡ 4,8¹⁵ = 4 × 2 × 18 × 8 = 1152 mod 23 = 2 ✓。窃听者手里是 23、5、8、19。
(2) 3 的幂模 7:3、2、6、4、5、1,第 6 步回到 1,阶 6,是原根。6 的幂模 7:6、1,第 2 步就回到 1,阶 2,不是。
(3) 5¹ = 5,5² = 2,撞上 B = 2,所以 b = 2。K = Aᵇ = 10² = 100 mod 23 = 8。验算:5³ = 10,a = 3,Bᵃ = 2³ = 8 ✓。
闪卡自测
1. DH 里的四类量分别是什么?攻击者能拿到哪几类?
公开参数 p、g;私值 a、b;公开值 gᵃ、gᵇ;共享密钥 g^(ab)。攻击者拿到公开参数和公开值,拿不到私值和共享密钥(p.27–28)。
2. 为什么 Alice 和 Bob 算出的 K 一样?
(gᵇ)ᵃ = g^(ab) = (gᵃ)ᵇ,而且每步都可以先取模(p.29)。
3. P = 23 时 9 是原根吗?
不是。9 的阶是 11,只能走遍一半元素;算出的 DH 密钥仍然一致(p.30)。
4. p = 23、g = 5、a = 4、b = 3 时共享密钥是多少?
18。A = 4,B = 10,10⁴ ≡ 18,4³ ≡ 18(p.32)。
5. DH 能不能用来加密一段消息?
不能。它只产出共享密钥,加密交给对称算法。p.40 的表里 DH 只有密钥交换是 Yes(p.28、p.40)。
6. Exercise-5 里暴力攻击具体在做什么?
逐个算 3ᵏ mod 353,直到撞上 40(k = 97)或 248(k = 233),这就是暴力解离散对数(p.50)。
下一讲
DH 只管换钥匙。下一页退一步看整个公钥体系:加密、签名、先签后加密各用谁的钥匙,三易两难的要求,以及陷门函数和分解难题为什么撑得住 RSA,见 L03b-2。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。