L04d DSA:把 Elgamal 搬进一个小圈子
从零讲 DSA:先看 q 阶子群是怎么从大模数里挑出来的,再一帧一帧走完课件的小数字签名与验证,最后说清 r 为什么要取两层模、签名为什么变短。
一句话版
DSA 是 Elgamal 的官方精简版。它在大模数 p 里挑出一个只有 q 个元素的小圈子,签名和验证的指数都在 mod q 下算,签名从两个 p 那么长的数缩成两个 q 那么长的数。
这一页要用到 Elgamal 的签名方程,见上一页 L04c。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| DSS | Digital Signature Standard,数字签名标准 | 美国官方签名标准的名字 |
| DSA | Digital Signature Algorithm,数字签名算法 | DSS 里规定的那个算法 |
| q 阶子群 | subgroup of order q | g 的乘方只在 q 个数里打转,转 q 次回到 1 |
| H(X) | 消息 X 的哈希值 | DSA 签的是哈希,不是原文 |
| w、t₁、t₂、v | 验证中间量 | 验证方算出来、最后拿 v 和 r 比 |
一个类比:大操场里划出一条小跑道
Elgamal 像在整个大操场上跑圈,每一格都可能踩到,记录步数要用很大的数。
DSA 先在操场里划出一条只有 q 格的小跑道,规定只在这条跑道上跑。跑道外面的人看到的还是大操场上的位置(mod p),可步数只需要记到 q 为止(mod q)。
签名记的是步数,所以签名变短了。难度没降多少,因为外人要猜的仍是「在这条跑道上走了几步」。
类比在哪里失效:真正的跑道格子是挨着的,子群里的数在 1 到 p−1 之间散落得毫无规律,外人看不出哪些数属于这条跑道。
从零讲起
1. 先补一块:q 阶子群(补充)
它解决什么问题
DSA 想让指数在 mod q 下算,q 远小于 p。这要求底数 g 转 q 次就回到 1。这一节说清这样的 g 怎么造出来。
直觉
模 29 下非零数有 28 个。28 = 4 × 7,7 是它的一个素因子。
随便挑一个 h,算 g = h⁴ mod 29,也就是 h^(28/7)。这样的 g 再升 7 次方,等于 h²⁸,按费马小定理就是 1。所以 g 转 7 次一定回到 1。
一步一步看
目标:用 p = 29、q = 7 造出 g = 23,看出 g 的乘方只在 7 个数里打转,指数可以先模 q。
-
选素数 q,要求 q 整除 p−1。课件例子 p = 29、q = 7。
-
选 h,算 g = h^((p−1)/q) mod p。h = 3 时,g = 3⁴ = 81 mod 29 = 23。
-
检查 g > 1。如果算出 1 就换一个 h。
-
列出 23 的乘方,看它在几个数里打转:
-
这 7 个数就是 q 阶子群。之后所有 g 的乘方都落在里面,指数可以先 mod 7。
怎么算
gᵠ = (h^((p−1)/q))ᵠ = h^(p−1) ≡ 1 (mod p)
意思是:g 升 q 次方一定回到 1,所以 g 的阶整除 q。q 是素数,g 又不等于 1,阶只能恰好是 q。
阶是 q 带来的好处:g 的指数相差 q 的倍数时结果一样,所以 DSA 里所有指数都可以 mod q。
常见误解
以为 g 必须是 mod p 的生成元
Elgamal 要生成元,DSA 反过来:故意选一个阶只有 q 的 g。23 在 mod 29 下只走 7 格,这正是 DSA 想要的。
试一下
p = 29、q = 7,如果选 h = 1,会出什么问题?
g = 1⁴ = 1,1 的任何次方都是 1,子群里只有一个数,什么也藏不住。所以要求 g > 1,算出 1 就换 h。
2. DSA 签名与验证
它解决什么问题
Elgamal 的签名两个数各有 p 那么长,算起来也慢。DSA 把运算搬进 q 阶子群,签名变短、计算变快,同时保留离散对数的难度。
从哪来(补充)
NIST 在 1991 年 8 月提出 DSA,1994 年作为 FIPS 186 正式采用。专利 US 5,231,668 归在前 NSA 雇员 David W. Kravitz 名下,现已过期。2023 年 2 月发布的 FIPS 186-5 不再允许用 DSA 生成新签名,只允许验证此前生成的签名。出处:Wikipedia: Digital Signature Algorithm
直觉
DSA 的签名方程和 Elgamal 长得很像,有两处改动:签的是哈希 H(X);减号换成加号,模数换成 q。
验证也换了一种方式。Elgamal 比较两边是否相等;DSA 用公开值重新算出一个 v,看它和 r 是否相同。
一步一步看
目标:用课件的小数字走完 DSA 建参、签名和验证,看出验证算出的 v 怎样回到 r。
用课件的小数字:p = 29、q = 7、h = 3、私钥 u = 2、H(X) = 5、临时 k = 4。
-
建参数:g = 23,公钥 y = 23² mod 29。23 ≡ −6,所以 y ≡ 36 ≡ 7。
-
签名:k⁻¹ = 2(4 × 2 = 8 ≡ 1 mod 7)。r = (23⁴ mod 29) mod 7 = 20 mod 7 = 6;s = 2 × (5 + 2 × 6) mod 7 = 6。
-
验证中间量:w = 6⁻¹ mod 7 = 6,t₁ = 5 × 6 mod 7 = 2,t₂ = 6 × 6 mod 7 = 1。
-
算 v:v = ((23² × 7¹) mod 29) mod 7 = 20 mod 7 = 6。v = r,有效。
怎么算
密钥:q 是 160 bit 素数;p 是 512–1024 bit 素数,长度是 64 的倍数,q 整除 p−1;g = h^((p−1)/q) mod p;私钥 u < q;公钥 y = gᵘ mod p。
签名(随机 k < q):
- r = (gᵏ mod p) mod q
- s = k⁻¹(H(X) + u·r) mod q
验证:
- w = s⁻¹ mod q
- t₁ = H(X)·w mod q,t₂ = r·w mod q
- v = ((g^t₁ · y^t₂) mod p) mod q,v = r 则接受
为什么 v = r(补充,课件不证):由 s 的定义,H + ur ≡ k·s (mod q),两边乘 w = s⁻¹ 得 w(H + ur) ≡ k。
g^t₁ · y^t₂ = g^(Hw) · g^(urw) = g^(w(H + ur)) = gᵏ (mod p)
意思是:验证方用公开值重新算出了 gᵏ mod p,再 mod q 就是签名者当初的 r。g 的阶是 q,所以指数只要在 mod q 下相等就行。
常见误解
以为 DSA 也能加密
DSA 只能签。签名和验证式里没有哪一步能把消息藏起来,它也不能用来交换密钥。
把 Elgamal 和 DSA 的 s 记混
Elgamal 是 k⁻¹(X − xr) mod (p−1),DSA 是 k⁻¹(H(X) + ur) mod q。减号变加号,原文变哈希,模数变 q。
以为每个用户要自己生成 p、q、g
(p, q, g) 是公开参数,可以多人共用。每人只需自己的私钥 u 和公钥 y。
试一下
同一组参数,验证方拿到的签名是 (6, 5),H = 5。签名有效吗?
w = 5⁻¹ mod 7 = 3(5 × 3 = 15 ≡ 1),t₁ = 5 × 3 mod 7 = 1,t₂ = 6 × 3 mod 7 = 4。v = ((23¹ × 7⁴) mod 29) mod 7。7² ≡ 20,7⁴ ≡ 400 mod 29 = 23,23 × 23 = 529 mod 29 = 7,v = 7 mod 7 = 0 ≠ 6,无效。
3. 两层取模与签名长度
它解决什么问题
DSA 里最容易丢分的是取模层数。这一节把「哪些量 mod 一层、哪些 mod 两层」理清,顺带说明签名为什么变短。
直觉
gᵏ 本身活在大模数 p 里,得先 mod p 算出它在子群里的位置。签名只需要记一个小于 q 的数,所以再 mod q 一次。
s、w、t₁、t₂ 都是指数层面的量,指数只需 mod q,一层就够。
一步一步看
目标:跟着 gᵏ 先模 p 再模 q 走两层,看出签名和验证都走这两层,签名的两个数也都小于 q。
-
算 gᵏ:例子里是 23⁴。
-
先 mod p = 29,得 20。
-
再 mod q = 7,得 r = 6。
-
验证时 v 走同样两层:g^t₁ · y^t₂ 先 mod 29 得 20,再 mod 7 得 6。
-
签名 (r, s) 两个数都小于 q。q 是 160 bit 时,签名是两个 160 bit 的数。
怎么判断
拿到一个量,问它属于哪一层:
| 量 | 属于哪层 | 取模 |
|---|---|---|
| gᵏ、g^t₁ · y^t₂、y | 大模数里的元素 | mod p |
| r、v | 元素压成小数 | 先 mod p 再 mod q |
| s、w、t₁、t₂、k⁻¹ | 指数 | mod q |
签名长度跟着 q 走。Elgamal 的 s 是 mod (p−1) 的数,两个签名数各有 p 那么长;DSA 两个都小于 q。
常见误解
r 只 mod p 不 mod q
那样 r 会是 20 而不是 6,后面 s 和验证都对不上。r 和 v 必须两层。
把 k⁻¹ 求成 mod p 或 mod (p−1)
DSA 里的 k⁻¹、w 都是 mod q 的逆。例子里 k⁻¹ = 4⁻¹ mod 7 = 2,不是 mod 29。
试一下
另一组参数里 2⁷ mod 47 = 34,q = 23。r 是多少?
r = 34 mod 23 = 11。
把它们串起来
DSA 是 Elgamal 换到小圈子里的版本。q 阶子群先把指数的范围压到 mod q,签名方程照搬 Elgamal 的形状,只把原文换成哈希、减号换成加号。验证方用 w、t₁、t₂ 把公开值拼回 gᵏ,再压两层模和 r 比。
三种签名放在一起看:
RSA 签名没有临时随机数,同一条消息每次签出来都一样;Elgamal 和 DSA 每次换 k,签名每次不同。盲签名不在表里,它是套在 RSA 签名外面的协议。
整讲用到的零件到这里都齐了:平方-乘算乘方,扩展欧几里得求逆,先哈希再签防伪造。
课件里的坑
- [补充] p.25 的 160 bit q、512–1024 bit p 是 1994 年原版参数,现行 FIPS 186-5 已改成 (2048, 224)、(2048, 256)、(3072, 256) 三组;答题按课件写(p.25)
- [补充] p.24 的 DSS 是标准名,DSA 是标准里的算法名,考试可能混用(p.24)
- [写法] p.27 算 y = 23² mod 29 用了 23 ≡ −6 的技巧,(−6)² = 36 ≡ 7(p.27)
- [易错] p.29 的 t₂ = 36 mod 7,很多人算成 0,正确是 1(p.29)
- [巧合] p.44 的 r 和 s 恰好相等、t₂ 又是 1,是这组小数字的巧合,不是规律(p.44)
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写 DSA 五个参数和签名、验证共六个量的公式,每个标上 mod 几层;再把 p.44 那道题不看解答重算;最后用两行推一遍 v 为什么等于 r。三步做完再往下看答案。
必背
- DSS = FIPS 186,NIST 1991 提出、1994 发布;DSA 只能签,不能加密也不能交换密钥。
- DSA 五个量:q(160 bit 素数)、p(512–1024 bit,q 整除 p−1)、g = h^((p−1)/q) mod p > 1、私钥 u < q、公钥 y = gᵘ mod p;(p, q, g) 可多人共用。
- DSA 签名 r = (gᵏ mod p) mod q、s = k⁻¹(H(X) + ur) mod q;验证 w = s⁻¹、t₁ = Hw、t₂ = rw(均 mod q)、v = ((g^t₁ y^t₂) mod p) mod q,v = r 则接受。
- DSA 例:p = 29、q = 7、h = 3 → g = 23、u = 2 → y = 7;H = 5、k = 4 → (r, s) = (6, 6);w = 6、t₁ = 2、t₂ = 1、v = 6。
- Exercise-8:p = 47、q = 23、g = 2、x = 10、k = 7、H = 13 → y = 37、(r, s) = (11, 11)、w = 21、t₁ = 20、t₂ = 1、v = 11。
- s、w、t₁、t₂ 只 mod q;r 和 v 先 mod p 再 mod q,两层括号别丢。
课件例题
例 1(课件 p.27–29):DSA 小数字例子,建参数、签名、验证
题面:p = 29,q = 7,h = 3,私钥 u = 2。消息哈希 H(X) = 5,临时 k = 4。求 g、y,签名 (r, s),再算 w、t₁、t₂、v 验证。
提示
g 的指数是 28 / 7。y 用 23 ≡ −6。k⁻¹、w 都在 mod 7 下求。v 要两层取模。
解答
建参数:7 整除 28。g = 3^(28/7) = 3⁴ = 81 mod 29 = 23。y = 23² mod 29,23 ≡ −6,所以 y ≡ 36 ≡ 7。
签名:k⁻¹ = 4⁻¹ mod 7 = 2,因为 4 × 2 = 8 ≡ 1。23⁴ mod 29 = 20,r = 20 mod 7 = 6。s = 2 × (5 + 2 × 6) mod 7 = 34 mod 7 = 6。签名 (6, 6)。
验证:w = 6⁻¹ mod 7 = 6,因为 6 × 6 = 36 ≡ 1。t₁ = 5 × 6 mod 7 = 30 mod 7 = 2。t₂ = 6 × 6 mod 7 = 1。v = ((23² × 7¹) mod 29) mod 7 = (49 mod 29) mod 7 = 20 mod 7 = 6。v = r,接受。
例 2(课件 p.44):Exercise-8,DSA 签名与验证
见下方完整例题。
完整例题
课件 p.44 题面没给答案,从建公钥一路算到验证。这是 take-home 练习,不代表官方承诺考试题型。
H(m) = 13,p = 47,q = 23,g = 2,私钥 x = 10,临时 k = 7(p.44 Exercise-8)
- 核参数:46 / 23 = 2,q 整除 p−1;2²³ mod 47 = 1,2 的阶是 23 ✓。
- 公钥 y = 2¹⁰ mod 47 = 1024 mod 47 = 37(47 × 21 = 987)。
- r:2⁷ = 128 mod 47 = 34,r = 34 mod 23 = 11。
- k⁻¹ = 7⁻¹ mod 23 = 10(7 × 10 = 70 = 3 × 23 + 1)。s = 10 × (13 + 10 × 11) mod 23 = 1230 mod 23 = 11(23 × 53 = 1219)。签名 (11, 11)。
- 验证中间量:w = 11⁻¹ mod 23 = 21(11 × 21 = 231 = 10 × 23 + 1);t₁ = 13 × 21 mod 23 = 273 mod 23 = 20;t₂ = 11 × 21 mod 23 = 1。
- v:2²⁰ mod 47 = 37² = 1369 ≡ 6;y^t₂ = 37;6 × 37 = 222 ≡ 34;v = 34 mod 23 = 11 = r,接受。
变式题(先自己做)
改编自课件 p.27–29:参数不变(p = 29、q = 7、g = 23、u = 2、y = 7),H(X) = 5,这次临时 k = 3。求 (r, s),再算 w、t₁、t₂、v 验证。
提示
23 的乘方 mod 29 前几项是 1, 23, 7, 16, 20。k⁻¹ = 3⁻¹ mod 7。算 v 要用 7³ mod 29。
判分点与答案(非官方评分标准)
判分点:r、v 两层取模;k⁻¹、w 在 mod 7 下求并验算;s、t₁、t₂ 只 mod 7。
r = (23³ mod 29) mod 7 = 16 mod 7 = 2。k⁻¹ = 3⁻¹ mod 7 = 5(3 × 5 = 15 ≡ 1)。s = 5 × (5 + 2 × 2) mod 7 = 45 mod 7 = 3。签名 (2, 3)。w = 3⁻¹ mod 7 = 5,t₁ = 5 × 5 mod 7 = 4,t₂ = 2 × 5 mod 7 = 3。23⁴ mod 29 = 20,7³ = 343 mod 29 = 24,20 × 24 = 480 mod 29 = 16,v = 16 mod 7 = 2 = r ✓。
闪卡自测
1. DSS 哪年提出、哪年发布、编号多少?DSA 能不能加密?
NIST 1991 提出、1994 发布,FIPS 186;只能签,不能加密(p.24)。
2. DSA 的 q、p 各有什么要求?
q 是 160 bit 素数;p 是 512–1024 bit 素数,长度是 64 的倍数,且 q 整除 p−1(p.25)。
3. g 怎么造?为什么它的阶是 q?
g = h^((p−1)/q) mod p,要求 g > 1;gᵠ = h^(p−1) ≡ 1,q 是素数,所以阶恰好是 q(p.25)。
4. 写出 DSA 的 r 和 s。
r = (gᵏ mod p) mod q,s = k⁻¹(H(X) + ur) mod q(p.26)。
5. DSA 验证的四个中间量是什么?哪两个量要 mod 两层?
w = s⁻¹、t₁ = H·w、t₂ = r·w,都 mod q;v = ((g^t₁ y^t₂) mod p) mod q。r 和 v 先 mod p 再 mod q(p.26)。
6. p.27–29 例子的 g、y、(r, s)、v 各是多少?
g = 23,y = 7,(r, s) = (6, 6),v = 6(p.27–29)。
下一讲
下一讲进入电子支付协议 SET,它的双重签名就是这一讲的 RSA 签名加先哈希:两份消息各哈希、拼接后再哈希、再签。见 L05a。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。