比特币技术原理与应用-1 密码学基础

  • 符钦伟
  • 更新于 2020-04-02 10:45
  • 阅读 5829

刚开始接触比特币的同学,可能会听说比特币采用了多么高级的密码学技术,没有人能够破解。但是实际上比特币采用的密码学技术是非常成熟的,已经广泛应用于传统金融机构中。比...

本系列文章: 比特币技术原理与应用-1 密码学基础 比特币技术原理与应用-2 数据结构


密码学基础

刚开始接触比特币的同学,可能会听说比特币采用了多么高级的密码学技术,没有人能够破解。但是实际上比特币采用的密码学技术是非常成熟的,已经广泛应用于传统金融机构中。比特币中的密码学技术主要采用了哈希函数和数字签名。

哈希函数

哈希函数(Hash Function),其实有一个更通俗的名字——散列函数。(哈希是对Hash的音译,散列则是意译,中文博大精深啊)

举一个生活中常见的例子,来帮助大家理解一下散列函数。在学校里我们平常去取快递,快递小姐姐会让你报一下手机尾号后四位,然后去对应的货架上找你的快递。根据手机尾号KXXX,小姐姐会去货架K上面按照顺序一个一个查找你的快递。这就是一个散列函数,提高了找快递的效率。但是,散列函数会遇到碰撞的问题,先假设货架都是空的,第一个快递,手机尾号为0086的快递放在了货架0的左上角第一个位置,第二个快递,手机尾号是0010,小姐姐拿着0010快递来到货架0,发现左上角第一个位置被占了,已经有0086快递放着了。这就是两个元素取哈希之后发生了碰撞。但是小姐姐想着把0010这个快递放在0086快递的右边空位就好了。往后要是还有0XXX尾号的快递,就从货架0左上角开始查找空位置,找到空位摆放快递就行了。这就是采用线性探测法解决了碰撞问题

image20200401152929814.png

比特币中使用的哈希函数是SHA-256(Secure Hash Algorithm: 安全哈希算法),SHA-256接收输入数据后,无论输入数据1MB还是1TB还是更大,都会输出256位的二进制数,并且不同的数据输入会得到不同的256位二进制数。

image20200401161103716.png

比特币使用的哈希函数有三个重要特性:碰撞阻力(collision resistance),隐秘性(hiding)和谜题友好性(puzzle friendly)。

碰撞阻力

上面列举的快递手机尾号例子,两个手机尾号以0开头的快递可能会发生碰撞,那要如何才能保证两个0XXX快递不会碰撞?如果我们在货架0上准备1000个小隔间,编号0000-0999,这样对应的手机尾号可以直接找到对应的隔间,并且也不会被别的快递占位置。这样相当于我们扩大了输出空间,原本所有的手机尾号只可能有10个输出——货架0-货架9,现在是有10000个输出——小隔间0000-9999。

SHA-256的输出空间为$$2^{256}$$ 换算成10进制,约为$$10^{77}$$这个数是个什么概念呢?地球大约由$$10^{50}$$个原子构成,也就是说给地球上的每一个原子分配一个哈希值,还有剩余。

碰撞阻力是指很难找到两个不同的输入,经过SHA-256计算后得到相同的哈希值。 注意,这里没有说不可能找到,而是很难找到。因为输入空间是有限的,2的256次方,而输入空间是无限的,在理论上是可以找到的。但是在实际中,就算调用全世界的计算机来做运算,算到地球爆炸那一天都不一定能找到满足条件的输入,因此说在实际操作中很难找到哈希值相同的两个不同输入。

image20200401163305514.png

隐秘性

隐秘性是指通过H(x)无法推算出x。这样保证了哈希函数的单向性,x经过SHA-256计算得到H(x),但是想要通过H(x)逆运算得到x是不可行的。

image20200401164251782.png

谜题友好性

比特币中矿工挖矿,就是在解一个谜题,谁先解出来谁就拥有了记账权,就会得到比特币奖励。为了保持公平性,这个谜题肯定不能有最优解,只能通过暴力运算的方法来解题。

谜题友好性是指想得到满足某个条件的H(x),只能蛮力求解x,没有什么优美解法。

举个例子,有个谜题是求一个输入x, 使得 $$ H(x)<2^{128} $$ 我想解这个谜题,并没有什么优美的解法,我只能通过暴力运算的方法,不断试各种不同的输入x1,x2,...,直到求得xn使得 $$ H(x_n)<2^{128} $$

数字签名

我们日常生活中的需要签名的场景,比如很多材料需要给领导审批签字,领导的这个签名代表了领导已经审批并批准了该文件,签名将领导的公信力赋予一份文件,即领导为这份文件背书。

比特币中的数字签名是在你发起一笔交易的时候,证明你对即将支付的比特币拥有支配权。 也就是说你得证明这些币是你的,你才能转账给别人,数字签名就是为了干这事的。

数字签名采用了非对称加密算法,首先我们了解一下非对称加密算法和对称加密算法的区别

对称加密算法在加密和解密两个环节用的是同一个密钥,比如你事先知道我的密钥,我用同样的密钥加密一条消息并发送给你,你用密钥解开密文就可以看到我的消息。对称加密的缺点是一个密钥同时掌握在两个人手里,易丢失,难以保证安全性。

image20200401203018538.png

非对称加密算法,包含两个密钥:公钥和私钥,公钥是公开的,所有人都可以看到,私钥则是自己保存的。

在场景1中,小明想要发一条消息给所有人,首先小明公开自己的公钥,然后用自己的私钥加密消息并把密文发布出去,知道小明公钥的所有人都可以用公钥来验证这条消息,能够证实这条消息确实是小明发出来的。相反,大家想要给小明发消息,可以用小明的公钥加密一条消息,密文只有小明用自己的私钥能够解密。

在场景2中,如果是小明和小花都希望双方的通信消息是加密的,则小明生成公钥A和私钥A,小花生成公钥B和私钥B,公钥是公开的,双方互相知道对方的公钥。小明想要发消息c给小花,用小花的公钥B加密消息c,把密文cx发给小花,小花用自己的私钥B解密cx,得到消息c。相反,小花要发消息d给小明,就用小明的公钥A加密消息d生成密文dx发送给小花,小明用私钥A解密dx后得到消息d。

image20200401203040625.png

在比特币系统中,当你发起一笔转账交易的时候,用你的私钥签名,将交易信息和私钥广播发送给所有人,所有人都可以用公钥来验证签名,从而证实这笔交易确实是由你发出的。

image20200401212940225.png

小结

以上介绍了比特币中使用的密码学基础知识,其中哈希函数具有三个特性:碰撞阻力、隐秘性和谜题友好性,数字签名则通过非对称加密算法提高了消息发送的安全性。

参考文献:

  1. 北京大学肖臻老师《区块链技术与应用》公开课
  2. 《区块链 技术驱动金融:数字货币与智能合约技术》[美] 阿尔文德·纳拉亚南(Arvind Narayanan),约什·贝努 等 著,林华,王勇,帅初 等 译

欢迎大家提出问题,批评指正。

点赞 2
收藏 2
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
符钦伟
符钦伟
让一部分人先懂区块链