8BTCCI: 14124.52 +1.13% 8BTCVI: 6786.28 +0.40% 24H成交额: ¥3690.15亿 -11.23% 总市值: ¥19452.75亿 +1.69%
科普 | 一文读懂比特币Schnorr签名

科普 | 一文读懂比特币Schnorr签名

头等仓 发布在 技术指南 海盗号 607773

公私密钥对是加密货币安全性的基石,从安全的网页浏览到加密货币金融业务。公私密钥对是不对称的,这意味着给定一串数字(私钥),可以导出另一串(公钥)。但是,反之就不可行。正是这种不对称性允许人们公开分享公钥,公开也能确信没有人可以推导出私钥(私钥需要秘密且安全地保管)。

非对称密钥对主要用于两种应用:

· 在身份验证中,你需要证明自己掌握私钥;

· 在加密过程中,信息可以编码,只有拥有私钥的人才能解密和阅读消息。

在本篇数字签名的介绍中,我们将讨论一类特定的钥匙:从椭圆曲线派生的钥匙,还有其他非对称方案,其中最重要的是基于素数乘积的方案,包括RSA密钥[1]。

我们假设你了解椭圆曲线加密(Elliptic Curve Cryptography)的基础知识,如果不了解的话没关系可以到原文的前一章节了解。

·进入正题

这是对数字签名的交互式介绍,使用Rust代码来演示本文提及的一些想法,因此你可以看到它们是如何运作的,本文介绍的代码使用的是libsecp256k-rs子库。

这个名字有点拗口,但secp256k1是椭圆曲线的名称,它用于保护很多加密货币交易,包括比特币。

这个特殊的库提供了一些很不错的功能,我们重写了加法和乘法运算符,以便Rust代码看起来更像数学公式,这使我们更容易试验想要实施的想法。

友情提示!不要在编写代码过程中使用此库,它没有经过验证,如果需要的话可以用这个子库替代。

·Schnorr签名的基础知识

·公钥和私钥

我们要做的第一件事是从椭圆曲线创建公钥和私钥。

在secp256k1中,私钥只是0到2256之间的标量整数值,数量之多相当于整个宇宙的原子数,所以有无穷无尽的可能性。

secp256k1曲线上有一个特殊点,名为G,它充当“原点”。公钥是通过将曲线上的G加到自身,乘以“Ka”,这是标量乘法的定义,写成:

Pa=KaG

举个例子,当以未压缩格式编写时,1的公钥是0479BE667 ... C47D08FFB10D4B8,以下代码演示了这一点:

 

·创建签名

采用方式

当为标量使用正确选择的随机值时,反转ECC数学乘法(即除法)几乎是不可行的([5],[6])。这个属性称为离散日志问题(Discrete Log Problem),作为许多加密货币和数字签名背后的原理使用。有效的数字签名是证明签名提供人知悉与消息相关联的公钥/私钥的证据,或者已解决离散日志问题的证据。

创建签名的方法始终遵循以下方法: 1. 生成秘密一次性数字r(称为随机数)。 2. 从r创建公钥R,其中(R=rG)。 3. 将以下内容发送给你的收件人Bob——你的消息(m),R和你的公钥(P=kG)。

通过哈希上述所有公共信息的组合来创建实际签名以创建问题,e:

e=H(R||P||m)

选择哈希函数,使e与私钥具有相同的范围,在我们的例子中,我们想要返回的信息是256位数字,所以SHA256是个不错的选择。

现在使用你的私人信息构建签名:s=r+ke

Bob现在也可以计算e,因为他已经知道m、R、P,但是他不知道你的私钥或随机数。

注意:创建这样的签名被称为Schnorr签名,我们稍后会继续讨论,还有其他创建s的方法,比如在比特币中使用的ECDSA [2]。

看这个例子:sG=(r+ke)G

将右侧相乘:sG=rG+(kG)e

替代R=rG和P=kG,可以得到:sG=R+Pe

所以Bob必须计算对应于签名(s.G)的公钥,并检查它是否与等式(R+Pe)右侧相等,这些消息对于Bob来说都已知。

 

·随机数Nonce的必要性,为什么标准签名中需要随机数?

假设我们仅仅只是签署了一条消息m:

e=H(P||m)

签名为s=ek

我们可以照常检验签名是否有效?

目前为止都正常,但是现在任何人都可以阅读你的私钥,因为s是标量,所以k=s/e并不难,至于随机数,必须求解k=(s-r)/e,但r是未知的,所以只要r是随机选择的,这就不是一个可行的计算。

我们可以证明,没有随机数确实是非常不安全的:

 

·ECDH是什么?

想要实现安全通信的各方要如何生成用于加密消息的共享密钥?一种方法称为椭圆曲线Diffie-Hellmam交换(Elliptic Curve Diffie-Hellmam exchange),这是一种简单的方法。

ECDH用于许多地方,包括通道协商期间的闪电网络[3]。

这是它的工作原理,Alice和Bob想要安全地沟通,一种简单的方法是使用彼此的公钥并进行计算:

出于安全原因,通常会为每个会话随机选择私钥(这涉及到“临时密钥”这一术语的使用),但是我们遇到的问题是不确定对方是否与他们声称的身份相符(可能是中间人攻击[4])。

可以采用其他身份验证步骤来解决此问题,这里不再详述。

 

·Schnorr签名

如果你经常关注加密货币新闻,就会知道比特币Schnorr签名是多热门的话题。

但实际上,这已经算是旧闻了,Schnorr签名被当作是随机预言模型中最简单的安全数字签名方案,它很有效并且生成短签名,获得美国专利4995082,该专利于2008年2月到期[7]。

 

·为什么Schnorr签名能引起关注?

Schnorr签名如此迷人而危险的原因在于简洁性。 Schnorr签名是线性的,因此具有一些优良属性。

椭圆曲线具有乘法性质,因此,如果有两个对应点X,Y和相应的标量x,y,则:

(x+y)G=xG+yG=X+Y

Schnorr签名的形式为s=r+ek,这种结构也是线性的,因此它非常适合椭圆曲线数学的线性。

在上一节中已经介绍了线性,当我们验证签名时,Schnorr签名的线性使其非常具有吸引力,其中包括: 1. 签名聚合; 2. 原子交换; 3.“无脚本”脚本

 

·Naïve签名聚合

让我们看看,Schnorr签名的线性属性如何用于构造多重签名。

Alice和Bob想要签署一些东西(比如Tari交易)而不必相互信任,也就是说,他们需要证明其各自密钥的所有权,并且只有在Alice和Bob都提供其签名部分时,聚合签名才有效。

假设私钥表示为ki,公钥表示为Pi。 如果我们要求Alice和Bob各自提供一个随机数,可以尝试:

所以Alice和Bob可以自己提供R,任何人都可以从R的总和公钥中构建两个两个签名,这的确可行:

但是这个框架并不安全!

 

·密钥消除攻击

依旧是上述场景,但这一次,在Alice公布以后,Bob提前知道了Alice的公钥和随机数。

现在Bob说谎并说他的公钥是P'b=Pb-Pa,公共随机数是R'b=Rb-Ra。

Bob并不知道伪造值的私钥,但是也没多大影响。

根据聚合方案,每个人都假设Sagg=Ra+R'b+e(Pa+P'b)。

但Bob可以自己创建这个签名:

 

·更好的聚合方法

在密钥取消攻击中,Bob不知道发布的R和P值的私钥,我们可以要求他签署一则消息证明他确实知道私钥,让Bob攻击失败。

这是有效的,但它需要在各方之间进行另一轮消息传递,这不利于良好的用户体验。

更好的方法是包含以下一个或多个功能的方法: · 它只需证明在普通的公钥模型中是安全的,而不必证实和密钥有关消息,因为我们可以要求Bob在naïve模式中证明。 · 它应该满足常规的Schnorr方程,即可以用R+eX形式的表达式验证得到的签名。 · 它允许交互式聚合签名(IAS),签名者需要配合。 · 它允许非交互式聚合签名(NAS),其中聚合可以由任何人完成。 · 它允许每个签名者签署相同的消息,m。 · 它允许每个签名者签署自己的消息,mi。

 

·多重签名

多重签名是最近提出的([8],[9])简单签名聚合方案,它满足前一节中的所有属性。

·多重签名演示

我们将在这里演示交互式多重签名方案,每个签名者签署相同的消息,该计划的工作原理如下: 1. 如前所述,每个签名者都有一个公私密钥对。 2. 每个签名者都对他们的公共随机数共享一个承诺(在本演示中跳过此步骤),此步骤对防止某些类型的恶意密钥攻击是必要的[10]。 3. 每个签名者都发布他们的随机数,Ri的公钥。 4. 每个人都计算相同的“共享公钥”,X如下:

请注意,在上述公钥排序中,应遵循某些既定规则,例如按字典顺序序列化密钥。 1. 每个人也计算共享的随机数,R=∑Ri。 2. 问题,e是H(R||X||m)。 3. 每位签名者都需要对签名提供贡献:

注意,标准Schnorr签名的唯一出发点是包含因子ai。

聚合总签名一般是总和,s=∑si。

通过以下方式确认验证:sG=R+eX

证明:

让我们用三重签名来演示:

 

·安全演示

作为最后的演示,让我们展示一下多重签名如何从naïve签名方案中抵御消除攻击。与密钥消除攻击部分想法相同,Bob在他的随机数和公钥中提供了假值:

这导致Alice和Bob共同进行了以下计算:

Bob随后在多重签名后构建单边签名:

我们现在假设ks不需要成为Bob的私钥,但是他可以使用他已知的信息来推导,要使其成为有效签名,必须验证R+eX,因此:

在之前的攻击中,Bob从类似计算中获得了所需的所有算式右侧信息,在多重签名中,Bob必须以某种方式知道Alice的私钥和伪造的私钥(这些条款不再取消)才能创建单边签名,因此他的消除攻击失败。

 

·重放攻击

每个签名仪式都要选择一个新的随机数,这一点至关重要,最好的方法是使用加密安全(伪)随机数生成器(CSPRNG)。

但即使是这种情况,攻击者可以通过将签名仪式“倒带”到产生部分签名的时间点来诱骗我们签署新消息,此时,攻击者提供了一个不同的消息,e'=H(...||m')来进行签名,而不会引起任何怀疑,每一方会再次计算他们的部分签名:

攻击者仍然可以访问第一组签名,只需要简单地做减法:

最终等式右侧的所有消息都被攻击者获取,因此他可以轻易地提取每个人的私钥,这种攻击很难防御。一种方法是增加终止和重启签名仪式的难度,如果多重签名仪式被中断,那么需要再次从第一步开始,这相当符合人体工程学,在出现更强大的解决方案之前,它可能是目前最好的解决方案!

参考资料:

[1]“RSA(Cryptosystem)”[OL]. https://en.wikipedia.org/wiki/RSA_ (cryptosystem). 访问日期:2018-10-11. [2]“椭圆曲线数字签名算法”,维基百科[OL]. https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm.  访问日期:2018-10-11. [3]“BOLT#8:加密和认证传输,Lightning RFC”,Github[OL].https://github.com/lightningnetwork/lightning-rfc/blob/master/08-transport.md. 访问日期:2018-10-11. [4]“中间人攻击”,维基百科[OL].https://en.wikipedia.org/wiki/Man-in-the-middle_attack. 访问日期:2018-10-11. [5]“密码安全随机数发生器如何工作?” StackOverflow“[OL]. https://stackoverflow.com/questions/2449594/how-does-a-cryptographically-secure-random-number-generator-work.  访问日期:2018-10-11. [6]“密码学安全伪随机数发生器”,维基百科[OL]. https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator.  访问日期:2018-10-11. [7]“Schnorr签名”,维基百科[OL]. https://en.wikipedia.org/wiki/Schnorr_signature.  访问日期:2018-09-19. [8]“Schnorr签名的密钥聚合”,Blockstream [OL]. https://blockstream.com/2018/01/23/musig-key-aggregation-schnorr-signatures.html_.  访问日期:2018-09-19. [9] Gregory Maxwell,Andrew Poelstra,Yannick Seurin和Pieter Wuille,“简单的Schnorr多签名应用比特币”[OL].https://eprint.iacr.org/2018/068.pdf. 访问日期:2018-09-19. [10] Manu Drijvers,Kasra Edalatnejad,Bryan Ford,Eike Kiltz,Julian Loss,Gregory Neven和Igors Stepanovs,“关于两轮多重签名的安全性”,密码学ePrint档案,报告2018/417 [OL]. https://eprint.iacr.org/2018/417.pdf.  访问日期:2019-02-21.

贡献者:

· CjS77 · SWvHeerden · Hansieodendaal · neonknight64 · anselld

本文来源:头等仓,是一家专业从事国内外区块链项目信息收集,项目分析,项目进展跟踪的信息资讯服务公司,面向国内外的区块链投资者,提供区块链项目的尽职调查与分析服务。

原文出处:https://tlu.tarilabs.com/cryptography/digital_signatures/introduction_schnorr_signatures.html

如需转载,请注明出处。

评论
登录 账号发表你的看法,还没有账号?立即免费 注册