文科生也能懂的比特币数学原理

已过立秋，但上海室外温度还在30℃+，虽然比7月份凉快了些许，但中午的太阳底下依然待不过五分钟。吓得我赶紧上楼，开了瓶82年的雪碧压压惊，继续跟大家聊聊比特币那些事。
   比特币（bitcoin）是一种能够快速交易、安全性高、不受地域限制，优秀的数字货币。它们需要消耗真实的资源（CPU时间和电力）来生产，所以它们是有价值的，它们不能够被重复使用，也不会消失，这是比特币的一个通俗的定义。大家都知道，金属货币依靠天然的产量限制其货币发行量，靠天然的化学属性来防伪，并且依靠其特有的稀缺性来保证购买力。同样的，纸币依靠中央银行的领导和经济专家来决定货币发行量，靠提高制作工艺和更先进的验钞机来防伪，而且可以依靠货币发行国的主权信用和军事国防能力来保证购买力。那么有童鞋就有疑问了，比特币靠什么来保证这些特性呢？
   在比特币的世界里，甚至可以延伸至基于区块链技术的货币世界，他们都是依托于数字世界的规则。通过数学，更切确地说是通过密码学来保证比特币种种不可思议的特性。
接下来我就和大家谈一谈比特币用到的数学基础，有童鞋一听数学马上脑袋就炸了。什么，你跟我一文科生（数学小白）谈数学？
   大家别慌，我采用举例说明的方式尽量把原理演绎清楚。另外对于有更高要求的学霸朋友，以延伸阅读的方式把其余技术和数学知识贴出，争取做到雅俗共赏。
一、密码学和协议
密码学主要关注有两点，一是加密解密的数学算法本身，另外一点是如何在现有算法基础上实现各种安全需求。
这两点有什么区别呢？举个栗子，以防止“消息泄露”为例：我们首先想到的是防止消息在传输过程中被第三方截获，比如说话被偷听、邮件被偷看、网络数据别窃取。而事实上，小偷是防不住的，但我们可以保证数据即使被偷了，窃取者也无法使用。只要双方事先约定一套加密解密的方法，以密文的方式传输信息，就可以有效地防止信息泄露。
实际情况可能比消息泄露还复杂，加密算法的方案并不适用。还是举个栗子吧，假设一家公司某小组有10个员工，他们都想知道组内平均月薪是多少，但都不愿意透露自己的月薪情况，公司HR也不允许他们这样做。有什么办法可以既得到答案又不泄露各自薪水数额呢？其实办法很简单，甚至不需要用到密码学知识。第一个人随便想一个数，比如12345，接着在纸上写上自己月薪与这个数字之和并传给第二个人；第二个人再在这个数字上加上自己的月薪，然后将最新数字写到另一张纸上传给第三个人；直到最后一个人把纸条传回第一个人，第一个人用字条上的最终结果减去只有自己知道的12345，就得到了所有人的月薪总和，而且每个人都没有泄露自己的薪水。
以上两种情况分别对应了密码学的两个研究方向：密码学不仅研究加密解密的数学算法，更多时候，它还研究信息安全策略，我们称之为“协议”。
二、哈希算法
现在设想这样一个场景：爱丽丝和杰克，也可以是罗斯和杰克，不重要，有个这样的概念就行。说回我们的爱丽丝和杰克，这两位童鞋商量明天一早谁先去教室打扫卫生。两个人都不想去，于是杰克想了一个办法：“我扔一枚硬币，你猜一下是正面朝上还是反面朝上。如果猜对了，我去打扫卫生。如果猜错了，嘿嘿......"如果爱丽丝和杰克此时是面对面地站在一起，那么这个策略当然没有问题，可以说相当公平，甚至可以用更简单的办法，比如石头剪刀布。可是，如果他们是通过网络聊天的方式商量，那爱丽丝显然不会同意这个办法，因为她担心自己无论猜正面还是反面，杰克都会说她错了。
   有什么办法可以保证通过网络聊天的方式也能做到公平扔硬币呢？有人会说，那我们给扔硬币的结果加个密吧。现在假设任意奇数都代表硬币的正面，任意偶数都代表硬币的反面。杰克随便想一个数，然后乘以另外一个数，把结果先告诉爱丽丝，比如1234×531=622254，杰克想的是1234，然后把622254这一结果告诉爱丽丝，并声称另一个秘密数字531是密钥，由他自己保管。但这样做显然也不行，这样杰克依然立于不败之地。但是如果杰克事先把密钥公布出来呢？这样也不行，因为爱丽丝知道密钥后可以直接算出原始数字，便失去了保密的作用。
   传统加密方法不能公开的原因是知道了加密方法也就知道了解密方法，只需要反向计算就能解密。那么，有没有一种加密方法，使得即使知道了加密方法，也不能恢复原文？有的，我们只需要在加密过程中加入一些不可逆运算就行了。这次杰克又设计了一种新的加密方式：
1.杰克先设想一个数，并加上123456。
2.把结果平方，取第3~10位，组成一个8位数。
3.再用这个数除以456789求余数，然后把这个结果告诉爱丽丝。
4.爱丽丝猜测杰克设想的是奇数还是偶数。
5.杰克告诉爱丽丝原始数字，爱丽丝按照上面的运算公式再计算一遍，看结果是否和杰克给的结果一致。
假设杰克想的依然是1234，按照上面的过程依次得到：
1234+123456=124690
124690×124690=15547596100
54759610mod456789=401719
（Mod表示除法求余数）
   爱丽丝拿到的结果是401719，既可以验证杰克有没有说谎，同时爱丽丝又很难根据401719反向算出123456。
   这样也不能绝对保证杰克不作弊，但如果杰克想作弊，他就必须事先找到一奇一偶两个数，它们按照上述的运算能得到一样的结果。这个难度取决于上面算法的难度。
在密码学中，这种会丢掉一部分信息的加密方式被称为“单向加密”，也叫做哈希算法。一个可靠的哈希算法至少需满足下面几个条件：
1.对于定义的数据X，很容易算出哈希值Y=F（X）；
2.根据Y很难算出X；
3.很难找到α和X令F（X）=F（α）。
   真实世界的哈希算法比上面的过程要复杂得多，但原理是类似的。而且即使对于很长一段数据，仅仅改变一个子母，也会造成二次哈希结果的巨大差异。被认为安全且在互联网中被广泛使用的哈希算法包括MD5（消息摘要算法第五版）、SHA-256等。这种单向加密算法并不能用来进行普通的信息传输，更多是用来进行传输结果的准确性验证。很多下载网站都提供了下载文件的原始MD5值供校验，以防止文件被病毒修改。常用的BT（比特流）下载也是通过特定的哈希算法来确认每一部分数据是否下载完成。
确定要往下看？这可是学霸区哦
三、非对称加密（延伸阅读）
   现在我们来看一下在真正要进行信息传输的情况下应该怎么办。
   同样假设爱丽丝和杰克要通过互联网传输一份绝密情报，那么，如何阻止第三方在网络上截获信息呢？如果是一般情况，可能的步骤是使用文件压缩工具，比如WinRAR对文件进行加密压缩，然后通过电子邮件或者QQ把加密的文件发过去，为了更安全，或许还会发短信或者打电话把解压密码告诉对方。但是作为绝密情报传输的操作人，面对的可能是国家机器，所有的网络和通信工具都处于被监听状态，如果按照上面的过程，依然会造成信息泄露。如果想办法把密码加密后再发过去，但是给密码加密的方式又该如何确定呢？如果爱丽丝和杰克事先认识，或许可以见面并约定将出生日期加上手机号作为密码，但更多情况下，双方并没有可以利用的公共秘密。
   传统密码世界一直需要面对这样一个看似死循环的无解问题。这里我们有两种思路可以尝试解决。
第一种，专门设计一个秘密的加密算法，使对方即使拿到密码也没有办法解密。如果是绝对的军事需求、能邀请高水平的数学家来确认算法的安全性，这样确实没有问题。但如果是互联网通用技术，如果不公开算法的细节，恐怕没有人肯使用。密码学世界有一个柯克霍夫原则：即使密码系统的任何细节已为人熟知，只要密钥（key）未泄露，它也应是安全的。无论在战争时代还是和平时期，都不能把保密的希望寄托于系统或算法的秘密性。机械可以拆解，软件可以反编译。密码系统的所有细节总会被有心人一一拆解。这个时候，如果系统符合柯克霍夫原则，那么即使对手方拆解了系统但不知道密钥，他也没有办法破译加密的信息。满足这种苛刻条件的密码系统才是安全的。
第二种方法更绝。要是有一种加密系统，加密和解密使用不同的密码，假设有2个密码A和B，使用A对数据M进行加密得到加密数据X=F（A，M）。但是，知道A和X无法解出M，必须用另一个密码B使得数据还原M=F（B，X）。爱丽丝只需要公布密码A，杰克使用公开渠道拿的A对情报进行加密，再通过任意方式发给爱丽丝进行解密，这样一来，即
使所有的通信被监听，对手方也不可能拿到情报。当然，这里依然有一个缺陷，即杰克如何确定自己拿到的密码A确实是爱丽丝给出的，而没有被别人替换掉，不过这是另一个关于可信认证的话题，这里暂时不展开讨论。
   如果使用我们设想的这些神奇加密算法，似乎问题就可以迎刃而解了，但问题是，这样的技术存在吗？听上去似乎并不可能，因为从直觉上判断，知道了加密方法就一定知道解密方法，只需要反过来计算就可以了。加密方法和解密方法是否可能不对称？
   有可能！答案就是RSA算法与椭圆曲线算法（ECC）！
   1977年，李维斯特、沙米尔和艾德曼设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。直到现在，RSA算法一直是应用最广泛的非对称加密算法。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。这种算法为什么这么晚才出现？或许类似的技术一直隐藏在“二战”的迷雾中不为人知。
   这一非对称加密模式的流程如下：
1.乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。
2.甲方获取乙方的公钥，然后用它对信息进行加密。
3.乙方得到加密的信息后，用私钥解密。
   由于公钥加密的信息只有私钥解得开，因此只要私钥不泄露，通信过程就是安全的。RSA算法为什么更加安全呢？在数学的世界里，有一些公认的、需要消耗极大计算量才能得出结果的难题，比如大数因式分解问题、离散对数问题、椭圆曲线问题。RSA算法正是用到了大数分解这一相当犀利的不对称难题。比如对于：4 000 000 000 000 000 000 000 000 000 001=1199481995446957×3334772856269093，反过来算乘积非常容易，但是要把4 000 000 000 000 000 000 000 000 000 001分解成后面两个乘数，在没有计算机的时代几乎不可能成功！而一旦数字长达数百位，即使是超级计算机也需要耗费海量的计算时间才有可能。这么说可能还是不够形象具体，我举个栗子吧。
   大数因式分解记录RSA200，一个共有200位的非特殊数字，在2005年，计算机花了18个月时间才把它分解成两个素数。2007年3月6日，一个国际组织打破了这个保持了两年之久的记录，来自3个机构（洛桑联邦理工学院、波恩大学、日本电话电报公司）的计算机集群在经历了11个月的计算后，终于成功地把一个有名的很难分解的大数——2^1039-1分解为素数因子。
   椭圆曲线算法（ECC）则是另一种著名的非对称算法，在比特币体系中占据重要地位，是比特币钱包安全性的密码学基石，也是比特币被称为密码学货币（Cryptography）的原因。
ECC各方面的性能和RSA比起来几乎完胜：
1.安全性能更高。比如160位ECC与1024位RSA有相等的安全强度。
2.计算量小，处理速度比RSA快得多。
3.存储空间占用小。密钥尺寸和系统参数与RSA相比要小得多。
4.带宽要求低。
ECC的这些特点使它逐渐取代RSA，成为通用的公钥加密算法。
   比特币所用到的数学基础就给大家介绍到这里了，希望比特币能够被更多IT圈和投资圈外的朋友们所熟悉，一起感受比特币这种新型数字货币的魅力。

浏览过的版块