📑 本页目录（点开跳转）
17 · 数字签名
⏱ 30 分钟 ｜ ⭐ 唯一能提供"不可否认"的工具
🎯 一句话
MAC 能证明"消息没被改"，但验证者自己也能伪造。 数字签名用私钥签、公钥验 —— 只有一个人能签，全世界都能验，而且他事后赖不掉。
🖋️ 一、定义与安全目标
Gen() → (pk, sk)
Sign(sk, m) → σ
Verify(pk, m, σ) → 0/1
安全定义：UF-CMA（选择消息攻击下的存在性不可伪造）
攻击者拿到 pk，可以让你签【任意多条】他挑的消息，
仍然无法为【一条没签过的消息】造出合法签名 ⭐
⚠️ 一个更强的要求：SUF-CMA（强不可伪造） 连"为已签过的消息造出另一个不同的合法签名"都不行。 💡 为什么重要：如果签名可延展（malleable）， 区块链上就能改变交易 ID —— 这就是比特币著名的 交易延展性漏洞， Mt. Gox 曾以此为破产理由之一。
| MAC | 数字签名 | |
|---|---|---|
| 密钥 | 对称（双方共享） | 非对称 |
| 谁能验证 | 只有持密钥的人 | 任何人 ⭐ |
| 不可否认 | ❌（验证者也能伪造） | ✅ |
| 速度 | 快（微秒） | 慢（毫秒） |
| 签名长度 | 16–32 字节 | 64–384 字节 |
🔑 二、RSA 签名
❌ 教科书版本
σ = M^d mod n，验证 σ^e ≟ M
💥 三个致命问题：
① 存在性伪造：随便选一个 σ，算 M = σ^e
→ (M, σ) 就是一个合法的"签名对"！攻击者无需私钥 ⭐
② 同态伪造：σ₁·σ₂ 是 M₁·M₂ 的合法签名
③ 只能签比 n 短的消息
✅ 必须先哈希再填充
FDH（全域哈希）：σ = H(M)^d mod n
├─ 哈希破坏了同态性（H(M₁·M₂) ≠ H(M₁)·H(M₂)）✅
├─ 反算的 σ^e 几乎不可能恰好是某个消息的哈希 ✅
└─ 任意长度消息都能签 ✅
PSS（概率签名方案）⭐ 实际标准：
├─ 加入随机盐 → 同一消息每次签名不同
└─ 有更紧的安全归约
💥 PKCS#1 v1.5 签名的 Bleichenbacher'06 攻击： 如果验证实现没有严格检查填充结构（只是"找到 hash 就通过"）， e=3 时攻击者可以伪造签名 —— 影响过 OpenSSL、Firefox、多个 JOSE/JWT 库。
📐 三、DSA / ECDSA 与那个致命的 k
签名（ECDSA）：
① 选随机 k
② r = (kG).x mod n
③ s = k⁻¹(H(m) + r·d) mod n ← d 是私钥
签名 = (r, s)
💀 k 的三条铁律
⭐ ① k 重复 ⟹ 私钥直接泄露
两个签名用了同一个 k：
s₁ = k⁻¹(H₁ + rd)
s₂ = k⁻¹(H₂ + rd)
⟹ s₁ - s₂ = k⁻¹(H₁ - H₂)
⟹ k = (H₁ - H₂)/(s₁ - s₂) ← 解出 k
⟹ d = (s₁k - H₁)/r ← 解出私钥 💀
⭐ ② k 部分可预测 ⟹ 用格约减（LLL）也能恢复私钥
（只要泄露每个 k 的几个 bit，几十个签名就够）
⭐ ③ k 泄露 ⟹ 单个签名就能算出私钥
💥 真实事故： - PlayStation 3（2010）：Sony 把 k 写成固定常数 → 私钥被算出 → 任何人都能签发"官方"固件，主机被彻底越狱 ⭐ - Android 比特币钱包（2013）：
SecureRandom缺陷导致 k 重复 → 私钥被算出，钱被盗 - 多个硬件钱包 / IoT 设备：熵不足导致 k 可预测
✅ 解法：确定性签名
RFC 6979：k = HMAC(私钥, H(消息))
→ 【完全不需要随机数】，同一消息总是产生同一签名 ⭐
→ 熵源坏掉也不会泄露私钥
Ed25519 内建这个设计 ⟹ 这也是推荐它的重要原因
🔑 这是一个漂亮的工程教训： 把"需要好随机数"这个脆弱的依赖，替换成"需要一个好哈希" —— 后者可靠得多。
🎩 四、Schnorr 签名与 Fiat–Shamir
Schnorr 签名结构极其简洁：
公钥 y = g^x
签名：
① 选随机 r，算承诺 t = g^r
② 挑战 c = H(m ‖ t) ⭐ 用哈希代替"验证者发挑战"
③ 响应 s = r + c·x
签名 = (t, s)
验证：g^s ≟ t · y^c
📐 验证为什么成立（想看再点）
$$g^s = g^{r + cx} = g^r \cdot g^{cx} = t \cdot (g^x)^c = t\cdot y^c \quad\checkmark$$
⭐ Fiat–Shamir 转换：一个通用的魔法
原本：一个【交互式】身份认证协议
（证明者发承诺 → 验证者发随机挑战 → 证明者响应）
转换：把"验证者发的随机挑战"替换成 c = H(消息 ‖ 承诺)
→ 变成【非交互式】的签名 ⭐
💡 为什么安全：哈希的输出不可预测，
证明者无法"先知道挑战再准备承诺"
🔑 这个转换是密码学里最有用的工具之一： 任何交互式的零知识证明，都能用它变成一个签名或非交互式证明。 🔗 第 21 章会看到它是 zk-SNARK 的基础。
⚠️ Fiat–Shamir 的经典实现坑： 哈希必须把承诺 t 和消息 m 都包含进去。 只哈希消息（漏掉 t）会导致可伪造 —— 这被称为 "weak Fiat–Shamir"， 2023 年还在多个 zk 库里被发现。
Schnorr 的优势
| 优势 | 说明 |
|---|---|
| 可证明安全 | 在 ROM 下从离散对数归约，比 ECDSA 干净 |
| 线性结构 | ⭐ 支持多签聚合（MuSig）、门限签名 |
| 签名短 | 64 字节 |
💡 比特币 2021 年的 Taproot 升级引入了 Schnorr 签名， 主要动机就是多签可以聚合成一个签名 —— 省空间，还提高隐私。
🔍 五、实践中的选型
| 算法 | 签名长度 | 特点 |
|---|---|---|
| Ed25519 ⭐ | 64 B | 首选。快、确定性、无 k 值风险 |
| ECDSA P-256 | 64 B | 兼容性好，但 k 值风险高 |
| RSA-PSS 3072 | 384 B | 遗留系统兼容 |
| BLS | 48 B | ⭐ 可聚合：一千个签名合成一个（第 16 章配对） |
| ML-DSA | ~2.4 KB | 抗量子（第 23 章） |
from cryptography.hazmat.primitives.asymmetric.ed25519 import Ed25519PrivateKey
sk = Ed25519PrivateKey.generate()
sig = sk.sign(b"message") # ⭐ 64 字节，确定性
sk.public_key().verify(sig, b"message") # 失败抛 InvalidSignature
⚠️ 六、签名之外的三个协议层问题
签名验证通过 ≠ 这条消息可以被接受
① 重放：老签名仍然合法 → 需要序号/时间戳（第 11 章）
② 上下文混淆：A 场景的签名被拿到 B 场景用
✅ 解法：【域分隔】—— 签名前加前缀 "myapp:v1:transfer:" ⭐
③ 密钥复用：同一密钥既签名又加密 → 可能互相打穿
✅ 解法：不同用途用不同密钥
💥 上下文混淆的真实例子：某些钱包用同一个密钥签"登录挑战"和"转账交易"， 攻击者把一个伪装成登录请求的转账交易发给用户签名 → 钱直接没了。 域分隔能完全堵住这类攻击。
🔗 和站内其他章的关系
| 相关的地方 | 和这一章的关系 |
|---|---|
| 第 11 章 MAC | 签名是它的非对称版，多了不可否认 |
| 第 14 章 RSA 同态性 | 教科书签名可伪造的原因 |
| 第 9 章 抗碰撞 | 碰撞 ⟹ 能把签名"搬到"另一条消息上 ⭐ |
| 第 4 章 随机数 | k 值事故的根因 |
| 第 21 章 ZKP | Fiat–Shamir 是共用的桥梁 |
| 第 18 章 PKI | 证书就是 CA 的签名 |
| 模型上线之后 · 合规审计与模型卡 | 那边列的「审计要能回答的五个问题」（决策怎么做的 / 用了哪些数据 / 有没有对某群体不利 / 怎么发现和纠正 / 谁负责）全都默认记录本身是可信的——而「记录有没有被事后改过」它没有回答，数据库时间戳也答不了，只有签名 + 哈希链答得了 ⭐ |
| Claude 资料库 · AI 原生 SDLC 安全 | 供应链信任的地基：签名的镜像、签名的权重、签名的依赖；⚠️ 但签名只保证「这是我发的」，不保证「这是好的」 |
✅ 检查点
- 数字签名和 MAC 的三个关键区别？
- UF-CMA 和 SUF-CMA 的区别？后者为什么重要？
- 教科书 RSA 签名的三个问题？
- FDH 怎么解决其中两个？
- ECDSA 中 k 重复会怎样？写出推导。
- RFC 6979 的做法是什么？它体现了什么工程思想？
- Fiat–Shamir 转换做了什么？它的经典实现坑是什么？
- Schnorr 签名相比 ECDSA 的三个优势？比特币为什么引入它？
- 什么是域分隔？它防的是什么攻击？
👀 答案
- ①MAC 对称、签名非对称 ②MAC 只有持密钥者能验，签名任何人都能验 ③MAC 不提供不可否认（验证者也能伪造），签名提供。
- UF-CMA：无法为没签过的消息造合法签名。SUF-CMA：连"为已签过的消息造出另一个不同的合法签名"都不行。重要是因为签名可延展会改变区块链上的交易 ID——比特币的交易延展性漏洞。
- ①存在性伪造：随便选 σ 算 M=σ^e 就得到合法签名对 ②同态伪造：σ₁·σ₂ 是 M₁·M₂ 的签名 ③只能签比 n 短的消息。
- σ = H(M)^d：哈希破坏同态性（H(M₁M₂)≠H(M₁)H(M₂)），且反算的 σ^e 几乎不可能恰好是某消息的哈希；顺带解决了长度限制。
- s₁ = k⁻¹(H₁+rd)，s₂ = k⁻¹(H₂+rd) ⟹ s₁−s₂ = k⁻¹(H₁−H₂) ⟹ k = (H₁−H₂)/(s₁−s₂) ⟹ d = (s₁k−H₁)/r，私钥直接泄露。
- k = HMAC(私钥, H(消息))——完全不需要随机数，同一消息总产生同一签名。思想：把"需要好随机数"这个脆弱依赖，替换成"需要一个好哈希"。
- 把交互式协议里验证者发的随机挑战替换成 c = H(消息‖承诺)，变成非交互式签名。坑：哈希必须同时包含承诺 t 和消息 m，漏掉 t 就是 "weak Fiat–Shamir"，可伪造——2023 年仍在多个 zk 库中被发现。
- ①可证明安全（ROM 下从 DLP 干净归约）②线性结构支持多签聚合和门限签名 ③签名短。比特币 Taproot 引入它主要为了多签聚合成一个签名——省空间且提高隐私。
- 签名前加上用途前缀（如 "myapp:v1:transfer:"）。防上下文混淆——A 场景的签名被拿到 B 场景用。真实例子：钱包用同一密钥签"登录挑战"和"转账交易"，攻击者把转账伪装成登录请求让用户签。
🛑 可以停在这里
⚡ 走神救援
签名 = 私钥签、公钥验，唯一提供不可否认的工具（MAC 的验证者也持密钥所以能伪造）。UF-CMA：签过任意多条也造不出新消息的签名；SUF-CMA 更强（连给已签消息造另一个签名都不行）——重要是因为签名可延展会改变区块链交易 ID（比特币交易延展性漏洞）。教科书 RSA 签名三宗罪：⭐存在性伪造（随便选 σ 算 M=σ^e 就是合法签名对，不需私钥）、同态伪造 σ₁σ₂、长度受限 → ✅必须先哈希（FDH 破坏同态且反算的 σ^e 几乎不可能是某消息的哈希），实际标准是 PSS。💀⭐ECDSA 的 k 三条铁律：k 重复 ⟹ k=(H₁−H₂)/(s₁−s₂) ⟹ d=(s₁k−H₁)/r，私钥直接泄露；k 部分可预测 ⟹ 格约减(LLL)几十个签名就能恢复；k 泄露 ⟹ 单签名即破。💥PS3 把 k 写成常数被彻底越狱、Android 比特币钱包 k 重复被盗。✅RFC 6979 确定性签名：k=HMAC(私钥, H(消息))，完全不需要随机数（Ed25519 内建）——⭐把"需要好随机数"这个脆弱依赖换成"需要好哈希"。Schnorr：t=g^r，c=H(m‖t)，s=r+cx，验证 g^s ≟ t·y^c；⭐Fiat–Shamir 转换=把验证者的随机挑战换成哈希，任何交互式零知识证明都能变成签名（zk-SNARK 的基础）；⚠️坑：哈希必须同时含承诺 t 和消息 m，漏掉 t = "weak Fiat–Shamir"，2023 年仍在多个 zk 库中被发现。Schnorr 优势：可证明安全、⭐线性结构支持多签聚合（比特币 Taproot 的动机）、签名短。选型：⭐Ed25519 首选（64B、确定性、无 k 风险）、BLS 可聚合（一千个签名合成一个）、ML-DSA 抗量子。⚠️协议层三问题：重放（要序号/时间戳）、⭐上下文混淆（防御是域分隔：签名前加 "myapp:v1:transfer:" 前缀；真实事故是钱包用同一密钥签登录和转账）、密钥复用。
下一节 👉 18-PKI与证书.md