1.1　加密散列函数

在实际应用中，加密散列函数将变长的位字符串输入固定地映射为定长的位字符串输出。

如前所述，散列碰撞是不可避免的，但是一个安全的散列函数需要具备抗碰撞性，也就是应该很难发现碰撞。当然，一次碰撞是可以被意外发现或者提前计算的。这就是为什么这类函数始终需要数学证明。

加密散列函数在密码学中非常重要，并且在数字签名、模式验证和消息完整性等许多实际场景中有着广泛应用。

加密散列需要满足以下三个主要要求：

·工作因数——为使暴力破解变得困难，加密散列在计算上应该是高代价的。

·黏性状态——加密散列的状态不应依赖于合理输入模式。

·扩散——加密散列的每个输出比特都应该是与每个输入比特同样复杂的函数。

理论上，加密散列函数可以进一步分为使用密钥的键控散列函数和不使用密钥的非键控散列函数。概率数据结构仅仅使用非键控散列函数，包括单向散列函数、抗碰撞性散列函数和全域单向散列函数。这些函数仅仅在一些额外属性上有所差异。

单向散列函数满足如下要求：

·可以应用于任意长度的数据块（当然，在实际应用中数据块的长度不会超过一个很大的值）。

·散列的输出是定长的。

·它们应该具备抗原像性（单向特性），即给定特定的散列结果，找到该结果对应的输入在计算上是不可行的。

此外，对于抗碰撞性散列函数来说，给定两个不同的输入，它们产生相同散列值的概率应该是非常小的。

如果不具备抗碰撞性，全域单向散列函数需要具备目标耐碰撞性或抗第二原像性，即在计算上找到与指定输入相同的输出的第二个不同输入是不可行的。

需要注意的是，具有抗碰撞性意味着这个函数同时具有抗第二原像性，但是找到抗第二原像性的一般复杂度要比找到碰撞对高得多。

由于它们的设计（特别是工作因数要求），加密散列函数的效率要远低于非加密散列函数。例如，接下来将要讨论的SHA-1函数的速度是540MiB/s[1]，而当下流行的非加密散列函数速度为2500MiB/s，甚至更快。

（1）消息-摘要算法

1991年，Ron Rivest发明了著名的消息-摘要算法（Message-Digest Algorithm，又称MD5），以替代旧的MD4标准。MD5是一个定义在IETF RFC 1321中的加密散列算法，它以任意大小的消息作为输入，并生成长度为128比特的散列值作为输出。

MD5算法基于Merkle-Damgård模式。在第一个阶段，MD5算法使用符合MD模式的填充函数将任意长度的输入转换为一系列固定长度的数据块（大小为512比特的数据块或16个大小为32比特的字）。之后，这些数据块被一个特殊的压缩函数逐一处理，每一个数据块都会使用前一个输出的结果。为了保证压缩的安全性，MD5算法使用Merkle-Damgård增强，然后填充函数使用原始消息的编码长度。最终的MD5散列摘要（大小为128比特）在处理完最后一个数据块后生成。

MD5算法通常被用来验证文件的完整性。相较于通过检查原始数据来验证文件是否被更改的方式，比较MD5的散列值已经足够。

如漏洞说明VU#836068[2]所称，MD5算法容易遭受碰撞攻击。算法中发现的缺陷使得使用相同的MD5散列构建不同的消息成为可能。结果是，攻击者可以生成密码令牌或其他非法显示为真实的数据。不再建议将MD5用作安全的加密算法。但是，这种漏洞对概率数据结构影响不大，仍然可以使用。

（2）安全散列算法

安全散列算法由美国国家安全局（NSA）开发，并由美国国家标准技术研究院（NIST）发布。该系列中的第一个算法SHA-0于1993年发布，并很快被其后继SHA-1所取代，SHA-1已在全球范围内被广泛接受。SHA-1产生了更长的160比特（20B）散列值，同时通过修复SHA-0的弱点提高了它的安全性。

SHA-1已在各种应用程序中被广泛使用了多年，大多数网站都使用基于SHA-1的算法进行签名。然而，在2005年，SHA-1的一个弱点被发现。因此，在2010年，NIST不赞成将其用于政府用途。而且，从2011年起，它在互联网上遭到了弃用。与MD5一样，SHA-1所发现的弱点并没有影响其用作概率数据结构的散列函数。

SHA-2在2001年发布，其中包括6个具有不同摘要大小的散列函数：SHA-224、SHA-256、SHA-384、SHA-512等。SHA-2比SHA-1更强大，在当前的计算能力下，对SHA-2的攻击不太可能发生。

（3）RadioGatún

RadioGatún加密散列函数族于2006年在第二届加密散列研讨会上被提出［Be06］。RadioGatún的设计改进了已知的巴拿马散列函数。

与其他常用的散列函数类似，RadioGatún加密散列函数的输入被分成一系列数据块。这些数据块使用一个特殊函数注入算法的内部状态，然后迭代应用单个非加密轮函数（称为belt-and-mill round函数）。在每一轮中，状态被表示为两个部分，皮带和磨机，这两个部分由轮函数进行不同的处理。轮函数的应用包括四个并行操作：1）应用于磨机的非线性函数，2）应用于皮带的简单线性函数，3）以线性方式将磨机的一些位前馈给皮带，4）以线性方式将皮带的一些位前馈给磨机。注入所有输入块后，该算法将执行多轮，而无须输入或输出（空白轮），然后将部分状态作为最终的散列值返回。

在该系列中，带有64位字的RadioGatún64是默认选择，并且是64位平台的最佳选择。为了在32位平台上获得最佳性能，还可以使用带有32位字的RadioGatún32。

在相同的时钟频率下，据称RadioGatún32对于长输入而言，其速度比SHA-256快12倍；对于短输入而言，其速度比SHA-256快3.2倍，同时门数更少。对于长输入，RadioGatún64甚至比SHA-256快24倍，但逻辑门却多出约50％。

[1] Crypto++6.0.0 Benchmarks https://www.cryptopp.com/benchmarks.html

[2] VU#836068 http://www.kb.cert.org/vuls/id/836068