SHA-256加密算法浅析

　　利用显卡挖矿获得数字化的“矿产”，再换成金钱是Geek玩家中的一件时髦的事情。那么，挖矿是如何进行的？挖的究竟又是什么？今天，本文就结合密码学和数学的内容，为大家介绍有关比特币挖矿背后的故事。

　　无论是比特币还是莱特币，大家都已经非常熟悉了，本刊也在之前做过很多次如何用显卡挖矿的文章。挖矿成为近年来玩家们讨论得最多的事情，市面上的高端AMD显卡也一卡难求。不过，电脑究竟是如何挖矿的，挖矿时CPU、GPU甚至专用的大规模集成电路ASIC究竟计算的是什么内容？这些内容对人们的生产生活有用吗？请听我们下面的分解。

　　为了搞清楚比特币在算什么，先来看看有关比特币计算方法的内容。如果抛开一些繁杂的技术背景来说，比特币计算内容可以用下列公式来表示：

　　SHA256(SHA256(version+prev_hash+merkle_root+ntime+nbits+x》

　　在上述式子中，x使用了加粗的黑体字来表示。比特币的算法就是为了寻找到这样一个x，使其符合整个公式的需求。在这个看起来很复杂的公式中，涉及到的内容如下：

　　1．比特币区块的版本号：version

　　2上一个区块的散列值：prev_hash

　　3．需要写入交易记录散列数的值：merkle_root

　　4．更新的时间：ntime

　　5．当前的难度：nbits

　　根据比特币相关算法的定义，×的值存在于0到2的32次方之间，TARGET是已经给定的、根据当前难度求得的数值。比特币算法的特点在于：由于散列的性质，比特币需要的那个x只能通过计算得出，而没有任何的捷径可走。这个x就是BlockHash，找到合适的Block是一件非常困难的事情，需要通过大量的计算来得到，该计算过程就是挖石广J首个发现Block的人将获得比特币奖励（目前是25个比特币，未来的产量还会减半）。持续的挖矿为整个比特币系统的正常运转提供动力，不断接入新的Block延续Block Chain的过程。如果节点的算力为整个比特币网络的n%，那么该节点就有n/-100的概率找到这个Block Hash。

　　找到Block Hash，也就是公式里的x，可以做什么用呢？答案很直接：除了获得比特币外，就没有任何用处了。在整个比特币计算体系中，挖矿有三个重要的功能，一是在21 00万的总量达到前获得新的货币；二是维系货币的吏付功能；三是通过算力保证整个比特币系统的安全。也就是说，计算本身的价值是和比特币的价值直接相关的，它既不能贡献计算结果给科研机构（比如寻找外星人、蛋白质折叠等都是大规模计算项目，但它们的结果是有用的），也不能创造产值，它只是计算出了一个相对无意义的数据，通过这个数据和比特币的关系，为计算赋予了价值。金矿通过资源的消耗生产黄金，然后注入流通领域。电脑挖矿也一样，通过电力和时间的消耗，得到比特币，然后又注入交易系统。

　　还有一个问题：比特币为什么这么难算呢？

　　实际上，除了比特币本身的特性：比如生产速度在一定的区块被找到后自动降低一半，整个比特币的规模被限定在21 00万个，使得比特币在后期产量越来越少外。比特币所使用的算法诸如SAH-256和其他的一些加密算法，本身也需要耗费大量的计算量。从计算角度来看，SHA算法是比特币数学结构的核心，没有SHA算法，比特币的安全性将不复存在。在上文给出的比特币简述计算公式中，SHA-256成为其中最核心的内容。那么，SHA是什么意思呢？除了在比特币使用外，SHA还在哪些地方有应用呢？

　　SHA的全名是Secure HashAlgorithm，简写为SHA，翻译过来兢是安全散列算法。散列的英文是Hash，也被翻译成“哈希”。安全散列算法，顾名思义，它的安全性是被最优先考虑的。散列算法的方法其实比较多，包括HAVAL、MD2、MD4、MD5（就是我们常见的MD5值的算法）、PANAMA、SHA家族等多个算法。其中最重要的是SHA家族，SHA家族是由美国国家安全局设计，由美国国家标准与技术研究院发布的、注重安全性和加密性的算法。在详细解释SHA有关内容之前，先来了解—下散列和散列函数的相关知识吧l 散列其实不难理解。从方法上来说，它是一种将原数据，通过特殊的算法，变换成另一种便于搜索的、固定长度的新数据的方法。新数据和原数据之间存在一定的关系，这样人们可以通过查找新数据，得到原数据的相关信息。

　　简单打个比方来说，如果有1 200头小猪，怎么才能最快速的找到其中的X号猪呢？传统的方法只能一一比对，这样的速度太慢了。但是换一种方法，考虑到这些小猪的体重在某个量级（比如精确到克，假设小猪的体重从不改变）上都是完全不同的，体重的范围从60干克到120干克不等，那么按照10公斤为级别划分很多个层次，这样可以列出如下体重散列表：

　　(60，70，80，90，100，110，120)

　　表里面一共7个数。接下来，人们建造了7个猪栏，分别将计算出体重散列相同的小猪赶到一起（假设平均每个猪栏有200头猪）。这样当某人要查找X号小猪时，只要知道它的体重，比如1-12干克，就可以知道小猪在1 1 0千克对应的围栏，然后再去查找小猪，搜索的范围就大大缩小到-1/200了。

　　当然，jl/200还是比较难找。如果这个养猪场的实力强大，完全可以多建猪栏，比如建立60个猪栏每个猪栏只有20头猪左右。如果还觉得难找，还可以继续细分下去。不过分得越多，要求空间也就越大，存储也就越麻烦；分得越少，数据越简单，但是每个数据指向的内容变多，也就显得没有那么方便了。

　　从上例可以看出，散列实际上就是原数据的一种映射，它通过专门的函数计算，将原数据和新数据之间建立起特殊的关系。在生活中这样的例子其实非常多。比如我们的字典为了查找方便，就建立了字母拼音x到首字母(y)的一种函数关系，用户可以直接通过查找首字母来快速得到相关的字——不但首字母使用了特殊的、方便使用的排列方法，字典中字所对应的拼音的第二个字母甚奎第三个字母，都使用了相关的排序，这样大大方便了人们的查找和使用。

　　具体到数据加密上，散列以及其代表的散列函数被广泛应用在数据加密计算中。散列函数的特点是能够将任意有限长度（常常有规定）的数据映射为固定长度，并且在没有计算方法的情况下，是几乎无法被逆向计算的，因为散列算法在计算中依1日丢失了原文的部分信息。为什么会丢失信息呢？本文举个稍复杂一点的例子来说明：

　　需要加密的文字为：微型计算机

　　加密特征值取“笔画数+拼音首字母的排列数”。比如“微”字，笔画13画，拼音的首字母“VV”是23，那么特征值是“13+23=36”。

　　其余的几个数字分别是：

　　9+24=33， 4+10=14， 14+j19=35，6+10=16。然后所有的数字都除以1 0取余数，得到6，3，4，5，6，相加后得到24作为最终的密文。

　　最终的密文就是24。

　　当24被公开出去后，谁都不知道这代表的是“微型计算机”这几个字，因为大量的信息在计算过程中被抛弃了。但如果知道算法的话，很容易就能验证“微型计算机”代表的是24。甚至可以根据这套算法，制造一个解密表，将所有的常用词汇都以数字的方式代指，最终就可以形成一个完整的密码本，可以轻松加密解密了， 不过问题又出现了，很多情况下，别的一组词汇，最终计算出来的结果也是24，这怎么办？这就是散列算法的碰撞问题。所谓碰撞，是指两个不同的明文，经过计算后，得到完全一样的密文，这样的结果会导致数据可靠性降低。举例来说，如果发生碰撞现象，两份经过散列函数处理的文件都拥有一样的最终值的话，那么在接收到最终值的用户眼中，就无法区分哪一份是真的，哪一份是假的了。以上题为例，假设“微型计算机”和“微型故事会”经过计算后密文都是24，当用户得到这个数字后，他就无法确定自己需要购买的是《微型计算机》还是《微型故事会》了。

　　遗憾的是，目前已经确定所有的散列函数都存在碰撞可能（可以被信息学方法证明）。那么，这是不是降低了散列函数的安全性呢？在某些程度上是有可能的，不过实际应用中的散列函数都经过了极为艰辛的筛选，经过筛选后，散列函数的“抗碰撞”能力变得极为强大。一般来说，在可能使用到的内容中，用户几乎不可能遇到两组信息都拥有完全一样的散列计算结果的情况。因此散列算法在很大的程度上依1日是可靠的。

　　说完了散列和散列函数，那么什么叫做安全的散列算法呢？根据官方描述，SHA之所以被称之为“安全”，是基于以下两点：

　　首先，白信息摘要反推原输入信息，从计算理论上来说是非常困难的。这句话的意思是：使用了SHA算法后，即使你看到最终的散列计算结果，也很难知道原来的内容是什么。当然，任何函数都有被反推从而计算出来的可能，也没有任何人试图否认这种可能。但是，这种计算方法所需要的资源以及计算的难度，尤其是计算量的难度，超过了人们目前所能掌握的计算能力（当然不排除一些特殊的算法，但绝大部分情况下，反推SHA函数都只能依靠暴力破解）。

　　其次，想要找到两组不同的信息对应到相同的信息摘要，从计算理论上来说也是很困难的（抗碰撞能力极好）。任何对输入信息的变动，都有很高的机率导致其产生的信息摘要迥异。这一点的意思是说，SHA的算法，可以将任两组不同的信息，经过处理后生成完全不同的计算结果。任何对原始信息的哪怕极为微小的改动，都会导致计算结果极大程度的差异。 虽然单独看起来，满足第一条和第二条都不算困难，但是既要满足相当复杂的加密性能，又要维持非常优秀的抗碰撞能力，在实际使用中并不容易。SHA是人们经过长期选择后发现的最为安全、优秀的散列算法之一，它能同时满足人们对安全性和稳定性的要求。 目前的SHA算法已经发展出了一个家族，其中包含SHA1、S HA-224、SHA-256、SHA-384、SHA-512多个算法。其中最古老的算法是SH A--I，后面四个算法会被统称为SHA-2。相比SHA-1，SHA-2的保密性更强，更为难以破解。

　　由于其优秀的加密效果和保密能力，SHA家族被广泛应用在计算机加密、文件加密等诸多方面。此外，目前大名鼎鼎的比特币等虚拟货币，也是用SHA算法进行加密。为了确保安全性，比特币的计算中不仅采用了SHA-256算法，还采用了诸如ECDSA椭圆曲线加密算法。在整个比特币的计算中，需要进行多次SHA-256的计算或者相关变换，使得最终的结果更为复杂并难以破解。

　　本文向大家介绍了很多散列算法以及其安全性的内容。那么，这是不是意味着散列算法本身的安全性就毋庸置疑了呢？答案是否认的。

　　1993年，SHA最初发布的是SHAO版本，但是友布后即被美国国家安全局撤回。在1998年的CRYPTO会议上，最初的SHA算法SHAO就被宣布可能会有攻击方式。两位法国研究者认为，存在一种算法，使得SHA-O的安全性达不到一个理想散列函数所必须拥有的抗攻击能力所具有的复杂程度。很快，在2004年的CRYPTO2004上宣布了SHAO以及MD5等采用类似算法的散列函数攻击完成。2004年8月，在美国加州圣芭芭拉召开的国际密码大会上，并没有被安排发言的王小云教授拿着自己的研究成果找到会议主席，没想到慧眼识珠的会议主席破例给了她15分钟时间来介绍自己的成果，而通常发言人只被允许有两三分钟的时间。王小云等人展示了MD5、SHA-O及其他相关杂凑函数的杂凑冲撞。所谓杂凑冲撞指两个完全不同的讯息经杂凑函数计算得出完全相同的杂凑值。根据鸽巢原理，以有长度限制的杂凑函数计算没有长度限制的讯息是必然会有冲撞情况出现的。一直以来，专家都认为要任意制造出冲撞需时太长，在实际情况上不可能发生，而王小云等的发现可能会打破这个必然性。就这样，王小云在国际会议上首次宣布了她及她的研究小组近年来的研究成果——对M D5、HAVAL-128、MD4和RIPEMD等四介著名密码算法的破译结果。这篇论文引发了一片哗然，人们对SHA-O以及M D5的安全性产生了质疑。

　　随后的SHA-O以及M D5算法也有过一些补救措施，比如在信息中加入随机的特征值（加盐），这样降低了被攻破的可能性。但随着超级计算机越来越先进，由于算法本身的缺陷，此类算法的安全性已经不足以保证绝密级别信息和内容的安全了，因此很快就被业内整体放弃。当然，对绝大部分民用内容来说，SHA-O的算法安全还是够用的。

　　随后王小云也在2005年宣布SHA--I告破。相比SHA--I所需要拥有的2的80次方计算量的安全性而言，王小云等人提出的算法在2的63次方以内就能寻找到碰撞性。但令人稍感安慰的是，这样的计算难度其实也非常夸张，一般的内容也没有必要进行如此高强度的暴力攻击。

　　好在由于计算算法的调整以及计算难度大幅度增加，目前SHA-2家族的破解算法虽然有一些论文出现，但是依1日维持了很好的安全性。美国国家安全机构也推荐有需要的用户尽快迁移到更为安全的SHA-2家族算法上来。

　　好戏还没结束，让MD5、SHA-O、SHA--I、SHA-2家族算法感到难受的是“彩虹表”的出现，让这些算法都遇到了穷举的威胁。所谓彩虹袁，就是穷尽所有算法可能的密码表格。对DM5和SHA-I这样的以快速计算为目的算法而言，如果用户只是快速加密，并且数据没有经过“加盐”处理，那么彩虹表的存在就基本上决定了这些密码已经彻底变得不安全。因为目前的彩虹表已经纳入了大部分MD5和SH A--I算法的明文和密文，以及部分SHA-256等加密算法的结果。

　　彩虹表是典型的“空间换取时间”的方法，目前市面上最大的彩虹表已经超过了jIOTB以上，包含了几乎目前可以计算出来的所有的加密信息，用户只要查询一次花费大约几秒钟时间就能通过密文得到明文。

　　除了本身数学上的算法外，目前也有部分专家认为SHA系列算法是美国宣布的，美国很可能在其中留下了难以发现的漏洞，由于“棱镜门”的出现，这样的质疑变得越来越多。但是一些用户也称，同样作为密码大国的德国、法国、俄国和中国，都没有对SHA系列算法提出任何政治和学术意义上的质疑，并且在行业中广泛使用，因此安全性是可以保证的。

　　由于SHA家族算法优秀的加密效果，因此被广泛应用在计算机加密、文件加密等诸多方面。比如很多银行、购物网站都使用SHA算法对用户的敏感信息进行加密。用户输入的任何信息，包括身份证号码、登录密码、银行卡号等，在首次输入时，就使用SHA加密变成密文存放在银行的系统中。当用户需要消费成者购物的时，用户输入自己的信息和密码后，计算机再次进行计算，并且将用户本次输入的数据计算的结果，和之前SHA加密后存留的结果进行对比。如果信息相符，就允许用户操作。这样做的好处非常明显，比如相关的工作人员在没有权限的情况下，很难知道用户的密码和部分敏感信息的情况，此外，所有的信息都是以密文的方式存储，即使信息泄露，只要对方不知道算法，还是无法解密。此外，在一些带有加密功能的设备上，比如加密USB闪存盘、加密移动硬盘等设备，都往往会使用SHA家族的算法对数据进行加密。虽然前面我们提到过SHA算法的破译，但王小云教授的方法只是缩短了找到碰撞的时间，找到的是强无碰撞，要能找到弱无碰撞，才算真正破解，才有实际意义，再加上破解的时间相当长，所以大可以放心。

　　对于SHA这样的散列加密算法而言，数据相关性意义并不大，因此适合于使用诸如GPU、特定的大规模集成电路进行快速的、并行的计算。对SHA在GPU上计算的研究，在2008年后有很多的研究。尤其是在比特币诞生后，对SHA-256的GPU并行算法的研究就更为成熟了。

　　对GPU而言，支持拥有大量逻辑判断的操作是极为困难的。但是SHA-256的算法仅仅是单纬的数学计算，没有太多的逻辑内容，基本操作是由大量的32位整数循环右移运算组成，因此在GPU上不但容易并行化，并且运算效率比CPU计算要高出很多。这也是目前比特币使用GPU加速挖矿的重要原因所在。一些测试表明，目前最快的Core i7 4770K在比特币的计算方面速度只有不到-IOM H/s，但是低端的显卡诸如Radeon HD7750可以轻松达到130M H/s左右，最快的Radeon HD 7990甚至超过了1000M H/s，是CPU的100信以上！

　　莱特币也是目前热门的虚拟电子货币的一种。菜特币使用的算法是由黑客Co…Percival为自己的备份服务器开发的Scrypt。Scrypt算法和SHA系列算法还是有比较大的差别，它对内存的要求比较高，计算性能依赖于计算资源，而SHA-256对内存要求很低。此外，Scrypt没有经过广泛的讨论和严格的检验，可能存在不明的安全性问题。

　　由于Scrypt的特殊性，开发针对Scrypt的加速计算方法就显得比较困难了。尤其Scrypt对算法带宽要求非常高，因此很多显卡计算莱特币的效率都不是很高，只能达到KH/s级别，和比特币的M H/s级别相距甚远，比如Radeon HD7970酌速度大概在700KH/s。但是用显卡进行计算的速度也要远远高于处理器。也正是由于Scrypt的特性，开发莱特币的ASIC（大规模集成电路）矿机也比较困难，其性能基本瓶颈往往在I/O部分，也需要更多的引脚才能实现更大的存储带宽，成本比较高，目前还没有效率出色的ASIC矿机出现。

　　总的来说，SHA家族算法是目前应用最为广泛、安全性最好的加密算法之一，它的应用远远不止挖矿这么简单。SHA家族算法由于其易用、安全的特性，被广泛使用在大量的生活产品中。每个人每天几乎都能遇到多次和SHA家族算法相关的操作，比如你输入电脑密码、使用加密存储设备、在银行交易、炒股等多种场景下，SHA家族算法都在默默的保护着你的安全。最新的消息是，在SHA_2系列算法之后，美国国家安全局又在开发SHA-3系列算法，SHA-3使用了全新的计算方法，用于和SHA2实现相互补充，在不同的应用下发挥自己强大的加密能力，保障数据安全。未来的信息和数据，一定会随着加密算法的越来越强大，变得更为安全和坚固。