一文读懂比特币Schnorr签名
落日余晖97
发表于 2023-1-1 00:07:10
225
0
0
非对称密钥对主要用于两种应用:5 I" v4 w+ @* V. s9 c Y- U% L& V
· 在身份验证中,你需要证明自己掌握私钥;
· 在加密过程中,信息可以编码,只有拥有私钥的人才能解密和阅读消息。
在本篇数字签名的介绍中,我们将讨论一类特定的钥匙:从椭圆曲线派生的钥匙,还有其他非对称方案,其中最重要的是基于素数乘积的方案,包括RSA密钥[1]。& R( |0 R+ j* z$ B
我们假设你了解椭圆曲线加密(Elliptic Curve Cryptography)的基础知识,如果不了解的话没关系可以到原文的前一章节了解。$ @4 _" p" m: Z3 j, _1 p( \
·进入正题
这是对数字签名的交互式介绍,使用Rust代码来演示本文提及的一些想法,因此你可以看到它们是如何运作的,本文介绍的代码使用的是libsecp256k-rs子库。
这个名字有点拗口,但secp256k1是椭圆曲线的名称,它用于保护很多加密货币交易,包括比特币。
这个特殊的库提供了一些很不错的功能,我们重写了加法和乘法运算符,以便Rust代码看起来更像数学公式,这使我们更容易试验想要实施的想法。- O0 V/ a2 ]3 \. s
友情提示!不要在编写代码过程中使用此库,它没有经过验证,如果需要的话可以用这个子库替代。
·Schnorr签名的基础知识4 Z. }) f) Z$ }. i5 F* J4 H! W
·公钥和私钥: ^6 q( W2 V2 P4 x- E: j
我们要做的第一件事是从椭圆曲线创建公钥和私钥。) z v9 y7 n- W" q' \
在secp256k1中,私钥只是0到2256之间的标量整数值,数量之多相当于整个宇宙的原子数,所以有无穷无尽的可能性。# R$ t7 J8 x2 P6 Z O# ^6 e% K" a
secp256k1曲线上有一个特殊点,名为G,它充当“原点”。公钥是通过将曲线上的G加到自身,乘以“Ka”,这是标量乘法的定义,写成:
Pa=KaG
举个例子,当以未压缩格式编写时,1的公钥是0479BE667 ... C47D08FFB10D4B8,以下代码演示了这一点: X1 o' S9 m* r7 E1 M3 j! Z1 M0 A
·创建签名, z5 Y( x; A/ H, J; {7 `
采用方式- _2 X. n; l( E2 Z* {1 ?3 r
当为标量使用正确选择的随机值时,反转ECC数学乘法(即除法)几乎是不可行的([5],[6])。这个属性称为离散日志问题(Discrete Log Problem),作为许多加密货币和数字签名背后的原理使用。有效的数字签名是证明签名提供人知悉与消息相关联的公钥/私钥的证据,或者已解决离散日志问题的证据。" R6 f, W& w6 w: G, R
创建签名的方法始终遵循以下方法: 1. 生成秘密一次性数字r(称为随机数)。 2. 从r创建公钥R,其中(R=rG)。 3. 将以下内容发送给你的收件人Bob——你的消息(m),R和你的公钥(P=kG)。& m! h3 {' x5 ~
通过哈希上述所有公共信息的组合来创建实际签名以创建问题,e:8 {1 a" ]7 l1 C, `6 e
e=H(R||P||m)
选择哈希函数,使e与私钥具有相同的范围,在我们的例子中,我们想要返回的信息是256位数字,所以SHA256是个不错的选择。8 U5 z0 c3 h6 U9 ~1 R8 Y
现在使用你的私人信息构建签名:s=r+ke
Bob现在也可以计算e,因为他已经知道m、R、P,但是他不知道你的私钥或随机数。% Z1 a) }) g) |% M! w
注意:创建这样的签名被称为Schnorr签名,我们稍后会继续讨论,还有其他创建s的方法,比如在比特币中使用的ECDSA [2]。% a! H; g2 L( @( s, o
看这个例子:sG=(r+ke)G: l8 I% Z6 | E
将右侧相乘:sG=rG+(kG)e9 v1 i% k( ^- j+ k) G9 `
替代R=rG和P=kG,可以得到:sG=R+Pe
所以Bob必须计算对应于签名(s.G)的公钥,并检查它是否与等式(R+Pe)右侧相等,这些消息对于Bob来说都已知。# h0 z( c( t3 K& U$ Y
·随机数Nonce的必要性,为什么标准签名中需要随机数?
假设我们仅仅只是签署了一条消息m:
e=H(P||m)! F, Q" d# T& ?. ]4 M1 q9 z: T
签名为s=ek
我们可以照常检验签名是否有效?
目前为止都正常,但是现在任何人都可以阅读你的私钥,因为s是标量,所以k=s/e并不难,至于随机数,必须求解k=(s-r)/e,但r是未知的,所以只要r是随机选择的,这就不是一个可行的计算。
我们可以证明,没有随机数确实是非常不安全的:
·ECDH是什么?; J- E0 L/ L I; S
想要实现安全通信的各方要如何生成用于加密消息的共享密钥?一种方法称为椭圆曲线Diffie-Hellmam交换(Elliptic Curve Diffie-Hellmam exchange),这是一种简单的方法。; {' a+ R! S; [8 f! L
ECDH用于许多地方,包括通道协商期间的闪电网络[3]。
这是它的工作原理,Alice和Bob想要安全地沟通,一种简单的方法是使用彼此的公钥并进行计算:
出于安全原因,通常会为每个会话随机选择私钥(这涉及到“临时密钥”这一术语的使用),但是我们遇到的问题是不确定对方是否与他们声称的身份相符(可能是中间人攻击[4])。6 X) y' f9 n2 \9 M4 U" X p
可以采用其他身份验证步骤来解决此问题,这里不再详述。
·Schnorr签名
如果你经常关注加密货币新闻,就会知道比特币Schnorr签名是多热门的话题。% c/ x4 z0 X0 r0 l
但实际上,这已经算是旧闻了,Schnorr签名被当作是随机预言模型中最简单的安全数字签名方案,它很有效并且生成短签名,获得美国专利4995082,该专利于2008年2月到期[7]。
; n! e- d B. R
·为什么Schnorr签名能引起关注?8 B% O" t9 b$ V) v W
Schnorr签名如此迷人而危险的原因在于简洁性。 Schnorr签名是线性的,因此具有一些优良属性。
椭圆曲线具有乘法性质,因此,如果有两个对应点X,Y和相应的标量x,y,则:; A7 Y( }) b- T& C r; I: r0 o
(x+y)G=xG+yG=X+Y
Schnorr签名的形式为s=r+ek,这种结构也是线性的,因此它非常适合椭圆曲线数学的线性。
在上一节中已经介绍了线性,当我们验证签名时,Schnorr签名的线性使其非常具有吸引力,其中包括: 1. 签名聚合; 2. 原子交换; 3.“无脚本”脚本
+ @, e, P$ R# K9 A+ d
·Na?ve签名聚合
让我们看看,Schnorr签名的线性属性如何用于构造多重签名。! @& w& @2 R$ }/ c, g4 M
Alice和Bob想要签署一些东西(比如Tari交易)而不必相互信任,也就是说,他们需要证明其各自密钥的所有权,并且只有在Alice和Bob都提供其签名部分时,聚合签名才有效。0 n c2 v- R. J0 D+ K, _* d" q
假设私钥表示为ki,公钥表示为Pi。 如果我们要求Alice和Bob各自提供一个随机数,可以尝试:
所以Alice和Bob可以自己提供R,任何人都可以从R的总和公钥中构建两个两个签名,这的确可行:
7 R4 u- f. G9 t* I5 c3 N' \$ C" ^
但是这个框架并不安全!
+ v+ T* S+ _! H
·密钥消除攻击2 ?+ P6 M4 T+ W' [0 @
依旧是上述场景,但这一次,在Alice公布以后,Bob提前知道了Alice的公钥和随机数。' n& o' ]( `9 `3 F7 b3 Z
现在Bob说谎并说他的公钥是P'b=Pb-Pa,公共随机数是R'b=Rb-Ra。
Bob并不知道伪造值的私钥,但是也没多大影响。
根据聚合方案,每个人都假设Sagg=Ra+R'b+e(Pa+P'b)。# }+ p0 D& P2 [1 h3 m1 T4 V
但Bob可以自己创建这个签名:
/ R, x. p5 n6 ` z# L
. `+ r3 Y* h9 p- h% y8 s
·更好的聚合方法
在密钥取消攻击中,Bob不知道发布的R和P值的私钥,我们可以要求他签署一则消息证明他确实知道私钥,让Bob攻击失败。' N+ p+ c# t1 |% \- i
这是有效的,但它需要在各方之间进行另一轮消息传递,这不利于良好的用户体验。+ N0 @+ Z3 ?& d, s( \3 K8 Z: |# y
更好的方法是包含以下一个或多个功能的方法: · 它只需证明在普通的公钥模型中是安全的,而不必证实和密钥有关消息,因为我们可以要求Bob在na?ve模式中证明。 · 它应该满足常规的Schnorr方程,即可以用R+eX形式的表达式验证得到的签名。 · 它允许交互式聚合签名(IAS),签名者需要配合。 · 它允许非交互式聚合签名(NAS),其中聚合可以由任何人完成。 · 它允许每个签名者签署相同的消息,m。 · 它允许每个签名者签署自己的消息,mi。
·多重签名# `/ |, x% @4 c( b% X
多重签名是最近提出的([8],[9])简单签名聚合方案,它满足前一节中的所有属性。
·多重签名演示
我们将在这里演示交互式多重签名方案,每个签名者签署相同的消息,该计划的工作原理如下: 1. 如前所述,每个签名者都有一个公私密钥对。 2. 每个签名者都对他们的公共随机数共享一个承诺(在本演示中跳过此步骤),此步骤对防止某些类型的恶意密钥攻击是必要的[10]。 3. 每个签名者都发布他们的随机数,Ri的公钥。 4. 每个人都计算相同的“共享公钥”,X如下:
请注意,在上述公钥排序中,应遵循某些既定规则,例如按字典顺序序列化密钥。 1. 每个人也计算共享的随机数,R=∑Ri。 2. 问题,e是H(R||X||m)。 3. 每位签名者都需要对签名提供贡献:/ w! B( d$ m- R& T* [/ A+ n
注意,标准Schnorr签名的唯一出发点是包含因子ai。, g0 k# t/ U2 y, X/ [+ I
聚合总签名一般是总和,s=∑si。
通过以下方式确认验证:sG=R+eX% [- m5 k$ P. H9 l0 @
证明:
让我们用三重签名来演示:
·安全演示
作为最后的演示,让我们展示一下多重签名如何从na?ve签名方案中抵御消除攻击。与密钥消除攻击部分想法相同,Bob在他的随机数和公钥中提供了假值:
这导致Alice和Bob共同进行了以下计算:% Y& m. B0 R9 E0 M4 x
Bob随后在多重签名后构建单边签名:2 L8 ~. O3 D+ \0 _0 ^/ E
我们现在假设ks不需要成为Bob的私钥,但是他可以使用他已知的信息来推导,要使其成为有效签名,必须验证R+eX,因此:
在之前的攻击中,Bob从类似计算中获得了所需的所有算式右侧信息,在多重签名中,Bob必须以某种方式知道Alice的私钥和伪造的私钥(这些条款不再取消)才能创建单边签名,因此他的消除攻击失败。$ Q! E0 w# W- Q- @2 j% l
·重放攻击
每个签名仪式都要选择一个新的随机数,这一点至关重要,最好的方法是使用加密安全(伪)随机数生成器(CSPRNG)。9 A8 v- W$ a8 a) F
但即使是这种情况,攻击者可以通过将签名仪式“倒带”到产生部分签名的时间点来诱骗我们签署新消息,此时,攻击者提供了一个不同的消息,e'=H(...||m')来进行签名,而不会引起任何怀疑,每一方会再次计算他们的部分签名:8 [) u9 |2 k/ Z
攻击者仍然可以访问第一组签名,只需要简单地做减法:
最终等式右侧的所有消息都被攻击者获取,因此他可以轻易地提取每个人的私钥,这种攻击很难防御。一种方法是增加终止和重启签名仪式的难度,如果多重签名仪式被中断,那么需要再次从第一步开始,这相当符合人体工程学,在出现更强大的解决方案之前,它可能是目前最好的解决方案!
成为第一个吐槽的人