数字签名 — RSA/ECDSA/EdDSA/Schnorr 系统对比

日期: 2026-11-15 方向: 密码学 / 经典原语 阶段: Phase 4 - 经典密码学 (Day 195-208) 标签: #密码学 #数字签名 #Schnorr #ECDSA #EdDSA

---

今日目标

---

一、签名方案的安全模型

1.1 安全等级

EUF-CMA (Existential Unforgeability under Chosen Message Attack): 攻击者可对任意消息查询签名 oracle，目标是伪造一个新消息的有效签名。

SUF-CMA (Strong): 即使对已签消息伪造新签名也不允许。

malleability: 给定 $(m, \sigma)$，能否构造 $(m, \sigma')$ 使 $\sigma' \ne \sigma$ 仍验证通过？

• ECDSA: ✗ malleable（$(r, s)$ 和 $(r, -s)$ 都有效）→ Bitcoin BIP-62 强制 low-s
• EdDSA: ✓ 非 malleable
• Schnorr (BIP-340): ✓ 非 malleable

1.2 困难假设

---

二、Schnorr 签名 — 优雅的标杆

2.1 协议（识别版本）

参数: 群 $G$ (order $q$, generator $g$), 哈希 $H$。私钥 $x \in \mathbb{Z}_q$, 公钥 $X = g^x$.

交互式识别（Schnorr ID）:

1. P 选 $r \stackrel{R}{\leftarrow} \mathbb{Z}_q$，发送 $R = g^r$
2. V 发送随机挑战 $c \stackrel{R}{\leftarrow} \mathbb{Z}_q$
3. P 计算 $s = r + c \cdot x \pmod q$，发送
4. V 验证 $g^s \stackrel{?}{=} R \cdot X^c$

Fiat-Shamir 变换: 把 $c$ 替换为 $H(R | X | m)$，变成非交互签名。

2.2 Schnorr 签名

Sign(sk, m):

1. $r = $ 随机或 RFC6979 确定性派生
2. $R = g^r$
3. $c = H(R | X | m)$
4. $s = r + c \cdot x \pmod q$
5. 输出 $\sigma = (R, s)$

Verify(pk, m, σ):

1. $c = H(R | X | m)$
2. 接受当 $g^s = R \cdot X^c$

2.3 BIP-340 (Bitcoin Taproot)

Bitcoin 2021 升级，Schnorr 取代 ECDSA。规范化:

• 32 字节 x-only 公钥（隐式 even-y）
• 64 字节签名 $(R_x, s)$
• 哈希用 BIP-340 tagged hash: $H_{\text{BIP340}/\text{nonce}}, H_{\text{BIP340}/\text{challenge}}, H_{\text{BIP340}/\text{aux}}$
• 强制 low-s 防 malleability
• 用辅助随机 + 私钥 + 消息派生 nonce（非纯确定性，对抗故障注入）

2.4 安全性证明

定理 (Pointcheval-Stern 1996): 在 ROM + 一般群模型下，Schnorr 签名 EUF-CMA-secure，归约到 DLP。

Forking Lemma 关键技巧: 如果攻击者能伪造，倒带 hash oracle 让其用相同 $R$ 但不同 $c$ 再回答一次，得到两个等式 $s_1 = r + c_1 x, s_2 = r + c_2 x$，可解出 $x = (s_1-s_2)/(c_1-c_2)$ → 解 DLP。

2.5 线性性 — Schnorr 的核武器

$$\sigma_1 + \sigma_2 = (R_1 + R_2, s_1 + s_2)$$

只要 hash 用统一 challenge 即可聚合多签。这是 MuSig / FROST 的基础。ECDSA 没有这种线性性，所以 Bitcoin 引入 Schnorr 才能搞 Taproot 多签。

---

三、ECDSA — 标准但有陷阱

3.1 协议

公钥 $Q = d \cdot G$.

Sign(d, m):

1. $z = $ truncated $H(m)$
2. $k \stackrel{R}{\leftarrow} \mathbb{Z}_q$
3. $(x, y) = k \cdot G$, $r = x \mod q$. 若 $r = 0$ 重选
4. $s = k^{-1}(z + rd) \mod q$. 若 $s = 0$ 重选
5. $\sigma = (r, s)$

Verify(Q, m, σ):

1. $z = $ truncated $H(m)$
2. $u_1 = z s^{-1}, u_2 = r s^{-1}$
3. $(x, y) = u_1 G + u_2 Q$
4. 接受当 $r \equiv x \pmod q$

3.2 ECDSA 的设计缺陷

• Nonce 重用 = 私钥泄漏（明日详讲 Sony PS3）
• Malleability: $(r, s)$ 和 $(r, q-s)$ 都有效 → BIP-62 强制 low-s
• 不易聚合: 不像 Schnorr 线性
• 复杂验证: 需 $s^{-1}$ 计算
• 签名时无 message commitment: $r$ 只来自 $kG$，不绑定消息（弱抗故障注入）

3.3 为什么 ECDSA 仍流行

• 标准化早（1992 NIST）
• TLS / SSH / Bitcoin / Ethereum / 所有主流 CA 默认
• 切换成本巨大

---

四、EdDSA / Ed25519

4.1 设计目标 (Bernstein et al. 2011)

• 完全确定性（$k = H(\text{prefix} | m)$）
• 抗侧信道（无分支、无 secret-dependent 内存访问）
• 高速（curve25519 比 NIST P-256 快 3-5×）
• 简单实现（防呆）

4.2 Ed25519 协议

私钥 $sk$ (32 字节)，扩展 $H(sk) = h_0 | h_1$（各 32 字节）。

• 签名密钥 $a = $ clamp($h_0$) 转 scalar
• 公钥 $A = a B$ (B = base point)

Sign(sk, m):

1. $r = H(h_1 | m) \mod \ell$（确定性）
2. $R = r B$
3. $c = H(R | A | m) \mod \ell$
4. $s = r + c a \mod \ell$
5. $\sigma = (R, s)$

Verify(A, m, σ):

1. $c = H(R | A | m) \mod \ell$
2. 检查 $sB = R + cA$

4.3 Ed25519 vs Schnorr 区别

实质相同（都基于离散对数 + Fiat-Shamir），区别是：

• Ed25519 用 Edwards 曲线（性能 + 完全公式）
• Ed25519 强制确定性 nonce
• Ed25519 hash 用 SHA-512
• 签名编码格式标准化

4.4 cofactor 陷阱

Curve25519 cofactor = 8。验证若不严格检查 (e.g., RFC 8032 vs ZIP-215 不同)，可能存在多个有效 R 值。Zcash / Tendermint 用 ZIP-215 严格批量验证规则。

---

五、RSA-PSS

5.1 PKCS#1 v1.5 的死穴

旧 RSA 签名: $\sigma = m^d \mod n$，简单但已知多种攻击（Bleichenbacher 1998 padding oracle）。

5.2 PSS (Probabilistic Signature Scheme)

由 Bellare-Rogaway 1996 提出。

Sign(d, m):

1. $\text{salt} \stackrel{R}{\leftarrow} {0,1}^{\text{slen}}$
2. $H = \text{Hash}(0^{64} | m | \text{salt})$
3. $\text{DB} = \text{PS} | 0x01 | \text{salt}$ ($PS = $ zeros)
4. $\text{maskedDB} = \text{DB} \oplus \text{MGF1}(H)$
5. $\text{EM} = \text{maskedDB} | H | 0xbc$
6. $\sigma = \text{EM}^d \mod n$

为什么 PSS 安全: ROM 下严格归约到 RSA 问题 (Coron 2002)。

5.3 RSA 在 Web3 的现状

几乎不用。原因:

• 公钥太大（2048-4096 bit）→ on-chain 存储贵
• 签名验证慢（重 bigint 模幂）
• 无线性聚合
• ECDSA/Schnorr/BLS 全面更优

仅在 PKI / TLS 证书 / Web2 集成场景出现。

---

六、代码实现 — schnorr.py

"""
schnorr.py - secp256k1 上的 Schnorr 签名 (BIP-340 兼容)
"""
from __future__ import annotations
import hashlib
import os
from dataclasses import dataclass

# secp256k1 参数
P = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
GX = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
GY = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

# --------------------------- 椭圆曲线运算 ---------------------------

def inv(x: int, m: int = P) -> int:
    return pow(x, -1, m)

def point_add(P1, P2):
    if P1 is None: return P2
    if P2 is None: return P1
    x1, y1 = P1
    x2, y2 = P2
    if x1 == x2:
        if (y1 + y2) % P == 0:
            return None
        # double
        m = (3 * x1 * x1) * inv(2 * y1, P) % P
    else:
        m = (y2 - y1) * inv(x2 - x1, P) % P
    x3 = (m * m - x1 - x2) % P
    y3 = (m * (x1 - x3) - y1) % P
    return (x3, y3)

def scalar_mul(k: int, point) -> tuple:
    """double-and-add"""
    result = None
    addend = point
    while k:
        if k & 1:
            result = point_add(result, addend)
        addend = point_add(addend, addend)
        k >>= 1
    return result

G = (GX, GY)

def has_even_y(P_pt) -> bool:
    return P_pt[1] % 2 == 0

# --------------------------- BIP-340 tagged hash ---------------------------

def tagged_hash(tag: str, msg: bytes) -> bytes:
    th = hashlib.sha256(tag.encode()).digest()
    return hashlib.sha256(th + th + msg).digest()

# --------------------------- 编码 ---------------------------

def x_only(P_pt) -> bytes:
    return P_pt[0].to_bytes(32, 'big')

def lift_x(x: int):
    """Reverse of x_only: return point with even y."""
    y_sq = (pow(x, 3, P) + 7) % P
    y = pow(y_sq, (P + 1) // 4, P)
    if pow(y, 2, P) != y_sq:
        return None
    if y % 2 != 0:
        y = P - y
    return (x, y)

# --------------------------- Schnorr Sign / Verify ---------------------------

@dataclass
class Schnorr:
    @staticmethod
    def keygen(seed: bytes = None) -> tuple[int, bytes]:
        d = int.from_bytes(seed or os.urandom(32), 'big') % N
        if d == 0:
            d = 1
        P_pt = scalar_mul(d, G)
        # BIP-340: if y is odd, negate d
        if not has_even_y(P_pt):
            d = N - d
            P_pt = (P_pt[0], P - P_pt[1])
        return d, x_only(P_pt)

    @staticmethod
    def sign(sk: int, msg: bytes, aux_rand: bytes = b'\x00' * 32) -> bytes:
        # BIP-340 deterministic+aux nonce
        P_pt = scalar_mul(sk, G)
        if not has_even_y(P_pt):
            sk = N - sk
            P_pt = (P_pt[0], P - P_pt[1])
        pk_x = x_only(P_pt)

        t = bytes(a ^ b for a, b in zip(
            sk.to_bytes(32, 'big'),
            tagged_hash("BIP0340/aux", aux_rand)
        ))
        rand = tagged_hash("BIP0340/nonce", t + pk_x + msg)
        k0 = int.from_bytes(rand, 'big') % N
        if k0 == 0:
            raise RuntimeError("nonce zero, retry")
        R = scalar_mul(k0, G)
        if not has_even_y(R):
            k = N - k0
        else:
            k = k0
        Rx = x_only(R)
        e = int.from_bytes(tagged_hash("BIP0340/challenge", Rx + pk_x + msg), 'big') % N
        s = (k + e * sk) % N
        return Rx + s.to_bytes(32, 'big')

    @staticmethod
    def verify(pk_x: bytes, msg: bytes, sig: bytes) -> bool:
        if len(sig) != 64 or len(pk_x) != 32:
            return False
        P_pt = lift_x(int.from_bytes(pk_x, 'big'))
        if P_pt is None:
            return False
        rx = int.from_bytes(sig[:32], 'big')
        s = int.from_bytes(sig[32:], 'big')
        if rx >= P or s >= N:
            return False
        e = int.from_bytes(tagged_hash("BIP0340/challenge", sig[:32] + pk_x + msg), 'big') % N
        # R = sG - eP
        sG = scalar_mul(s, G)
        eP = scalar_mul(e, P_pt)
        R = point_add(sG, (eP[0], P - eP[1]))
        if R is None:
            return False
        if not has_even_y(R):
            return False
        return R[0] == rx

    @staticmethod
    def batch_verify(items: list[tuple[bytes, bytes, bytes]]) -> bool:
        """
        Batch verify n signatures using random linear combination.
        50-70% faster than n single verifies.
        Items: list of (pk_x, msg, sig)
        """
        # sum_i a_i (s_i G - e_i P_i - R_i) = 0
        sum_s = 0
        # accumulator for points
        acc = None
        for i, (pk_x, msg, sig) in enumerate(items):
            P_pt = lift_x(int.from_bytes(pk_x, 'big'))
            if P_pt is None:
                return False
            R = lift_x(int.from_bytes(sig[:32], 'big'))
            if R is None:
                return False
            s = int.from_bytes(sig[32:], 'big')
            e = int.from_bytes(tagged_hash("BIP0340/challenge", sig[:32] + pk_x + msg), 'big') % N
            a = 1 if i == 0 else int.from_bytes(os.urandom(16), 'big')
            sum_s = (sum_s + a * s) % N
            acc = point_add(acc, scalar_mul(a, R))
            acc = point_add(acc, scalar_mul(a * e % N, P_pt))
        # check sum_s * G == acc
        lhs = scalar_mul(sum_s, G)
        if lhs is None and acc is None:
            return True
        if lhs is None or acc is None:
            return False
        return lhs == acc

# --------------------------- 自检 ---------------------------

if __name__ == "__main__":
    sk, pk = Schnorr.keygen(b'\x01' * 32)
    msg = b'hello schnorr' + b'\x00' * 19  # 32 bytes
    msg = hashlib.sha256(b'hello schnorr').digest()
    sig = Schnorr.sign(sk, msg)
    assert Schnorr.verify(pk, msg, sig)
    print(f"Schnorr sign/verify: PASS (sig={sig.hex()})")

    # Batch verify 10 sigs
    items = []
    for _ in range(10):
        s, p = Schnorr.keygen()
        m = os.urandom(32)
        items.append((p, m, Schnorr.sign(s, m)))
    assert Schnorr.batch_verify(items)
    print(f"Schnorr batch verify (10 sigs): PASS")

    # malleability check: flipping s should invalidate
    bad_sig = sig[:32] + ((N - int.from_bytes(sig[32:], 'big')) % N).to_bytes(32, 'big')
    assert not Schnorr.verify(pk, msg, bad_sig)
    print("Malleability resistance: PASS")

---

七、真实漏洞 / 事件

---

八、协议应用 — Web3 中的签名

为什么以太坊不立即换 Schnorr: 已部署 EOA 用 ECDSA，硬切需所有私钥迁移。EIP-7702 + ERC-4337 提供 AA 路径，可让 smart account 用任意签名（Schnorr / EdDSA / WebAuthn）。

---

九、常见陷阱

1. ECDSA nonce 重用 = 私钥泄漏（永远确定性 RFC6979 + 防故障 aux）
2. Signature malleability: 处理 ECDSA 时强制 low-s（Bitcoin BIP-62, Ethereum EIP-2）
3. Hash-to-scalar 错误: 用整 hash 不模 $q$ 截断 → 偏置攻击
4. Verifying without canonical encoding: Ed25519 R 编码可有多个有效，ZIP-215 强制
5. Mixing ECDSA recovery (recover_id) without msg: ecrecover 漏洞 (Solidity ecrecover return 0 not revert)
6. Cross-protocol replay: 同 hash 在不同链有效（EIP-155 chain ID 域分离）
7. Schnorr nonce 复用 同样致命（虽然非交互单签场景少，但 MuSig 中至关重要）
8. Public key 验证不足: 不在子群内的 public key → small subgroup attack

---

十、关键速查

主流签名对比

Schnorr 性能 (secp256k1)

---

十一、面试题

Q1: 为什么 Bitcoin Taproot 选 Schnorr 而非 EdDSA？ A: (1) 兼容现有 secp256k1（不改基础 EC，只换签名层）；(2) Schnorr 数学相同性能但更易做 MuSig 聚合；(3) Ed25519 用 curve25519 + cofactor 8，与 BTC 现有栈无关；(4) BIP-340 引入 tagged hash 域分离，比 Ed25519 hash 派生 nonce 更灵活。

Q2: Schnorr 比 ECDSA 在多签上好在哪？ A: 线性性！Schnorr $\sigma = (R, s)$ 中 $R = \sum R_i, s = \sum s_i$，$n$ 人签名仍 64 字节。ECDSA 因为 $s = k^{-1}(z + rd)$ 的 $k^{-1}$ 破坏线性，多签需要交互式协议或 ZK，复杂度高。MuSig2 / FROST 都基于 Schnorr 线性性。

Q3: ECDSA ecrecover 在 Solidity 中的安全坑？ A: (1) 失败时返回 zero address（不是 revert）→ 必须检查返回值；(2) 不验证 s 是否 low-s → malleability；(3) v 取值 27/28（pre-EIP-155）vs chain_id*2 + 35/36（post）→ 跨链重放风险；(4) 签名消息缺 EIP-191 prefix → 签名可被泛用。OpenZeppelin ECDSA library 处理这些。

Q4: 为什么 Ed25519 强制确定性 nonce 而 Schnorr 不强制？ A: Ed25519 (Bernstein) 哲学是"无 RNG 故障可能"，nonce = $H(\text{prefix} | m)$ 完全由密钥+消息决定，无需熵源。BIP-340 折中:确定性 + 可选 aux_rand，因为纯确定性在故障注入下危险（同 nonce 被强制重放可推 key），加 aux_rand 提供故障防御。

Q5: 后量子时代签名怎么选？ A: NIST 选 Dilithium（主推）+ FALCON（短签名）+ SPHINCS+（保守）。Web3 短期内不切换（PQ 签名都比 ECDSA 大 30-200×，区块链空间昂贵）。中期方案: hash-based hybrid（XMSS/LMS）或 STARK-friendly 签名 (Picnic)。Ethereum 路线图含 ZK-friendly hash 签名 (Winternitz over Poseidon)。

---

十二、明日预告

Day 199: ECDSA 陷阱 — 深入剖析 Sony PS3 案例（同一 nonce 签名 → 私钥彻底泄漏的数学推导）、Curl 漏洞、Bitcoin 弱 nonce 历史事件，并完整复现 nonce 重用攻击代码。