#1 比特币的密码学原理

sam_nau

2019年12月01日 23:46

收录于文集

共3篇

0 最前

这一篇文章对应肖老师课程的P2

12:03

172.3万观看 3.3万弹幕

北京大学肖臻老师《区块链技术与应用》公开课 01-课程简介

1 哈希函数

比特币中的哈希函数，是cryptographic hash function（密码哈希函数），是hash function（哈希函数）的一种。

下面我将先带大家复习一下函数的定义（1.1），然后简单介绍一下hash function哈希函数的基本性质（1.2），然后我会按照老师的视频，讲三个比特币中哈希函数的性质：

collision resistance（1.3）
hiding property（1.4）
puzzle friendly（1.5）

1.1 函数

函数有一个映射的定义

对于集合A中的任意一个数x，在集合B中都有唯一确定的数y与之对应。

要注意：

集合A中的元素a，都能找到有且仅有一个集合b中数与之对应；即不存在f(a)=b1，又有f(a)=b2的情况
但是，存在f(a1)=b，同时又有f(a2)=b的情况

1.2 哈希函数是一种函数

哈希函数本质上你们可以理解为是一个特殊的函数。它首先符合函数的映射定义。

我们记y=H(x)为哈希函数，其中x我们成为输入值，y我们成为哈希值。

哈希函数的特殊性体现在：

输入x可以为任意字符串。即，x可以是这样的中文，也可以是一部电影、一首歌、一个软件等等（因为这些东西在电脑里都是字符串）
输出y，是一个固定长度的字符串。即，无论一个哈希函数的输入值是什么，它的输出值，都是固定长度的字符串。比如，比特币使用的SHA256哈希函数，输出就是256位的二进制数（如下图，256位二进制转换为十六进制就是64位）

SHA256加密过程

1.3 比特币用到的哈希函数的3个性质之一：collision resistance

collision resistance，即抗碰撞性。

①首先要知道，什么是collision（碰撞）

对函数f(x)而言，存在x1≠x2，使得f(x1)=f(x2)，即碰撞

②那什么是collision resistance，即抗碰撞性。

我们很难人工的去找到（即除了穷举brute-force外）一组x1≠x2，使得f(x1)=f(x2)

要注意的是，collision resistance，并不是collision free。以SHA256为例，其输出空间为2^256，如果我们的输入空间为2^256+1，那必然发生碰撞。而事实上，如果我们的输入空间达到了2^130次，就有99%的可能发生碰撞。关于这块数学问题，我们称之为“生日碰撞问题”，想要简单了解的同学，可以观看李永乐老师的视频。

10:49

6.6万观看 480弹幕

手机支付中的数字签名是如何保证信息安全的？李永乐老师讲解生日碰撞和哈希函数（2018最新）

如果想要深入了解其推理过程，可查阅该文章：

http://www.ruanyifeng.com/blog/2018/09/hash-collision-and-birthday-attack.html

③collision resistance性质的作用

检测软件是否被更改：对于一个软件的安装包，官方可以在其官网公布一个哈希函数H(x)，和对该软件包求哈希的一个哈希值y。网友可以用他下载到的该软件安装包，用公布的哈希函数求哈希值y1，比较y1与y是否相等，就可以发现该软件是否被更改。（）
检测上传到云端的文件是否被更改（老师举例）：上传文件前先求该文件的hash值，过段时间下载该文件后，再求一次hash值，比较两值是否相等即可知道文件是否被篡改

上述两个case中，由于无法人工制造hash碰撞，因此坏人如果想搞更改软件安装包或者你上传的文件，必然求得的哈希值会改变。

④collision resistance并不是永恒的

（这段我自己写的，如果有误请私信告诉我）

我国著名密码学家王小云教授，就找到算法，人工制造了哈希函数MD5的哈希碰撞，使得MD5函数安全性收到了冲击。

这块我想要啰嗦一下……为什么人工制造了哈希碰撞，函数安全性就大幅降低了。我们以上述软件安装包为例。某坏人在某软件安装包中植入密码后，新安装包的哈希值与安装包就不一致了，但是由于该坏人掌握了人工制造哈希碰撞的方法，他只需要在新安装包中再做修改（比如增加一些无用的内容），使得新安装包的哈希值与原安装包一直，这样网友运用collision resistance的原理就检测不出来软件经过修改。所以我说安全性大幅降低了。

如果无法人工制造哈希碰撞，那么坏人就只能用brute-force蛮力穷举，这种工作量就巨大到不可能了。

1.4 比特币用到的哈希函数的3个性质之二：hiding property

①hiding property的含义

hiding property，大家可以理解为单向性。即，对于函数y=H(x)，给定输入x，能够很容易求得哈希值y。但给定哈希值y，很难求得输入x。通俗的说，除了brute-force蛮力求解（穷举）外，函数不可解。

②hiding property成立的前提

输入空间要足够大，不然很容易可以遍历完。
输入空间分布要比较均匀，各种取值的可能性要差不多。简言之，不能为蛮力求解提供方便。

③hiding property性质的作用

hiding property+collision resistance结合，可以实现digital commitment or digital equivalent of sealed envelope。

老师的举例：某股票大神，预测第二天某些股票会涨停。但是他不能提前公布出来，因为他的猜想会影响股市。他要把他的猜想放到一个“密封的信封”中。这个时候，他可以这么做：将他的猜想x，求哈希值y。然后他可以把哈希值公布出来。这个时候，由于hiding property单向性，韭菜们无法知道这位大神写的是什么。而由于collision resistance，第二天股市收盘后，这位专家也没办法按照股票收盘后的结果，重新找到一个x'，是其哈希值y'=y，即他无法更改他的猜想。

实际操作中需要注意的是，由于股票就那么几只，即输入的空间很有限，那么坏人就可以通过brute-force的方法暴力破解，从而hiding就不hiding了。所以上面说，输入空间要足够大才可以。

那么这位大神要怎么做呢？他可以将他的猜测的后面拼一个随机数nonce，比如大神的猜想是“亨通光电和恒力股份”，那么大神要在后面拼一个随机数“亨通光电和恒力股份1234567890”，整体取哈希值。

1.5 比特币用到的哈希函数的3个性质之三：puzzle friendly

所谓puzzle friendly，意思是对于哈希函数，他的输出是无法预测的，要找到特定区间内的哈希值的输入x，没有捷径。（）

比如，我要找到SHA256函数的哈希值，前60位都是零，我除了一个一个试验以外，没有其他的方法。

3 签名

这一节，老师上课主要讲了两个内容，一个是比特币中账户如何生成，另一个是简单提了一下非对称加密体系。因为这一部分老师讲的比较浅，但是后面的内容，实际上需要稍微深入理解一下数字签名的内涵，所以我这边写的稍微多了点。

我在下面附带了两个视频，分别是妈咪说的讲非对称加密的数学原理（主要是前半段），和好奇猫的讲数字签名的。其中妈咪说的讲的非常深入，尤其是ecc曲线那边，确实很难懂，大家也不用太沮丧。而好奇猫将数字签名还是很好懂的，大家可以2倍速看一看。

3.1 比特币中的账户管理

①比特币如何开户

比特币中如果你要开户（账户地址），只需要创建一对公私钥即可。

随机数生成器生成私钥 ➡️通过私钥创建公钥（ECC） ➡️通过公钥创建账户地址（2次哈希）

（盗图）也可用这张图来解释，其中公钥到地址需要两次哈希运算

其中，公钥可以公开出去，大家给你的账户地址转账就汇到你账户地址就可以了。

如果大家想要了解私钥如何通过ECC生成公钥，其安全性和其中的数学问题，可以看下面这个视频（相信我，你们看不懂的）

25:03

14万观看 2199弹幕

椭圆曲线加密与哈希函数是什么？非对称加密是什么？比特币中的数学原理

②产生公私钥的过程，需要好的随机源

为了防止坏人疯狂生成私钥，从而生成公钥，从而生成地址，来达到攻击的目的（如果找到和某人地址一样的地址，就可以获得这个人的私钥），比特币生成私钥的生成器，需要非常好的随机源和非常大的输出空间。并且要求在从私钥生成公钥的过程中，也要有非常好的随机源（理解这句话，还是要看一下上面妈咪说的视频，虽然也看不懂）