📑 本页目录（点开跳转）
17 · 数字签名
⏱ 30 分钟 ｜ ⭐ 唯一能提供"不可否认"的工具
🎯 一句话
MAC 能证明"消息没被改"，但验证者自己也能伪造。 数字签名用私钥签、公钥验 —— 只有一个人能签，全世界都能验，而且他事后赖不掉。
🖋️ 一、定义与安全目标
信息关系
安全定义：UF-CMA（选择消息攻击下的存在性不可伪造）
对照
攻击者拿到 pk，可以让你签【任意多条】他挑的消息，
仍然无法为【一条没签过的消息】造出合法签名 ⭐
⚠️ 一个更强的要求：SUF-CMA（强不可伪造） 连"为已签过的消息造出另一个不同的合法签名"都不行。 💡 为什么重要：如果签名可延展（malleable）， 区块链上就能改变交易 ID —— 这就是比特币著名的 交易延展性漏洞， Mt. Gox 曾以此为破产理由之一。
| MAC | 数字签名 | |
|---|---|---|
| 密钥 | 对称（双方共享） | 非对称 |
| 谁能验证 | 只有持密钥的人 | 任何人 ⭐ |
| 不可否认 | ❌（验证者也能伪造） | ✅ |
| 速度 | 快（微秒） | 慢（毫秒） |
| 签名长度 | 16–32 字节 | 64–384 字节 |
🔑 二、RSA 签名
❌ 教科书版本
操作步骤
✅ 必须先哈希再填充
关键信息
- 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 可预测
✅ 解法：确定性签名
关键信息
🔑 这是一个漂亮的工程教训： 把"需要好随机数"这个脆弱的依赖，替换成"需要一个好哈希" —— 后者可靠得多。
🎩 四、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 转换：一个通用的魔法
信息关系
🔑 这个转换是密码学里最有用的工具之一： 任何交互式的零知识证明，都能用它变成一个签名或非交互式证明。 🔗 第 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 章 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 的验证者也持密钥，所以他能伪造。
除了「造不出新消息的签名」，还有更强的一档：连给已经签过的消息再造一个不同的签名都不行。⭐ 它重要是因为签名可延展会改变交易 ID——历史上真出过事。
教科书 RSA 签名三宗罪里最刺眼的是 ⭐ 存在性伪造：随便挑一个数反算回去，就得到一对合法的「消息+签名」，全程不需要私钥。 ✅ 所以必须先哈希——它同时破坏了同态性，并让反算出来的东西几乎不可能正好是某条消息的哈希。
💀⭐ ECDSA 那个一次性随机数的三条铁律：重复使用会直接解出私钥；部分可预测时用格约减、几十个签名就能恢复；泄露则单个签名即破。💥 历史上游戏机被越狱、钱包被盗都栽在这里。 ✅ ⭐ 处方是确定性签名：随机数由私钥和消息哈希算出来，完全不需要随机源——把「需要好随机数」这个脆弱依赖换成了「需要好哈希」。
⭐ Schnorr 那条线通向别处：把验证者的随机挑战换成哈希，任何交互式零知识证明都能变成签名。⚠️ 但哈希必须同时包含承诺和消息——漏掉承诺是一个真实存在、且近年仍在库里被发现的漏洞。它的另外两个好处是可证明安全和⭐ 线性结构支持多签聚合。
⚠️ 协议层三个问题里最容易忽略的是 ⭐ 上下文混淆——真实事故是钱包用同一把密钥既签登录又签转账。防御是域分隔：签之前先加一个写明用途的前缀。
下一节 👉 18-PKI与证书.md