3.3 哈希函数
数据在存储、传输和处理中可能遭受未授权、未预期或无意的修改，这就破坏了数据的完整性。确保数据的完整性除了事前的访问控制，还可以通过事后的完整性检测。本节将介绍哈希函数，利用哈希函数进行消息的完整性检测和哈希函数在数字签名中的应用。
3.3.1 哈希函数基本概念
1.哈希函数的概念
哈希（Hash）函数又称为散列函数、消息摘要（Message Digest）函数、杂凑函数。哈希函数可以把满足要求的任意长度的输入转换成固定长度的输出。它是一种单向密码体制，即从明文到密文的不可逆映射，只有加密过程，没有解密过程。与对称密码算法和公钥密码算法不同，哈希函数没有密钥。
哈希函数可以表示为
h=H(M)
其中，H是哈希函数；M是任意长度的明文消息；h是固定长度的输出，称为原消息的哈希值（Hash Value），或是散列值、消息摘要、数字指纹。
2.哈希函数的特性
哈希函数具有如下特性：
1）易压缩。对任意大小的信息产生很小长度的哈希值。例如产生 160位的哈希值，即 20个字节。而且对同一个源数据反复执行哈希函数，得到的哈希值保持一致。
2）不可预见。产生的哈希值的长度和内容与原始信息的大小和内容没有任何联系，但是源数据的一个微小变化都会影响哈希值的内容。
3）不可逆。哈希函数是单向的，从源数据很容易计算其哈希值，但是无法通过生成的哈希值恢复源数据。
4）抗碰撞。寻找两个不同输入得到相同的哈希值在计算上是不可行的。对于消息 M，如果找到另一个消息M'并满足H(M')=H(M)，则称M和M'是哈希函数H的一个碰撞（Collision）。
5）高灵敏。输入数据某几位的变化会引起所生成的哈希值几乎所有位的变化。
3.哈希函数的应用
由于哈希函数的单向特性以及输出的哈希值长度固定的特点，使得它可以生成消息或数据的哈希值，因此它在数据完整性验证、数字签名、消息认证、保护用户口令，尤其是区块链等领域有着广泛的应用。
（1）校验数据完整性
哈希函数具有抗碰撞的能力，两个不同的数据的哈希值不可能一致。发送方将数据和数据的哈希值一并传输，接收方可以通过将接收的数据重新计算哈希值，并与接收的哈希值进行比对，以检验传输过程中数据是否被篡改或损坏。
数据文件发生任何一点变化，通过哈希函数计算出的哈希值就会不同。如图3-11所示，两幅肉眼无法看出区别的图片计算出的哈希值（采用SHA-1算法计算，该算法将在下一小节介绍）完全不一样，虽然其中一张图中只被做了一点修改。
图3-11 通过计算哈希值鉴别图片是否有变化
对于相当多的数据服务，例如网盘服务，同样可以用哈希函数来检测重复数据，避免重复上传。
（2）数字签名
因为非对称加密算法的运算速度较慢，所以在数字签名应用中，哈希函数起着重要的作用。对消息摘要进行数字签名，在统计上可以认为与对消息文件本身进行数字签名是等效的。更多技术细节将在3.4节中介绍。
（3）消息认证
在一个开放通信网络环境中，传输的消息还面临伪造、篡改等威胁，消息认证就是让接收方确保收到的消息与发送方的一致，并且消息的来源是真实可信的。哈希函数可以用于消息认证，更多技术细节将在3.4.3节中详细介绍。
（4）保护用户口令
将用户口令的哈希值存储在数据库中，进行口令验证时只要比对哈希值即可。不过，如果攻击者获取了口令的哈希值，虽然由于哈希函数的不可逆，不能直接还原出口令，但还是可以通过字典攻击得到原始口令。更多的细节将在第4章中讨论。
（5）区块链
在区块链中很多地方都用到了哈希函数，例如，区块链中节点的地址、公钥、私钥的计算，比特币中的挖矿等。
3.3.2 常用哈希函数
常用的哈希函数有两类：MD（Message Digest，消息摘要）系列算法和SHA（Secure Hash Algorithm，安全哈希算法）。
1.MD系列算法
MD系列算法都是由Ron Rivest设计的，包括MD2、MD3、MD4和MD5。MD5对于任意长度的输入消息产生128位长度的哈希值。
MD5曾有着广泛的应用，一度被认为是非常安全的。然而，在 2004年 8月召开的国际密码学会议上，我国的王小云教授公布了一种寻找MD5碰撞的新方法。目前利用该方法用普通PC，在数分钟内就可以找到MD5的碰撞。可以说MD5已被攻破。
文档资料3-3
王小云与王氏攻击
2.SHA
SHA由美国NIST设计，并于1993年作为联邦信息处理标准FIPS 180发布。随后该版本的SHA（后被称为SHA-0）被发现存在缺陷，修订版于 1995年发布（FIPS 180-1），称之为SHA-1。SHA-1算法输入消息的最大长度为264-1位，输入的消息按512位的分组进行处理，输出是一个160位的哈希值。
2002年开始，NIST陆续发布了SHA-2系列的哈希算法，其输出长度可取 224位、256位、384位和 512位，分别称为SHA-224、SHA-256、SHA-384、SHA-512。2005年，NIST宣布了逐步废除SHA-1的意图，逐步转向SHA-2版本。SHA-2系列算法比之前的哈希算法具有更强的安全强度和更灵活的输出长度。
2012年，NIST还选择了Keccak（读作“ket-chak”）算法作为新的哈希标准，该算法被称为SHA-3。SHA-3并不是要取代SHA-2，因为SHA-2目前并没有出现明显的弱点。但是由于对MD5以及SHA-1出现了成功的破解，NIST感觉需要一个与之前算法不同的，可替换的哈希算法，也就是现在的SHA-3。设计者宣称这个算法比其他哈希算法具有更强的安全性和软硬件实现性能。
拓展知识：哈希函数的安全性
对于SHA-1，因为产生的输出是160位，攻击者要想找到一组碰撞的话，最显然的方法是选取 2160组不同的数据，依次计算它们的哈希结果，根据抽屉原理，必然会出现一组数据，使得其哈希结果相同。不过，2160的计算代价太大，可以通过概率方法寻找。这就是著名的生日攻击（Birthday Attack）。根据抽屉原理，一个屋子里必须有366个人（一年有365天，不考虑闰年）才能保证一定有2个人生日相同。然而，如果一个屋子里有23个人，则50%的概率有2个人生日相同。根据概率论，第2个人和第1个人生日不相同的概率为
，第3个人和第1个人生日不相同的概率为
，和第2个人生日也不相同的概率为
（因为此时已经假定前2个人生日不同），因此和前2个人生日都不相同的概率为
，…，第23个人和前22个人生日都不相同的概率为
。上述事件同时发生时，23个人生日才会各不相同。因此，23个人中存在2个人生日相同的概率为
。
寻找哈希碰撞时也可以采用这个方法。对于SHA-1来说，选择大约280组不同的数据并计算哈希结果，则有50%的概率有2个数据的哈希结果相同。密码学上认为，如果能找到一种方法，能在小于 280运算量的情况下，有超过生日攻击的概率找到一组碰撞，则认为这个哈希函数就不安全了。
我国密码学家王小云研究团队在2004年证明：常用的哈希函数MD4、MD5、HAVAL-128和RIPEMD这 4个哈希算法不具有抗碰撞性。2005年 2月，王小云团队又证明，哈希函数SHA-1的抗碰撞性不如人们想象的那样强，并给出了一个在 269量级的运算内找到碰撞字符串的方法。这一开创性工作让进一步破解SHA-1成为可能。
2005年8月，王小云、姚期智（2000年图灵奖获得者）和储枫又进一步将269量级的运算缩短至263量级的运算。
2013年，阿姆斯特丹数学与计算机研究中心（CWI）的Stevens提出的攻击方法进一步将计算量级缩短至261。
2017年2月23日，谷歌在博客上宣布实现了SHA-1的碰撞。由Stevens等人参与完成的论文The First Collision for Full SHA-1展示了从应用角度破解SHA-1的方法。他们成功构造了两个PDF文件（有意义、可以真正打开的文件），使得SHA-1结果相同。