2.2.2 密码哈希函数

为了保证数据安全，区块链中使用的哈希函数是密码哈希函数（Cryptographic Hash Function），又称密码散列函数。它是哈希函数的拓展，被认为是一种单向函数，即很难通过哈希函数的输出结果来逆推出输入数据，可以理解为只有加密，没有解密。在信息安全领域中，有很多重要的应用都使用密码哈希函数来实现，比如数字签名、消息认证码等。

2.2.2.1 密码哈希函数特性

密码哈希函数除了具有一般哈希函数特性外，还具备另外三个特性：碰撞阻力、隐秘性以及谜题友好性。这三个特性在成就区块链的功劳簿上占据显赫地位，功不可没。

1．碰撞阻力

哈希函数的碰撞，指的是对于该函数，存在两个不同的输入，产生了相同的输出。如图2-14所示，数据A和数据B经过哈希计算得出相同的哈希值C。比如前面的求余函数H（x）=xmod 3，当x=2时，H（x）=2；当x=5时，H（x）=2。两个不同的输入2和5得到相同的输出值2，于是该函数是具有碰撞性的。换句话说，该哈希函数不具备碰撞阻力。如果无法找到两个不同的输入值x和y，使得H（x）=H（y），则称该哈希函数具有碰撞阻力。

这是一个很有意思的事情，哈希函数的输入因为可以是任意长度，所以其输入空间无限，而输出为固定长度，那么输出空间有限，这种情况下却找不到两个相同的输入来使得输出一样？根据鸽巢原理（Pigeonhole Principle），如果输入数量无限，而输出数量有限，那么必然会存在至少一个输出对应两个或两个以上的输入，即不同的输入会被映射到同一个输出，这意味着碰撞阻力失效。

延伸阅读

Pigeonhole Principle：鸽巢原理，又称抽屉原理。

原理阐释：如果要将n+1个物品放进n个抽屉里，那么至少有一个抽屉要放两个或两个以上的物品。如图2-15所示，苹果和抽屉可以理解为输入和输出的映射关系。

实际上，碰撞确实是存在的。考虑计算机的二进制只有0和1两个数码，举个简单的例子，对于有3位输出的哈希函数，输出最多有23个值。选择23+1个不同的输入，计算每一个输入对应的哈希值输出。每个输入仅对应一个输出（对应图2-15，一个苹果只能被放进一个抽屉，而不会同时被放进两个抽屉），输入有9个值，输出有8个值，必然会出现某两个不同的输入对应同一个输出，也就是说必然产生哈希碰撞。既然每个哈希函数一定存在碰撞，为什么会有我们前面提到的部分哈希函数具有碰撞阻力呢？那是因为对于某些哈希函数，人们经过努力尚未找到有效的碰撞方法，实践中包括区块链使用的密码哈希函数都是如此，至今没有发现碰撞。以前应用较多的MD5密码哈希函数，经过时间的推移，已经找到了碰撞方法，所以渐渐在实践中被淘汰弃用了。

你可能会问，我们是否可以遍历整个输入空间，这样总能找到两个不同的输入对应同一个输出？比如前面提到的3位输出的哈希函数，找23+1个不同的值作为函数的输入进行计算。能想到这一步非常不错，输出位数为3时，最坏的情况下只要计算23+1也就是9次，我们一定可以找到碰撞。然而，当输出位数扩展到256位呢？最坏的情况下需要计算2256+1次，平均计算次数是2128次注1，这个数字有多大呢？如果一台计算机每秒运行10000次哈希运算，那么计算2128次需要花大约1027年的时间注2。通过遍历输入空间来暴力破解哈希值如图2-16所示。

注1根据生日悖论，N位长度的哈希表可能发生碰撞测试次数是2的次方。通过检验可能输出数量的平方根次数，就能大体找到碰撞。

注21天哈希计算量=24×60×60×10000=864000000，1年哈希计算量=365×864000000=315360000000，由此计算2128哈希计算量所花费时间为：2128/315360000000≈1027。

所以通过遍历输入空间来找到哈希碰撞的概率是非常小的。如果有一天，区块链中使用的密码哈希函数被发现有高效的碰撞算法，那么它也会在实践中被逐渐淘汰。

密码哈希函数的碰撞阻力有什么作用呢？通过密码哈希函数，能够把任意位数的输入值变换为一个固定位数的值，这个输出值是对原值的加密结果，也可以称为原值的摘要，作为辨别原值的依据。正因为有碰撞阻力，才不会有两个不同的输入值对应同一个加密结果。就像我们的18位身份证号一样，不同的人对应不同的身份证号，而每个身份证号与具体的每个人对应，无论这个人高矮胖瘦，面目狰狞还是长相可爱，都有唯一的一个18位身份证号与其对应。身份证号可以作为辨识本人的依据，密码哈希函数亦是如此。不论数据多大，数据内容是什么，我们都可以通过计算其密码哈希函数值来辨识数据。比如，我们在云服务器里存放了一个重要的文件，这个文件有几百吉字节的大小。当我们重新下载时，文件可能因为网络传输问题丢包而导致数据不完整，或者已经在云服务器上被人为篡改了。遇到这种情况，我们可以通过计算密码哈希函数值来识别。在文件上传前计算整个文件的密码哈希函数值，并在本地保存。下载后再次计算下载文件的密码哈希值，与之前保存的哈希值进行比较。根据密码哈希函数的碰撞阻力性质，如果文件有变化，即两次计算的密码哈希函数的输入不同，其得到的哈希值也一定不同，因为如果输出相同就碰撞了。所以，不可能出现这样的情况：文件内容变化了而哈希值还相同。因此只要我们比较的哈希值一致，则判定文件一定没改变。另外，如果我们比较得到的哈希值不一致，则两次输入的文件数据一定不同，从而可以判定文件被损坏或者在云端被篡改，如图2-17所示。这样我们无须占用很大的存储空间保存文件，将下载的文件与上传前的文件本身做比较，而是通过所需存储空间很小的密码哈希值就能简单地判断“它还是它吗”。因此，密码哈希值可以用作信息摘要来验证数据是否有变化，而无须比较数据本身。也许有一天，电视剧里会出现这样一幕，当女主角歇斯底里地纠缠男主角问：“你是不是变心了？”此时男主角淡定地拿出“心”的哈希值，说：“你来验证！”如图2-18所示。

以MD5密码哈希函数为例，不同的输入值对应的MD5哈希值如表2-1所示。可以看到，输入字符串仅仅修改了一位，两者的MD5值就千差万别。

2．隐秘性

下面我们来认识密码哈希函数的第二个重要特性：隐秘性，即：对于密码哈希函数y=H（x），给定输出值y，无法知道其对应的输入值x，如图2-19所示。

密码哈希函数的隐秘性类似于给定一个身份证号，我们无法通过该身份证号推导出这个人的模样。对于某些函数，比如y=x+1，很容易得出x=y－1，给定y值就能计算出x。可并非每个函数都是如此，对于有些函数并不能推导出x，它们的y值就像是给x值戴的一个面具，我们只能看到面具，却无法揭开面具得到x的真面目。在输入集合很小的情况下，通过遍历计算是可以得到每个输入与输出的对应关系的，从而能够在给定y值的情况下找到其对应的x值。举个例子，假设哈希函数的输入集合中x有3个可能值，分别对应3个输出值，将3个x值分别代入函数计算，找到3个x值与3个y值的一一对应关系，这样给定其中的一个y值时就很容易找到其对应的x值。但对于输入集合非常广泛的情况，一些函数无法通过输出值反解出输入值，也不可能遍历找到对应关系，真正实现了隐秘性。所以，为了具有隐秘性，我们需要x值来自于广泛的集合。那么，如果输入来自于很小的集合，还有办法实现隐秘性吗？答案是肯定的。只要把输入x与另一个分散的输入r进行结合，就可以实现隐秘性。如同几个零星的输入，分散到更大的输入空间后被隐秘起来，就像是被追踪的人躲到人群里，这里引入的集合R是用来掺杂输入集合X混淆视听的，如图2-20所示。

准确地说，输入r选自一个高阶最小熵的概率分布（high min-entropy）。所谓“熵”，是指混乱、随机程度，是对不确定性的度量。越不确定的事件，熵值越大。“高阶最小熵的概率分布”可以理解为最小熵的最大分布，保证分布的最大均匀，这样就不会因为和自己相关而很容易被预测出来。密码哈希函数隐秘性面临的问题就是当输入x范围有限时无法保证隐秘性，其解决方案是在最小熵的最大分布中选取一个输入，与x混合连接变为新的值作为输入，则能最大保证x的隐秘性。简单地说，高阶最小熵描述分散程度，比如r从128位的字符串中随意选出，那么某一个值被选中的概率为1/2128，这个概率是非常非常小的。r的取值相当分散，即使x是确定的几个可能取值，在给定的H（r‖x）条件下也无法确定x值（符号“‖”表示把两者连接起来）。

密码哈希函数的隐秘性有什么作用呢？一个典型的应用就是“承诺”，如图2-21所示。打个比方，我们有一个魔镜，魔镜根据其背面写的数字的不同，在镜子前面可以展示出不同的图案。图案对每个人可见，但是魔镜背面的数字并不是对每个人可见的，只有写字的人知道。所谓“承诺”，就是指写字的人对所写数字作承诺。过了一段时间，请大家来验证，当时自己写的的确是该数字。如何验证呢？大家只知道当时魔镜显示的图案。此时写字的人公布数字，并在魔镜的背面写上该数字，然后请大家看魔镜展示的图案，和之前大家看到的那个图案进行比较，如果两个图案一样，即可证明当时写字的人在魔镜背面写的的确是公布的数字，以此验证承诺。这里隐秘性的价值在于，数字的取值非常广泛，其他人看到图案后无法通过图案反推出所写的数字。承诺的应用场景有很多，例如，某个人为了向大家证明自己在某时刻知道某个问题的答案，而这个答案当时不能被其他人知晓，于是他运用密码哈希函数的隐秘性作承诺，隔段时间后再公布答案让大家验证。

同时，碰撞阻力在承诺里也是有作用的，如图2-22所示。不能有两个不同的输入数字对应相同的图案，否则承诺就乱套了。为什么呢？有一天，小李做出承诺：这个西红柿图案输入的数字是1。如果存在碰撞，那么另一个数字（假设是2），也对应西红柿的图案。过了两天小李改变主意了，对大家说自己输入的数字是2。因为输入2呈现的图案和输入1呈现的图案一样，那么大家就会有异议了，小李承诺的到底是1还是2？正因为有了碰撞阻力，一旦公开承诺，就无法欺骗别人该承诺是别的数字。

我们得出结论，对于承诺函数，隐秘性在于仅仅知道承诺函数的输出，无法反推出承诺函数的输入。就像是魔镜，看到展示的图形不能反推出输入的数字，需要公布承诺才可以被别人验证。另外还有约束性，一旦承诺了就不能更改这个信息，也即承诺不能发生碰撞。我们可以通过密码哈希函数来实现：y=H（nonce‖msg），其中nonce是随机生成的一个临时随机数，用于在更大输入空间内隐藏msg；msg是我们承诺的信息；y就是魔镜的图案，公布了nonce和msg以后能让其他人来验证承诺。

3．谜题友好性

谜题友好性的定义：对于任意n位的输出值y，假定k选自高阶最小熵分布，如果无法找到一个可行的方法，在比搜索2n次少很多的时间内找到输入值x，使得H（k‖x）=y成立，那么我们称哈希函数H为谜题友好。

谜题友好性可以简单地理解为对于谜题函数的求解无捷径，只能对全部的输入空间进行搜索，将输入空间里的值逐个代入函数计算，判断输出结果是否符合要求。比如要求y值落在某个目标集合内，只能通过遍历的方法找到使得y值符合要求的输入值x，除此以外别无他法。我们认为该函数具有谜题友好性，虽然实际上寻找符合要求的x是个苦力活，一点都不友好。具体来说，对于

H（id‖x）∈Y

其中，id是从高阶最小熵分布中选取的一个值，Y是目标集合，比如由256位的0和1组合的值中，前10位全部是0的数值组成的集合。谜题是：请找出一个合适的x，使得哈希函数H（id‖x）计算出来的值在Y的目标集合内。这里的id是从高阶最小熵分布中选出的，也就是它的分散程度非常高，从而保证了求解无捷径。集合Y决定了谜题的难度，最难的谜题是Y只有一个元素。比特币的挖矿谜题就使用了这个策略。

总结加密数字货币中应用到的密码哈希函数三个特性：第一个是碰撞阻力，无法找到两个不同的输入使得密码哈希函数的输出相同；第二个是隐秘性，密码哈希函数不能反解出输入x的值；第三个是谜题友好性，求解x值无捷径，只能遍历整个输入空间，依次代入可能的输入观察密码哈希函数的输出是否落在特定的集合内，从而得出x的值。这三个特性都被运用在区块链技术中。

2.2.2.2 常用的密码哈希函数

我们已经介绍了密码哈希函数具备的三个特性，下面简单介绍几种具体的密码哈希函数。

（1）MD4：麻省理工学院Ronald Rivest教授于1990年设计的一种密码哈希函数。其哈希值长度为128位。该函数已经找到了碰撞方法，变得不安全了，但是这个算法影响了后来的很多算法，如MD5、SHA家族和RIPEMD等，其中MD是信息摘要（Message Digest）的简写。

（2）MD5：同样是麻省理工学院Ronald Rivest教授于1992年设计的一种密码哈希函数。其哈希值长度为128位。该函数在2004年被山东大学王小云教授团队破解，同样变得不安全了。

（3）SHA-1：由美国国家安全局设计、美国国家标准技术研究所（National Institute of Standards and Technology, NIST）1995年发布的一种能产生160位哈希值的密码哈希函数，但是该函数在2005年被山东大学王小云教授团队破解。

（4）SHA-2：由美国国家安全局设计、NIST 2002年发布的一系列密码哈希函数，包括SHA-256、SHA-384和SHA-512，它们的哈希值长度分别为256位、384位和512位。SHA-2和SHA-1虽然不完全相同，但是它们的数学理论是一致的，因此有着相同的缺陷。SHA-2通过增加密码哈希值长度来确保其安全，目前尚未被攻破，不过对SHA-2的攻击会随着时间的推移而变得越来越容易。

（5）SHA-3：由Guido Bertoni等人设计的Keccak算法，该算法在2012年由NIST组织的SHA-3竞赛中脱颖而出，成为SHA-3标准。虽然SHA-2目前已成为主流的密码哈希函数且没有明显的破绽，但是NIST仍坚持要设计一种不同于以往算法的密码哈希函数，所以才有了SHA-3。

（6）RIPEMD-160：由比利时鲁汶大学（University of Leuven）的Hans Dobbertin等人于1996年设计的一种密码哈希函数，能产生160位的密码哈希值。虽然其原始版RIPEMD已经于2004年被攻破，但是RIPEMD-160还未被攻破。

（7）SM3：它是我国采用的一种密码哈希函数标准，由国家密码管理局于2010年12月17日发布。SM3主要应用于数字签名及验证、消息认证码生成及验证、随机数生成等，其安全性及效率与SHA-256相当。

下面简要介绍比特币技术中大量使用的密码哈希函数SHA-256。SHA-256是SHA-2算法族中的一种，SHA全称是安全哈希算法（Secure Hash Algorithm）。SHA-256的输入消息长度为任意位数，其输出的密码哈希值长度固定为256位。SHA-256具备密码哈希函数的一般特性。在比特币技术中，无论是区块的头部信息还是交易信息，都是使用这个密码哈希函数来计算相应的密码哈希值，从而保证数据的完整性（运用到密码哈希的碰撞阻力特性）。另外，在比特币系统中，基于寻找指定范围的SHA-256哈希值，设计了工作量证明的共识机制（运用到密码哈希的隐秘性和谜题友好性，通过计算出特定范围内的密码哈希值所做的计算工作来考量工作量）；同时SHA-256也被用来构造比特币地址，用来识别不同的用户（运用到密码哈希的碰撞阻力特性）。

一般情况下，比特币用SHA-256对数据计算密码哈希值时，需要计算两次，称为双重SHA-256，即Hash=SHA256（SHA256（数据）），比如对字符串“bitcoin”进行两次SHA-256哈希计算，如表2-2所示。

我们要求哈希函数的输入可以是任意长度。只要我们建立一个用于固定长度输入的哈希函数，采用一种称为Merkle-Damgard（MD）的变换方法，就能实现将接收固定长度输入的哈希函数转换为可接收任意长度输入的哈希函数。实际上，有很多哈希函数都采用了MD变换，包括SHA-256。这种基础的、可用于固定输入长度、具有碰撞阻力的哈希函数称为压缩函数。目前已经证明，将具有碰撞阻力的压缩函数进行MD转换后的哈希函数同样具有碰撞阻力的特性。

MD变换方法如下：

（1）假设一个固定输入长度的压缩函数，输入固定长度为len_m，输出长度为len_n，其中len_n＜len_m，那么输入和输出的长度差值为：△=len_m－len_n，如图2-23所示。

（2）将任意长度的输入数据，按照△大小进行划分。我们可以通过补位把输入长度变成△的整数倍，便于后续的处理，如图2-24所示。

（3）将固定长度△的分块和前一个分块的输出len_n一起代入压缩函数，如图2-25所示。为什么要使用前一分块的输出呢？答案是：输入△+len_n=（len_m－len_n）+len_n=len_m，这样一来，压缩函数的输入长度其实就是其本身的固定输入长度len_m，输出仍为len_n。

（4）基于对任意长度输入的分块思想，可以实现对任意长度输入的哈希计算，如图2-26所示。前一个分块的输出作为下一个压缩函数的输入之一，形成一个链式结构，其中第一个压缩函数的输入len_n是初始向量，可以自行设置，但长度必须为压缩函数的固定输出长度。

以密码哈希函数SHA-256为例，我们已知一个压缩函数输入为768位，输出为256位，SHA-256可以理解为将该压缩函数通过MD变换为可以输入任意长度而输出为256位的函数。如何实现转换呢？我们将函数SHA-256的输入分为n个块，每个块的长度是压缩函数输入和输出长度的差值，即：768-256=512位。如图2-27所示，设置一个标准的256位初始向量作为原始输入，这样针对输入是512位整数倍长度的值，最后的输出就是256位。图2-27显示了SHA-256的工作流程。

延伸阅读

SHA-256究竟是否安全？从目前SHA-256的运行情况来看，没有漏洞爆出。但是有人担心，SHA-256（包括SHA-2系列）的设计与美国国家安全局（NSA）有密切的关系，NSA一直希望能获得关于SHA-2的信息破解能力，有阴谋论者认为NSA可能在SHA-2设计中留有后门，还有人认为虽然目前没有公开SHA-2的漏洞，但是并不代表没有漏洞，或许有人已经发现了漏洞但是不愿意发布，只希望为自己所用。另外，相反的观点认为，SHA-2是美国主导设计开发的，如果有漏洞，其他国家早就已经发现了。

2013年9月发生的一件事引起了BitcoinTalk（比特币论坛）的轩然大波，很多人对SHA-2是否安全产生了质疑。当月10日，NSA要求约翰·霍普金斯大学的计算机科学教授、知名的加密算法专家Matthew Green删除他的一篇与NSA有关的破解加密算法的博客，同时约翰·霍普金斯大学服务器上的该博客镜像也被删除。当记者向该校求证时，该校称从未收到来自NSA的要求。记者无法在原网址再次找到该博客，幸运的是，从谷歌的缓存中可以找到。该博客提到NSA每年花费2.5亿美元为自己在解密信息方面获取优势，并列举了NSA一系列见不得人的做法。

为了加深对各种密码哈希函数直观的理解，我们来看一个例子，“好好学习区块链技术，人生会得到升华”这句话的MD5、SHA-1、SHA-256、SHA-512以及RIPEMD-160的哈希值如表2-3所示。