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

謝平華

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

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

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

但是，若采用直接比較郵件內(nèi)容的方法來識(shí)別重復(fù)郵件，不僅需要將郵件原文全部保存入庫，而且對(duì)大文本進(jìn)行逐字匹配的效率也不高，算法在時(shí)間復(fù)雜度和空間復(fù)雜度上都有較大的缺憾，還會(huì)影響新郵件的實(shí)時(shí)接收。鑒于此，我們經(jīng)過認(rèn)真研究，決定在郵件分析程序中構(gòu)造郵件要素的特征值，并應(yīng)用MD5算法，實(shí)現(xiàn)對(duì)重復(fù)郵件的識(shí)別，從而準(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ù)字簽名軟件簽署私人密匙前被“壓縮”成一種保密的格式（即將一個(gè)任意長(zhǎng)度的字節(jié)串變換成一個(gè)定長(zhǎng)的大整數(shù)）。MD5的典型應(yīng)用是對(duì)一段信息產(chǎn)生信息摘要（Message-Digest），以防止信息內(nèi)容被篡改。比如，在UNIX下有很多軟件在下載的時(shí)候都有一個(gè)相同的擴(kuò)展名為.md5的文件，在這個(gè)文件中通常只有一行文本，大致結(jié)構(gòu)如：

MD5（tanajiya.tar.gz）=0ca175b9c0f726a831d895e269332461

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

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

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

1）補(bǔ)位

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

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

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

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

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

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

4）定義四個(gè)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）定義四個(gè)分別用于四輪變換的函數(shù)：

設(shè)Mj表示消息的第j個(gè)子分組（從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）對(duì)輸入數(shù)據(jù)作變換

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

7）輸出結(jié)果

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

例：MD5 ("") = d41d8cd98f00b204e9800998ecf8427e

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

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

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

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

3 結(jié)論

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

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

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