密码学之Schnorr签名、多签

  • 皓码
  • 发布于 1天前
  • 阅读 161

Schnorr签名单签Schnorr签名是一种数字签名方案,由德国密码学家Claus-PeterSchnorr提出,最早在1989年的一篇论文中(EfficientSignatureGenerationbySmartCards)被描述,文中提出了一种身份认证方案

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$,那么根据签名算法我们得到 $$ \begin{aligned} s_0=r+H(m_0,R,Y)x \ s_1=r+H(m_1,R,Y)x \end{aligned} $$ 将上面两个等式相减得到,$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)$ 聚合公钥,这让多签名的输出与标准的输出看起来没有分别,一模一样。

未完待续

点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
皓码
皓码
学历:研究生 方向:公钥密码学及其相关内容应用研究 工作经历:隐私计算行业7年