第五节 信息摘要算法的分析

信息摘要（Message Digest, MD）算法（通常称之为哈希算法），能对任何输入的信息进行处理，生成128位长的“信息摘要”输出，也称为“指纹采集”。理论上，要求两个不同的输入信息不能有相同的信息摘要。

信息摘要算法技术的产生源于非对称密钥体制的发展。RSA的出现使数字签名成为可能，但由于RSA的计算效率较低，难以实用化。于是RSA的发明者之一，MIT的Ron Rivest教授提出了信息摘要算法MD，由于该算法用于商业化的安全产品，所以没有发表。Rivest教授后来又提出了MD2（RFC1319）。之后，Xeror的Merkle于1990年提出一个新的信息摘要算法SNEFRU，计算效率比MD2高几倍，这又促使Rivest将MD2改进为MD4，效率比SNEFRU更高一些。SNEFRU于1992年被攻破，即可以为一个摘要构造出两个不同的信息；MD4也发现有一些弱点，于是MD4又改进为MD5，强度增加，效率降低。美国NIST另外建议了一个信息摘要算法SHS，它比MD5强度更高，但效率更低。下面简单分析几个常用的信息摘要算法。

一、MD5算法

MD5是MD算法的最新版本，是一种安全的哈希算法，是由RSA Data Security公司提出的。MD5（Message-Digest Algorithm 5）是一个在世界范围内有着广泛应用的散列函数算法，它曾一度被认为是非常安全的。然而，在2004年8月17日美国加利福尼亚圣巴巴拉召开的国际密码学会议上，来自我国山东大学的王小云教授做了破译MD5、HAVAL-128、MD4和RIPEMD算法的报告。她的研究成果是近年来密码学领域的最具实质性的进展。

王小云教授发现，可以很快找到MD5的“碰撞”，这意味着，当在网络上使用电子签名签署一份合同后，还可能找到另外一份具有相同签名但内容迥异的合同，这样两份合同的真伪性便无从辨别。王小云教授的研究成果证实了利用MD5算法的“碰撞”可以严重威胁信息系统的安全，这一发现使目前电子签名的法律效力和技术体系受到挑战。

但是就目前的技术水平和可能的应用而言，还很难找到一种综合性能更好的可以替代MD5的算法，所以本节仍对MD5做介绍。

1．MD5算法原理

该算法将所需处理的文件以512位分组，每一分组又划分为16个32位子分组，并初始化四个32位的变量A、B、C、D。算法的输出由四个32位变量组成，将它们连接形成一个128位散列值。MD5对文件进行“摘要”的过程如下。

1）填充文件，使其长度为模512余448位。填充方法是，填充部分第一位为1，后面全为0，如图1.8所示。

2）添加文件原始长度（未填充前）项64位，使此时文件总长度正好为512的整数倍，如图1.8所示。

3）初始化四个32位连接变量A、B、C、D，其中A=0x1234567, B=0x89abcdef, C=0xfedcba98, D=0x76543210。

4）进行算法主循环。主循环次数是文件中512位分组的数目。每次主循环又分四轮，每一轮进行16次操作。每次主循环时，先将A、B、C、D复制到另四个变量a、b、c、d中，每次操作对a、b、c和d中的任意三个做一次非线性函数运算，然后将所得结果加上第四个变量、文件中的一个子分组和一个常数，再将所得结果向左移若干位，并加上a、b、c或d中的一个，后用该结果取代a、b、c或d中的一个。

四轮操作结束后，将A、B、C、D分别加上d、b、c、d，然后用下一分组数据继续运行算法，最后的输出是A、B、C和D的级联。算法流程如图1.9所示。

在算法中用到的四个非线性函数（每轮一个）为

F(X, Y, Z)=(X&Y)|((~X)&Z)

G(X, Y, Z)=(X&Z)|(Y&(~Z))

H(X, Y, Z)=X ^Y ^Z

I(X, Y, Z)=Y ^(X |(~Z))

其中，&表示与，|表示或，~表示反，^表示异或。

设Mj表示文件的第j个子分组（0＜j＜15），＜＜＜s表示循环左移s位，ti表示常数，则四种操作为

FF（a, b, c, d, Mj, s, ti）表示a=b+(a+(F(b, c, d)+ Mj+ti)＜＜＜s)

GG（a, b, c, d, Mj, s, ti）表示a=b+(a+(G(b, c, d)+ Mj+ti)＜＜＜s)

HH（a, b, c, d, Mj, s, ti）表示a=b+(a+(H(b, c, d)+ Mj+ti)＜＜＜s)

II（a, b, c, d, Mj, s, ti）表示a=b+(a+(I(b, c, d)+ Mj+ti)＜＜＜s)

常数ti可按如下方法选择：在第i步中，ti是232*abs(sin(i))的整数部分，i的单位为弧度。

2．MD5算法的应用

可以利用MD5算法设计一个文件完整性检测的程序。

为了检测数据是否被非法篡改，一般可采用比较数据文件长度、文件修改时间等方法，以此来判断数据文件是否发生了变化。但这样的比较存在一些问题：当入侵者仅将数据文件中的一部分内容替换成大小相同的其他内容时，通过比较文件的长度就无法发现文件的改变；当入侵者修改了系统时间后，通过比较数据文件的修改时间也无法发现文件已被篡改。而采用单向散列函数可克服这些缺陷。通过将单向散列函数作用于数据文件，得到一个固定的散列值。数据文件发生任何一点变化，通过单向散列函数计算出的散列值就会不同。

为了便于应用，我们将MD5封装为一个方便使用的类。

        Class MD5
        {
            Public:
            MD5（）;
              Virtual ~MD5（）；
              Char ＊sig_md5_get（CString fd）;
            Private:
            Void MD5Update（MD5_CTX ＊mdContest, unsigned char ＊inBuf , unsigned int inlen）;
            Static void Transform（UINT4 ＊buf, UINT4 ＊in）;
            Void MD5Init（MD5_CTX ＊mdContext）;
            Void MD5Final（MD5_CTX ＊mdContext）;
        };

程序运行时，仅需通过文件对话框选择所要检测的数据文件即可自动备份相关文件到指定磁盘中，在备份的同时，系统将所需检测的数据文件的文件名、数字摘要以及备份文件的磁盘符、路径、文件名写入数据表，以供检测时使用。

当进行检测时，系统每隔指定的时间（如半小时），将数据表中所需检测的文件轮询一遍，把根据文件计算出的当前数字摘要与数据表中该文件原有的数字摘要做比较，来判断文件是否被修改。若发现改动，则立即报警，并用备份盘上的备份文件进行恢复。一次轮询过程如图1.10所示。

二、其他信息摘要算法

1．安全哈希算法

安全哈希算法（SHA）也被称为安全哈希标准（Secure Hash Standard, SHS），是由美国政府提出的，它能为任意长度的字符串生成160位的哈希值。它比MD5慢25%，但更安全，因为它的信息摘要比由MD函数产生的要长25%，这使得它能比MD5更加有效地抵抗强行攻击。

SHA在结构上与MD4、MD5相似，即将信息分成若干个512位的定长块，每一块与当前的信息摘要值结合，产生信息摘要的下一个中间结果，直至处理完毕。对于每一个信息块，SHA使用五遍扫描，因此效率比MD5低。SHA的填充与MD4一样。信息摘要的初值为0X67452301、0XEFCDAB89、0X98BADCFE和0XC3D2E1F0。

2．HMAC算法

HMAC（RFC2104）是由IBM的H. Krawczyk等人于1997年提出的一种利用对称密钥K和单向函数H（类同于MD5或SHA-1等）生成信息鉴别码的方法，其特点是直接使用现有的单向函数，计算效率和安全强度依赖于所选用的单向函数，密钥和函数的管理比较简单。

令B为信息的块长，L为单向函数输出长度，均用字节表示。HMAC使用的密钥可以是任意长度，如大于B，则首先用H函数将其压缩至B。K的长度不小于L，否则会降低单向函数的安全性。定义了如下两个固定的填充串。

ipad=0x36重复B次。

opad=0x5c重复B次。

于是HMAC的计算公式为H（K⊕opad, H（K⊕ipad, text））。具体步骤如下。

1）在K之后用0x00进行填充至B字节长度，如K为20字节长而B为64，则在K后面填充44个0x00。

2）计算填充过的K⊕ipad。

3）用同样方法对信息text进行填充。

4）用步骤2）的结果和填充过的text进行H计算。

5）计算K⊕opad。

6）用同样方法对步骤4）的结果进行填充。

7）用步骤5）和步骤6）的结果进行H计算，得到最终结果。

（K⊕opad）和（K⊕ipad）可以预先一次性计算好，因此HMAC的计算效率高，但这些预先计算好的值需要像密钥那样得到安全保护。由于信息鉴别无后效性，即使HMAC所使用的单向函数被攻破，也无法影响已经进行过的鉴别结论，只是以后的信息鉴别需要更换新的单向函数，这一点与加密函数有很大的不同。