3.3.1
哈希函数

实际中，信息 m 可能很长，直接对 m 进行签名是低效的。一般的方法是先为信息 m 生成“摘要”，然后对摘要进行签名，这并不影响签名的安全性。哈希函数就是生成数字摘要的有效手段。

哈希函数的计算过程可用 y = h ( x )表示。 x 是原始信息， y 是 x 的短摘要。哈希函数有几个重要特点。第一，它是单向的，即只能由 x 求解 y ，而不能轻易用 y 反推 x 。第二，它要抗碰撞，即在计算上很难找到两个不同的原始消息 x ₁ 和 x ₂ ，使它们的摘要相等，即 h ( x ₁ )= h ( x ₂ )。

最常见的哈希函数有MD5和SHA-1算法。它们的哈希摘要长度不同，SHA-1算法的哈希摘要长度为160，而MD5算法的摘要长度为128。

1979年，Merkle提出了一种统一的哈希函数构造。该构造中，消息 m 被划分为若干等份，然后迭代式地运用一个压缩函数 f 对每一块进行处理，最终得出摘要。这个过程如图3-3所示。

MD5函数和SHA-1函数都采用上述通用架构。

MD5将原文消息划分为长度为512比特的等份。由于原文消息的长度是任意的，在MD5算法的开始阶段首先要对消息进行填充，使得它恰好为512的整数倍。对每一个512长度的分块，按照通用架构的过程，利用函数 f _MD5 进行迭代式的处理。 f _MD5 函数的内部结构也是迭代的，它包含64步操作，主要由逻辑与、或、异或和否等运算组成，中间结果保存在4个32位的寄存器中，非常便于计算机实现。上述两个层次的迭代和多种逻辑运算，使得MD5输出的128位摘要值的每一位都和输入消息 m 的每一位相关，充分地混淆和扩散了数据。由于具有这样的效果，因此人们也将哈希函数称为“散列”函数。

SHA-1算法对原始信息的分块预处理、整体的运算架构和MD5算法并无重大区别。但在每一轮迭代的压缩函数 f _SHA-1 比MD5算法设计更精妙。SHA-1算法中的每个数据块要经过80轮的运算，每一轮计算的中间结果保存在5个32位的寄存器中。进一步来说，在每一轮运算中， f _SHA-1 引入了可变的运算子函数和加法常量，冗余度和复杂性都比MD5更高。SHA-1的哈希摘要长度比MD5长32位，因此一般认为SHA-1的抗攻击性稍高，但是其计算复杂度也更高一些。

一般认为，摘要长度越长，哈希函数的安全性越高。在SHA-1之后，美国标准局又引入了SHA-256、SHA-384和SHA-512，进一步扩展了摘要长度。 wn8FEfXYhrZgR6MW8oj+fPdBKZBUKaFoLVkiTPb0bROv4Y64rTqsoECAfBiORUmh