MD5算法在重復(fù)郵件識別方面的研究和實現(xiàn)

謝平華

貴州大學(xué)計算機科學(xué)與信息技術(shù)學(xué)院，貴州貴陽 550025

隨著網(wǎng)絡(luò)和通信技術(shù)的發(fā)展，國際互聯(lián)網(wǎng)正日漸成為全球最大的信息媒體，在人們的生活中發(fā)揮著越來越重要的作用。其中，電子郵件作為一種新的聯(lián)系方式，在互聯(lián)網(wǎng)上的應(yīng)用十分普遍，郵件服務(wù)器眾多，用戶數(shù)量巨大。通過電子郵件，人們可以方便、快捷地向他人傳遞信息，可以和他人實現(xiàn)跨時間、跨地域的相互交流。電子郵件正代替?zhèn)鹘y(tǒng)的通信信件，成為人們生活當(dāng)中不可或缺的一部分。

在實際的應(yīng)用中，輿情監(jiān)測系統(tǒng)每天從互聯(lián)網(wǎng)上實時獲取大量的電子郵件信息，存儲在本地之后，再進行后續(xù)地處理和分析，因為存在著以下的情況，很多重復(fù)的郵件也被采集存儲下來：同一封郵件同時向地址簿中的多個聯(lián)系人發(fā)送；向同一個人重復(fù)發(fā)送同一封郵件。重復(fù)郵件的存在，不僅浪費了寶貴的存儲空間和帶寬資源，而且大大增加了后端人員對郵件的處理和分析工作量。因此，對重復(fù)郵件進行識別和過濾，成為提高工作效率的關(guān)鍵環(huán)節(jié)。

但是，若采用直接比較郵件內(nèi)容的方法來識別重復(fù)郵件，不僅需要將郵件原文全部保存入庫，而且對大文本進行逐字匹配的效率也不高，算法在時間復(fù)雜度和空間復(fù)雜度上都有較大的缺憾，還會影響新郵件的實時接收。鑒于此，我們經(jīng)過認真研究，決定在郵件分析程序中構(gòu)造郵件要素的特征值，并應(yīng)用MD5算法，實現(xiàn)對重復(fù)郵件的識別，從而準(zhǔn)確、快速地將無用郵件過濾出來。

1 MD5算法描述

MD5的全稱是Message-Digest Algorithm 5（信息-摘要算法）[2]，在90年代初由MIT Laboratory for Computer Science和RSA Data Security Inc的Ronald L. Rivest開發(fā)出來，經(jīng)MD2、MD3和MD4發(fā)展而來。它的作用是讓大容量信息在用數(shù)字簽名軟件簽署私人密匙前被“壓縮”成一種保密的格式（即將一個任意長度的字節(jié)串變換成一個定長的大整數(shù)）。MD5的典型應(yīng)用是對一段信息產(chǎn)生信息摘要（Message-Digest），以防止信息內(nèi)容被篡改。比如，在UNIX下有很多軟件在下載的時候都有一個相同的擴展名為.md5的文件，在這個文件中通常只有一行文本，大致結(jié)構(gòu)如：

MD5（tanajiya.tar.gz）=0ca175b9c0f726a831d895e269332461

這就是tanajiya.tar.gz文件的數(shù)字簽名。MD5將整個文件當(dāng)作一個大文本信息，通過其不可逆的字符串變換算法，產(chǎn)生了這個唯一的MD5信息摘要。如果在以后傳播這個文件的過程中，無論文件的內(nèi)容發(fā)生了任何形式的改變（包括人為修改或者下載過程中線路不穩(wěn)定引起的傳輸錯誤等），只要對這個文件重新計算MD5，就會發(fā)現(xiàn)信息摘要不相同，由此可以確定得到的是一個不正確的文件。

MD5還廣泛用于加密和解密技術(shù)上。比如在UNIX系統(tǒng)中，用戶的密碼就是以MD5（或其它類似的算法）經(jīng)加密后存儲在文件系統(tǒng)中。當(dāng)用戶登錄的時候，系統(tǒng)把用戶輸入的密碼計算成MD5值，然后再去和保存在文件系統(tǒng)中的MD5值進行比較，進而確定輸入的密碼是否正確。通過這樣的步驟，系統(tǒng)在并不知道用戶密碼的明碼的情況下就可以確定用戶登錄系統(tǒng)的合法性。這不但可以避免用戶的密碼被具有系統(tǒng)管理員權(quán)限的用戶知道，而且還在一定程度上增加了密碼被破解的難度。

MD5算法輸入是一個任意長度的字節(jié)串，每個字節(jié)是8個bit。算法的執(zhí)行分為以下幾個步驟：

1）補位

MD5算法先對輸入的數(shù)據(jù)進行補位，使得數(shù)據(jù)的長度（以byte為單位）對64求余的結(jié)果是56。即數(shù)據(jù)擴展至LEN=K*64+56個字節(jié)，K為整數(shù)。補位方法：補一個1，然后補0至滿足上述要求。相當(dāng)于補一個0x80的字節(jié)，再補值為0的字節(jié)。這一步里總共補充的字節(jié)數(shù)為0個～63個。

2）附加數(shù)據(jù)長度

用一個64位的整數(shù)表示數(shù)據(jù)的原始長度（以bit為單位），將這個數(shù)字的8個字節(jié)按低位的在前，高位在后的順序附加在補位后的數(shù)據(jù)后面。這時，數(shù)據(jù)被填補后的總長度為：LEN=K*64+56+8=(K+1)*64 Bytes。

3）初始化MD5參數(shù)

設(shè)置四個32位整數(shù)變量（A,B,C,D）用來計算信息摘要，每一個變量被初始化成以下用十六進制數(shù)表示的數(shù)值：

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

4）定義四個MD5基本的按位操作函數(shù)

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位整數(shù)。

5）定義四個分別用于四輪變換的函數(shù)：

設(shè)Mj表示消息的第j個子分組（從0到15），常數(shù)ti為4294967296*abs(sin(i))的整數(shù)部分，i的單位是弧度, i的取值從1到64，s表示左移的位數(shù)，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）對輸入數(shù)據(jù)作變換

處理步驟2中得到的被填補后的數(shù)據(jù)，以64個字節(jié)為一組，每組作一次循環(huán)，每次循環(huán)進行四輪操作。

7）輸出結(jié)果

循環(huán)完成后，將a、b、c、d的值順序拼接在一起，共128位，再轉(zhuǎn)換為16進制，以字符串的形式輸出。

例：MD5 ("") = d41d8cd98f00b204e9800998ecf8427e

2 MD5算法在重復(fù)郵件識別中的具體實現(xiàn)

在實際系統(tǒng)中，我們針對每封郵件抽取其發(fā)件人郵箱、郵件主題、郵件正文的文本內(nèi)容、附件名稱、附件大小等五種要素，采用字符串拼接的方式，構(gòu)造郵件的特征值T，則T=發(fā)件人郵箱+郵件主題+郵件正文文本+附件名稱+附件大小,

對特征值T采用MD5算法進行運算，得到每封郵件唯一的哈希值：H=MD5(T)，將已有郵件i的哈希值Hi保存在數(shù)據(jù)庫中。當(dāng)新郵件j到達時，比較Hj和Hi,若Hj=Hi,則j為重復(fù)郵件，丟棄，否則將j作為有用郵件進行后續(xù)處理，并將Hj寫入數(shù)據(jù)庫保存。程序流程如下圖所示。

基于MD5算法的成熟和易實現(xiàn)性，系統(tǒng)采用比較郵件的MD5哈希值的方法來識別重復(fù)郵件，程序的可移植性強，對重復(fù)郵件的判斷準(zhǔn)確，過濾效果較好，克服了直接比較郵件內(nèi)容在時間復(fù)雜度和空間復(fù)雜度上的缺點，在實際工作中發(fā)揮了巨大的作用。基于這種理論思路，我們將其擴展到整個系統(tǒng)的數(shù)據(jù)去重的處理上面，達到了很好的實際效果。

3 結(jié)論

本文首先簡要介紹了海量數(shù)據(jù)挖掘及輿情分析技術(shù)，然后規(guī)劃了整個系統(tǒng)的系統(tǒng)模型。隨后本文以BBS輿情分析系統(tǒng)的實現(xiàn)，闡述了輿情分析系統(tǒng)的具體實現(xiàn)方式和原理。然后，本文又重點研究了MD5算法在重復(fù)郵件識別中的應(yīng)用，并將其廣泛應(yīng)用于數(shù)據(jù)去重方面的處理。

[1]王永成，沈州，許一震.改進的多模式匹配算法[J].計算機研究與發(fā)展，2002，39(1)：55-60.

[2]萬國根，秦志光.改進的AC－BC字符串匹配算法.電子科技大學(xué)學(xué)報，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.