散列函数主要用于消息认证（Message Authentication）。在介绍散列函数之前，先了解一下什么是消息认证。加密是为了防止消息的泄露，实现机密性。有时候，我们不需要对消息进行保密，而需要保证消息是真实的并且其来源是可靠的。消息认证是一种允许通信方验证所接收或存储的消息是否真实的过程。消息认证包括两个重要方面：① 验证消息的内容没有被修改；② 验证消息的来源是真实的。除此之外，我们也可能希望验证消息的时效性（即消息没有被人为延迟或重放）和顺序。所有这些都是为了实现消息或数据的完整性。

有多种方法可以实现消息认证，如使用对称加密。假设只有发送方和接收方共享一个密钥，那么，只有真正的发送方才能够成功地为接收方加密消息（如果接收方能够识别有效的消息的话）。而且，如果消息中包含了错误检测码和序号的话，则接收方还可以确信消息没有被修改且顺序也是正确的。如果消息中包含了一个时间戳，则接收方还可以确信消息的传输没有超出网络传输的正常延迟。尽管如此，单独使用对称加密并不适合用于消息认证。

另外一种实现消息认证的方法是消息认证码（Message Authentication Code，MAC），它在密钥的参与下把一个消息转换成一个长度固定的小数据块，附在消息之后。这种技术假定通信双方（如A和B）共享一个密钥KAB。当A向B发送消息M时，它利用确定的算法和密钥KAB计算消息认证码：MAC = F（KAB，M）。消息和认证码MAC一起被发送给接收方。接收方B使用相同的密钥和算法对接收的消息执行同样的计算，产生一个新的MAC，然后与收到的MAC进行比较。如果二者相同，则接收方B可以相信消息的内容没有被修改，且消息来自真正的发送方A。有多种算法可以用来生成MAC，如使用DES算法并采用CBC模式，最后一个密文块的最后16 bit或32 bit作为MAC。

尽管消息认证码有时是一种非常有效的消息认证的方法，但实际得到广泛使用的是散列函数与公钥密码相结合的消息认证方法。因为后者效率更高，也更安全、更方便。

散列函数（Hash Function）是一种不可逆函数，它将任意长度的消息或数据映射成一个较短的、固定长度的数字串（如160 bit）。散列函数值又被称为散列值、散列码、消息摘要或数字指纹。散列函数在数学上保证：只要改动消息M的任何一比特，重新计算出的消息摘要就会与原消息的消息摘要不同，因此可以使用散列函数检测出对数据的任何修改。散列函数不仅在消息认证中而且在数字签名中都是很重要的。用于消息认证和数字签名的散列函数H必须具有以下性质：

（1）H可应用于任意大小的数据块。

（2）H产生固定长度的输出。

（3）对于任意给定的x，计算H（x）比较容易，并且其硬件和软件实现都是如此。

（4）对于任意给定的散列码h，找到满足H（x）= h的x在计算上是不可行的。

（5）对于任意给定的数据块x，找到满足y≠x且H（x）= H（y）的y在计算上是不可行的。

（6）找到满足H（x）= H（y）的任意的x和y在计算上是不可行的。

前3个性质是散列函数实际应用于消息认证所必须满足的。第4个性质是单向性，即由消息很容易计算出散列码，但是由散列码却不能计算出相应的消息。第5条性质可以保证，不能找到与给定消息具有相同散列值的另一个消息。当对散列码加密时，这可以阻止伪造消息。如果散列函数不具有这个性质，那么攻击者可以：首先观察或拦截一条消息及其加密的散列码；然后由这个消息产生一个未加密的散列码；最后产生另一条具有相同散列码的消息。

一个散列函数，如果满足上面列出的前5条性质，则称其为弱散列函数。如果也满足第6条性质，则称其为强散列函数。一个强散列函数能够防止一方伪造另一方签名的消息。例如，假如Alice同意在Bob发给她的欠款较少的欠条上签名。再假如Bob能够找到两条具有相同散列值的消息。一条消息要求Alice偿还较少的钱，另一条要求偿还较多的钱。Alice对第一条消息签名，而Bob却能够声称第二条消息是真的。

和对称加密一样，有两种方法可以攻击散列函数：密码分析和蛮力攻击。与对称加密算法一样，散列函数的密码分析也涉及利用算法中的逻辑漏洞。散列函数抵抗蛮力攻击的能力仅仅依赖于算法所产生的散列码的长度。早期使用的散列函数MD5的散列码长度为128 bit，被认为已不再安全。目前使用较广的是160 bit的SHA-1。不过，因为计算速度大幅提升等原因，160 bit的散列函数很快也会被淘汰。

需要注意的是，单独使用散列函数并不能实现消息认证，因为攻击者可以既修改消息也修改散列码。因此，散列函数通常与某种保密技术结合在一起使用，如公钥密码技术。

安全散列函数SHA（Secure Hash Algorithm）是由美国标准与技术研究所（NIST）设计的，并于1993年成为联邦信息处理标准。1995年NIST对它做了少量修订，通常称之为SHA-1。SHA-1生成160 bit的散列值。2002年，NIST再次对标准进行了修订，并定义了3个新版本的SHA，散列值的长度分别是256 bit、384 bit和512 bit，分别称为SHA-256、SHA-384和SHA-512。它们一起被称为SHA-2。新版本的SHA-2具有与SHA-1一样的底层结构，使用了与SHA-1同样类型的模运算和二元逻辑运算。表2-2给出了SHA-1和SHA-2的参数比较，其中的所有数据都以bit为单位。(www.daowen.com)

表2-2　SHA的参数比较

本节将简单描述SHA-512。其他版本与它非常相似。这个算法以最大长度不超过2128 bit的消息作为输入，生成512 bit的散列码或消息摘要。输入的消息被分成1 024 bit的数据块，逐块处理。图2-11描述了处理消息并生成摘要的全过程。处理过程包括以下步骤：

图2-11　用SHA-512生成消息摘要

第1步：添加填充比特。填充消息，使其长度值除以1 024后余数为896。注意，即使消息的长度值已经满足这个要求，仍然需要填充。因此，填充的比特数在1～1 024。所填充的值由一个1和后续的0组成。

第2步：添加长度值。在消息后附加128 bit的数据块。这个数据块被看作是一个无符号的128 bit的整数，其值等于原始消息的长度。注意，128+896 = 1 024。所以，至此，原始消息已经被处理成多个1 024 bit的数据块。

第3步：初始化散列缓冲区。散列函数的中间结果和最终结果保存在一个512 bit的缓冲区中。这个缓冲区可以用8个64 bit的寄存器（用a、b、c、d、e、f、g、h来表示）表示。这8个寄存器被初始化成8个不同的整数值。这些整数值取自前8个素数的平方根的小数部分的前64 bit。

第4步：以1 024 bit为单位，逐块处理消息。算法的核心是一个包含了80轮运算的模块。该模块的80轮运算在图2-11中标记为F，其逻辑如图2-12所示。

图2-12　SHA-512处理单个1 024 bit的数据块

每一轮都以512 bit的缓冲区值abcdefgh作为输入，并更新缓冲区的内容。在第0轮的输入处，缓冲区中存放有中间的散列值Hi-1。任意第t轮都使用一个64 bit值Wt，这个值来自当前正在处理的1 024 bit数据块（Mi）。每一轮还使用一个附加的常数Kt，其中0≤t≤79表示80轮中的某一轮。这些常数取自前80个素数的立方根的小数部分的前64 bit。它们用来随机化64 bit模式，消除输入数据中的任何规律。每一轮中执行的操作包括循环移位和基于与（AND）、或（OR）、非（NOT）、异或（XOR）的简单逻辑运算。

第79轮（从0轮开始，实际上是第80轮）的输出加到第0轮的输入（Hi-1）上，生成Hi。注意，每个寄存器单独与Hi-1中相应的64 bit相加，模264。

第5步：输出。当所有N个1 024 bit的数据块都处理完毕后，从第N个阶段输出的就是512 bit的消息摘要。

SHA-512算法具有这样的性质：散列码的每一比特都是消息的每一比特的函数。F的复杂的重复产生了很好的混淆效果，也就是说，即使随机选择的两条消息呈现出相似的规律，它们各自的散列码也很难相同。