密码学-比特币的数学基础

一、密码学的本质

很显然，之所以要有密码，是想对信息保密，而之所以要保密，是出于政治、军事、经济以及个人的利益而着想。那么可想而知，一旦密码被破译，将产生极为严重的后果。

所以，密码学的思考方向总结来说有两点：一个是要有一套加密解密的规则（或者数学算法），二是研究如何在现有规则（算法）的基础上确保所传递信息安全的策略。通俗点讲，我们传递信息时主要是要防备信息的泄露。那么我们首先想到的是防止消息在传输过程中被第三方截获，比如说话被偷听、邮件被偷看、网络数据被窃取。而事实上，在现代技术极大透明的情况下，不被窃取是很难做到的，所以，我们要保证的是，即使数据被窃取了，窃取者也无法使用。而要做到这一点，只要双方事先约定一套加密解密的方法，以密文的方式传输信息，就可以有效地防止信息泄露。

二、什么是哈希算法

在早期，传统加密方法是不能公开的，因为知道了加密方法，只需要反向计算就能解密。那么，有没有一种加密方法，使得即使知道了加密方法，也不能恢复出原文呢？随着技术的进步，尤其是数学理论的扩展，密码学也得以发展，现在我们只需要在加密过程中加入一些不可逆的运算就可以达到这个目的。我们来举个例子，Bob想向Alice递一些小秘密，但为了防止Bob说谎，我们可以这样做：

1.Bob先设想一个数，并加上123456。

2.把结果平方，取第3～10位，组成一个8位数。

3.再用这个数除以456789求余数，然后把这个结果告诉Alice。

4.Alice猜测Bob设想的是奇数还是偶数。

5.Bob告诉Alice原始数字，Alice按照上面的过程再计算一遍，看结果是否和Bob给的结果一致。

我们假设Bob设定的是1234，按照上面的过程依次得到：

1234 123456=124690

124690×124690=15547596100

54759610mod456789=401719（Mod表示除法求余数）

Alice拿到的结果是401719，这样既可以验证Bob有没有撒谎，同时Alice又很难根据401719反向算出123456。这样也不能绝对保证Bob不作弊，但如果Bob想作弊，他就必须事先找到一奇一偶两个数，它们按照上面的运算能得到一样的结果。这个难度取决于上面算法的难度。

而在密码学中，这种会丢掉一部分信息的加密方式被称为“单向加密”，也叫作哈希算法。

一个可靠的哈希算法至少需要满足下面几个条件：

1.对于给定的数据M，很容易算出哈希值X=F（M）；

2.根据X很难算出M；

3.很难找到M和N令F（M）=F（N）。

目前在互联网世界中，被认为安全且被广泛使用的哈希算法包括MD5、SHA-256等。哈希算法的结果长度都是固定的，MD5的结果长度为32个字符，SHA-256则达到64个字符，所以SHA-256看起来更安全一些，更难找到能算出相同结果的M和N。比如“1234”使用MD5算法计算的结果是81DC9BDB52D04DC20036DBD8313ED055”，而用SHA-256算法计算出的结果是“03AC674216F3E15C761EE1A5E255F067953623C8B388B4459E13F978D7C846F4”。

然而，这种单向加密算法并不能用来进行普通的信息传输，更多是用来进行传输结果的准确性验证。很多下载网站都提供了下载文件的原始MD5值供校验，以防止文件被病毒修改。

三、非对称加密

现在我们来看一下在真正要进行信息传输的情况下应该怎么办。同样假设Alice和Bob要通过互联网传输一份绝密情报，那么，如何阻止第三方在网络上截获信息呢？对于我们普通大众来说，一般是使用如WinRAR等 工具 对文件进行加密压缩，然后通过电子邮件或者QQ把加密的文件发过去，同时，通过发短信或者打电话把解压密码告诉对方。但是，若是重大的商业情报或者国家的绝密情报，这种做法很显然非常容易被窃取并破解。那么怎么办呢？这里我们有两种思路可以尝试解决：

1.密码学世界有一个柯克霍夫原则：即使密码系统的任何细节已为人熟知，只要密钥（key）未泄露，它也应是安全的。无论是在战争时期还是和平时期，都不能把保密的希望寄托于系统或算法的秘密性。机械可以拆解，软件可以反编译。密码系统的所有细节总会被有心人一一拆解。这个时候，如果系统符合柯克霍夫原则，那么即使对手拆解了系统但不知道密钥，他也没有办法破译加密的信息。满足这种严苛条件的密码系统才是安全的。

2.要是有一种加密系统，加密和解密使用不同的密码，假设有2个密码A和B，使用A对数据M进行加密得到加密数据X=F（A,M）。但是，知道A和X无法解密出M，必须用另一个密码B使得数据还原M=F（B,X）。Alice只需公布密码A，Bob使用公开渠道拿到的A对情报进行加密，再通过任意方式发给Alice进行解密，这样一来，即使所有的通信被监听，对手也不可能拿到情报。

如果使用我们设想的这些神奇加密算法，似乎问题就可以迎刃而解了，但问题是，这样的技术存在吗？听上去似乎并不可能，因为从直觉上判断，知道了加密方法就一定知道解密方法，只需要反过来计算就可以了。加密方法和解密方法是否可能不对称？有可能！

四、数学小魔术的秘密

我们来看一个小时候经常在《趣味数学》这类书里看到的数学小魔术：让对方任意想一个三位数，并把这个数和91相乘，然后说出乘积的最后三位数，就可以猜出对方想的是什么数字。比如对方想的是123，那么对方就计算出123×91＝11193，并把结果的末三位193告诉我。看起来，这么做似乎损失了不少信息，我可能没法反推出原来的数。不过，我仍然有办法：只需要把对方告诉我的结果乘以11，乘积的末三位就是对方刚开始想的数字了。可以验证一下，193×11=2123，末三位正是对方所想的秘密数字！其实道理很简单，91乘以11等于1001，而任何一个三位数乘以1001后，末三位显然都不变（例如123乘以1001就等于123123）。先让对方用他所想的数字乘以91，假设乘积为X；我再在X的基础上乘以11，其结果相当于我俩合作把原数乘以了1001，末三位自然就变了回去。X乘以11后的末三位是什么只与X的末三位有关，因此，对方只需要告诉我X的末三位就行了，这并不会丢失信息。知道原理后，我们可以构造一个定义域和值域更大的加密解密系统。比如，任意一个数字乘以400000001后，末八位都不变，而400000001=19801×20201，于是你乘以19801，我乘以20201，一个加密解密不对称的系统就构造好了。我们甚至还可以构造一个更大的系统：

4000000000000000000000000000001=1199481995446957×3334772856269093，这样我们就成功构造了一个30位的加密系统。这是一件非常酷的事情，任何人都可以按照这个方法加密一个数字，但是只有自己才知道怎么把所得的密文变回去。

但如果仅仅按照上面的思路，如果对方知道原理，知道我要构造出带很多0的数，根据19801和8位算法这两个条件其实可以比较容易地穷举出400000001这个目标值。要解决这个问题，我们来看看真实世界是怎么处理的。

五、RSA算法与椭圆曲线算法

直到1976年以前，所有的加密方法都是同一种模式：

1.甲方选择某一种加密规则，对信息进行加密；

2.乙方使用同一种规则，对信息进行解密。

由于加密和解密使用同一种规则（简称“密钥”），这被称为“对称加密算法”。这种加密模式有一个最大的弱点：甲方必须把加密规则告诉乙方，否则无法解密。这样一来，保存和传递密钥就成了最让人头疼的问题。尤其是人数多了之后，每两个人都要互相商量一个密钥，复杂性大大提高，而传递密钥则带来更高的安全风险。

直到1977年，李维斯特、沙米尔和艾德曼设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫作RSA算法。直到现在，RSA算法一直是应用最广泛的非对称加密算法。毫不夸张地说，只要有计算机网络的地方，就有RSA算法，其非对称加密模式的流程如下：

1.乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。

2.甲方获取乙方的公钥，然后用它对信息进行加密。

3.乙方得到加密的信息后，用私钥解密。

由于公钥加密的信息只有私钥解得开，因此只要私钥不泄露，通信过程就是安全的。

RSA算法为什么更加安全呢？在数学世界里，有一些公认的、需要消耗极大计算量才能得出结果的难题，比如大数因式分解问题、离散对数问题、椭圆曲线问题。RSA算法正是用到了大数分解这一相当犀利的不对称难题。比如对于我们上面构造过的30位加密系统：

4000000000000000000000000000001=1199481995446957×3334772856269093

反过来算乘积非常容易，但是要把4000000000000000000000000000001分解成后面两个乘数，在没有计算机的时代几乎不可能成功！而一旦数字长达数百位，即使是超级计算机也需要耗费海量的时间来计算才有可能。

椭圆曲线算法（ECC）则是另一种著名的非对称算法，在比特币体系里占据重要地位，是比特币钱包安全性的密码学基石，也是比特币被称为密码学货币（Cryptography）的原因。

ECC各方面的性能和RSA比起来几乎完胜：

1.安全性能更高。比如160位ECC与1024位RSA有相等的安全强度。

2.计算量小，处理速度比RSA快得多。

3.存储空间占用小。密钥尺寸和系统参数与RSA相比要小得多。

4.带宽要求低。

ECC的这些特点使它逐渐取代RSA，成为通用的公钥加密算法。