謝平華
貴州大學(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)測系統(tǒng)每天從互聯(lián)網(wǎng)上實(shí)時(shí)獲取大量的電子郵件信息,存儲在本地之后,再進(jìn)行后續(xù)地處理和分析,因?yàn)榇嬖谥韵碌那闆r,很多重復(fù)的郵件也被采集存儲下來:同一封郵件同時(shí)向地址簿中的多個(gè)聯(lián)系人發(fā)送;向同一個(gè)人重復(fù)發(fā)送同一封郵件。重復(fù)郵件的存在,不僅浪費(fèi)了寶貴的存儲空間和帶寬資源,而且大大增加了后端人員對郵件的處理和分析工作量。因此,對重復(fù)郵件進(jìn)行識別和過濾,成為提高工作效率的關(guān)鍵環(huán)節(jié)。
但是,若采用直接比較郵件內(nèi)容的方法來識別重復(fù)郵件,不僅需要將郵件原文全部保存入庫,而且對大文本進(jìn)行逐字匹配的效率也不高,算法在時(shí)間復(fù)雜度和空間復(fù)雜度上都有較大的缺憾,還會(huì)影響新郵件的實(shí)時(shí)接收。鑒于此,我們經(jīng)過認(rèn)真研究,決定在郵件分析程序中構(gòu)造郵件要素的特征值,并應(yīng)用MD5算法,實(shí)現(xiàn)對重復(fù)郵件的識別,從而準(zhǔn)確、快速地將無用郵件過濾出來。
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è)任意長度的字節(jié)串變換成一個(gè)定長的大整數(shù))。MD5的典型應(yīng)用是對一段信息產(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ò)誤等),只要對這個(gè)文件重新計(jì)算MD5,就會(huì)發(fā)現(xiàn)信息摘要不相同,由此可以確定得到的是一個(gè)不正確的文件。
MD5還廣泛用于加密和解密技術(shù)上。比如在UNIX系統(tǒng)中,用戶的密碼就是以MD5(或其它類似的算法)經(jīng)加密后存儲在文件系統(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è)任意長度的字節(jié)串,每個(gè)字節(jié)是8個(gè)bit。算法的執(zhí)行分為以下幾個(gè)步驟:
1)補(bǔ)位
MD5算法先對輸入的數(shù)據(jù)進(jìn)行補(bǔ)位,使得數(shù)據(jù)的長度(以byte為單位)對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ù)長度
用一個(gè)64位的整數(shù)表示數(shù)據(jù)的原始長度(以bit為單位),將這個(gè)數(shù)字的8個(gè)字節(jié)按低位的在前,高位在后的順序附加在補(bǔ)位后的數(shù)據(jù)后面。這時(shí),數(shù)據(jù)被填補(bǔ)后的總長度為: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)對輸入數(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
在實(shí)際系統(tǒng)中,我們針對每封郵件抽取其發(fā)件人郵箱、郵件主題、郵件正文的文本內(nèi)容、附件名稱、附件大小等五種要素,采用字符串拼接的方式,構(gòu)造郵件的特征值T,則T=發(fā)件人郵箱+郵件主題+郵件正文文本+附件名稱+附件大小,
對特征值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哈希值的方法來識別重復(fù)郵件,程序的可移植性強(qiáng),對重復(fù)郵件的判斷準(zhǔn)確,過濾效果較好,克服了直接比較郵件內(nèi)容在時(shí)間復(fù)雜度和空間復(fù)雜度上的缺點(diǎn),在實(shí)際工作中發(fā)揮了巨大的作用?;谶@種理論思路,我們將其擴(kuò)展到整個(gè)系統(tǒng)的數(shù)據(jù)去重的處理上面,達(dá)到了很好的實(shí)際效果。
本文首先簡要介紹了海量數(shù)據(jù)挖掘及輿情分析技術(shù),然后規(guī)劃了整個(gè)系統(tǒng)的系統(tǒng)模型。隨后本文以BBS輿情分析系統(tǒng)的實(shí)現(xiàn),闡述了輿情分析系統(tǒng)的具體實(shí)現(xiàn)方式和原理。然后,本文又重點(diǎn)研究了MD5算法在重復(fù)郵件識別中的應(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.