MD5算法在重复邮件识别方面的研究和实现

摘 要 描述 MD5 信息-摘要算法。这种算法可以将任意长度的信息处理成一个128bit(定长)的“指纹”或“信息摘要”。任意两个不同信息不可能处理成同样的信息摘要，同时根据得到的信息摘要也不可能逆推出原始信息。MD5算法主要用于数字签名，出于安全的考虑，任何信息(明文)在用公钥加密系统(例如RSA)加密传送前，都要用MD5算法处理出一个信息摘要。并应用MD5算法，实现对重复邮件的识别，从而准确、快速地将无用邮件过滤出来。

关键词 MD5；信息-摘要算法；重复邮件的识别；邮件过滤

中图分类号TN918 文献标识码A 文章编号 1674-6708（2011）57-0185-02

随着网络和通信技术的发展，国际互联网正日渐成为全球最大的信息媒体，在人们的生活中发挥着越来越重要的作用。其中，电子邮件作为一种新的联系方式，在互联网上的应用十分普遍，邮件服务器众多，用户数量巨大。通过电子邮件，人们可以方便、快捷地向他人传递信息，可以和他人实现跨时间、跨地域的相互交流。电子邮件正代替传统的通信信件，成为人们生活当中不可或缺的一部分。

在实际的应用中，舆情监测系统每天从互联网上实时获取大量的电子邮件信息，存储在本地之后，再进行后续地处理和分析，因为存在着以下的情况，很多重复的邮件也被采集存储下来：同一封邮件同时向地址簿中的多个联系人发送；向同一个人重复发送同一封邮件。重复邮件的存在，不仅浪费了宝贵的存储空间和带宽资源，而且大大增加了后端人员对邮件的处理和分析工作量。因此，对重复邮件进行识别和过滤，成为提高工作效率的关键环节。

但是，若采用直接比较邮件内容的方法来识别重复邮件，不仅需要将邮件原文全部保存入库，而且对大文本进行逐字匹配的效率也不高，算法在时间复杂度和空间复杂度上都有较大的缺憾，还会影响新邮件的实时接收。鉴于此，我们经过认真研究，决定在邮件分析程序中构造邮件要素的特征值，并应用MD5算法，实现对重复邮件的识别，从而准确、快速地将无用邮件过滤出来。

1 MD5算法描述

MD5的全称是Message-Digest Algorithm 5（信息-摘要算法）[2]，在90年代初由MIT Laboratory for Computer Science和RSA Data Security Inc的Ronald L. Rivest开发出来，经MD2、MD3和MD4发展而来。它的作用是让大容量信息在用数字签名软件签署私人密匙前被“压缩”成一种保密的格式（即将一个任意长度的字节串变换成一个定长的大整数）。MD5的典型应用是对一段信息产生信息摘要（Message-Digest），以防止信息内容被篡改。比如，在UNIX下有很多软件在下载的时候都有一个相同的扩展名为.md5的文件，在这个文件中通常只有一行文本，大致结构如：

MD5（tanajiya.tar.gz）=0ca175b9c0f726a831d895e269332461

这就是tanajiya.tar.gz文件的数字签名。MD5将整个文件当作一个大文本信息，通过其不可逆的字符串变换算法，产生了这个唯一的MD5信息摘要。如果在以后传播这个文件的过程中，无论文件的内容发生了任何形式的改变（包括人为修改或者下载过程中线路不稳定引起的传输错误等），只要对这个文件重新计算MD5，就会发现信息摘要不相同，由此可以确定得到的是一个不正确的文件。

MD5还广泛用于加密和解密技术上。比如在UNIX系统中，用户的密码就是以MD5（或其它类似的算法）经加密后存储在文件系统中。当用户登录的时候，系统把用户输入的密码计算成MD5值，然后再去和保存在文件系统中的MD5值进行比较，进而确定输入的密码是否正确。通过这样的步骤，系统在并不知道用户密码的明码的情况下就可以确定用户登录系统的合法性。这不但可以避免用户的密码被具有系统管理员权限的用户知道，而且还在一定程度上增加了密码被破解的难度。

MD5算法输入是一个任意长度的字节串，每个字节是8个bit。算法的执行分为以下几个步骤：

1）补位

MD5算法先对输入的数据进行补位，使得数据的长度（以byte为单位）对64求余的结果是56。即数据扩展至LEN=K*64+56个字节，K为整数。补位方法：补一个1，然后补0至满足上述要求。相当于补一个0x80的字节，再补值为0的字节。这一步里总共补充的字节数为0个~63个。

2）附加数据长度

用一个64位的整数表示数据的原始长度（以bit为单位），将这个数字的8个字节按低位的在前，高位在后的顺序附加在补位后的数据后面。这时，数据被填补后的总长度为：LEN=K*64+56+8=(K+1)*64 Bytes。

3）初始化MD5参数

设置四个32位整数变量（A,B,C,D）用来计算信息摘要，每一个变量被初始化成以下用十六进制数表示的数值：

A=0x67452301；B=0xefcdab89；C=0x98badcfe；D=0x10325476

4）定义四个MD5基本的按位操作函数

F(X,Y,Z) = (X and Y) or (not(X) and Z)

G(X,Y,Z) = (X and Z) or (Y and not(Z))

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

I(X,Y,Z) = Y xor (X or not(Z))

其中，X，Y，Z均为32位整数。

5）定义四个分别用于四轮变换的函数：

设Mj表示消息的第j个子分组（从0到15），常数ti为4294967296*abs(sin(i))的整数部分，i的单位是弧度, i的取值从1到64，s表示左移的位数，a、b、c、d的初值分别取A、B、C、D：

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

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

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

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

四轮变换分别是：

第一轮：

FF(a,b,c,d,M0,7,0xd76aa478)；

FF(d,a,b,c,M1,12,0xe8c7b756)；

… FF(b,c,d,a,M15,22,0x49b40821)；

第二轮

GG(a,b,c,d,M1,5,0xf61e2562)；

GG(d,a,b,c,M6,9,0xc040b340)；

… GG(b,c,d,a,M12,20,0x8d2a4c8a)；

第三轮

HH(a,b,c,d,M5,4,0xfffa3942)；

HH(d,a,b,c,M8,11,0x8771f681)；

… HH(b,c,d,a,M2,23,0xc4ac5665)；

第四轮

II(a,b,c,d,M0,6,0xf4292244)；

II(d,a,b,c,M7,10,0x432aff97)；

… II(b,c,d,a,M9,21,0xeb86d391)；

6）对输入数据作变换

处理步骤2中得到的被填补后的数据，以64个字节为一组，每组作一次循环，每次循环进行四作。

7）输出结果

循环完成后，将a、b、c、d的值顺序拼接在一起，共128位，再转换为16进制，以字符串的形式输出。

例：MD5 ("") = d41d8cd98f00b204e9800998ecf8427e

2 MD5算法在重复邮件识别中的具体实现

在实际系统中，我们针对每封邮件抽取其发件人邮箱、邮件主题、邮件正文的文本内容、附件名称、附件大小等五种要素，采用字符串拼接的方式，构造邮件的特征值T，则T=发件人邮箱+邮件主题+邮件正文文本+附件名称+附件大小,

对特征值T采用MD5算法进行运算，得到每封邮件唯一的哈希值：H=MD5(T)，将已有邮件i的哈希值Hi保存在数据库中。当新邮件j到达时，比较Hj和Hi,若Hj=Hi,则j为重复邮件，丢弃，否则将j作为有用邮件进行后续处理，并将Hj写入数据库保存。程序流程如下图所示。

基于MD5算法的成熟和易实现性，系统采用比较邮件的MD5哈希值的方法来识别重复邮件，程序的可移植性强，对重复邮件的判断准确，过滤效果较好，克服了直接比较邮件内容在时间复杂度和空间复杂度上的缺点，在实际工作中发挥了巨大的作用。基于这种理论思路，我们将其扩展到整个系统的数据去重的处理上面，达到了很好的实际效果。

3 结论

本文首先简要介绍了海量数据挖掘及舆情分析技术，然后规划了整个系统的系统模型。随后本文以BBS舆情分析系统的实现，阐述了舆情分析系统的具体实现方式和原理。然后，本文又重点研究了MD5算法在重复邮件识别中的应用，并将其广泛应用于数据去重方面的处理。

参考文献

[1]王永成，沈州，许一震.改进的多模式匹配算法[J].计算机研究与发展，2002，39(1)：55-60.

[2]万国根，秦志光.改进的AC－BC字符串匹配算法.电子科技大学学报，2006，35(4).

[3]Rivest, R., "MD4 信息摘要算法", RFC 1320, MIT and RSA Data Security, Inc., 1992，四,.

[4]Rivest, R., "MD4 信息摘要算法", in A.J. Menezes and S.A.Vanstone, editors, Advances in Cryptology - CRYPTO '90 Proceedings, pages 303-311, Springer-Verlag, 1991.