Schnorr 签名算法原理：数学基础、协议设计与门限签名

概述

Schnorr 签名算法是由德国数学家 Claus Schnorr 于 1989 年提出的一种基于离散对数问题的数字签名方案。与 ECDSA（椭圆曲线数字签名算法）相比，Schnorr 签名具有线性可加性（Linearity），这一特性使其天然支持密钥聚合（Key Aggregation）和批量验证（Batch Verification），在区块链、隐私通信和高安全场景中有广泛应用。

Schnorr vs ECDSA 概览

数学基础：离散对数问题

群论基础

Schnorr 签名基于有限循环群上的离散对数困难问题。设 $G$ 是一个阶为素数 $q$ 的循环群，生成元为 $g$，群运算为乘法记法（也可使用椭圆曲线上的加法记法）。

离散对数问题（Discrete Logarithm Problem, DLP）： 给定 $G$ 的生成元 $g$ 和群元素 $h \in G$，找到整数 $x \in \mathbb{Z}_q$ 使得：

$$h = g^x$$

在适当选择的群上，已知最佳算法的计算复杂度为亚指数级别（如数域筛法），因此当群的阶足够大时（如 256 位），DLP 被认为是计算困难的。

椭圆曲线上的 Schnorr

在实际部署中（如比特币的 BIP-340 taproot 升级），Schnorr 签名使用椭圆曲线群。设椭圆曲线 $E$ 定义在有限域 $\mathbb{F}_p$ 上，基点 $G$ 的阶为 $n$（素数），私钥为 $d \in [1, n-1]$，公钥为：

$$Q = d \cdot G$$

Schnorr 签名协议

密钥生成

输入：安全参数 λ（群的阶 n）
输出：(privkey, pubkey)

1. 随机选择私钥 d ∈ [1, n-1]
2. 计算公钥 Q = d · G
3. 返回 (d, Q)

签名生成

对消息 $m \in \{0,1\}^*$ 进行签名：

输入：私钥 d，消息 m
输出：签名 (R, s)

1. 随机选择 nonce k ∈ [1, n-1]
2. 计算 R = k · G（R 为椭圆曲线上的点）
3. 计算 e = H(R || Q || m)（哈希挑战值）
4. 计算 s = k + e · d (mod n)
5. 返回签名 σ = (R, s)

其中 $H$ 是一个密码学哈希函数，在 BIP-340 中定义为 SHA256(SHA256(tag) || SHA256(tag) || R || Q || m)，使用 BIP0340/challenge 作为 tag 域分离。

签名验证

输入：公钥 Q，消息 m，签名 (R, s)
输出：有效/无效

1. 验证 R 是有效的椭圆曲线点（非无穷远点）
2. 验证 s ∈ [1, n-1]
3. 计算 e = H(R || Q || m)
4. 验证 s · G = R + e · Q
5. 若等式成立则接受，否则拒绝

正确性证明

验证等式成立当且仅当签名是有效的：

$$s \cdot G = (k + e \cdot d) \cdot G = k \cdot G + e \cdot d \cdot G = R + e \cdot Q$$

这说明诚实的签名者生成的签名总是能通过验证。

安全性分析

安全模型

Schnorr 签名的安全性在随机预言模型（Random Oracle Model, ROM）下被证明是安全的。

安全定理（简化版）： 在 ROM 下，如果离散对数问题是困难的，则 Schnorr 签名在适应性选择消息攻击下是不可伪造的（EUF-CMA 安全）。

安全性证明思路

Schnorr 签名的安全性证明使用分叉引理（Forking Lemma）。证明的核心思想是：

• 假设存在一个伪造者 $\mathcal{A}$ 能够在适应性选择消息攻击下伪造 Schnorr 签名
• 模拟器 $\mathcal{S}$ 通过控制哈希查询的响应来"编程"挑战
• 通过分叉技术，从两个不同的伪造中提取相同的承诺 $R$ 但不同的挑战 $e_1 \neq e_2$
• 从这两个签名方程中求解离散对数：

• 这解决了离散对数问题，与假设矛盾

Nonce 重用攻击

Schnorr 签名的一个关键安全注意事项是 nonce 绝对不能重用。如果同一个 nonce $k$ 被用于签署两个不同的消息 $m_1$ 和 $m_2$：

$$s_1 = k + e_1 \cdot d$$ $$s_2 = k + e_2 \cdot d$$

攻击者可以计算： $$d = (s_1 - s_2) \cdot (e_1 - e_2)^{-1} \pmod{n}$$

直接恢复私钥！这与 ECDSA 的 nonce 重用攻击原理相同。

解决方案：使用确定性 nonce（RFC 6979 风格），通过私钥和消息的哈希值派生 nonce：

$$k = H(d || m)$$

BIP-340 进一步改进了 nonce 派生方式，引入额外的随机性和公钥信息：

$$k' = H(\text{privkey} || \text{aux} || \text{msg})$$ $$k = k' \bmod n$$

线性可加性与密钥聚合

Schnorr 签名最强大的特性是其线性可加性，这使得密钥聚合和批量验证成为可能。

密钥聚合（Key Aggregation）

给定两个签名者 $(d_1, Q_1)$ 和 $(d_2, Q_2)$，可以聚合为一个公钥：

$$Q_{agg} = Q_1 + Q_2 = d_1 \cdot G + d_2 \cdot G = (d_1 + d_2) \cdot G$$

聚合后的有效私钥为 $d_{agg} = d_1 + d_2 \pmod{n}$。

MuSig 协议（Multi-Signature）利用这一特性实现多签：

• 各参与方公布自己的公钥 $Q_i$
• 计算聚合公钥 $Q_{agg} = \sum Q_i$（实际实现中需要对公钥进行系数化处理以防止 rogue-key 攻击）
• 每个参与方使用自己的私钥份额 $d_i$ 生成部分签名
• 聚合部分签名得到完整签名

签名聚合

两个 Schnorr 签名可以线性聚合：

$$\sigma_1 = (R_1, s_1) \text{ on } m_1$$ $$\sigma_2 = (R_2, s_2) \text{ on } m_2$$

聚合签名： $$R_{agg} = R_1 + R_2$$ $$s_{agg} = s_1 + s_2 \pmod{n}$$

批量验证

批量验证可以同时验证多个签名，减少椭圆曲线点乘运算：

对于 $n$ 个签名 $(R_i, s_i)$ 对应消息 $m_i$ 和公钥 $Q_i$：

传统验证：$n$ 次点乘 + $n$ 次点加 = $2n$ 次椭圆曲线运算

批量验证：

• 随机选择系数 $c_i \in \mathbb{Z}_n$（防止流氓密钥攻击）
• 计算 $e_i = H(R_i || Q_i || m_i)$
• 验证：$\sum s_i \cdot G = \sum R_i + \sum e_i \cdot c_i \cdot Q_i$

门限 Schnorr 签名

门限签名（Threshold Signature）要求 $t$ 个签名者中至少 $t$ 个（$t \leq n$）参与才能生成有效签名。Schnorr 签名的线性性质使其天然适配门限签名方案。

基础门限方案

Shamir 秘密共享 + Schnorr：

• 密钥分发：使用 $(t, n)$-Shamir 秘密共享将私钥 $d$ 分成 $n$ 个份额 $d_i$
• 分布式签名：

• 验证：使用标准 Schnorr 验证 $s \cdot G = R + e \cdot Q$

安全性考虑

门限 Schnorr 签名的安全性面临以下挑战：

• 恶意参与方：恶意参与方可能在签名过程中发送错误的份额，导致签名失败或泄露信息
• 可验证秘密共享（VSS）：需要使用 VSS 确保每个参与方收到的份额与承诺一致
• 确定性 nonce：每个参与方需要使用确定性 nonce 派生，防止 nonce 重用攻击
• 密钥更新：定期更新密钥份额以应对长期密钥泄露风险

实际应用

1. 比特币 Taproot（BIP-340）

2021 年比特币 Taproot 升级引入了 Schnorr 签名（BIP-340），带来了：

• 更小的交易体积：Schnorr 签名固定 64 字节，比 ECDSA 的 71-72 字节更紧凑
• 原生多签：通过密钥聚合，多签交易与普通单签交易在链上不可区分
• 隐私增强：多重签名方案的链上足迹与单签相同
• 批量验证：节点可以批量验证区块中的签名，提升验证效率

2. 门限签名钱包

基于 Schnorr 门限签名的加密货币钱包可以实现：

• 私钥永不以完整形式存在于单一位置
• 支持灵活的 $t$-of-$n$ 安全策略
• 链上表现为普通单签名地址

3. 零知识证明辅助

Schnorr 签名的线性性质使其在零知识证明系统中也有应用，如：

• 证明知道某个 Schnorr 签名而不泄露签名内容
• 构建高效的签名证明系统

算法伪代码

完整签名流程（BIP-340 风格）

# BIP-340 Schnorr 签名（secp256k1 曲线）
import hashlib
import secrets

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

def hash_tag(tag: bytes, data: bytes) -> int:
    """Tagged hash as defined in BIP-340"""
    h = hashlib.sha256(tag + data).digest()
    return int.from_bytes(h, 'big')

def lift_x(x: int):
    """从 x 坐标恢复椭圆曲线点"""
    c = (x**3 + 7) % p
    y = pow(c, (p + 1) // 4, p)
    if y % 2 != 0:
        y = p - y
    return (x, y)

def point_add(P, Q):
    """椭圆曲线点加法"""
    if P is None: return Q
    if Q is None: return P
    x1, y1 = P
    x2, y2 = Q
    if x1 == x2 and y1 != y2:
        return None  # 无穷远点
    if x1 == x2:  # 倍点
        m = (3 * x1 * x1) * pow(2 * y1, p - 2, p) % p
    else:
        m = (y2 - y1) * pow(x2 - x1, p - 2, p) % p
    x3 = (m * m - x1 - x2) % p
    y3 = (m * (x1 - x3) - y1) % p
    return (x3, y3)

def point_mul(k, P):
    """标量乘法（double-and-add）"""
    R = None
    while k > 0:
        if k & 1:
            R = point_add(R, P)
        P = point_add(P, P)
        k >>= 1
    return R

def sign_bip340(privkey: int, msg: bytes, aux: bytes = b'') -> tuple:
    """BIP-340 Schnorr 签名"""
    assert 0 < privkey < n
    px, py = point_mul(privkey, G)  # 公钥
    d = privkey if py % 2 == 0 else n - privkey  # 偶数 y 约定
    
    # 确定性 nonce 派生
    t = (d ^ int.from_bytes(hash_tag(b"BIP0340/aux", aux), 'big')).to_bytes(32, 'big')
    t += px.to_bytes(32, 'big') + msg
    k_prime = int.from_bytes(hash_tag(b"BIP0340/nonce", t), 'big') % n
    assert k_prime != 0
    
    rx, ry = point_mul(k_prime, G)
    k = k_prime if ry % 2 == 0 else n - k_prime
    
    # 挑战
    e_data = rx.to_bytes(32, 'big') + px.to_bytes(32, 'big') + msg
    e = int.from_bytes(hash_tag(b"BIP0340/challenge", e_data), 'big') % n
    
    s = (k + e * d) % n
    return (rx, s)  # 签名 (r, s)

def verify_bip340(pubkey_x: int, msg: bytes, sig: tuple) -> bool:
    """BIP-340 Schnorr 验证"""
    r, s = sig
    if s >= n or r >= p:
        return False
    P = lift_x(pubkey_x)
    if P is None:
        return False
    px, py = P
    
    e_data = r.to_bytes(32, 'big') + px.to_bytes(32, 'big') + msg
    e = int.from_bytes(hash_tag(b"BIP0340/challenge", e_data), 'big') % n
    
    # 验证 s*G = R + e*P
    R = lift_x(r)
    lhs = point_mul(s, G)
    rhs = point_add(R, point_mul(e, P))
    return lhs == rhs

总结

Schnorr 签名算法凭借其优雅的设计和强大的线性性质，已经成为现代密码学中不可或缺的数字签名方案。其核心优势包括：

• 可证明安全性：在 ROM 下有严格的安全性证明
• 线性可加性：天然支持密钥聚合和批量验证
• 确定性 nonce：通过 RFC 6979 / BIP-340 的确定性派生，消除随机数生成器故障风险
• 更小的签名体积：固定 64 字节，适合区块链等存储敏感场景

参考来源

• Claus Schnorr, "Efficient Identification and Signatures for Smart Cards", CRYPTO 1989
• BIP 340: Schnorr Signatures for secp256k1
• MuSig2: Simple Two-Round Schnorr Multi-Signatures
• RFC 6979: Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)
• BIP 341: Taproot: SegWit version 1 spending rules
• GB/T 32918.2-2016 SM2 第2部分：数字签名算法

相关实践

• 如需了解 SM2 数字签名算法的国家标准实现，请参阅《SM2 椭圆曲线公钥密码算法》
• 如需了解 SM4 在区块链中的应用，请参阅《国密 SM4 数据库字段级加密实战》
• 如需了解数字签名方案的性能对比，请参阅《数字签名方案深度对比：SM2 vs ECDSA vs EdDSA》