哈希函数和消息认证码：保障信息安全的重要手段

一个密码学中的哈希函数基于运行单向压缩函数，使得从任意大小的数据块压缩到长度为n的固定输出。这一般通过运行许多轮运算实现，输出的长度n意味着哈希函数提供的安全等级。哈希函数应该容易计算，是人们共知的，并且使软/硬件实现更实际。哈希函数也应具有下列附加属性：

1）单向性：给定消息M的哈希值H=h（M），找到消息M是计算不可行的。

2）弱抗碰撞性：对任意给定的消息M，找到M′≠M，并且h（M′）=h（M），是计算不可行的。

3）强抗碰撞性：找到任意对（M，M′），使得h（M′）=h（M）是计算不可行的。

哈希函数将输入视为nbit块的序列，每次处理一块，重复进行。例9-5描述了一个简单哈希函数。注意到独立于输入数据的长度，此哈希函数总是生成一个nbit的值。

例9-5

使用逐比特异或运算的简单哈希函数

哈希函数可使用分组密码或模运算作为压缩函数。然而，因为密钥-子密钥处理过程使用分组密码，所以效率较低。大多数人的注意焦点是专用哈希函数如消息摘要（Message Digest，MD）系列MD2、MD4和MD5，安全哈希算法（Secure Hash Algorithm，SHA）系 列SHA-0、SHA-1、SHA-256、SHA-384和SHA-512，RIPEMD（RACE Integrity Primitives Evaluation Message Digest）系 列RIPEMD、RIPEMD-128和RIPEMD-160，以及其他的如HAVAL和Whirlpool。MD5仅对数据处理一遍，生成128bit的摘要。已多次证实MD5不能满足抗碰撞性质。2006年，公开了用简单的便携计算机，在几分钟内发现MD5摘要碰撞的算法（Klima，2006）。

例9-6描述的SHA-1是替代SHA-0的安全哈希算法，广泛应用在很多密码系统中。如例9-6所示，SHA-1以512bit块为单位处理数据，需要四轮运算。每轮20步，特定于某轮的一个函数如F、一个常量如K，作用于消息摘要缓冲区中的值。SHA-1产生长度为160bit的消息摘要。

例9-6

SHA_-1

符号：∨逻辑或运算

∧逻辑与运算

！逻辑反

⊕逻辑异或运算

←逐比特循环左移

|附加

输入预处理

为输入消息追加比特“1”

为输入消息填充k比特“0”，k≥0，最终消息长度是填充后消息的长度为512bit的某一倍数减64bit。在预处理前按比特填充消息，作为64bit big-endian整数。

初始化消息摘要缓冲区

H0=0x67452301

H1=0xEFCDAB89

H2=0x98BADCFE

H3=0x10325476

H4=0xC3D2E1F0

以512bit块为单位处理消息，直到消息末尾。

消息摘要缓冲区赋值

A=H0

B=H1

C=H2

D=H3

E=H4

块拆成32bit的16个字，即

w[i]，0≤i≤15

扩展块成80个字，即

For i from 16 to 79

w[i]=（w[i-3]⊕w[i-8]⊕w[i-14]⊕w[i-16]）←1

第1轮

K=0X5A827999

For i from 0 to 19

F=（B∧C）∨（！B∧D）（存在可替代的函数）

T=（a←5）+f+E+K+w[i]

E=D

D=C

C=B←30

B=A

A=T

第2轮(www.xing528.com)

K=0X6ED9EBA1

For i from 20 to 39

F=B⊕C⊕D

T=（a←5）+f+E+K+w[i]

E=D

D=C

C=B←30

B=A

A=T

第3轮

K=0X8F1BBCDC

For i from 40 to 59

F=（B∧C）∨（B∧D）∨（C∧D）（存在可替代的函数）

T=（a←5）+f+E+K+w[i]

E=D

D=C

C=B←30

B=A

A=T第4轮

K=0XCA62C1D6

For i from 60 to 79

F=B⊕C⊕D

T=（a←5）+f+E+K+w[i]

E=D

D=C

C=B←30

B=A

A=T这个块的哈希结果加到消息缓冲区

H0=H0+A

H1=H1+B

H2=H2+C

H3=H3+D

H4=H4+E当所有消息处理结束，输出消息摘要（MD）

MD=H0|H1|H2|H3|H4一个如SHA-1的哈希函数从两个固定长度的输入产生一个固定长度的输出。输出长度一般与其中一个输入的长度相同。SHA-1中，用于消息摘要缓冲区初始化的值的总长度是160bit，输出也是160bit，这与另一输入的长度（至少512bit）无关。因此，这类哈希函数也称为压缩函数，可以将大的输入变换到短的、固定长度的输出。

哈希函数提供了数据完整性手段。对消息M，计算哈希值H=h（M），并与消息一起发送。若接收者对接收的消息M′，用相同的哈希函数h计算的哈希值H′=h（M′）不同于与M一起发送的H，接收者必须接受M′是M的修改版。这里，H称为消息完整性码（Message Integrity Code，MIC），应该加密传输，作为消息完整性的一种可靠度量。

另一方面，在压缩过程中使用私钥作为输入的消息认证码（Message Authenti-cation Code，MAC）不需要加密。MAC算法的一个例子是哈希消息认证码（HMAC）。设计HMAC，使其能使用任何其他可用的哈希函数，如MD5或SHA-1。HMAC的设计目标如下：

1）使用任意可用的哈希函数；

2）容易替换旧的哈希函数；

3）除了使用的哈希函数的计算代价外，带来的计算代价可忽略；

4）对认证强度提供清晰的密码分析。

图9-10所示的HMAC结构，密钥首先在左端用0填充，变成bbit长。填充的

图9-10 HMAC

密钥K^+与ipad进行异或运算，其中ipad是00110110重复b/8次。运算结果填充到消息中。得到所选择哈希函数的输入。第二轮，K^+与另一常量opad进行异或运算，opad是01011100重复b/8次。运算结果追加到第一轮的输出中。最终的比特流再应用一次哈希运算，产生mbit的消息认证码。

总之，有三种方式产生MAC：

1）用密码学哈希函数生成MIC，并附加在用对称加密算法加密的消息后，这提供了完整性和认证。

2）用类似HMAC的结构生成MAC，并附加在传输的消息后，这也提供了完整性和认证。

3）用密码学哈希函数生成MIC，并附加在用非对称加密算法（如数字签名）加密的消息后。除了提供完整性和认证，这种方式也保证了不可否认性。