如果量子计算时代到来,我们的比特币安全吗?

安比实验室 2019-10-28 08:59

Editor's Note

【量子时代的到来不可避免,巨大的变革将会带来无尽的机会,区块链、密码学与数字资产安全无疑是未来十年的焦点,请扔掉包袱,与我们一起前行】


量子计算对挖矿的影响更多的是芯片升级的经济问题,而不是安全问题。


撰文:李画、安比实验室创始人郭宇

校正:郭宇

 
每次有量子计算的新闻出现时,人们都要担心一次比特币。原因很简单,比特币是基于密码学的,而密码学之所以能够成立,是基于某种计算上的不可能性。如果量子计算把原本不可能或难以实现的计算变成可以计算,那么这种密码学的方法就会失效。
 
这种担心是多余的。原因同样简单:我们只要有量子计算也无法完成的计算,不就可以吗?以这种计算为基础构建的密码学方法(量子安全密码学),量子计算也就无法破解,然后把比特币升级到该密码学方法之下即可。
 
「格困难问题」就是典型的代表,即便对于量子计算,它也保持着计算上的不可能性。基于人类的「无知」,我们很大程度上总可以找到方法生活在密码学的保护之下。
 

比特币中的密码算法
 
我们知道比特币钱包地址对应一个公钥和一个私钥,只有拥有私钥才能动用该钱包中的比特币,但私钥是安全的,它无法通过钱包地址或公钥被计算出来。

这是如何实现的?让我们从台球厅开始。
 
你去台球厅打台球,把一个球放在台球桌底边的一个位置上,就叫它 A 点,然后你把这个球打出去,假设你击球的力气超级大,那么球从 A 点出发,总会撞到台球桌某条边上的一个点,然后又会从该点弹到台球桌另一条边上的另一个点……它可能这样弹了 B 次(比如一万次),最后停在了台球桌某条边的一个点上,就叫它 C 点。
 
这时候你的朋友来了,他能看见台球在 C 点的位置,你告诉他这个球最初的位置 A 点和击球的角度,问他这个球中间弹了多少次,也就是 B 是多少?你的朋友应该一时回答不上来。
 
这就是一个简单的公、私钥生成算法,C(位置)是公钥,B(次数)是私钥。在我们知道 A 点和 B 次弹跳的情况下,是能得到 C 点的;但如果我们只知道 A 点和 C 点,是很难算出弹跳次数 B 的。
 
在真正的密码学中,台球桌的边被换成了椭圆曲线,A 是椭圆曲线(其实是椭圆群)上一个固定的点,它击打自己(球从该点的切线位置被击打出去),球在椭圆群里撞来撞去撞了 B 次,最后落在了椭圆群的一个点上,还要对该点再做一次映射,有了椭圆群上的一个点 C。C 是公钥,B 是私钥。
 
这就是著名的椭圆曲线算法,被用于生成公钥、私钥,是比特币系统中的第一个密码学方法
 
椭圆曲线算法难以被破解(基于「离散对数困难问题」),但并非不能被破解,足够强大的量子计算可以找到多项式算法,通过 A 和 C 计算出 B,也就是可以通过公钥算出私钥。所以,如果真的进入到量子计算时代,椭圆曲线算法是需要被新的抗量子计算的算法替换的
 
量子计算与椭圆曲线算法

比特币采用的椭圆曲线数字签名算法的安全性是 2^128(secp256-k1 曲线群的阶接近于 2^256,椭圆曲线攻击算法的复杂度大约都是 O(sqrt(N)),对 2^256 开平方,得到2^128 )。这是个天文数字。
 
在量子计算的情况下,使用 Peter Shor 提出的 Shor 算法,它攻击椭圆曲线的复杂度大概是 O(log(N)^3) ,对于比特币而言,理论上的计算量级是 128^3 次。
 
相关论文研究显示,构造一个攻击 secp256-k1 曲线的量子计算机,假设该计算机能把比特错误率降低到 10^-4,那么有希望在使用 170 万个量子比特的情况下,在 7 天之内完成计算。
 
在比特币系统中,还有另一个密码学方法,哈希函数 SHA-256,它被用于生成与公钥对应的钱包地址。该算法很好理解,就是把一个输入以一种不可逆的方式转换成一个输出,它有非常强的单向性,想通过输出来计算输入是不可能的
 
因此,哈希函数只能通过暴力的方式破解,也就是变换输入值一次次去试,直到可以用某个输入值算出目标输出值。

相较于经典计算机,量子计算机在暴力搜索上具有可观的优势,不过仍然是一种多项式级别的性能优化,我们可以通过加倍安全位数,比如采用 SHA-512 来维持安全性
 
比特币钱包地址是公钥经过两次哈希计算得到的,一次是 SHA-256,一次是RIPEMD-160(另一种哈希函数),量子计算很难攻破两道哈希关口,通过钱包地址「撞」出公钥。
 
量子计算与 SHA-256

目前在量子算法里可以加速计算SHA-256 的是Lov Grover 在1996年提出来的 Grover 算法,它可以将暴力搜索的性能提高到平方倍。假设我们要在一个 N× N 的巨大方格里寻找一根针,经典计算机需要逐一搜索每一个方格,最坏情况下需要搜索N×N 次;但Grover 算法即使是在最坏的情况下也只需要搜索 N 次。

总结一下:比特币中有两种基础密码算法,一是椭圆曲线算法,一是哈希函数 SHA-256。目前能够找到前者的高效量子计算方法,实现破解;但并没有找到后者的高效量子计算方法。当然,破解的前提是量子计算真的发展到足够强大,要知道,谷歌最新的量子芯片只有 54 个量子比特。
 

我们的比特币安全吗?
 
如果进入到量子计算时代,我们只需要用抗量子计算的密码学算法生成公钥、私钥、钱包地址即可。但假如用户未能升级公钥私钥,他们钱包中的比特币是否就一定会被窃取?答案是否定的。

大致有如下几种情况:
 
1. 如果钱包地址中的比特币从未被使用过,那么该地址的公钥是不被人知晓的,其他人所知道的只有钱包地址(只有当我们花费某地址上的比特币时才需要给出公钥,不过哪怕只花费过一次,公钥就会被广播到全网)
 
如前文所述,SHA-256 是难以被量子计算破解的,这意味着其他人是无法通过钱包地址算出公钥的。所以,即使可以通过公钥算出私钥,那些没有暴露过公钥的钱包地址也是安全的
 
2. 如果有好的比特币使用习惯,一个钱包地址只使用一次,那么同理,新地址的公钥也是不被人知晓的,新地址中的比特币是安全的。
 
3. 如果用户重复使用一个钱包地址,那么该地址对应的公钥就处于暴露状态;如果量子计算破解了椭圆曲线算法,那么该地址中的比特币就面临被窃取的危险。
 
据统计截止到当前,有将近 500 万个比特币是存放于公钥暴露的地址中的,此外还有将近 177 万个比特币使用的是 P2PK 地址,这是最早期的比特币账户格式,公钥是公开的,其中就包括被认为是中本聪的账户。如果这些比特币不更换地址,它们是在量子计算攻击范围内的(数据来源:安比实验室)
 
除了钱包地址,在比特币系统中还有一个重要的地方使用到了 SHA-256,那就是挖矿。挖矿就是暴力破解哈希函数的过程,通过调整输入值「撞」出落在目标区间的输出值。
 
如前文所述,从理论上讲,量子计算机芯片在暴力搜索时是可以「碾压」经典计算机芯片的,但我们同样需要考虑到它的技术发展水平和芯片制作工艺。此外,芯片本就是随着技术的发展不断升级的,量子计算对挖矿的影响更多的是芯片升级的经济问题,而不是安全问题
 

量子计算下的安全:格密码
 
在量子计算发展的同时,量子安全密码学也在飞速发展,这其中最具代表性的是「格密码」,它是基于格的密码体制(lattice-based cryptography)
 
「格」是一个系数为整数的向量空间,可以把它理解成一个高维度空间,它有两个基本的「格困难问题」,一是最短向量问题,一是最近向量问题,求解这类问题需要指数时间的复杂度,那么如果因子为多项式,这类问题就不存在多项式时间算法,对于量子计算也是一种计算上的不可能性。
 
这听起来有些抽象,也许可以这么去理解:用笔在一张 A4 纸上画出很多黑色的点,然后换支笔在纸上画下一个红色的点,我们需要做的是找到距离红点最近的黑点,这很容易;现在从 A4 纸这个二维空间到一个三维空间,想象一下空间里漂浮着很多黑色的点,这时放一个红色的点进去,同样是去找距离红点最近的黑点,这并不算很难,但相对于二维空间,其困难度已经不在一个级别了
 
现在,我们把三维空间变成一个三百维的空间,给定一个红点去找距离它最近的黑点,这个黑点一定存在,但想想看,找出它是不是几乎不可能?这就是格困难问题
 
格空间与椭圆曲线是相似的。在椭圆曲线上,可以有数学公式(椭圆曲线算法)把公钥和私钥放在一个等式的两头,在格空间里,也有数学公式(比如LLL算法)可以把类似黑点和红点的东西放在一个等式的两头,那么我们就可以利用这类公式来生成公钥和私钥。
 
在椭圆曲线算法中,因为「离散对数困难问题」,传统计算机无法通过公钥计算出私钥;在格密码的算法中,因为「格困难问题」,量子计算机也无法通过公钥算出私钥。
 
格密码发展很快,基于格我们不仅有抗量子计算的公钥和私钥,还有抗量子计算的对应于经典密码概念的一系列密码学算法或协议,它们可以被用于数字签名、密钥交换、零知识证明等等应用领域。
 
「宇宙相信加密。加密容易,解密难。」在可以预见的未来,依然如此。所以,不用担心,对于比特币是这样,对于区块链也是。
 

参考资料

[1] Arute, Frank, Kunal Arya, Ryan Babbush,Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas et al. "Quantumsupremacy using a programmable superconducting processor." Nature 574,no. 7779 (2019): 505-510.
[2] Andreas M. Antonopoulos答疑量子计算问题:
www.youtube.com/watch?v=eo7mwcsUbdo;www.youtube.com/watch?v=wlzJyp3Qm7s
[3] Gentry, Craig. "Fully homomorphic encryption using ideallattices." In Stoc, vol. 9, no. 2009, pp. 169-178. 2009.
[4] Aggarwal,Divesh, Gavin K. Brennen, Troy Lee, Miklos Santha, and Marco Tomamichel."Quantum attacks on Bitcoin, and how to protect against them." arXivpreprint arXiv:1710.10377 (2017).
[5]Stewart, I., D. Ilie, Alexei Zamyatin, Sam Werner, M. F. Torshizi, and WilliamJ. Knottenbelt. "Committing to quantum resistance: a slow defence forBitcoin against a fast quantum computing attack." Royal Society openscience 5, no. 6 (2018): 180410.
[6] Regev,Oded. "Lattice-based cryptography." In Annual International CryptologyConference, pp. 131-141. Springer, Berlin, Heidelberg, 2006.





往期回顾

探索零知识证明系列(一):初识「零知识」与「证明」

探索零知识证明系列(二):从「模拟」理解零知识证明

探索零知识证明系列(三):读心术:从零知识证明中提取「知识」

zkPoD:区块链,零知识证明与形式化验证,实现无中介、零信任的公平交易

PoD-Tiny——实现零信任交易的最简协议

zkSNARK 合约「输入假名」漏洞致众多混币项目爆雷

Move语言:我眼中的 Libra 最大亮点




Image

长按二维码添加微信进群讨论零知识证明

info@secbit.io

安比(SECBIT)实验室








Modified on 2019-10-28

Scan to Follow