3.2 散列函数与数据完整性

数据在存储、传输和处理过程中可能遭受未授权、未预期或无意的修改，这就破坏了数据的完整性。确保数据的完整性除了事前的访问控制，还可以通过事后的完整性检测。本节将介绍散列函数，以及利用散列函数进行消息的完整性检测和散列函数在数字签名中的应用。

3.2.1 散列函数

1.散列函数的概念

散列函数又称为哈希（Hash）函数、消息摘要（Message Digest）函数、杂凑函数。散列函数可以把任意长度的输入转换成固定长度的输出。它是一种单向密码体制，即从一个明文到密文的不可逆映射，只有加密过程，没有解密过程。与对称密码算法和公钥密码算法不同，散列函数没有密钥。

散列函数可以表示为

h ＝ H （ M ）

其中，H是散列函数，M是任意长度的明文消息，h是固定长度的散列值（或称为哈希值、消息摘要、数字指纹）。

2.散列函数的特性

散列函数具有如下特性：

1）它能处理任意大小的信息，并将其摘要生成固定大小的数据块（例如160位，即20个字节），对同一个源数据反复执行散列函数总是得到同样的结果。

2）它是不可预见的。所产生数据块的大小与原始信息的大小没有任何联系，同时源数据和产生的数据块看起来没有明显关系，但源数据的一个微小变化都会对数据块产生很大的影响。

3）它是完全不可逆的。即散列函数是单向的，从源数据中很容易计算出其散列值，但没有办法通过生成的散列值恢复源数据。

4）它是抗碰撞的。即寻找两个输入得到相同的输出值在计算上是不可行的。对于消息M，要找到另一消息M′并满足H（M′）＝H（M），则称M和M′是散列函数H的一个碰撞（Collision）。

由于散列函数的单向特性以及输出长度固定的特点，使得它可以生成消息或数据的散列值（哈希值、消息摘要），因此它在数据完整性验证、数字签名和消息认证等领域有着广泛的应用。

单向散列函数最主要的用途是数字签名。现在使用的重要计算机安全协议，如SSL、PGP都用散列函数来进行签名。第3.3节中将详细介绍数字签名。

3.散列函数的应用

散列函数通常具有以下用途：

（1）校验数据完整性

散列函数具有抗碰撞的能力，两个不同的数据，其散列值不可能一致。发送方将数据和数据经散列函数处理后的结果一并传输，接收方可以通过将接收的数据重新进行计算，并与接收的散列值进行比对，可以检验传输过程中数据是否被篡改或损坏。

数据文件发生任何一点变化，通过单向散列函数计算出的散列值就会不同。如图3-11所示，两幅肉眼无法看出区别的图片计算出的散列值（采用SHA-1算法计算，将在第3.3节中介绍）完全不一样，虽然其中一张图中只做了一点点的修改。

对于相当多的数据服务，例如网盘服务，同样可以用散列函数来检测重复数据，避免重复上传。

（2）消息认证

在一个开放通信网络环境中，传输的消息还面临伪造、篡改等威胁，消息认证就是让接收方确保收到的消息与发送方的一致，并且消息的来源是真实可信的。散列函数可以用于消息认证，将在第3.4节中介绍。

（3）数字签名

因为非对称加密算法的运算速度较慢，所以在数字签名应用中，散列函数起着重要的作用。对散列值进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。

（4）保护用户口令

将用户口令的散列值存储在数据库中，进行口令验证时只要比对散列值即可。不过如果攻击者获取了口令的散列值，虽然由于散列函数的不可逆，不能直接还原出口令，但还是可以通过字典攻击得到原始口令。更多的细节将在第4章中讨论。

3.2.2 常用散列函数

常用的散列函数有两类：MD5（Message-Digest Algorithm 5，消息摘要算法第5版）和SHA（Secure Hash Algorithm，安全散列算法）。

（1）MD5

MD系列算法都是由Ron Rivest设计的，包括MD2、MD3、MD4和MD5。MD5对于任意长度的输入消息，都将产生128位长度的输出值。MD5曾有着广泛的应用，一度被认为是非常安全的。然而，在2004年8月召开的国际密码学会议上，我国的王小云教授公布了一种寻找MD5碰撞的新方法。目前利用该方法在普通PC上数分钟内就可以找到MD5的碰撞。可以说MD5已被攻破。增加散列值的长度成为弥补安全性的一种手段。

（2）SHA

安全散列算法由美国NIST设计，并于1993年作为联邦信息处理标准FIPS 180发布。随后该版本的SHA（后被称为SHA-0）被发现存在缺陷，修订版于1995年发布（FIPS 180-1），通常称为SHA-1。SHA-1产生160位的Hash值。

2002年，NIST发布了修订版FIPS 180-2，其中给出了三种新的SHA版本，Hash值长度依次为256、384和512位，分别称为SHA-256、SHA-384、SHA-512，这些算法又被统称为SHA-2。SHA-2同SHA-1类似，都使用了相同的迭代结构和同样的模算数运算与二元逻辑操作。在2008年发布的修订版FIP PUB 180-3中，增加了224位版本。2005年，NIST宣布了逐步废除SHA-1的意图，逐步转向SHA-2版本。2012年，NIST发布了修订版FIP PUB 180-4。

2012年，NIST还选择了Keccak算法作为新的散列标准，该算法被称为SHA-3。SHA-3并不是要取代SHA-2，因为SHA-2目前并没有出现明显的弱点。但是由于对MD5出现成功的破解方法，以及对SHA-0和SHA-1出现理论上破解的方法，NIST感觉需要一个与之前算法不同的、可替换的散列算法，也就是现在的SHA-3。设计者宣称这个算法比起其他散列算法明显地快很多。读者可以在完成本章思考与实践中的第17题时，进一步了解最新的知识。 1AKWWSHvidIBr/Qi3WFGLC2O8Z17bNNINg+uYWOyvm0aMapzQJNijjXK6/t075ot