L04c 离散对数与 Elgamal:一个私钥、一个临时 k、一对 (r, s)
从零讲离散对数:先认识生成元,再查模 7 的乘方表看「正着算快、倒着算难」,最后一帧一帧走完 Elgamal 签名,看签名方程怎么搬到指数上变成验证式。
一句话版
前两页的签名压在大数分解上,这一页换一个难题:离散对数。已知 g 和 gᵃ mod p,反推 a 很难。Elgamal 签名就压在它上面,签名从一个数变成一对 (r, s),每次签都要换一个临时随机数 k。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 生成元 g | generator,也叫原根 | 模 p 下自乘能走遍 1 到 p−1 每个数的那个数 |
| 离散对数(DL) | discrete logarithm | 已知 g 和 gᵃ mod p,反推指数 a |
| 单向函数 | one-way function | 正着算容易、倒推不可行 |
| 陷门 | trapdoor | 只有知道某个秘密的人才能倒推的后门,RSA 的 d 就是 |
| 临时随机数 k | ephemeral key | 每签一次就换一个的随机数 |
| (r, s) | 签名对 | Elgamal 的签名是两个数,不像 RSA 只有一个 |
一个类比:转了多少圈只有转的人知道
离散对数像一个只有 p−1 格的转盘。起点固定,每转一步就把当前格子的数乘 g 再取模。
告诉你转了 a 步,算出停在哪格很快。反过来只告诉你停在哪格,要猜转了几步,只能一步步试。
生成元是能走遍每一格的转法。有的 g 转几步就回到起点,只在少数几格打转;生成元会把每一格都踩一遍再回来。只有这样,「停在某格」才对应唯一的步数。
Elgamal 签名像每次签字都换一瓶一次性墨水。私钥 x 是你固定的笔迹,k 是这次的墨水。签名的一半记录墨水(r),另一半把笔迹、墨水和消息搅在一起(s)。
类比在哪里失效:
- 转盘真的只能一步步试。离散对数有比穷举快得多的算法,只是参数够大时仍然不可行。
- 墨水用两次只是浪费。k 用两次会让两条签名的 r 相同,两式相减就能解出私钥。
从零讲起
1. 先补一块:生成元(补充)
它解决什么问题
离散对数要「反推步数」,得先保证每格只对应一个步数。生成元就是让这件事成立的底数。Elgamal 的密钥生成第一步就要挑一个生成元。
直觉
在模 7 下拿 3 自乘:3、9 mod 7 = 2、6、18 mod 7 = 4、12 mod 7 = 5、15 mod 7 = 1。六步把 1 到 6 全踩了一遍,回到 1。
换成 2:2、4、8 mod 7 = 1,三步就回到 1,之后只在 2、4、1 里打转。3 是生成元,2 不是。
一步一步看
目标:在模 7 下把每个底数乘到回 1,看出周期等于 6 的只有 3 和 5,它们就是生成元。
-
固定模数 7,非零的数只有 1 到 6 这六个。
-
拿底数 b 从 b¹ 开始往上乘,每次乘 b 再 mod 7。
-
记下多少步回到 1,这个步数叫 b 的周期。
-
周期等于 6(也就是 p−1)的底数是生成元。模 7 下只有 3 和 5 两个。
-
周期不到 6 的底数,同一个结果会在不同步数重复出现。
怎么判断
问一句:b 的乘方回到 1 之前,有没有把 1 到 p−1 全走一遍?
- 走遍了 → 生成元,每个数恰好对应一个指数。
- 提前回到 1 → 不是生成元,有的数到不了,到得了的对应好几个指数。
模 7 下:3 和 5 走遍;2 和 4 的周期是 3;6 的周期是 2;1 的周期是 1。
常见误解
以为模 p 下每个数都是生成元
模 7 下六个底数只有两个是生成元。挑 g 时要先验,例如 p = 11 时 2 的幂依次是 2, 4, 8, 5, 10, 9, 7, 3, 6, 1,走遍十个,才能用。
试一下
模 7 下 5 的乘方依次是什么?它是不是生成元?
5、25 mod 7 = 4、20 mod 7 = 6、30 mod 7 = 2、10 mod 7 = 3、15 mod 7 = 1。六步走遍,5 是生成元。
2. 离散对数:乘方容易、取对数难
它解决什么问题
签名需要一个「我能算、别人倒推不了」的东西。RSA 用的是大数分解。离散对数提供另一个:公开 gˣ mod p 很安全,因为从它反推 x 不可行。
直觉
正着算 gᵃ mod p,用平方-乘几十步就出来。倒着从结果找 a,没有已知的快办法,参数小时只能列表穷举。
参数有多大才够难?课件给的说法是:能解 DL 的 p 和能分解的 n 规模大致相同,所以 Elgamal 和 RSA 用差不多长的模数。
一步一步看
目标:对着模 7 的乘方表查离散对数,看出底数是生成元时答案唯一,参数一大这张表就没法查。
-
定义:给素数 p、生成元 g 和某个 b,求 a 使 gᵃ ≡ b (mod p),记作 a = dlog(b)。
-
参数很小时,直接把所有乘方列成表:
图片来源:COMP5521 Lecture 4 Digital Signature, p.18 -
求以 3 为底 6 的离散对数:在 b = 3 那行找 6,它在第 3 列,所以答案是 3。
-
换成以 2 为底 4:b = 2 那行第 2 列和第 5 列都是 4,答案有两个,因为 2 不是生成元。
x 1 2 3 4 5 6 3ˣ mod 7 3 2 6 4 5 1 2ˣ mod 7 2 4 1 2 4 1 -
参数变大(几千 bit),这张表大到写不下,就没法查了。
怎么算
DL 假设写成一句:没有多项式时间算法能解 DLP。
f(x) = gˣ mod p
意思是:给 x 算 f(x) 容易,给 f(x) 反求 x 难。这叫单向函数。
它和 RSA 的区别在陷门。RSA 是陷门单向函数:知道 d 的人能倒推。离散对数没有陷门,签名者的优势只来自他知道 x 本身。
常见误解
以为 DL 难题比分解难题难很多(或容易很多)
两者规模大致相同:能解 DL 的 p 和能分解的 n 差不多长,所以 Elgamal 和 RSA 用的模数长度相近。
以为 DL 也是陷门单向函数
不是。DL 没有像 d 那样的后门;Elgamal 里签名者能签,只因为他知道指数 x。
试一下
查上面那张表:以 5 为底,模 7 下 2 的离散对数是多少?
b = 5 那行是 5、4、6、2、3、1,2 在第 4 列,所以 dlog₅(2) = 4。验算 5⁴ = 625 = 89 × 7 + 2 ✓。
3. Elgamal 签名
它解决什么问题
有了离散对数这个难题,怎么用它签名?Elgamal 给出一种做法:私钥 x 藏在公钥 y = gˣ mod p 后面,签名时再引入一个每次都换的 k,签出一对 (r, s)。
从哪来(补充)
Elgamal 签名方案由 Taher Elgamal 在 1985 年提出。原版方案实际很少使用,它的变体 DSA(下一页讲)用得广得多。出处:Wikipedia: ElGamal signature scheme
直觉
公钥 y = gˣ 和 DH 里的公开值是同一个形状。签名时先拿 k 算 r = gᵏ,这一半公开了「墨水」。另一半 s 把消息 X、私钥 x、r 和 k 拴进一个方程。
验证者不知道 x 和 k,但手里有 y = gˣ 和 r = gᵏ。把方程搬到 g 的指数上,正好只剩这两个公开值。
一步一步看
目标:用 p = 11 的小数字走完建钥、选 k、签名、验证,看出验证式两边为什么都算出 6。
用课件的小数字:p = 11、g = 2、私钥 x = 3、消息 X = 9、临时 k = 7。
-
建密钥:y = 2³ mod 11 = 8,公开 (11, 2, 8)。
-
选 k:gcd(7, 10) = 1,k⁻¹ 在 mod 10 下求,7 × 3 = 21 ≡ 1,所以 k⁻¹ = 3。
-
签名:r = 2⁷ mod 11 = 7;s = 3 × (9 − 3 × 7) mod 10 = −36 mod 10 = 4。签名消息是 (9, (7, 4))。
-
验证:左边 2⁹ mod 11 = 6;右边 8⁷ × 7⁴ mod 11 = 2 × 3 = 6。两边相等,有效。
怎么算
密钥:私钥 x,公钥 y = gˣ mod p。p 要选得让 p−1 有大素因子,g 是原根。
签名(消息 X):
- 选 k,gcd(k, p−1) = 1
- r = gᵏ mod p
- s = k⁻¹(X − x·r) mod (p−1)
验证:比较 gˣ 和 yʳ·rˢ (mod p)。
为什么相等:s ≡ k⁻¹(X − xr),两边乘 k,移项得 X ≡ xr + ks (mod p−1)。
gˣ = g^(xr + ks) = (gˣ)ʳ · (gᵏ)ˢ = yʳ · rˢ (mod p)
意思是:签名方程搬到指数上就是验证式。指数只需在 mod (p−1) 下相等,因为 g^(p−1) ≡ 1(费马小定理)。
三个模数分清:r 和验证式 mod p,s mod (p−1)。
常见误解
把 s 也 mod p
s 在指数上,所以 mod (p−1)。k⁻¹ 也在 mod (p−1) 下求,这就是 k 要和 p−1 互素的原因。
负数取模写成负数
−36 mod 10 是 4,不是 −6。括号里 X − xr 常常是负数,乘完要折回 0 到 p−2。
以为 k 可以重复用
k 必须每次不同且保密。两条消息用同一个 k,r 会相同,两条 s 的方程相减就能解出私钥 x。
试一下
上面的例子里,验证者手里有哪些数?哪些数他不需要?
他有公开的 (p, g, y) = (11, 2, 8)、消息 9 和签名 (7, 4)。他不需要 x = 3,也不需要 k = 7。
把它们串起来
这一页是一条线:先认生成元,再立难题,最后用难题签名。
生成元让「停在哪格」对应唯一的步数,离散对数才有定义。离散对数正着算快、倒着算难,于是 y = gˣ 可以放心公开。Elgamal 在这上面签名:r 公开了 gᵏ,s 把消息、x 和 k 拴进一个方程,验证者把方程搬到 g 的指数上,只用公开的 y 和 r 就能核对。
零件都是旧的:平方-乘算 gᵏ 和 yʳrˢ,扩展欧几里得求 k⁻¹ mod (p−1)。新东西只有两样:签名是一对数;每次签名要换一个 k。
Elgamal 的签名两个数各有 p 那么长。下一页的 DSA 把运算搬进一个小得多的子群,签名一下缩短很多。
课件里的坑
- [读图] p.19 最后一问「以 2 为底模 7 求 4 的离散对数」答案不唯一,2 和 5 都行,因为 2 的周期只有 3,它不是生成元;老师放一个 How about 就是要你发现这一点(p.18–19)
- [读图] p.22 右侧那句 Using the received values 指向验证式:验证者只用收到的 (X, r, s) 和公开的 (p, g, y),不需要 k 和 x(p.22)
- [补充] p.21 要求 p−1 有大素因子,否则离散对数会被按小因子拆开算;课件只写要求不讲原因(p.21)
- [写法] p.23 整页留空要自己填,−36 mod 10 要写成 4(p.23)
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写 Elgamal 的 r、s 和验证式,各标上 mod 什么;再推一遍 X ≡ xr + ks 怎么变成验证式;最后把 p.23 那道题不看解答重算。三步做完再往下看答案。
必背
- DLP:给 g、p、b 求 a 使 gᵃ ≡ b (mod p);mod 7 的生成元只有 3 和 5;以 2 为底模 7 求 4 的离散对数有 2 和 5 两个解,因为 2 的周期只有 3。
- 可解 DL 的 p 与可分解的 n 规模相当;DL 是单向函数,没有 RSA 那样的陷门。
- Elgamal 密钥:私钥 x,公钥 y = gˣ mod p,公开 (p, g, y);g 是原根,p−1 要有大素因子。
- Elgamal 签名 r = gᵏ mod p、s = k⁻¹(X − xr) mod (p−1),验证 gˣ 与 yʳrˢ 是否相等 (mod p);r 和验证式 mod p、s mod (p−1),k 与 p−1 互素且每次不同。
- 验证式的来历:X ≡ xr + ks (mod p−1),搬到 g 的指数上得 gˣ = (gˣ)ʳ·(gᵏ)ˢ = yʳrˢ。
- p = 11、g = 2、x = 3、X = 9、k = 7:y = 8、k⁻¹ = 3、r = 7、s = 4,两边验证值都是 6。
- Exercise-5/6:p = 29、g = 2、x = 12、k = 5、X = 26 → y = 7、r = 3、k⁻¹ = 17、s = 26,验证两边都是 22。
课件例题
例 1(课件 p.18–19):查模 7 的乘方表求离散对数
题面:课件给出 b 从 1 到 6、x 从 1 到 6 的 b^x mod 7 表。已知以 3 为底模 7 时 2 的离散对数是 2。求以 3 为底 6 和 5 的离散对数,再求以 2 为底 4 的离散对数。
提示
前两问只看 b = 3 那行。最后一问看 b = 2 那行,数一数 4 出现了几次。
解答
b = 3 那行是 3、2、6、4、5、1。3³ ≡ 6,所以以 3 为底 6 的离散对数是 3。3⁵ ≡ 5,所以 5 的离散对数是 5。
以 2 为底 4:b = 2 那行是 2、4、1、2、4、1,2² 和 2⁵ 都 ≡ 4,答案有 2 和 5 两个。原因是 2 不是模 7 的生成元,周期只有 3,定义里「唯一」的前提不成立。
例 2(课件 p.23):Elgamal 签名逐格填
题面:p = 11、g = 2,私钥 x = 3,消息 X = 9,临时 k = 7。求公钥 y、k⁻¹、r、s,写出签名消息并验证。
提示
k⁻¹ 在 mod 10 下求。s 的括号里是负数。验证右边 8⁷ 用 8² 和 8⁴ 拼。
解答
2 的幂 mod 11 依次是 2, 4, 8, 5, 10, 9, 7, 3, 6, 1,跑遍十个,2 是生成元。
公钥 y = 2³ mod 11 = 8。gcd(7, 10) = 1,k⁻¹ = 7⁻¹ mod 10 = 3,因为 7 × 3 = 21 ≡ 1。
r = 2⁷ mod 11 = 128 mod 11 = 7。s = 3 × (9 − 3 × 7) mod 10 = 3 × (−12) mod 10 = −36 mod 10 = 4。签名消息是 (9, (7, 4))。
验证左边 2⁹ mod 11 = 512 mod 11 = 6。右边 8⁷ × 7⁴ mod 11:8² ≡ 9,8⁴ ≡ 4,8⁷ = 4 × 9 × 8 = 288 ≡ 2;7² ≡ 5,7⁴ ≡ 3;2 × 3 = 6。两边相等,接受。
例 3(课件 p.41–42):Exercise-5/6,Elgamal 签名与验证
见下方完整例题。
完整例题
课件 p.41–42 是同一组数字的签名和验证,连起来走一遍。这是 take-home 练习,不代表官方承诺考试题型。
p = 29、g = 2、x = 12、k = 5,签 X = 26 并验证(p.41–42 Exercise-5/6)
- 公钥 y = 2¹² mod 29:2⁵ = 32 ≡ 3,2¹⁰ ≡ 9,2¹² = 9 × 4 = 36 ≡ 7。发 (29, 2, 7)。
- gcd(5, 28) = 1 ✓。r = 2⁵ mod 29 = 3。
- k⁻¹ = 5⁻¹ mod 28 = 17(5 × 17 = 85 = 3 × 28 + 1)。
- s = 17 × (26 − 12 × 3) = 17 × (−10) = −170 mod 28 = 26(−170 + 196 = 26)。签名 (3, 26)。
- 验证左边 yʳrˢ = 7³ × 3²⁶ mod 29:7³ = 343 ≡ 24;3³ ≡ −2,3⁶ ≡ 4,3¹² ≡ 16,3²⁴ ≡ 24,3²⁶ = 24 × 9 = 216 ≡ 13;24 × 13 = 312 ≡ 22。
- 验证右边 gˣ = 2²⁶ mod 29:2²⁰ ≡ 81 ≡ 23,2²⁶ = 23 × 3 × 2 = 138 ≡ 22。相等,有效。
变式题(先自己做)
改编自课件 p.23:p = 11、g = 2,私钥 x = 3,这次签 X = 5,临时 k = 9。求 y、k⁻¹、r、s,并验证。
提示
先核 gcd(9, 10) = 1。9 的逆 mod 10 就是它自己。算 s 时括号里是负数,乘完再折回 0 到 9。验证右边的 8⁶ 可以借 8⁴ 和 8² 拼出来。
判分点与答案(非官方评分标准)
判分点:r 和验证式 mod 11,s mod 10;k⁻¹ 要验算;负数取模要折回正数。
y = 2³ = 8。k⁻¹ = 9⁻¹ mod 10 = 9(81 = 8 × 10 + 1)。r = 2⁹ mod 11 = 512 mod 11 = 6。s = 9 × (5 − 3 × 6) = 9 × (−13) = −117 mod 10 = 3。签名 (6, 3)。验证左边 2⁵ = 32 mod 11 = 10。右边 8⁶ × 6³:8² ≡ 9,8⁴ ≡ 4,8⁶ ≡ 36 ≡ 3;6³ = 216 ≡ 7;3 × 7 = 21 ≡ 10 ✓。
闪卡自测
1. mod 7 的生成元有哪些?以 2 为底求 4 的离散对数为什么特殊?
3 和 5。2 的周期只有 3,2² 和 2⁵ 都 ≡ 4,答案不唯一(p.18–19)。
2. DL 是不是陷门单向函数?
不是。它是单向函数,但没有 RSA 的 d 那样的后门,签名者的优势只来自知道 x(p.20)。
3. Elgamal 公开什么、保密什么?
公开 (p, g, y),y = gˣ mod p;保密 x(p.21)。
4. Elgamal 的 r、s 各 mod 什么?k 要满足什么?
r = gᵏ mod p,s = k⁻¹(X − xr) mod (p−1);gcd(k, p−1) = 1(p.22)。
5. 验证式 gˣ = yʳrˢ 怎么推出来?
由 s 的定义得 X ≡ xr + ks (mod p−1),放到 g 的指数上,g^(xr) = yʳ,g^(ks) = rˢ(p.22)。
6. p.23 的 y、k⁻¹、r、s 各是多少?
y = 8,k⁻¹ = 3,r = 7,s = 4;两边验证值都是 6(p.23)。
下一讲
下一页讲 DSA:在 p 里挑一个 q 阶小子群,r 和 s 都 mod q,签名变短。见 L04d。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。