加密货币中的“加密”:为什么一切又怪又难

从数学和科学角度来看,什么是密码学?其在实践中是如何运作的?

加密货币中的“加密”:为什么一切又怪又难

注:本文为技术公司Blockstream研究主管Andrew Poelstra在纽约MCC会议中发表的演讲。他在演讲中从密码学讲到了数字签名的安全,指出签名机制的设计从理论和实际应用情况来看是完全不同的,因此对于很多自称能创造神奇效果的项目来说,用户应该更多选择保持警惕。同时,在他看来,比特币的发展速度惊人,因此从技术角度来看,适当地放慢脚步并没有错。

以下为演讲全文:

我没有准备PPT。我想要尽可能地让这次演讲不是那么技术,我试图剥夺自己在屏幕上写下方程式的权力。我演讲的主题是为什么在加密货币中所有的一切都是奇怪和困难的。从数学和科学角度来看,什么是密码学?其在实践中是如何运作的?

加密

从历史上看,密码学的用途是加密,就像试图想出一些随机的东西。这里的安全性很简单:如果你有一个密钥,那么你就可以解密一些东西,而使用一个安全模型或风险模型来描述它的想法实际上没有意义。

在现代,密码学已经取得了长足的进步,包括零知识证明。零知识证明是由计算机程序证明的,这些程序只对输入进行状态说明,而不泄露输入的细节。

数字签名和加密是相关的。签名类似于对两个密钥的加密,一个公钥和一个私钥。任何拥有公钥的人都可以加密数据,任何拥有解密密钥或私钥的人都可以解密数据。这也意味着经过加密的数据可以通过不安全的通道进行发送。

数字签名

数字签名正好相反——只有拥有私钥的人才能生成签名,只有拥有公钥的人才能验证签名。如果你想讨论这里方案的安全性,那就更难做到,也更难做出定义。我要讲的是学术背景下的数字签名,然后我要讲的是随机数生成的实际问题,然后如果我有时间,我要讲的是如何将其扩展到多重签名设置。

没有密钥的人就不能伪造消息和公钥的签名。从学术上来说,将其形式化是相当困难的。这里所说的形式化指的是做一个定义清晰的状态说明。

多年之后,我们尝试了很多次来找出这些定义——我们得出了这样的结论:如果不存在任何多项式概率时间算法可以成为主导,那么数字签名方案就是安全的。我们将绝对排除任何算法存在的可能性(只要其界限合理),绝对不能伪造。即使这样,在定义的时候,也很难证明其安全性。在现实生活中,有一个知道密钥的人,这个人应该能够生成签名。所以你怎么能明确排除一切但依然包含特殊情况?

假设在一场比赛中你有一个对手,你的对手无法赢得下面的比赛:我随机取一个私钥和一个公钥,我把公钥给了你的对手。如果他能生成一个签名,那么这个签名就是伪造的,这个方案是不安全的。

直观地来看,这是有道理的。你生成了一个随机密钥,对手没有私钥。对手唯一知道的关键只有公钥。然而,这种想法是错误的。这个方案的问题在于,对手掌握了这个公钥的大量签名,而类似GPG的东西可能在区块链上进行过电子邮件或者过往的比特币交易签名。这个公钥包含了一堆签名。现有的签名方案对能够看到公钥的对手是安全的,但对看到签名的对手是不安全的。这不应该是其运作方式,但现实仍然如此。这东西很难。有一种竞争币就有这个问题。有许多人声称能解决不可能解决的问题。但大多数人都在对你撒谎,这才是这次演讲的真正目的。

假设这个对手更强大,他可以向挑战者索要信息,而挑战者必须在这条信息上签名。现在,对手不仅可以伪造信息,而且是在我们给出了几乎所有可能给出的信息的情况下。我们想提供尽可能多的信息。因此,在任意消息上签名就足够了。当对手伪造信息时,他必须在一条新的信息上生成签名。

这安全吗?这在常规的安全概念下是安全的,又被称为选择信息攻击下的存在性不可伪造性。但是在更复杂的系统中,由于一些原因,这是不安全的。我们在比特币中发现,通过允许对手只在一条新消息上提供签名,我们排除了对手可能使用现有的签名并在保持其有效性的同时对其进行调整的可能性。模型中没有捕捉到这一点。一旦某条消息签名完成,谁在乎对手可以针对同一条消息产出不同的签名?

在比特币中,我们使用的ECDSA和txid都是基于这些签名的。所以攻击者有能力改变签名,允许他们改变交易的txid,这将保持交易的有效性,但会使任何引用该txid的交易无效,因为txid是有延展性的。所以我们需要一个更强的模型。

我们现在需要一个对手,我们说,如果其在某个消息上提供签名,消息可以是相同的,但签名也必须是始终相同的。这就是所谓的“强签名”。这是安全的吗?不。

假设你有一个签名方案——假设你正在使用Schnorr签名,这些签名特别容易受到攻击,比如1989年的原始Schnorr算法……攻击者获取了你的一个签名,他没有对签名进行调整,而是以一种保留消息有效性但更改公钥的方式对签名进行调整。他将获取一个针对一个公钥进行验证的签名,并生成一个与第一个公钥相关的签名。通过比特币,某种程度上你可以生成与代数相关的密钥,比如bip32分层确定性生成的密钥。

理论上来说,有人可以生成一个签名,其他人可以拿到这个签名的交易,在另一个交易上创建一个签名,这是针对不同密钥的代数关系攻击。

在实际情况中,这对比特币来说不是一个问题,因为基于比特币的设计,在比特币交易中签名的数据不仅包括有关交易的所有细节,还包括之前的交易(以及其公钥)。所以结果就是你得到了一个看起来像Schnorr签名的东西(除了公钥)……但事实证明,这比“强签名”更安全,这就是对签名信息和同一签名密钥的零知识签名。这比我想讲的要复杂得多。

在每一个步骤中,我都在强化安全的概念,并彻底消除伪造的可能性。我们花了一些时间来探索这个设计,研究伪造行为以及其在实际情况中的表现。对于签名,我能够在舞台上描述一个安全比赛,而不需要到处使用图表和箭头。多重签名则更加复杂。

当你谈论零知识证明——包含一个零知识证明和一个模拟器和所有不同的规则——试图证明这些复杂系统的独特性,部署更理想的模型等等,直到你得到一些具体的东西。然而,在现实生活中,拥有可证明的安全性具有巨大的价值。

可证明的安全性

接下来我想谈谈可证明安全的概念,尽管我告诉过你们这很难。其中一件事就是随机数生成的概念。我将把话题从定义安全性切换到部署安全系统实操。

基于ECDSA或Schnorr,生成这些签名需要生成一致随机数据。一致随机是指你可以选择所有可能的随机数——实际上是在0和某个固定的大素数之间。如果你没能随机生成数字,你在多个签名中重复使用相同的数字或相同的nonce,那么你的币就会被盗。这种情况已经发生过几次了,比如有人用这个小问题破解了ps3。2012年比特币就发生了这种情况,一些安卓钱包重复使用了nonces,并且生成了一个糟糕的随机数生成器。最终很多人的密钥及币都丢了。

并不是nonce被重用了。随机的nonces是存在的,但是有一些软件生成的nonces在某种程度上是有偏差的,比如前几位始终是0。即使与随机数无关,只要有足够的签名,也足以泄露你的私钥。所以我们有这些在学术模型中被证明是安全的签名方案,但他们总是需要一致的随机性。直觉告诉我们随机不能被猜出来,但这里随机和一致随机没有区别。把两者区分开来就足以打破学术证明,而在实践中,你会丢失密钥和币。

 总结

这些东西是困难而微妙的,对于那些自称能够创造神奇事物的新项目,你不应该感到兴奋,而是保持怀疑态度。比特币的发展速度非常快。我们需要慢下来,保持警惕。

转载声明:本文 由CoinON抓取收录,观点仅代表作者本人,不代表CoinON资讯立场,CoinON不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。若以此作为投资依据,请自行承担全部责任。

声明:图文来源于网络,如有侵权请联系删除

风险提示:投资有风险,入市需谨慎。本资讯不作为投资理财建议。

(0)
打赏 微信扫一扫 微信扫一扫
上一篇 2019年5月13日 下午7:20
下一篇 2019年5月13日 下午8:00

相关推荐

加密货币中的“加密”:为什么一切又怪又难

星期一 2019-05-13 19:22:00

加密货币中的“加密”:为什么一切又怪又难

注:本文为技术公司Blockstream研究主管Andrew Poelstra在纽约MCC会议中发表的演讲。他在演讲中从密码学讲到了数字签名的安全,指出签名机制的设计从理论和实际应用情况来看是完全不同的,因此对于很多自称能创造神奇效果的项目来说,用户应该更多选择保持警惕。同时,在他看来,比特币的发展速度惊人,因此从技术角度来看,适当地放慢脚步并没有错。

以下为演讲全文:

我没有准备PPT。我想要尽可能地让这次演讲不是那么技术,我试图剥夺自己在屏幕上写下方程式的权力。我演讲的主题是为什么在加密货币中所有的一切都是奇怪和困难的。从数学和科学角度来看,什么是密码学?其在实践中是如何运作的?

加密

从历史上看,密码学的用途是加密,就像试图想出一些随机的东西。这里的安全性很简单:如果你有一个密钥,那么你就可以解密一些东西,而使用一个安全模型或风险模型来描述它的想法实际上没有意义。

在现代,密码学已经取得了长足的进步,包括零知识证明。零知识证明是由计算机程序证明的,这些程序只对输入进行状态说明,而不泄露输入的细节。

数字签名和加密是相关的。签名类似于对两个密钥的加密,一个公钥和一个私钥。任何拥有公钥的人都可以加密数据,任何拥有解密密钥或私钥的人都可以解密数据。这也意味着经过加密的数据可以通过不安全的通道进行发送。

数字签名

数字签名正好相反——只有拥有私钥的人才能生成签名,只有拥有公钥的人才能验证签名。如果你想讨论这里方案的安全性,那就更难做到,也更难做出定义。我要讲的是学术背景下的数字签名,然后我要讲的是随机数生成的实际问题,然后如果我有时间,我要讲的是如何将其扩展到多重签名设置。

没有密钥的人就不能伪造消息和公钥的签名。从学术上来说,将其形式化是相当困难的。这里所说的形式化指的是做一个定义清晰的状态说明。

多年之后,我们尝试了很多次来找出这些定义——我们得出了这样的结论:如果不存在任何多项式概率时间算法可以成为主导,那么数字签名方案就是安全的。我们将绝对排除任何算法存在的可能性(只要其界限合理),绝对不能伪造。即使这样,在定义的时候,也很难证明其安全性。在现实生活中,有一个知道密钥的人,这个人应该能够生成签名。所以你怎么能明确排除一切但依然包含特殊情况?

假设在一场比赛中你有一个对手,你的对手无法赢得下面的比赛:我随机取一个私钥和一个公钥,我把公钥给了你的对手。如果他能生成一个签名,那么这个签名就是伪造的,这个方案是不安全的。

直观地来看,这是有道理的。你生成了一个随机密钥,对手没有私钥。对手唯一知道的关键只有公钥。然而,这种想法是错误的。这个方案的问题在于,对手掌握了这个公钥的大量签名,而类似GPG的东西可能在区块链上进行过电子邮件或者过往的比特币交易签名。这个公钥包含了一堆签名。现有的签名方案对能够看到公钥的对手是安全的,但对看到签名的对手是不安全的。这不应该是其运作方式,但现实仍然如此。这东西很难。有一种竞争币就有这个问题。有许多人声称能解决不可能解决的问题。但大多数人都在对你撒谎,这才是这次演讲的真正目的。

假设这个对手更强大,他可以向挑战者索要信息,而挑战者必须在这条信息上签名。现在,对手不仅可以伪造信息,而且是在我们给出了几乎所有可能给出的信息的情况下。我们想提供尽可能多的信息。因此,在任意消息上签名就足够了。当对手伪造信息时,他必须在一条新的信息上生成签名。

这安全吗?这在常规的安全概念下是安全的,又被称为选择信息攻击下的存在性不可伪造性。但是在更复杂的系统中,由于一些原因,这是不安全的。我们在比特币中发现,通过允许对手只在一条新消息上提供签名,我们排除了对手可能使用现有的签名并在保持其有效性的同时对其进行调整的可能性。模型中没有捕捉到这一点。一旦某条消息签名完成,谁在乎对手可以针对同一条消息产出不同的签名?

在比特币中,我们使用的ECDSA和txid都是基于这些签名的。所以攻击者有能力改变签名,允许他们改变交易的txid,这将保持交易的有效性,但会使任何引用该txid的交易无效,因为txid是有延展性的。所以我们需要一个更强的模型。

我们现在需要一个对手,我们说,如果其在某个消息上提供签名,消息可以是相同的,但签名也必须是始终相同的。这就是所谓的“强签名”。这是安全的吗?不。

假设你有一个签名方案——假设你正在使用Schnorr签名,这些签名特别容易受到攻击,比如1989年的原始Schnorr算法……攻击者获取了你的一个签名,他没有对签名进行调整,而是以一种保留消息有效性但更改公钥的方式对签名进行调整。他将获取一个针对一个公钥进行验证的签名,并生成一个与第一个公钥相关的签名。通过比特币,某种程度上你可以生成与代数相关的密钥,比如bip32分层确定性生成的密钥。

理论上来说,有人可以生成一个签名,其他人可以拿到这个签名的交易,在另一个交易上创建一个签名,这是针对不同密钥的代数关系攻击。

在实际情况中,这对比特币来说不是一个问题,因为基于比特币的设计,在比特币交易中签名的数据不仅包括有关交易的所有细节,还包括之前的交易(以及其公钥)。所以结果就是你得到了一个看起来像Schnorr签名的东西(除了公钥)……但事实证明,这比“强签名”更安全,这就是对签名信息和同一签名密钥的零知识签名。这比我想讲的要复杂得多。

在每一个步骤中,我都在强化安全的概念,并彻底消除伪造的可能性。我们花了一些时间来探索这个设计,研究伪造行为以及其在实际情况中的表现。对于签名,我能够在舞台上描述一个安全比赛,而不需要到处使用图表和箭头。多重签名则更加复杂。

当你谈论零知识证明——包含一个零知识证明和一个模拟器和所有不同的规则——试图证明这些复杂系统的独特性,部署更理想的模型等等,直到你得到一些具体的东西。然而,在现实生活中,拥有可证明的安全性具有巨大的价值。

可证明的安全性

接下来我想谈谈可证明安全的概念,尽管我告诉过你们这很难。其中一件事就是随机数生成的概念。我将把话题从定义安全性切换到部署安全系统实操。

基于ECDSA或Schnorr,生成这些签名需要生成一致随机数据。一致随机是指你可以选择所有可能的随机数——实际上是在0和某个固定的大素数之间。如果你没能随机生成数字,你在多个签名中重复使用相同的数字或相同的nonce,那么你的币就会被盗。这种情况已经发生过几次了,比如有人用这个小问题破解了ps3。2012年比特币就发生了这种情况,一些安卓钱包重复使用了nonces,并且生成了一个糟糕的随机数生成器。最终很多人的密钥及币都丢了。

并不是nonce被重用了。随机的nonces是存在的,但是有一些软件生成的nonces在某种程度上是有偏差的,比如前几位始终是0。即使与随机数无关,只要有足够的签名,也足以泄露你的私钥。所以我们有这些在学术模型中被证明是安全的签名方案,但他们总是需要一致的随机性。直觉告诉我们随机不能被猜出来,但这里随机和一致随机没有区别。把两者区分开来就足以打破学术证明,而在实践中,你会丢失密钥和币。

 总结

这些东西是困难而微妙的,对于那些自称能够创造神奇事物的新项目,你不应该感到兴奋,而是保持怀疑态度。比特币的发展速度非常快。我们需要慢下来,保持警惕。