第 4 章：Schnorr 签名

学习定位：前置为第 2 章；配套完成实验 3：普通 Schnorr。本章只建立单方签名和线性直觉，真实门限实现留到实验 4。

Schnorr 签名只有一条核心验证等式，却把公钥密码学中最重要的几个思想连在一起：离散对数、随机 nonce、承诺—挑战—响应和 Fiat–Shamir 变换。它的线性结构也使其非常适合构造门限签名。

这份简洁既是优点，也是危险：nonce 只要重用一次，就可能直接泄露私钥。

学习目标

完成本章后，你应该能够：

从密钥生成到验证完整描述 Schnorr 签名；
推导验证等式为何成立；
解释挑战值为何必须绑定承诺、公钥、消息和协议上下文；
从两个重用 nonce 的签名中推导私钥恢复公式；
区分标量与群元素，以及它们各自的运算；
说明普通 Schnorr 如何线性扩展到门限 Schnorr，以及为什么不能停在朴素方案。

4.1 参数和符号

选择一个阶为素数 \(q\) 的循环群 \(\mathbb G\)，生成元为 \(G\)。采用加法记号。

符号	含义	类型
\(x\)	私钥	\(\mathbb Z_q\) 中的非零标量
\(X=xG\)	公钥	群元素
\(r\)	单次签名 nonce	\(\mathbb Z_q^*\) 中的非零秘密标量
\(R=rG\)	nonce 承诺	群元素
\(c\)	Fiat–Shamir 挑战	\(\mathbb Z_q\) 中的标量
\(z\)	签名响应	\(\mathbb Z_q\) 中的标量
\(m\)	消息	字节串

本章采用签名 \(\sigma=(R,z)\) 和验证式 \(zG=R+cX\) 的记号。有些标准使用不同符号、符号方向或编码约定；公式相似不代表字节级兼容。

4.2 从身份识别协议获得直觉

先不讨论签名。设证明者知道 \(x\)，验证者只知道 \(X=xG\)。证明者希望说明“我知道这个公钥对应的私钥”，但不公开 \(x\)。

一个三步交互协议如下：

承诺：证明者随机选择 \(r\leftarrow\mathbb Z_q^*\)，发送

\[ R=rG \]
挑战：验证者随机发送 \(c\leftarrow\mathbb Z_q\)。
响应：证明者发送

\[ z=r+cx\pmod q \]

验证者检查：

\[ zG\stackrel?=R+cX \]

为什么成立？把诚实响应代入左侧：

\[ \begin{aligned} zG &=(r+cx)G\\ &=rG+c(xG)\\ &=R+cX \end{aligned} \]

整个推导中，\(r,c,x,z\) 都在 \(\mathbb Z_q\) 中，\(R,X,G\) 都在 \(\mathbb G\) 中。

4.3 Fiat–Shamir：把交互挑战变成哈希

数字签名不能要求每次都有在线验证者来随机出题。因此用哈希函数从当前签名上下文确定挑战：

\[ c=H_{\mathrm{scalar}}( \text{domain}\parallel \operatorname{enc}(R)\parallel \operatorname{enc}(X)\parallel \operatorname{enc}(m) ) \]

这一步称为 Fiat–Shamir 变换。哈希输出需要通过协议规定的方法映射到 \(\mathbb Z_q\)。

挑战中每个部分都有作用：

\(R\)：绑定本次 nonce 承诺；
\(X\)：绑定签名所对应的公钥；
\(m\)：绑定消息；
domain：绑定协议、套件、版本和用途，避免跨协议混淆；
规范编码：确保不同实现哈希完全相同的字节。

若遗漏消息，签名就不能证明签署了哪条消息。若协议要求绑定公钥却遗漏它，某些密钥替换或多用户场景中的安全论证会改变。实现不应自行删减规范定义的 transcript 字段。

4.4 Schnorr 的三个算法

密钥生成

均匀选择非零标量：

\[ x\leftarrow\mathbb Z_q^* \]

计算公钥：

\[ X=xG \]

私钥是标量，公钥是群元素。私钥绝不能按曲线基域模数 \(p\) 约简。

签名

对消息 \(m\)：

安全地产生一次性非零秘密 nonce \(r\in\mathbb Z_q^*\)；
计算 \(R=rG\)；
计算

\[ c=H_{\mathrm{scalar}}( \text{domain}\parallel\operatorname{enc}(R) \parallel\operatorname{enc}(X)\parallel m) \]
计算

\[ z=r+cx\pmod q \]
输出 \(\sigma=(R,z)\)。

验证

收到 \((X,m,\sigma)\) 后：

严格解析并验证 \(X\)、\(R\)、\(z\) 的规范编码；
按完全相同的 transcript 重新计算 \(c\)；
接受当且仅当：

\[ zG=R+cX \]

验证器还需遵守具体协议对单位元、小阶点、子群和无效编码的规则。使用 Ristretto 一类素数阶群抽象能减少陷阱，但不能取消输入验证。

对本手册采用的 Schnorr/FROST 套件，公钥和 nonce 承诺都不得是群单位元 \(\mathcal O\)。若签名者使用 \(r=0\)，则 \(R=\mathcal O\)、\(z=cx\)；公开签名在 \(c\ne0\) 时会直接给出 \(x=z/c\)。因此生成端必须避免零 nonce，解析和验证端也必须在计算 challenge 前拒绝单位元。

4.5 一个可手算的玩具例子

假设有一个阶为 \(q=19\) 的抽象循环群。选择私钥：

\[ x=7,\qquad X=7G \]

本次 nonce 为：

\[ r=4,\qquad R=4G \]

假设哈希 transcript 后得到挑战 \(c=5\)。签名响应是：

\[ z=r+cx=4+5\cdot7=39\equiv1\pmod {19} \]

验证左侧：

\[ zG=1G \]

验证右侧：

\[ R+cX=4G+5(7G)=39G=1G \]

两边相等。

这里的 \(c=5\) 是为手算人为指定的。真实签名绝不能由调用者随意选择挑战，必须由规范定义的哈希 transcript 得出。

4.6 安全直觉：为何不能伪造

若攻击者先决定响应 \(z\) 和挑战 \(c\)，可以代数地令：

\[ R=zG-cX \]

这样验证等式确实成立。但在非交互签名中，挑战必须同时满足：

\[ c=H_{\mathrm{scalar}}(R,X,m,\ldots) \]

攻击者改变 \(R\) 就会改变哈希挑战，因而不能自由地同时控制二者。

严格安全性需要明确的群假设、哈希模型和签名变体；“看起来形成循环依赖”不是形式化证明。对学习者而言，关键直觉是：哈希把承诺、密钥和消息不可预测地绑定在一起，而离散对数困难性阻止攻击者从公钥得到私钥。

4.7 致命问题：nonce 重用直接泄露私钥

假设同一个私钥 \(x\) 使用同一个 nonce \(r\) 签了两条产生不同挑战的消息：

\[ z_1=r+c_1x\pmod q \]

\[ z_2=r+c_2x\pmod q \]

两式相减，nonce 被消去：

\[ z_1-z_2=(c_1-c_2)x\pmod q \]

只要 \(c_1\ne c_2\)，就能恢复：

\[ x=(z_1-z_2)(c_1-c_2)^{-1}\pmod q \]

攻击者只需要看到两个签名，不需要攻破设备或求解离散对数。

玩具泄露例子

仍在 \(\mathbb Z_{19}\) 中，私钥 \(x=7\)，重复使用 \(r=4\)：

\[ c_1=5,\quad z_1=1 \]

另一条消息产生 \(c_2=8\)：

\[ z_2=4+8\cdot7=60\equiv3\pmod {19} \]

观察者计算：

\[ x=(1-3)(5-8)^{-1}\pmod {19} \]

\(-2\equiv17\)，\(-3\equiv16\)，而 \(16^{-1}=6\)，所以：

\[ x=17\cdot6=102\equiv7\pmod {19} \]

私钥完整暴露。

4.8 nonce 不只是“不能重复”

可预测或有偏差的 nonce

多次签名中只泄漏 nonce 的部分比特、或 nonce 分布存在偏差，也可能通过格攻击等方法恢复私钥。它不需要出现完全相同的 \(R\)。

脆弱的随机数源

时间戳、计数器、普通 PRNG、短种子和错误恢复后的 RNG 回滚都不适合直接产生 nonce。

自创确定性 nonce

确定性 nonce 可以减少外部随机源失败风险，但不能简单写成 H(private_key || message) 就宣称安全。标准方案会规定域分离、密钥派生、辅助随机数、编码和故障假设。应实现选定标准，而不是发明变体。

预计算 nonce 的生命周期

预计算可以提高性能，却引入状态机风险：

nonce 秘密与承诺必须一一对应；
一旦承诺发布，该 nonce 即使会话失败也通常必须销毁；
崩溃恢复不能让“未标记已用”的 nonce 再次出现；
nonce 不得跨密钥、协议或参与者复用；
日志、备份和序列化不能泄漏 nonce 秘密。

对于签名密钥而言，nonce 管理往往比核心公式更难。

4.9 为什么 Schnorr 适合做门限签名

Schnorr 响应是线性的：

\[ z=r+cx \]

假设私钥通过 Shamir 共享，参与者 \(i\) 持有 \(x_i=f(i)\)。对本次签名集合 \(S\)：

\[ x=\sum_{i\in S}\lambda_i^Sx_i \]

如果各参与者还有 nonce 份额 \(r_i\)，使：

\[ r=\sum_{i\in S}r_i,\qquad R=\sum_{i\in S}R_i,\quad R_i=r_iG \]

那么可以构造签名份额：

\[ z_i=r_i+c\lambda_i^Sx_i \]

聚合后：

\[ \begin{aligned} z &=\sum_{i\in S}z_i\\ &=\sum_{i\in S}r_i +c\sum_{i\in S}\lambda_i^Sx_i\\ &=r+cx \end{aligned} \]

因此最终 \((R,z)\) 看起来就是一个普通 Schnorr 签名，验证者无需知道参与者是谁或门限是多少。

这段推导说明了线性结构，却不是可以直接部署的协议。朴素聚合没有完整处理恶意选择承诺、nonce 取消、参与者绑定、签名份额验证、会话重放和中止后的 nonce 状态。

4.10 FROST 如何补全朴素方案

FROST 是经过专门设计的门限 Schnorr 协议。以常见的两轮结构为直觉，每个签名者 \(i\) 会准备两个一次性 nonce：

\[ d_i,e_i\in\mathbb Z_q \]

并发布对应承诺：

\[ D_i=d_iG,\qquad E_i=e_iG \]

聚合者把消息、签名者集合和全部承诺组织成规范 transcript，并为每个参与者计算绑定因子 \(\rho_i\)。该参与者本次的有效承诺为：

\[ R_i=D_i+\rho_iE_i \]

群承诺为：

\[ R=\sum_{i\in S}R_i \]

挑战为：

\[ c=H_{\mathrm{scalar}}(R,X,m,\ldots) \]

签名份额具有如下结构：

\[ z_i=d_i+\rho_i e_i+c\lambda_i^Sx_i \]

聚合：

\[ z=\sum_{i\in S}z_i \]

绑定因子把每个参与者的有效 nonce 与本次消息、签名集合及承诺列表绑定，防止攻击者在观察其他承诺后自由操纵自己的组合。完整实现还应在聚合前验证每个签名份额，并严格遵循所选 FROST 规范的标识符、编码、群和哈希定义。

不同标准或密码套件可能对挑战符号、群承诺规范化及 transcript 字段作不同规定。实现时必须选定一个规范版本逐字节遵循，不能只凭本章公式拼装。

4.11 实现边界：哪些自己写，哪些交给库

为了学习，可以自己实现：

Schnorr 协议流程与状态类型；
transcript 构造；
签名与验证的组合逻辑；
单元测试、性质测试和故障注入；
后续的 Shamir 权重、签名份额与聚合逻辑。

不建议在同一项目中自己实现：

大整数有限域算术；
椭圆曲线点加法与标量乘法；
SHA-512 等哈希函数；
操作系统安全随机源；
常数时间比较和底层点编码。

“从零实现协议”不等于“从零实现所有密码学原语”。复用审计充分的基础库，才能把注意力放在 TSS 真正困难的协议状态与对手行为上。

4.12 建议的动手实验

实验一：正确性与篡改

生成密钥并签署消息；
验证原签名成功；
分别修改消息、\(R\)、\(z\) 和公钥；
确认每种篡改都验证失败；
对空消息、大消息和包含零字节的消息测试。
构造单位元公钥或单位元 \(R\)，确认在 challenge 计算前拒绝。

实验二：有意重用 nonce

仅在玩具测试代码中注入固定 nonce，对两条不同消息签名，然后根据：

\[ x=(z_1-z_2)(c_1-c_2)^{-1} \]

恢复私钥，并验证恢复出的 \(xG\) 与原公钥一致。这个实验会让 nonce 风险从一句警告变成可观察事实。

实验三：类型驱动接口

让 Rust 类型系统阻止以下误用：

把消息字节直接传给需要 Scalar 的函数；
把 Point 当作私钥；
将未验证的外部字节直接构造成已验证公钥；
在 API 中让调用者传入任意挑战 \(c\)；
在生产签名接口中传入可复用的固定 nonce。

实验四：门限等式模拟

这是进入下一章前的可选代数预演。只在玩具域或测试模块里验证求和关系，不建立可复用的 nonce/网络 API；真实曲线上的门限实现统一留到实验 4。

先在一个进程内模拟多个参与者：

用 Shamir 创建 \(x_i\)；
为一个固定集合 \(S\) 计算 \(\lambda_i^S\)；
分别产生 nonce 和签名份额；
聚合并用群公钥验证；
更换签名集合但故意复用旧拉格朗日系数，观察验证失败；
最后再进入 FROST 的双 nonce 与绑定因子设计。

4.13 常见误区

误区一：“\(R\) 公开了，所以 \(r\) 也不再重要”

错误。\(R=rG\) 可以公开，\(r\) 必须保密且只用一次。从 \(R\) 反求 \(r\) 是离散对数问题，但日志直接泄漏 \(r\) 就没有这层保护。

误区二：“只要随机数大概率不重复就够了”

不够。nonce 还必须不可预测、近似均匀，并能抵抗崩溃回滚、偏差和部分泄漏。

误区三：“不同私钥可以安全共用 nonce”

协议没有授权这种优化。跨密钥复用会产生额外代数关系，破坏安全证明，也容易演变为同密钥复用。每个签名会话都应使用按规范独立生成并绑定的 nonce。

误区四：“验证等式成立，就说明输入解析安全”

错误。非规范标量、无效点、单位元、小阶点和歧义编码可能在到达等式前就破坏安全边界。

误区五：“所有 Schnorr 签名都能互相验证”

错误。BIP-340、Ed25519 风格方案、Ristretto Schnorr 和不同 FROST 密码套件在群、编码、哈希、域分离和符号约定上可能不同。

误区六：“把每个人的普通 Schnorr 签名相加就是门限签名”

错误。参与者需要对同一个群承诺和挑战生成按 Shamir 权重调整的签名份额，还需要防止恶意承诺与 nonce 攻击。

误区七：“会话失败后 nonce 没产生签名，可以重新使用”

危险。一旦 nonce 承诺或相关信息被对外公开，就应按协议将其视为已消费。重试必须使用全新 nonce。

4.14 章节检查题

Schnorr 中哪些量是标量，哪些量是群元素？
从 \(z=r+cx\) 推导验证等式。
挑战哈希为什么应包含 \(R\)、\(X\)、\(m\) 和域分离标签？
同一 nonce 签署两条消息时，攻击者如何恢复私钥？
为什么“确定性生成 nonce”并不等于可以自由设计 nonce 哈希公式？
普通 Schnorr 的哪项代数性质使它适合门限化？
朴素门限推导中的签名份额 \(z_i\) 是什么？为什么该推导还不是完整安全协议？
FROST 中第二个 nonce 和绑定因子大致解决什么问题？
签名会话在发布 nonce 承诺后崩溃，恢复时可以重用它吗？

参考答案

\(x,r,c,z\) 是 \(\mathbb Z_q\) 中的标量；\(G,X,R\) 是群元素；\(m\) 是字节串。
\(zG=(r+cx)G=rG+c(xG)=R+cX\)。
它们分别把挑战绑定到本次承诺、签名公钥、消息和具体协议用途；遗漏字段可能允许重放、替换或跨协议混淆，并改变安全模型。
由两个响应相减，得到 \(x=(z_1-z_2)(c_1-c_2)^{-1}\pmod q\)。
nonce 派生涉及域分离、编码、密钥派生、辅助随机性和故障模型；自创公式没有标准方案的分析与互操作保证。
响应 \(z=r+cx\) 对 nonce 和私钥都是线性的，因此各参与者的加权份额可以相加成普通响应。
朴素形式为 \(z_i=r_i+c\lambda_i^Sx_i\)。它没有完整抵抗恶意承诺选择、nonce 取消、重放等攻击，也缺少严谨状态机和份额验证。
双 nonce 经 \(\rho_i\) 组合后，把参与者的有效承诺绑定到本次 transcript，限制恶意参与者观察他人承诺后操纵聚合 nonce。
不应重用。承诺一经发布，nonce 通常必须视为已消费；恢复或重试使用新 nonce。

本章小结

Schnorr 的核心是：用一次性秘密 \(r\) 隐藏私钥响应，用哈希挑战把承诺、公钥与消息绑定，再通过线性群等式验证。线性结构为门限签名打开了大门，而 nonce 的脆弱性决定了 FROST 实现必须把会话状态、承诺绑定和一次性消费当作核心安全逻辑，而不是外围工程细节。

Keyboard shortcuts

TSS 从理论到 Rust 实现