Google的量子计算机真能破解比特币BTC吗?

比特币大家已经不陌生了,很多人之所以相信它的价值,是因为大家觉得靠数学算法背书比靠政府背书更合理,后者可能有太多的人为因素。至于比特币背后的技术,其实大部分人并不了解,有了之前我们学的数学基础,我们就可以谈谈比特币或者更广泛地讲,区块链的数学基础了。

为什么加密的本质是数学的不对称性?

从数学上讲,所有的加密货币之所以能够流通,而且不被破解,靠的是数学上一种不对称的美。人们通常喜欢对称,厌恶不对称,觉得后者不完美。在获取信息时,大家都希望透明,因为不透明、藏着掖着总让人感觉不踏实。但是,不对称有时却自有其妙处与美感,比如黄金分割就是不对称的。

对于信息安全来讲,完全透明、完全对称会带来很多安全隐患。当我们自己是信息的拥有者时,其实并不希望别人可以获得我们的信息,特别是私密信息,只不过常常为了便利,不得不开放许多信息的访问权限,好让对方验证真伪,知道我们是谁,或者能够让对方进行一些统计,来为我们提供更好的服务。过去,我们不开放信息,很多事情就做不成,比如你向银行申请贷款时,几乎就是把所有个人和财务信息开放给了银行。

在完全开放信息的社会里,彻底保护信息安全几乎是天方夜谭,这些我们在上一次加餐里已经说了。要想保护私有信息,特别是隐私,必须有一套不对称的机制,做到在特定授权的情况下,不需要拥有信息也能使用信息,在不授予访问信息的权限时,也能验证信息。

而比特币的意义就在于,它证实了我们可以通过加密和授权,兼顾保护信息不外泄,而且某些得到授权的人还能使用信息。

比特币做到这一点,是靠加密的密钥和解密所需要的密钥不是同一把这个特性。加密时用的密钥是所谓的私钥,只有比特币的主人有,解密的人用的则是由私钥生成的公钥,它可以给任何人。

这种加密的不对称性就在于,在有限的计算时间里,无法从公钥倒推出私钥。因此你可以认为拿着私钥的人,能看到全部信息,而拿到公钥的人,只能看到部分信息或者只验证信息的真伪。为了进一步理解这种非对称的特性,我们不妨看一个具体的例子。

假如,我们要卖房子,首先就要证明这个房子属于我们,有资格出售,过去我们要让买主看房产证,并且要由有关部门或者公证机构证明房产证是真的。这样来回来去多次,买房的人对你的很多信息就了解了,他们甚至就可以伪造一份和你一模一样的房契。

在未来,数字化的房产证可以用区块链来保存,作为房主,区块链的算法会给我们一个私钥,全部信息在你手上。然后可以产生相应的公钥给购房者,用于验证我们房主的所有权,这就足够了,购房者不需要了解我们的其他信息。

这个利用区块链协议验证房产证的过程,可以用一张图来说明:

当然,需要说明的是,购买者使用公钥后验证了房契的真伪。如果他购买了房子,房契会转到他的名下,并作废原来房主的私钥,然后新房主可以拥有新的私钥,这个过程都会记录在区块链的账本里。

区块链房地产

接下来,我们就来看看这件事在数学上是怎么做到的。我们还是以比特币协议为例来说明。它采用的是一种被称为椭圆曲线加密的方法。相比目前比较流行的RSA加密算法,采用椭圆曲线加密方法可以用更短的密钥达到相当或更好的加密效果。

那么,什么是椭圆曲线加密呢?我们就要从椭圆曲线及其性质说起。

椭圆曲线其实和椭圆没有什么关系,它是具有如下性质的一组曲线:y² = x³ + ax + b

这一类曲线的形状如下图所示:

椭圆曲线加密的原理

椭圆曲线加密的原理

这种曲线的特点是上下对称,非常平滑,具有很多很好的性质,特别是从曲线上的任意一点(图中的A点)画一条直线,它最多和曲线本身有三个交点(包括该点本身)。

那么这样一种曲线,与加密有什么关系呢?我们用下面的图来说明。

椭圆曲线上的点乘运算过程

椭圆曲线上的点乘运算过程

在图中,我们从A点出发,画一条线经过B点,最后又和曲线交于C点。利用这条性质,我们定义一种运算,叫做点乘“·”,我们用

A·B=C

来表示这三个点之间的关系,意思就是:从A点向B点连线,与曲线相交于C点。由于椭圆曲线是相对x轴对称的,因此我们做C关于x轴的对称点D,把D作为新的一个点,再与A点连一条线。于是,便与椭圆曲线又有了一个交点E,这么一连,就得到

A·D=E

然后我们可以不断重复这个过程。假设我们最后经过K次这样的点乘运算,停到了Z点。

注:在这个过程中,有四点需要作一下说明:

首先,点乘这个运算满足交换律和结合律,因此先算哪一步,后算哪一步结果是一样的。这个性质我们就不证明了。

其次,有可能这样的点乘计算了若干次后,某个交点的x值,即横坐标非常大,为了防止不断迭代后计算结果发散,我们在右边某个横坐标很大的地方设一个边界Max(最大值),超过Max后,再让直线反射回来。

再其次,虽然图中的曲线是连续的,每一个点的取值是实数,但是我们在真正使用时,是通过某种变换将它离散化了,因此所有的点都是整数值。

最后,有人可能担心,经过这一次次的运算,会不会又回到原来某个点了。这个不用担心,这个操作有点像两个巨大的素数相乘后,再对某个素数相除取余数(也被称为模运算,Mod),只要算法设计得好,和原来某个点重复的可能性近乎为零。

如果我们把上述曲线操作中的点乘想象为数字的乘法,经过K次点乘,就相当于做了K次方的乘方,那么当给定起点A和终点Z之后,K其实相当于以A为底Z的对数。因此,这种计算的过程便被称为椭圆曲线的离散对数计算。那我为什么要给你讲这个连来连去的计算过程呢?

我上面说的椭圆曲线的计算有一个特点,如果我告诉你一开始是从A经过B到C,再到D,到E等等,一共走了K步,你可以推算出最后停到了Z,这一过程直观而简单。但是,如果我告诉你起点是A,终点是Z,你要想猜出我经过了多少步完成上述过程,这几乎是不可能的,或者说,计算量是极大的。这种不对称性使得验证结果非常容易,但是想破解密码却难上加难。

具体到比特币所使用的加密协议,是一种被称为SECP256K1的标准,采用的就是下面这条非常简单的椭圆曲线:y² = x³ + 7

比特币椭圆曲线加密

利用上面这个在形式上非常简单的曲线,我们就完成了在外界看来非常复杂的加密。

椭圆曲线的加密方法有很多种,它们的算法和密钥的长度虽然各不相同,但是它们的原理却大同小异。美国国家标准与研究院已经规定了这一类算法的最小密钥长度为160位,再往上还有192位、224位,等等。它们都比RSA所要求的最短1024位短很多,这是椭圆曲线加密的优势所在。

那么这么短的密钥安全么?事实上,2003年,一个研究团队用一万台PC花了一年半时间破解了一个较短的109位密钥。但是,破译的时间是随着密钥长度呈指数增长的,破解160位的密钥需要大约1亿倍的计算量,破译192位、224位的密钥就更难了。因此,除非计算机的速度有百万倍的提升,否则很难破译椭圆曲线加密的信息。

当然,2019年Google在量子计算上取得了突破,在特定计算中,可以将原来需要上万年才能完成的计算在瞬间完成。因此很多人担心区块链的加密是否还安全,应该讲如果Google的技术真能走出实验室,而且能用于更多的计算,而不仅是特定的计算,目前的区块链加密算法要修改。

但是,椭圆曲线加密的思想依然是安全的,因为加密(以及验证密码的难度)和解密永远不对称,就算计算机的计算能力提高了万亿倍,那么可以使用更复杂一点的加密,那样量子计算也无济于事。总之,只要数学的这种非对称性存在,加密就是安全的。

VIA:吴军 数学通识

相关推荐

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址