L04 数字签名：一枚只有你能盖、谁都能验的印章

一句话版

上一讲把消息锁进箱子，这一讲在箱子上盖章：用你的私钥签、用你的公钥验，三种签名算法压在两个数学难题上，最后加一个「签名者自己看不到内容」的盲签名协议。

一个类比：一枚只有你能盖、谁都能验的印章

数字签名是一枚印章。世上只有你能盖（私钥），但盖出来的印谁都能拿放大镜对（公钥）。课件 p.5 把手写签名的三个性质翻成数字版：你盖章容易、别人仿造难、任何人核对都容易。p.4 那朵画着三个小恶魔的 Internet 云说明了为什么需要它：Bob 收到一份「来自 Alice」的文件，加密回答不了「真的是她发的吗」，因为密文谁都能用 Alice 的公钥造出来。

印章和挂锁的钥匙方向正好相反。上一讲加密用收件人的公钥锁、收件人的私钥开；签名用发件人的私钥盖、发件人的公钥验。p.7 那张 Wikipedia 图下面有一句要记住的话：the message is only signed and not encrypted。盖了章的文件还是明着传，签名不负责保密，它负责的是 p.9 列的三样：认证（确实是你）、不可否认（你赖不掉）、完整性（改一个 bit 章就对不上）。

盖章之前先把文件压成一页摘要。p.8 这张 Stallings 的图比 p.6 的黑盒多了一个哈希函数：签的是 h = H(M)，验的时候重新算一遍 h。两个原因：RSA 一次只能处理小于 n 的数，长文件必须先压缩；更要紧的是，这一步堵住了 p.40 那道课后题教的伪造手法，后面会讲。

盲签名是隔着复写纸的信封盖章。p.31–35 的 Chaum 协议里，Alice 把文件塞进信封，信封夹层垫了复写纸，Bob 在信封外面盖章，章透过复写纸印到里面的文件上。Bob 盖了章，却没看到文件写了什么。数学上就是在 RSA 签名前后各乘一个随机数，p.36 的 Exercise-2 把它算了一遍。

类比在哪里失效：印章能被拓印，数字签名不能，因为签名和消息绑定，换一份文件章就失效。印章不分算法，数字签名分三种（RSA、Elgamal、DSA），签出来的东西长得不一样：RSA 签名是一个数，后两种是一对 (r, s)。复写纸信封的类比也漏掉一件事：Bob 事后拿到盖了章的原件，能验章是自己的，却对不上是哪次盖的，这种「验得出、认不出」的性质是电子现金匿名性的来源。

概念卡

1. 签名的形状：私钥签、公钥验

人话定义：Sign 盒吃进消息和私钥，吐出签名；Verify 盒吃进消息、签名和公钥，吐出 Valid 或 Invalid（p.6）。验签的输出是一个布尔值，它不「解出」任何东西。

例子：p.8 的两列各三步。Bob 这边：M → 哈希 → 用私钥签 → 发 M 和 S；Alice 这边：M → 哈希 → 用公钥验 → 有效或无效。注意这张图里签名的是 Bob、验的是 Alice，和 p.4–7 的角色反过来了，只认「私钥签、公钥验」，别认人名。

常见误解

以为签名就是「用私钥加密」→ 裸 RSA 的公式看上去确实像倒过来的加密，但签名验证返回的是真假，加密解密返回的是明文；而且真实系统签的是哈希值，不是消息本身。MAC 也能做消息认证，但 MAC 用共享密钥，收发双方都能造，第三方分不清是谁造的，所以 MAC 给不了不可否认性，签名可以（p.9，补充）。

2. RSA 签名：把加密公式倒过来用

人话定义：和上一讲同一套密钥 n = pq、ed ≡ 1 (mod φ(n))。签名 S = Mᵈ mod n，验证看 Sᵉ mod n 是否等于 M。d 叫签名私钥，(e, n) 叫验证公钥（p.10）。

例子：p.11 用 p = 47、q = 71，n = 3337，φ = 3220，e = 1019，d = 79（1019 × 79 = 80501 = 25 × 3220 + 1）。签 M = 688 得 S = 688⁷⁹ mod 3337 = 1570，验证 1570¹⁰¹⁹ mod 3337 = 688。p.12 把 e 换成 3，d 变成 2147，S = 513，验证只要算 513³ mod 3337。e 小验签快、签名慢，反过来也成立。

代价：p.13 那张表说 RSA-2048 只相当于 112 bit 对称强度，RSA-3072 才到 128 bit，对称密钥每加 16 bit，RSA 模长要翻倍。p.14 补一刀：签名时间和密钥长度的立方成正比，RSA-2048 比 RSA-1024 慢 8 倍。这就是第 8 周椭圆曲线登场的理由。

常见误解

把 p.13 表最后一行的 15,380 当准确数 → NIST SP 800-57 的对照表写的是 15360，也就是 15 × 1024。差 20 bit 不影响结论，答题写 15360 更稳，老师坚持课件数字就按课件（补充校订）。

3. 离散对数：乘方容易、取对数难

人话定义：给定素数 p、生成元 g 和某个 b，求 a 使 gᵃ ≡ b (mod p)，记作 a = dlog(b)。DL 假设是没有多项式时间算法能解它（p.17）。正向算 gᵃ mod p 用平方-乘很快，反向求 a 只能穷举，这就是单向函数（p.20）。

例子：p.18 列了 b^x mod 7 的整张表，只有 b = 3 和 b = 5 两行跑遍了 1 到 6，它们是模 7 的生成元。

p.19 让你查表：3³ ≡ 6，所以以 3 为底 6 的离散对数是 3；3⁵ ≡ 5，所以 5 的离散对数是 5。最后一问「以 2 为底 4 的离散对数」是个坑：2² ≡ 4，2⁵ ≡ 4 也成立，答案有两个。p.17 定义里那个「唯一」依赖 g 是生成元，2 的周期只有 3，前提不成立。

常见误解

以为 DL 难题和分解难题是两个量级 → p.20 说能解 DL 的 p 和能分解的 n 规模大致相同，所以 Elgamal、DSA 和 RSA 用差不多长的模数。另一个误解是把 DL 当成上一讲的陷门单向函数：DL 没有陷门，签名者的优势只来自他知道 x，没有 d 那样的「后门」（补充）。

4. Elgamal 与 DSA：一个私钥、一个临时 k、一对 (r, s)

人话定义：Elgamal 的私钥是 x，公钥 y = gˣ mod p。签一条消息 X 时先选一个临时的 k（与 p−1 互素），算 r = gᵏ mod p，s = k⁻¹(X − xr) mod (p−1)，签名是 (r, s)。验证看 gˣ 和 yʳ·rˢ 在 mod p 下是否相等（p.21–22）。DSA 是它的官方精简版：在 p 里挑一个 160 bit 的素数 q 整除 p−1，用 g = h^((p−1)/q) 生成 q 阶子群，签名 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 就接受（p.25–26）。

例子：p.23 用 p = 11、g = 2、x = 3、X = 9、k = 7。y = 2³ = 8，k⁻¹ = 3（7 × 3 = 21 ≡ 1 mod 10），r = 2⁷ mod 11 = 7，s = 3 × (9 − 21) = −36 mod 10 = 4。验证 2⁹ mod 11 = 6，8⁷ × 7⁴ mod 11 = 2 × 3 = 6，两边相等。DSA 例子 p.27–29：p = 29、q = 7、h = 3，g = 3⁴ mod 29 = 23，u = 2，y = 23² ≡ (−6)² = 36 ≡ 7；H = 5、k = 4，r = (23⁴ mod 29) mod 7 = 20 mod 7 = 6，s = 2 × 17 mod 7 = 6；验证 w = 6，t₁ = 2，t₂ = 1，v = (7 × 7 mod 29) mod 7 = 20 mod 7 = 6。

为什么验得出来：X ≡ xr + ks (mod p−1)，两边放到 g 的指数上，g^(xr) 是 yʳ，g^(ks) 是 rˢ。整讲最值得背的一行推导（p.22）。

常见误解

三个 mod 混用 → Elgamal 的 r 和验证式 mod p，s mod (p−1)；DSA 的 s、w、t₁、t₂ 全 mod q，r 和 v 要先 mod p 再 mod q，两层括号别丢。另一个常见错：负数取模，−36 mod 10 是 4 不是 −6。还有一个课件没细讲的坑：k 复用两次会让两条签名的 r 相同，两式相减就能解出私钥，第 9 周比特币那讲会以 ECDSA 随机数重用的形式再遇到（补充）。

5. 盲签名：隔着信封盖章

人话定义：Alice 想让 Bob 签 m，又不想让 Bob 看到 m。她选一个和 n 互素的随机数 k，算 m′ = m·kᵉ mod n 发给 Bob；Bob 签 s′ = (m′)ᵈ mod n 发回；Alice 算 s = k⁻¹·s′ mod n，得到的 s 正好等于 mᵈ mod n，和 Bob 直接签 m 一模一样（p.34–35）。

例子：p.36 的 Exercise-2，e = 5、n = 119、m = 37、k = 29。

为什么能剥掉 k：(m·kᵉ)ᵈ = mᵈ·k^(ed)，而 k^(ed) ≡ k，所以除掉 k 就剩 mᵈ。Alice 事先用公钥把 k 升了 e 次方，Bob 签名的 d 次方正好把它降回来，Bob 自己却不知道（p.35）。

常见误解

以为盲签名是第四种签名算法 → 它是套在 RSA 签名外面的两方协议，得到的 s 用 Bob 的公钥按普通方式验（p.32）。另一个读图坑：p.33 那张 Wikipedia 图把模数写成 p、盲化因子叫 r，p.35 课件自己的记号是 n 和 k，答题用 p.35 的。

6. 存在性伪造：为什么要先哈希

人话定义：Eve 没有 Bob 的私钥，但她可以倒着来，先随便挑一个「签名」S，用公钥算 m = Sᵉ mod n，把 (m, S) 发出去。Alice 验签算的正是 Sᵉ mod n，当然等于 m，于是接受（p.40）。

例子：n = 2021、e = 155，Eve 挑 S = 1158，算出 m = 1158¹⁵⁵ mod 2021 = 1702。Alice 验：1158¹⁵⁵ mod 2021 = 1702，相等，她会以为 1702 来自 Bob。

这攻击的边界：Eve 控制不了 m，1702 是算出来的乱数。真实系统签的是哈希 H(m)，Eve 拿到 1702 后还得找到一条消息哈希等于 1702，这是求哈希原像，做不到。p.8 那个哈希框就是为这件事放的。

常见误解

以为 Alice「应该」能发现 1702 是假的 → 验证算法只做一件事：算 Sᵉ mod n 和 m 比。它不判断 m 有没有意义。裸 RSA 签名在数学上就是允许这种伪造的，防御在协议层（先哈希），不在验证式里（补充）。

把它们串起来

三个 Part 是「换难题、再套协议」的一条线。Part 1 把签名的形状立起来（私钥签、公钥验、先哈希），用 RSA 实例化，代价是 RSA 长度涨得慢、签名时间按立方涨。Part 2 换一个难题：离散对数。Elgamal 用一个私钥 x 加一个每次都换的 k，签出一对 (r, s)；DSA 把运算搬进 q 阶子群，签名从两个 p 那么长的数缩成两个 160 bit 的数。Part 3 不换算法，在 RSA 签名前后各乘一个随机数，让签名者签得出、看不见。

上一讲的零件在这里各归各位：RSA 的 e、d、φ(n) 原样搬来，扩展欧几里得从「由 e 求 d」扩展到「由 k 求 k⁻¹ mod (p−1)」和「由 s 求 s⁻¹ mod q」；DH 的 gˣ mod p 换个名字叫 Elgamal 的公钥 y。课后 8 道 Exercise 全是手算，中间值都写在注解版里。

课件里的坑

• [补充校订] p.13 表最后一行印的 15,380，NIST SP 800-57 的数字是 15360（= 15 × 1024）；写 15360 更稳（p.13）
• [读图] p.19 最后一问「以 2 为底模 7 求 4 的离散对数」答案不唯一，2 和 5 都行，因为 2 的周期只有 3，它不是生成元；老师放一个 How about 就是要你发现这一点（p.18–19）
• [读图] p.33 的 Wikipedia 示意图用 p 当模数、r 当盲化因子，p.35 课件自己的记号是 n 和 k；两页是同一个协议，答题按 p.35（p.33、35）
• [读图] p.35 推导方框最后一行写着 D’s signature on m，D 指前文的签名者 Bob，是引用外部材料残留的记号（p.35）
• [补充] p.8 图里签名者是 Bob、验证者是 Alice，和 p.4–7 反过来；只认钥匙不认人名（p.8）
• [补充] p.25 的 160 bit q、512–1024 bit p 是 1994 年原版参数，现行 FIPS 186-5 已改成 2048/224、2048/256、3072/256；答题按课件写（p.25）

课后 10 分钟：考点复习

这 10 分钟怎么用：合上页面，先默写三条——RSA 签名的两个公式、Elgamal 的 r 和 s 各 mod 什么、DSA 验证的四个中间量；再把下面「变式题」的 Elgamal 一题算完；最后回查两处最容易错的地方——负数取模、Elgamal 的 s 到底 mod p 还是 mod (p−1)。三步做完再往下看答案。

必背

1. 签名用发件人私钥、验签用发件人公钥，与加密方向相反；签名提供认证、不可否认、完整性，不提供保密，原文明传。
2. RSA 签名 S = Mᵈ mod n，验证 Sᵉ mod n = M；p = 47、q = 71、e = 1019 时 d = 79，M = 688 签成 1570；实际系统签的是哈希 H(M)。
3. RSA-2048 约等于 112 bit、RSA-3072 约等于 128 bit 对称强度；签名时间与密钥长度的立方成正比，2048 比 1024 慢 8 倍。
4. DLP：给 g、p、b 求 a 使 gᵃ ≡ b (mod p)；mod 7 的生成元只有 3 和 5；以 2 为底模 7 求 4 的离散对数有 2 和 5 两个解，因为 2 的周期只有 3。
5. 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 互素且每次不同。
6. 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 则接受。
7. Chaum 盲签名 m′ = m·kᵉ → s′ = (m′)ᵈ → s = k⁻¹s′ = mᵈ，签名者看不到 m 但结果与普通 RSA 签名相同；裸 RSA 可被存在性伪造：先挑 S 再算 m = Sᵉ，防御是先哈希再签。

完整例题

课件 p.39–44 六道 take-home 覆盖三种签名，下面挑一道 RSA、一道 Elgamal 走完整步骤，DSA 那道（p.44）的答案在变式题参考答案后面一起给。

(1) n = 2021、e = 155，Bob 签 m = 411（p.39 Exercise-3）

1. 题目只给公钥，先分解：试除到 45，2021 = 43 × 47。φ = 42 × 46 = 1932。
2. 求 d = 155⁻¹ mod 1932，扩展欧几里得：1932 = 12 × 155 + 72，155 = 2 × 72 + 11，72 = 6 × 11 + 6，11 = 1 × 6 + 5，6 = 1 × 5 + 1。回代得 1 = 28 × 1932 − 349 × 155，所以 d ≡ −349 ≡ 1583。验算 155 × 1583 = 245365 = 127 × 1932 + 1 ✓。
3. 签名 S = 411¹⁵⁸³ mod 2021 = 402（平方-乘，逐步取模）。
4. 验证 402¹⁵⁵ mod 2021 = 411 ✓。
5. 给分点是分解 n 和五步回代，签名那一步考场上只要求写出平方-乘的形式。

(2) p = 29、g = 2、x = 12、k = 5，签 X = 26 并验证（p.41–42 Exercise-5/6）

1. 公钥 y = 2¹² mod 29：2⁵ = 32 ≡ 3，2¹⁰ ≡ 9，2¹² = 9 × 4 = 36 ≡ 7。发 (29, 2, 7)。
2. gcd(5, 28) = 1 ✓。r = 2⁵ mod 29 = 3。
3. k⁻¹ = 5⁻¹ mod 28 = 17（5 × 17 = 85 = 3 × 28 + 1）。
4. s = 17 × (26 − 12 × 3) = 17 × (−10) = −170 mod 28 = 26（−170 + 196 = 26）。签名 (3, 26)。
5. 验证左边 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。
6. 验证右边 gˣ = 2²⁶ mod 29 = 2²⁰ × 2⁵ × 2 = 23 × 3 × 2 = 138 ≡ 22。相等，有效。

变式题（先自己做）

同样两类，数字换掉：

(1) e = 5、n = 391 = 17 × 23，请求者要签 m = 89，盲化因子 r = 48。求签名者私钥 d、盲化值 m′、盲签名 s′、去盲后的 s，并验证 s 就是 m 的普通 RSA 签名（p.43 Exercise-7）。 (2) p = 47、q = 23、g = 2、私钥 x = 10、k = 7、H(m) = 13。求公钥 y 和 DSA 签名 (r, s)，再算 w、t₁、t₂、v 验证（p.44 Exercise-8）。

提示

第一题算 48⁴ 时 48² ≡ 349，把 349 写成 −42 再平方能少一位数；去盲要的 48⁻¹ mod 391 用扩展欧几里得。第二题先核 2²³ mod 47 = 1 确认 g 的阶是 23；2¹⁰ mod 47 会在算 y 和算 g^t₁ 时各用一次，记下来。

参考答案与自检（非官方评分标准）

自检要点：① 盲签名题每一步先写「谁算、用哪把钥匙、mod 什么」；② d 和 r⁻¹ 都要验算乘积 ≡ 1；③ DSA 题 r 和 v 要写两层括号，s、w、t₁、t₂ 只 mod q。

(1) φ = 16 × 22 = 352，352 = 70 × 5 + 2，5 = 2 × 2 + 1，回代 1 = 141 × 5 − 2 × 352，d = 141。盲化：48² ≡ 349 ≡ −42，48⁴ ≡ 42² = 1764 ≡ 200，48⁵ = 200 × 48 = 9600 ≡ 216；m′ = 89 × 216 = 19224 ≡ 65。签名 s′ = 65¹⁴¹ mod 391 = 56。去盲：48⁻¹ ≡ 334（48 × 334 = 16032 = 41 × 391 + 1），s = 334 × 56 = 18704 ≡ 327。核对 89¹⁴¹ mod 391 = 327，验签 327⁵ mod 391 = 89 ✓。

(2) y = 2¹⁰ mod 47 = 1024 ≡ 37。gᵏ = 2⁷ = 128 ≡ 34，r = 34 mod 23 = 11。k⁻¹ = 7⁻¹ mod 23 = 10（70 = 3 × 23 + 1），s = 10 × (13 + 110) = 1230 mod 23 = 11，签名 (11, 11)。验证：w = 11⁻¹ mod 23 = 21（231 = 10 × 23 + 1），t₁ = 13 × 21 = 273 mod 23 = 20，t₂ = 11 × 21 = 231 mod 23 = 1；2²⁰ mod 47 = 37² = 1369 ≡ 6，6 × 37 = 222 ≡ 34，v = 34 mod 23 = 11 = r ✓。r 和 s 相等是这组小数字的巧合。

闪卡自测

1. 签名和加密的钥匙方向各是什么？签名提供保密吗？

签名用发件人私钥、验用发件人公钥；加密用收件人公钥、解用收件人私钥。签名不提供保密，原文明传（p.5–7）。

2. 签名提供的三个功能是什么？哪一个 MAC 给不了？

认证、不可否认、完整性。不可否认 MAC 给不了，因为共享密钥双方都能造（p.9）。

3. Figure 13.1 里签的是 M 还是 H(M)？为什么？

签的是 h = H(M)。RSA 一次只能处理小于 n 的数，且哈希堵住存在性伪造（p.8、p.40）。

4. p = 47、q = 71、e = 1019：PK、SK 和 M = 688 的签名各是多少？

n = 3337，φ = 3220，d = 79；PK = (1019, 3337)，SK = 79，S = 1570，验证 1570¹⁰¹⁹ mod 3337 = 688（p.11）。

5. RSA-2048 比 RSA-1024 签名慢多少倍？为什么？

8 倍。签名时间与密钥长度的立方成正比，2³ = 8（p.14）。

6. mod 7 的生成元有哪些？以 2 为底求 4 的离散对数为什么特殊？

3 和 5。2 的周期只有 3，2² 和 2⁵ 都 ≡ 4，答案不唯一（p.18–19）。

7. Elgamal 的 r、s 各 mod 什么？验证式怎么推？

r = gᵏ mod p，s = k⁻¹(X − xr) mod (p−1)。X ≡ xr + ks，放到 g 的指数上得 gˣ = yʳrˢ (mod p)（p.22）。

8. DSA 的 (p, q, g) 为什么可以多人共用？g 怎么来的？

它们是公开参数，私密的只有各人的 u；g = h^((p−1)/q) mod p，阶为 q（p.25）。

9. Chaum 盲签名三步各算什么？为什么 k 能剥掉？

m′ = m·kᵉ，s′ = (m′)ᵈ，s = k⁻¹s′。因为 k^(ed) ≡ k，Bob 的 d 次方把 kᵉ 降回 k（p.35）。

10. Eve 挑 S = 1158 后发出的消息是多少？Alice 接受吗？

m = 1158¹⁵⁵ mod 2021 = 1702，Alice 验签相等会接受。这是存在性伪造，先哈希再签可防（p.40）。

下一讲

第 6 周（10-09）讲 ePayment protocol，SET 的双重签名会正式登场：两份消息各哈希、拼接后再哈希、再用这一讲的 RSA 签名签。把 p.8 那张图看熟，SET 的流程图就是三张它拼起来。开课前把 p.23、p.41–42 两道 Elgamal 题和 p.36、p.43 两道盲签名题不看步骤各重做一遍，卡住就回上一讲的扩展欧几里得和平方-乘。