← COMP5521 全部讲次
L04d · 第 5 周

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。

  1. 选素数 q,要求 q 整除 p−1。课件例子 p = 29、q = 7。

  2. 选 h,算 g = h^((p−1)/q) mod p。h = 3 时,g = 3⁴ = 81 mod 29 = 23。

  3. 检查 g > 1。如果算出 1 就换一个 h。

  4. 列出 23 的乘方,看它在几个数里打转:

    mod 29 下 23 生成的 7 阶子群:23 的 0 到 6 次方 mod 29 依次是 1、23、7、16、20、25、24,七个数围成一圈,第 7 次回到 1;mod 29 共有 28 个非零数,g 只在其中 7 个里打转

  5. 这 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。

  1. 建参数:g = 23,公钥 y = 23² mod 29。23 ≡ −6,所以 y ≡ 36 ≡ 7。

    DSA 签名第 1 帧:五个格子依次是参数 p=29 q=7 h=3、g 和 y、签名 (r,s)、w t₁ t₂、v = r ?;g 和 y 格子被青绿框标出,写着 g=23 y=7;下方说明 g = 3 的 4 次方 mod 29 = 23,私钥 2,公钥 23 的平方 mod 29 = 7,(p, q, g) 可以多人共用

  2. 签名: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。

    DSA 签名第 2 帧:签名格子被青绿框标出,写着 (r,s)=(6,6);下方说明 H(X) = 5,临时 k = 4,k 的逆 mod 7 是 2,r = 20 mod 7 = 6,s = 2 乘 (5 + 2 × 6) mod 7 = 6

  3. 验证中间量:w = 6⁻¹ mod 7 = 6,t₁ = 5 × 6 mod 7 = 2,t₂ = 6 × 6 mod 7 = 1。

    DSA 签名第 3 帧:w t₁ t₂ 格子被青绿框标出,写着 6, 2, 1;下方说明验证方只拿到签名 (6, 6)、哈希 5 和公钥 7,w = 6 的逆 mod 7 = 6,t₁ = 2,t₂ = 1

  4. 算 v:v = ((23² × 7¹) mod 29) mod 7 = 20 mod 7 = 6。v = r,有效。

    DSA 签名第 4 帧:v = r ? 格子被青绿框标出,写着 v = 6;下方说明 v = (23 的平方乘 7 mod 29) mod 7 = 20 mod 7 = 6,等于 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。

  1. 算 gᵏ:例子里是 23⁴。

  2. 先 mod p = 29,得 20。

  3. 再 mod q = 7,得 r = 6。

    r 的两层取模:三个格子依次是 23 的 4 次方、mod p = 29 得 20、mod q = 7 得 r = 6;下方说明签名里的 r、s 都小于 q,课件参数里 q 是 160 bit,所以签名是两个 160 bit 的数;验证时的 v 也先 mod p 再 mod q,s、w、t₁、t₂ 只 mod q 一层

  4. 验证时 v 走同样两层:g^t₁ · y^t₂ 先 mod 29 得 20,再 mod 7 得 6。

  5. 签名 (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 签名压在大数分解上,私钥 d、公钥 (e, n),无临时随机数,签名 S = M 的 d 次方 mod n,验证 S 的 e 次方 mod n 是否等于 M,签名是一个数;Elgamal 压在离散对数上,私钥 x、公钥 y = g 的 x 次方,临时 k 与 p−1 互素,r = g 的 k 次方 mod p,s = k 的逆乘 (X − xr) mod (p−1),验证 g 的 X 次方是否等于 y 的 r 次方乘 r 的 s 次方,签名两个数各 p 那么长;DSA 压在 q 阶子群离散对数上,私钥 u、公钥 y = g 的 u 次方,k 小于 q,r = (g 的 k 次方 mod p) mod q,s = k 的逆乘 (H(X) + ur) mod q,验证 v 是否等于 r,签名两个数各 160 bit

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。三步做完再往下看答案。

必背

  1. DSS = FIPS 186,NIST 1991 提出、1994 发布;DSA 只能签,不能加密也不能交换密钥。
  2. 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) 可多人共用。
  3. 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 则接受。
  4. 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。
  5. 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。
  6. 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)

  1. 核参数:46 / 23 = 2,q 整除 p−1;2²³ mod 47 = 1,2 的阶是 23 ✓。
  2. 公钥 y = 2¹⁰ mod 47 = 1024 mod 47 = 37(47 × 21 = 987)。
  3. r:2⁷ = 128 mod 47 = 34,r = 34 mod 23 = 11。
  4. 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)。
  5. 验证中间量: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。
  6. 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。

下一讲 →
Lab3 Lab3 ERC-20 与 Hardhat:亲手发一枚只有你能增发的代币

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。