密码学之Schnorr签名、多签(一)

Schnorr 签名

单签

Schnorr 签名是一种数字签名方案，由德国密码学家 Claus-Peter Schnorr 提出，最早在 1989 年的一篇论文中(Efficient Signature Generation by Smart Cards)被描述，文中提出了一种身份认证方案，再通过Fiat-Shamir变换 (How To Prove Yourself: Practical Solutions to Identification and Signature Problems,1986) 转变成签名方案，它基于离散对数困难问题，具有高效性、安全性等优点，在区块链等领域有重要应用。\ 下面给出在椭圆曲线加法群中构造的算法流程。

$\text{KeyGen}:$\ 生成随机数 $x \xleftarrow{R}[1,N-1]$作为私钥，计算$Y=xG$作为公钥。\ 其中$G$是椭圆曲线群的生成元，$N$是椭圆曲线群的阶，是一个大素数。

$\text{Sign}:$\ 生成随机数 $r \xleftarrow{R}[1,N-1]$ 作为临时私钥，计算承诺$R=rG$。\ 计算$e=H(m,R,Y)$作为随机挑战。\ 计算$s=r+e*x$。\ $\sigma=(R,s)$ 作为消息 $m$ 签名 。\ 一定要注意：先计算承诺后计算随机挑战，承诺一定要作为哈希函数的输入。

$\text{Verify}:$\ 验证 $sG\xlongequal{?}R+H(m,R,Y)Y$

分析一下，对每一个签名，签名者都生成一个随机的一次性私钥 $r$，然后计算出$r$ 的公钥 $R$，一般称它为承诺。接下来，我们用$m,R,Y$作为输入计算哈希值，有时候也可以用$m,R$作为输出，有一点很重要就是一定将$R$作为输入。最后使用私钥$x$进行签名，就是做到隐藏私钥无法恢复私钥，一定是用一次性私钥$r$加上随机挑战$e$乘以私钥$x$。$(R,s)$ 就是签名。

在实现schorr签名算法时一定要注意以下几个陷阱：

1. 承诺重复使用 \ 假设对两个消息$m_0,m_1$进行签名时，使用了同一个承诺$R$，那么根据签名算法我们得到 <span style="display: block; text-align: center;">$s_0=r+H(m_0,R,Y)x$</span> <span style="display: block; text-align: center;">$s_1=r+H(m_1,R,Y)x$</span> 将上面两个等式相减得到，$x=\frac{s_0-s_1}{H(m_0,R,Y)-H(m_1,R,Y)}$，就能恢复出私钥，这样就不安全了。

2. 随机挑战的生成未使用承诺作为输入

   这种情况在计算$s$时，就变成了$s=r+H(m,Y)*x$，两边都乘以$G$得到$sG=R+H(m,Y)Y$，可以看出只要随机选择一个$s$，计算$R=sG-H(m,Y)Y$，于是$(R,s)$就是在不知道私钥的情况下伪造出来一个签名，也就是说，我们可以生成任意的 $s$ 值，然后根据这个值来计算 $R$ 值，只用到了$(m,Y)$的信息，就可以任意创建有效的数字签名，这样就不安全了。

   我们发现，这个情况还是可以避免的，我们只需要稍微调整一些东西来打破这种攻击。但是在 Schnorr 签名安全性证明的论文中介绍了它的真正本质，也许能让调整理解起来更加容易自然。

   可以尝试的思路是使得 $s$ 依赖于承诺 $R$，从而打破等式 $R=sG–H(m)Y$，就是在我们计算随机挑战时哈希函数的输入包含承诺 $R$，即 $s=r+H(m,R,Y)*x$。这就打破了伪造任意签名的攻击，因为给定一个随机的 $s$，找出一个 $R$ 使得 $R=sG–H(m,R,Y)Y$ 成立是很难的，因为 $R$ 要先参与哈希值的生成，除了暴力破解之外，没有更好的办法来找出合适的 $R$。

schnorr 签名有以下两个主要优点

• schnorr 签名数据存储比 ECDSA 更小

  计算和验证起来更快，在比特币现在使用的 ECDSA 签名方案中，一个签名（DER 编码）是 70 或 71 字节长；而 schnorr 签名的长度是 64 字节。此外，计算和验证 schnorr 签名都比 ECDSA 签名快得多。

• schnorr 签名形式是线性的

  这是 schnorr 与众不同的关键之处，线性这种属性可以很容易的用来构造多签名。

所以在实现签名算法的时候，一定要深入理解算法本身，不能想当然去认为，否则会发生非常糟糕的事情。

schnorr 签名是基于群上离散对数困难问题来设计的，依赖于安全的伪随机函数、安全的 hash 函数

多签名-MultiSig

schnorr 的多签名方案，在这篇论文 (Simple Schnorr Multi-Signatures with Applications to Bitcoin) 中提出。顾名思义，多签名方案就是一组签名私钥 $(x_1,x_2, … , x_n)$ 共同为一条消息生成一个签名。在普通的签名方案（比如 Schnorr 和 ECDSA）中，最简单的多签名方案就是把每一个签名者（对给定的一条消息）的单签名串联起来 $s=(\sigma_1,\sigma_2,\dots,\sigma_n)$ ，比特币已经支持这种串联多签方案了，实际上还支持创建 $n$ 个参与者中任意 $t$ 个（$t$ 小于 $n$）即可花费资金的地址，但我们不在这里讨论这种阈值签名，本篇只讨论 $n$ 个参与者一致参与的情形，即 $n$-$n$ 形式的多签。

虽然串联多签是一种正确的多签名方案，但是它有一些严重的缺陷：在 $n$-$n$ 的多签名方案中，签名的大小是普通单签名的 $n$ 倍，而且它要把 $n$ 个签名和公钥都暴露在链上，同样验证多签名也是验证单签名的时间的 $n$ 倍。它没有隐私特性，因为所有的参与者都是公开参与，用来验证签名。

schnorr 多签名方案就能很好的解决这些问题，无论签名的参与者有多少个，都只产生一个签名，且该签名与常规的 schnorr 单签名没有形式上的区别。此外，它还支持密钥聚合，所以签名私钥都可以保持隐私。具体来说，如果有 $n$ 个签名者 $Y_1,Y_2,\dots,Y_n$，要签名的消息记为 $m$，那么多签方案可以生成一个 schnorr 签名 (R, s)，该签名对应的验证公钥是 $Y=agg(Y_1,Y_2,\dots,Y_n)$ 聚合公钥，这让多签名的输出与标准的输出看起来没有分别。

构造多签名以及安全性分析

schnorr 签名形式是线性的，首先很容易想到的是在 $n$ 方参与签名时将他们的公钥聚合成一把公钥，并使该聚合公钥可用于 $n$ 方一致参与的情形中的签名验证。假设有一组公钥 $(Y_1,Y_2,\dots,Y_n)$，我们生成聚合公钥形式如下：\ <span style="display: block; text-align: center;">$Y=Y_1+Y_2+\dots+Y_n$</span> 假设每一方都按照单签名的形式生成自己的签名分片，形式如下：\ <span style="display: block; text-align: center;">$s_i=r_i+H(m,R_i,Y_i)x_i$</span> 发现这种形式无法聚合称一个签名$s$，因为$H(m,R_i,Y_i)$都不一样，解决办法是将每一方的$Y_i$替换成聚合公钥 $Y$，又因为承诺$R_i$是可以公开的，所以就能构造一个统一的聚合承诺如下： <span style="display: block; text-align: center;">$R=R_1+R_2+\dots+R_n$</span> 并替换每一方的$R_i$，则得 <span style="display: block; text-align: center;">$s_i=r_i+H(m,R,Y)x_i$</span> 聚合签名如下： <span style="display: block; text-align: center;">$s=s_1+s_2+\dots+s_n\=r_1+H(m,R,Y)x_1\+r_2+H(m,R,Y)x_2\+\dots\+r_n+H(m,R,Y)x_n\=(r_1+\dots+r_n)+H(m,R,Y)(x_1+\dots+x_n)\=r+H(m,R,Y)x$</span> 该形式就是一个单签名形式，验证 $sG\xlongequal{?}R+H(m,R,Y)Y$。这里$r$是一次性聚合私钥，$x$是聚合签名私钥，$R$是聚合承诺，$Y$是聚合公钥。

不幸的是这种方案无法抵御所谓的 Rogue Key 攻击，假设我的公钥是$Y_1$，计算$Y_1'=Y_1-Y_2-\dots-Y_n$，我这边撒谎说我的公钥是$Y_1'$，所以这种情况下，聚合公钥就是$Y_1$，$Y_1$对应的私钥我是知道的，我可以独自做任何交易和操作，而不需要任何人的同意。

怎么防止 Rogue Key 攻击呢，当然方法很多，其中一种就是让我出示证明来证明我知道我所公开的公钥对应的私钥即可，事实上，我是不知道 $Y_1'$ 对应的私钥的，所以无法给出证明，进而防止 Rogue Key 攻击。

但是还有一个问题，就是承诺 $R$ 仍然可以进行 Rogue Key 攻击，假设我的一次性私钥是$r_1$，计算承诺$R_1=r_1G$，只要是我等其他人先公开签名，然后计算聚合签名 $s=r_1+H(m,R,Y)x$ ，又因为我知道$r_1$，所以就能推出聚合私钥 $x$ 的值，这是非常危险的，非常不安全的。

因此，为了解决上述方案存在的问题，我们需要让聚合承诺 $R$ 和聚合公钥 $Y$ 都能抵抗 Rogue Key 攻击。对于承诺，我们让所有的参与者都先公开自己对 $R_i$ 的承诺，再公开具体的数值（这样就没有人能提前知道其他人的承诺并恶意生成自己的承诺）。具体来说，我们会要求每一方都广播 $t_i=H(R_i)$，并且只有在看到所有人的承诺 $t_i$ 之后才公开自己的 $R_i$ 。

但是这种方法对聚合公钥来说是不可行的，因为公钥公钥往往很早就公开了。可以采用如下方法：

• 对所有参与者的公钥串联起来并计算出一个哈希值，即$L=H(Y_1,\dots,Y_n)$
• 计算 $a_i=H(L,Y_i)$
• 计算聚合公钥 $Y=a_1\cdot Y_1+a_2\cdot Y_2+\dots+a_n\cdot Y_n$，因为聚合公钥的生成是由所有参与者$a_i$生成的，$a_i$又依赖所有的公钥，假设 $Y_1'=Y-a_1\cdot Y_1-\dots-a_n\cdot Y_n$，这是不可能的，因为$Y_1'$的计算依赖于$a_1$，而$a_1$的计算又依赖于$Y_1'$，所以不可能。

多签可以分为三步：

1. 所有参与者计算 $t_i=H(R_i)$ 并广播$t_i$
2. 所有参与者广播 $R_i$，每个参与者验证 $t_i\xlongequal{?}H(R_i)$
3. 计算签名分片 $s_i=r_i+H(m,R,Y)\cdot a_i\cdot x_i$

所以聚合签名为 <span style="display: block; text-align: center;">$s=s_1+s_2+\dots+s_n\=r+H(m,R,Y)\cdot x$</span> 其中 $r=r_1+r_2+\dots r_n$，$x=a_1\cdot x_1+a_2\cdot x_2+\dots a_n\cdot x_n$

此时，任何一个能收到所有的承诺 $R_i$ 数值和签名分片的的人都可以计算并使用schnorr签名 $(R, s)$。

MultiSig 协议的安全性证明是在开头提到的论文中，特别注意，上面三个步骤改为两步是不安全的，工程实现时一定要严格按照协议进行实现，不能想当然。

实际上是可以做到两步通信就能完成多签协议的，但凡有公钥密码学一定功底的人都能想到怎么做，绝对也会有这方面的论文进行发表的，这个方法就是每个参与方再生成一次性承诺$R_i$时同时提供一个$R_i$的NIZK证明，并将$R_i$和其证明都广播出去，因此第一步和第二步就可以合并成一步，进而实现了协议优化。