区块链科普（一）数字签名与密码学

科普

比特币、区块链的兴起

最近很多人都发现，不流行炒股而流行炒币。一种叫做“比特币”的纯虚拟货币突然走进了公众的视野。传说很多人一夜暴富，更有英国的程序猿追悔莫及、去垃圾箱刨自己几年前的硬盘。

那么，到底什么是区块链？什么是比特币？它因何出现、解决了什么问题、又为何成功？和我们虚拟账户上的余额有什么本质区别？

这篇（以及之后（如果能有的）的几篇）推送，将会努力为大家科普最基本的区块链入门知识。【但是还是老样子，慢慢来，前面很多铺垫可能会比较dull】
去中心化的含义

话说，当年有个村子叫赵家村，赵家村经济不是很发达，大家对于物品虽有大致的价值衡量，却没有货币。于是，赵村长提出，他给全村记账，格式如下：
2018.4.1：王老五欠张麻子两袋红薯

2018.4.9：张麻子欠李书记三只鸡

……

可是久而久之，很多问题就出现了……

什么情况？我明明啥也没拿，赵村长
为啥记我欠小赵一担米？

不知道呀，上次赵村长欠我羊的那笔账

，说没就没了，也不知道找谁说去。

嗨呀别提了，村长一天记那么多账，

谁知道有没有记错过……

账本上意外或并非意外的错误越来越多，大家都觉得不对劲，可无奈整个村子只有这个账本是唯一的权威。大家无力、无权监督。

直到有一天，村长不知道为什么，卷着村头村尾不计其数的鸡鸭牛羊的账，突然消失了，整个村子的经济也一下陷入了混乱……
发现了吗？一切问题的源头，都出在全村一切的经济活动都以村长的账单作为唯一的中心和参照。这样会带来很多问题，第一是中心的负荷很高，错误率也随之提升；第二则更加严重，唯一的中心很容易出现垄断、集权、腐败、被操控利用或者是突然崩塌导致瘫痪的风险。把上面的村长换成银行，你就很能理解被突然倒闭的银行卷走存款的用户的心情了。

所以，中本聪（Satoshi Nakamoto）这才提出了去中心化的思想，在论文中第一次提出了Peer-to-Peer network的概念……

换回到之前赵村的例子，村民们吸取经验教训，在每家每户门口都挂了块黑板，全村的人没事也会互相传抄，全村账单同步。这样，就不会有人有能力简单的翻云覆雨了【例如抹掉全村每个人黑板上自己的欠债记录】。所以，现在每家每户门前都写着诸如：

王老五欠张麻子两袋红薯
【王老五签名】

张麻子欠李书记三只鸡
【张麻子签名】

……

任何一个想要加入到这个村子交换体系中的人，都必须竖起这样一块黑板，并且保持着同步。

这里有些地方需要注意：
签名是很重要的，安全性能必须保障
道理很简单，如果有一个人能够随意伪造他人签名，那么整个制度形同虚设，因为他可以随便胡扯别人欠了自己钱和任何东西，而大家除了欠债者本人的签名，别无任何真实性的考证，只能传抄。所以，必须完成对签名安全性的保证。

然而，这件事情，容易却也不容易

数字签名：非对称加密体系
为什么说容易呢？细心的朋友可能刚才就敏锐的察觉到了一个矛盾，那就是：不能有人伪造签名，和我能够完美的复制一份签名到我自己的黑板上，似乎是矛盾的呀。伪造和复制的区别在哪？

原因是，在计算机网络的世界里，所有的签名都是数字的（即一串长度固定的01码），所以，当你传抄签名的时候，只需要直接复制那一长串的01二进制码就可以了。这也是我说容易的原因，现实世界你可没那么容易就把签名完美复制。

但最困难的地方却也在这容易复制上。

容易复制，意味着我们没法像现实中的签名那样在一笔一划间存储个性化的风格信息。一切都是以固定长度的01的字符串表示的，那么，凭什么你就能说这串数字签名只有你本人能够生成呢？

复制：意思是指能够保持所有信息原原本本的传输到别处，但是不改变其真实性

伪造：你能够欺骗大家，生成一段合法的全新的签名
首先，我们要知道一个神奇的函数，叫做
哈希函数
HASH
在这里哈希函数的作用，就是把一串输入的文本（字符串）转换成一串二进制码。但是，这是一个高度单向的函数。什么意思呢？就是，你把一个字符串喂进去得到输出的01串很容易，但是想要根据01串倒回去推导是什么字符串，则几乎是不可能做到的事情。

例如，比特币所使用的Hash算法SHA-256（Security Hash Algorithm，安全哈希算法），对于哈姆雷特的经典台词，给出的256位01串（为了方便写成64位十六进制串）是这样的：
To be or not to be, it is a question.

51614A7923A8B9E7253DB844D31DA910F2265B7B8A045DD7226DAF781200EBBE

我们把最后的句点去掉。

To be or not to be, it is a question

655F0CE857DA19FD76207917C4FD944B9B4419BCF819E988ADA3C928DB08CE7F
发现了吗？哈希函数值完全不同。
让我们再把it is改成it's

To be or not to be, it's a question

9C27C9E59C7D7C34EC889B40A1FCCEACEB791324C3B4FB0B9FBA8F989472433E
SHA-256具有很高的黑箱性质和安全的随机性，你可以认为这个函数内部几乎是以一种完全乱映射的方式把字符串映射成为01数字的。

可是问题来了？怎么检验主页菌是不是口胡了上面三串数字呢？
方法很简单，可以自行百度“SHA-256在线生成”，输入三段对应的文本，看看是不是一样的字符串。

也就是说，你虽然不能根据数字串简单反推出字符串是什么，但是你可以检验我是不是在口胡。

换句话说，假如我说小李欠我一顿饭，我能做的事情，不是根据小李写在黑板上的签名倒推出那句话，得到“5月2日小李欠LR一顿饭”；而是把“5月2日小李欠LR一顿饭”的句子输入哈希函数，看看结果的01串是不是跟他写的一样。

当然了，全村肯定都约定好了同样的一个记账语法格式，那就是时间+欠债人+“欠”+债权人+金额这样的格式，方便检验。

可是还有问题……

但是，既然人人百度都能找到哈希函数生成器，记账的规则又都一样，那岂不还是能够轻易的做出假账来？

所以，在我们得到这个原始的函数值之后，我们还需要做一步“个性化”操作，而正是这个个性化操作，使得这个01串带上了“非我莫属”的色彩，大家都可以复制我的签名，但是想要产生一个有效用的签名，只有我自己能做这个个性化操作。

有人会说，那不简单嘛，我也设置一个“谜之函数”，它乱七八糟的把一个01串瞎变换成另一个01串，这样这个操作就很个性化了。

可是不行

为什么呢？因为你同时还要能让别人鉴别，就像刚才的哈希函数SHA-256一样，你需要公开你的这个“谜之函数”，让别人得以鉴别的确这个谜之操作得到的是这个结果。但是一旦公开这个“谜之函数”，别人也就立刻可以拿着你的函数伪造你的签名了。

于是核心的困难点出现了：
如何在不暴露自己加密方式的情况下，人人都可以验证这是不是一个合法的加密呢？
首先把一长串整数拆成散列值（也就是一段段），然后逐一加密。我们先直接给出每一段的整数x的加密方法，然后简单解释一下原因：

加密方法：
选择两个很大的不一样的质数p和q，其中p和q除以3的余数都是2，设N=pq。注意到(p-1)(q-1)除以3的余数是1,所以一定有一个整数t使得3t除以(p-1)(q-1)的余数是1。然后把x^t除以N的余数y、以及乘积N公之于众。
验证方法：
把得到的加密结果y做三次方，求出其对N的余数，即为原来加密之前的原文x
上面这个套路，其核心就是大名鼎鼎的RSA公钥体系。以下我们将从几个角度来理解它：

RSA公钥
1.上面这坨东西为什么对
2.上面这坨东西为什么安全
铺垫：费马小定理
对于任何一个质数p和不是p的倍数的整数a，都有：

两边(q-1)次方我们有

同理有：

根据p和q都是质数我们有：

所以，当我们先把x做了t次方得到y，再把y三次方后，结果变成了

（请注意这里用到了3t是一个除以(p-1)(q-1)余数为1的整数,所以3t=k(p-1)(q-1)+1）

AMAZING!验证者在毫不知情的情况下，只需要进行三次方就可以变回原来的原文x，进而验证其正确性。更关键的是，验证者除了三次方之外，并不能获得任何加密者加密机制的信息。

等等！谁说没有泄露？
你在告诉别人每次运算都需要取的余数N的时候，N=pq，分解式里就透露出两个质因子p和q了，我只要掌握了p和q，就能找到你的“个性化操作”——t次方的那个t，那不就可以仿造签名了吗？

话是这么说没错，但是，以目前的人类了解来看，将一个很大的整数分解成两个质因数的乘积是一个非常困难的事情，随便动动手指头加个几位数字，计算机需要运算的时间就要翻番。

但是前些日子计算机学界提出了基于量子计算机的Shor算法，并在实践中完成了对15=3*5的分解，这个算法是可以在很快的时间（几乎是多项式）内完成大整数分解的，换言之密码体系遭受到威胁。这也是为什么每次量子计算机的发展，都会引起密码学界的不安。

于是到这里，终于把非对称的加密体系——也就是数字签名的原理讲完了，相信你对于区块链还有不少疑惑：

挖矿是怎么回事？
为什么挖矿越来越难？
为什么说比特币总数是有限的？
区块链是怎么同步的？

那就记得关注后续系列（主页菌争取能活着写完这个系列……）

漫士呓语，欢迎关注~

写的好累的，欢迎打赏