MD5 加密算法改進(jìn)及其特征碼在殺毒軟件中的應(yīng)用

賈曉強(qiáng)

（渭南師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院信息工程系， 陜西 渭南 714099）

隨著計(jì)算機(jī)網(wǎng)路技術(shù)和網(wǎng)絡(luò)通信技術(shù)[1]的應(yīng)用廣泛應(yīng)用， 各種數(shù)據(jù)信息尤其是關(guān)系到用戶利益的敏感數(shù)據(jù)與Internet 聯(lián)系日益增強(qiáng)，云計(jì)算以及大數(shù)據(jù)時(shí)代的到來(lái)，企業(yè)網(wǎng)建設(shè)，數(shù)據(jù)存儲(chǔ)和傳輸安全引起了更為廣大的關(guān)注。 在人們感受到網(wǎng)路通信帶給自己生活以及工作便利的同時(shí)，出現(xiàn)了一系列的與網(wǎng)絡(luò)信安全相關(guān)的問(wèn)題，用戶敏感數(shù)據(jù)的安全關(guān)系到用戶的切身利益。Message-Digest Algorithm 5（MD5）是一種被廣泛使用的散列算法。 此算法用來(lái)確保信息在網(wǎng)絡(luò)傳輸中的完整性，和一致性。 也被叫做哈希算法，或者摘要算法等。 散列算法的基本原理是：將數(shù)據(jù)，或者一段字符經(jīng)過(guò)一系列的變化運(yùn)算，移位運(yùn)算變?yōu)榱硪环N特定的長(zhǎng)度。MD2、MD3、MD4 都是MD5 的前身。 為了減小碰撞的概率和其安全性，必須對(duì)它進(jìn)行改進(jìn)。

1 MD5 加密算法的安全性分析及改進(jìn)

1.1 MD5 加密算法的原理

在MD5 算法中，開(kāi)始需要對(duì)信息進(jìn)行補(bǔ)充，使其字節(jié)長(zhǎng)度對(duì)512 取余數(shù)的結(jié)果為448。 必須保證所有的信息對(duì)512取余數(shù)的結(jié)果為448 這樣就需要對(duì)與512 取余結(jié)果不為448的數(shù)進(jìn)行填充，填充的值為“1”以及若干個(gè)0 附加在消息的末尾。然后將消息要以512 bit 分為許多組，分組之后，再將分組后的數(shù)據(jù)分別使用MD5 進(jìn)行加密[2]。然后將每組512 bit 的數(shù)據(jù)分為16 個(gè)32 位的分組[3]，接著將每個(gè)32 位的分組作為目標(biāo)數(shù)據(jù)進(jìn)行一系列的計(jì)算。

在進(jìn)行運(yùn)算之前，首先要把消息進(jìn)行分組，輸入的消息要以512 bit 分為許多組，分組之后，再將分組后的數(shù)據(jù)分別使用MD5 進(jìn)行加密。 然后將每組分為16 個(gè)32 位的分組，接著進(jìn)行一系列的計(jì)算。 最后的記過(guò)有4 組，分別都是32 位的分組成員， 然后見(jiàn)不過(guò)4 組成員鏈接成為一個(gè)128 bit 的值。即就是一個(gè)32 位的字符串。

第一步：消息的填充

在MD5 算法中，開(kāi)始需要對(duì)信息進(jìn)行補(bǔ)充，使其字節(jié)長(zhǎng)度對(duì)512 取余數(shù)的結(jié)果為448。 必須保證所有的信息對(duì)512 取余數(shù)的結(jié)果為448 這樣就需要對(duì)與512 取余結(jié)果不為448 的數(shù)進(jìn)行填充，填充的值為“1”以及若干個(gè)0 附加在消息的末尾。

第二步:記錄消息長(zhǎng)度

在上一步填充處理的基礎(chǔ)上， 附上64 比特的填充前消息長(zhǎng)度的二進(jìn)制表示.（將填充前的信息的長(zhǎng)度用二進(jìn)制表示后附在其后作為附加信息以示區(qū)別）。

第三步：加載初始標(biāo)準(zhǔn)數(shù)據(jù)

MD5 算法中含有4 個(gè)鏈變量，在進(jìn)行運(yùn)算之前必須將鏈變量加載進(jìn)去，4 個(gè)鏈變量加載后才能進(jìn)行四輪循環(huán)的運(yùn)算，4 個(gè)鏈變量分別為：A=14224567，B=19cbcdef，C=edcba98，D=76543210

第四步：四輪運(yùn)算

四輪運(yùn)算，每一輪循環(huán)的過(guò)程都是一樣的，每一輪操作16 次，每次分別對(duì)鏈變量的其中3 個(gè)利用提供的非線性函數(shù)做一次運(yùn)算，然后用第4 個(gè)變量加上循環(huán)所得出的結(jié)果。 接著進(jìn)行文本接下來(lái)的一個(gè)子分組和另一個(gè)常熟的運(yùn)算，將結(jié)果向左進(jìn)行隨機(jī)移位。 并加上鏈變量的任意一個(gè)，接著用所得結(jié)果替換鏈變量中的任意一個(gè)。 循環(huán)的次數(shù)是分組的個(gè)數(shù)（N+1）也就是求模運(yùn)算的商值加上補(bǔ)齊的一組的512 數(shù)據(jù)塊的數(shù)目進(jìn)行循環(huán)，每輪循環(huán)都很相似。

通過(guò)MD5 算法運(yùn)算后，可以將任意長(zhǎng)度的文件，轉(zhuǎn)換成一個(gè)不可逆的整數(shù)，此整數(shù)非常大長(zhǎng)度為128 bit；通常情況下所有的字符組合卻有無(wú)窮多個(gè)，MD5[4]所運(yùn)算出來(lái)的數(shù)字值域并不能完全的一對(duì)一的表示所有的字符組合。 所以就有可能有多個(gè)字符串計(jì)算出來(lái)的128 bit的特征碼是一樣的，也即是發(fā)生了碰撞。

1.2 MD5 加密算法的改進(jìn)意見(jiàn)

以下是對(duì)Hash 算法的改進(jìn)策略：加鹽值（salt）是最容易實(shí)現(xiàn)的一種改進(jìn)策略，具體做法為，在進(jìn)行散列計(jì)算式時(shí)，加入足夠長(zhǎng)的干擾[6]字符串，這些字符串就被叫做“鹽值”。 比較高級(jí)的一些鹽值常常為一些動(dòng)態(tài)信息。 比如根據(jù)時(shí)間生成隨機(jī)數(shù)，或者其他隨機(jī)碼[5]等。 這樣的做法更大程度上提高了MD5 算法的安全性能。

四輪共計(jì)64 次操作，除非線性運(yùn)算每輪一個(gè)不同外，運(yùn)算規(guī)則都很類似。 假設(shè)M 消息表示的第J 個(gè)子分組，ti 表示加入的鹽值，從0 到15，表示循環(huán)左移位，則改進(jìn)后MD5 的四輪運(yùn)算公式如下：

第一輪

（1）FF（a，b，c，d，M0，7，d76aa478）

（2）FF（d，a，b，c，M1，12，e8c7b756）

（3）FF（c，d，a，b，M2，17，24070db）

（4）FF（b，c，d，a，M3，22，c1bdceee）

（5）FF（a，b，c，d，M4，7，f57c0faf）

（6）FF（d，a，b，c，M5，12，4787c62a）

（7）FF（c，d，a，b，M6，17，a8304613）

（8）FF（b，c，d，a，M7，22，fd469501）

（9）FF（a，b，c，d，M8，7，698098d8）

（10）FF（d，a，b，c，M9，12，8b44f7af）

（11）FF（c，d，a，b，M10，17，ffff5bb1）

（12）FF（b，c，d，a，M11，22，895cd7be）

（13）FF（a，b，c，d，M12，7，6b901122）

（14）FF（d，a，b，c，M13，12，fd987193）

（15）FF（c，d，a，b，M14，17，a679438e）

（16）FF（b，c，d，a，M15，22，49b40821）

（15）GG（c，d，a，b，M7，14，676f02d9）

（16）GG（b，c，d，a，M12，20，8d2a4c8a）

第二輪

（1）GG（a，b，c，d，M1，5，f61e2562）

（2）GG（d，a，b，c，M6，9，c040b340）

（3）GG（c，d，a，b，M11，14，265e5a51）

（4）GG（b，c，d，a，M0，20，e9b6c7aa）

（5）GG（a，b，c，d，M5，5，d62f105d）

（6）GG（d，a，b，c，M10，9，02441453）

（7）GG（c，d，a，b，M15，14，d8a1e681）

（8）GG（b，c，d，a，M4，20，e7d3fbc8）

（9）GG（a，b，c，d，M9，5，21e1cde6）

（10）GG（d，a，b，c，M14，9，c33707d6）

（11）GG（c，d，a，b，M3，14，f4d50d87）

（12）GG（b，c，d，a，M5，20，455a14ed）

（13）GG（a，b，c，d，M13，5，a9e3e905）

（14）GG（d，a，b，c，M2，9，fcefa3f8）

（15）GG（c，d，a，b，M7，14，676f02d9）

（16）GG（b，c，d，a，M12，20，8d2a4c8a）

第三輪

（1）HH（a，b，c，d，M5，4，fffa3942）

（2）HH（d，a，b，c，M8，11，8771f681）

（3）HH（c，d，a，b，M11，16，6d9d6122）

（4）HH（b，c，d，a，M14，23，fde5380c）

（5）HH（a，b，c，d，M1，4，a4beea44）

（6）HH（d，a，b，c，M4，11，4bdecfa9）

（7）HH（c，d，a，b，M7，16，a4beea44）

（8）HH（b，c，d，a，M4，23，bebfbc70）

（9）HH（a，b，c，d，M13，4，289b7ec6）

（10）HH（d，a，b，c，M10，11，eaa127fa）

（11）HH（c，d，a，b，M3，16，d4ef3085）

（12）HH（b，c，d，a，M6，23，04881d05）

（13）HH（a，b，c，d，M9，4，d9d4d039）

（14）HH（d，a，b，c，M12，11，e6db99e5）

（15）HH（c，d，a，b，M15，16，1fa27cf8）

（16）HH（b，c，d，a，M2，23，c4ac5665）

第四輪

（1）II（a，b，c，d，M0，6，f4292244）

（2）II（d，a，b，c，M7，10，432aff97）

（3）II（c，d，a，b，M14，15，ab9423a7）

（4）II（b，c，d，a，M5，21，fc93a039）

（5）II（a，b，c，d，M12，6，65b59c3）

（6）II（d，a，b，c，M3，10，8f0ccc92）

（7）II（c，d，a，b，M10，15，ffeff47d）

（8）II（b，c，d，a，M1，21，85845dd1）

（9）II（a，b，c，d，M8，6，6fa87e4f）

（10）II（d，a，b，c，M15，10，fe2ce6e0）

（11）II（c，d，a，b，M6，15，a3014314）

（12）II（b，c，d，a，M13，21，4e0811a1）

（13）II（a，b，c，d，M4，6，f7537e82）

（14）II（d，a，b，c，M11，10，bd3af235）

（15）II（c，d，a，b，M2，15，2ad7d2bb）

（16）II（b，c，d，a，M9，21，eb86d391）

其中常數(shù)tj可以如下選擇：

在第i 步中，tj是4296767296*abs（sun（i））的整數(shù)部分，i的單位是弧度。（4294967296 等于2 的32 次方）。所有這些完成之后，將A、B、C、D 分別加上a、b、c、d，然后用下一分組數(shù)據(jù)繼續(xù)運(yùn)行算法，最后的輸出是A、B、C 和D 的級(jí)聯(lián)。

在這里假設(shè)： 要加密的信息為msg， 其比特串為11110101 01101010 01110011

比特串的長(zhǎng)度為24 位，于是在其末尾添加1 個(gè)“1”，后邊全部添加0 直到與512 的余數(shù)為448， 再加上64 比特串（24）16=00000000 0000001816（24 位的長(zhǎng)度）

即x=10110101 01101011 01100011 1 0…0 10001100 00110018， 共512 比特， 只有16 分組為：M0，M1，M2，M3，M4，M5，M6，M7，M8，M9，M10，M11，M12，M13，M14，M15， 所 以 有M4=M5=M6=M7=M8=M9=M10=M11=M12=M13=M14=00000000

M15=00000018

首先計(jì)算出

A=0123456719=0010 0011 1110 0011 0101 0101 0110 0111=a

B=89ABCDEF16=1011 1001 1011 1011 1100 1001 1110 1111=b

C=FEDCBA9816=1001 1110 1101 1100 1011 1010 1001 1000=d

D=7651321016=0001 0110 0101 0100 0011 0010 0001 0110=d

其次計(jì)算F（b，c，d）=（b∧c）|（b∧d）

=（1011 1011 1010 1011 1100 1101 1110 1100 1100 1110 1101 1100 1011 1010 1001 1011）|（0110 0110 0101 0100 0011 0010 0001 00000111 0110 0101 0100 0011 0010 1001 0000 =（1000 1110 1000 1010 1000 1110 1110 1000）|（0111 0110 0101 0111 0011 0010 0001 1100）=1111 1110 1101 1100 1011 1010 1001 1000

d76aa47816轉(zhuǎn)換為二進(jìn)制為1001 0100 0110 1010 1010 0100 0111 1011

FF（a，b，c，d，M0，d76aa478）結(jié)果為

a=b+（（a+（F（b，c，d）+M0+t0）＜＜7））

=（1011 1011 1010 1011 1100 1101 1110 1111）+（（0110 0101 0010 0011 0100 0101 0110 0011+1001 1110 1101 1100 1011 1010 1001 1000+0000 0111 1101 0000 0110 0110 0001 0011）+1101 0111 0110 1010 1010 0110 0111 1110）＜＜7）

=（1110 1001 1010 1011 1100 1101 1110 1100）+（（0110 0110 0011 1100 1000 0000 0110 1110+1101 0111 0110 1010 1010 0100 0111 1111）＜＜7）

=（1001 1111 1010 1010 1100 1101 1110 1001）+（1101 0111 1111 0010 1010 0110 1010 1111＜＜7）

=（1011 1011 1011 1011 1100 1101 1110 1001）+（0011 1111 1010 1111 0100 0101 0110 1011）=1001 1001 0101 1011 0001 0011 0011 1011=3551133116.

其他函數(shù)計(jì)算相似。

1.3 MD5 算法改進(jìn)后的安全性分析

改進(jìn)后的MD5 算法，可以將任意長(zhǎng)度的文件，轉(zhuǎn)換成一個(gè)不可逆的整數(shù)，此整數(shù)非常大長(zhǎng)度為128 bit；但是源字符串有可能有無(wú)窮多個(gè)，128 bit 的大整數(shù)只可以表示2 的128 次方的字符串。 所以就有可能有多個(gè)字符串計(jì)算出來(lái)的128 bit的特征碼是一樣的，也就是發(fā)生了碰撞。 也有一些黑客，為了獲取密碼，使用一種叫做“跑字典”[3]的方法，他們通過(guò)搜集常用密碼字符串表或者使用排列組合的放大獲取字典。 改進(jìn)后的MD5 算法可以較好的預(yù)防通過(guò)“跑字典”來(lái)獲取密碼。

1.4 MD5 算法改進(jìn)后性能分析

加鹽值提高加密的可靠性有以下特點(diǎn)：

1）算法結(jié)構(gòu)不用改變，繼承了原有算法的穩(wěn)定性。

2）算法的時(shí)間復(fù)雜度并沒(méi)有因?yàn)樗惴ǖ母倪M(jìn)而增加（四輪共進(jìn)行了64 次運(yùn)算算法復(fù)雜度T（n）=O（n）。

3）密碼被破譯的難度大大增加，窮舉耗時(shí)更長(zhǎng)，很大程度上提升了加密算法的安全性。

4）增加了參數(shù)之后，哈希函數(shù)的碰撞概率更近一步減小了，由于T 是根據(jù)文件時(shí)間動(dòng)態(tài)生成的，在原消息摘要加上T再進(jìn)行哈希運(yùn)算，其計(jì)算空間加大，對(duì)原消息的保護(hù)強(qiáng)度大大增強(qiáng)。

2 MD5 應(yīng)用現(xiàn)狀以及MD5 特征碼原理的殺毒軟件的實(shí)現(xiàn)

2.1 MD5 的一個(gè)實(shí)際應(yīng)用：MD5 特征碼原理的殺毒軟件

主要功能模塊如下：

1）MD5 算法函數(shù)的實(shí)現(xiàn)與封裝

2）配置文件的生成和排序

3）文件的全盤掃描及MD5 值的匹配

4）病毒文件的刪除以及病毒進(jìn)程的結(jié)束

5）文件完整性檢測(cè)模塊

2.2 算法流程圖

加入鹽值后，算法的流程圖如圖1 所示。

2.3 殺毒軟件測(cè)試

圖1 MD5 算法流程圖Fig. 1 Flow chart of MD5 algorithm

根據(jù)MD5 碼的特征，構(gòu)造了MD5 特征庫(kù)配置文件，配置文件如圖2 所示。 通過(guò)遍歷匹配MD5 值，能成功的刪除可疑文件。 測(cè)試效果如圖3、圖4 所示。

圖2 MD5 特征庫(kù)配置文件Fig. 2 MD5 feature library configuration file

圖3 軟件功能截圖Fig. 3 The software function screenshot

圖4 遍歷匹配MD5 值Fig. 4 Traversal matching MD5 value

3 結(jié) 論

從MD5 算法的誕生、發(fā)展、破解危機(jī)入手，研究了MD5算法的原理及其實(shí)際應(yīng)用意義，并對(duì)其做了改進(jìn)，在不改變時(shí)空復(fù)雜度的情況下，增強(qiáng)了算法的安全性，并通過(guò)MD5 特征碼將其應(yīng)用在殺毒軟件中。

[1] 廖海生，趙躍龍. 基于MD5算法的重復(fù)數(shù)據(jù)刪除技術(shù)的研究與改進(jìn)[J]. 計(jì)算機(jī)測(cè)量與控制，2010，18（3）:635-638.

LIAO Hais-heng，ZHAO Yue-long. The research and improvement of MD5 algorithm of Based on the deduplication[J].Computer Measurement and Control，2010，18（3）:635-638.

[2] 張裔智，趙毅，湯小兵. MD5 算法研究[J]. 計(jì)算機(jī)科學(xué)，2008，38（7）:295-297.

ZHANG Yi-zhi，ZHAO Yi，TANG Xiao-bing. The research of MD5 algorithm[J]. Journal of Computer Science，2008，38（7）:295-297.

[3] 陳少暉，翟曉寧，閻娜. MD5 算法破譯過(guò)程解析[J]. 計(jì)算機(jī)工程與應(yīng)用，2010，46（19）:100-101.

CHEN Shao-hui，ZHAI Xiao-ning，YAN Na. The MD5 algorithm decoding process analysis[J]. Computer Engineering and Application，2010，46（19）:100-101.

[4] 王衍波，薛通.應(yīng)用密碼學(xué)[M].北京：機(jī)械工業(yè)出版社，2013.

[5] 毛熠，陳娜. MD5算法的研究與改進(jìn)[J].計(jì)算機(jī)工程，2012，38（24）:112-114.

MAO Yi，CHEN Na. Research and improvement of the MD5 algorithm[J]. Computer Engineering，2012，38（24）:112-114.

[6] 周林，王政，韓文報(bào). MD5 差分和差分路徑的自動(dòng)化構(gòu)造算法[J]. 四川大學(xué)學(xué)報(bào):工程科學(xué)版，2010，42（6）:133-137.

ZHOU Lin，WNAG Zheng，HAN Wen-bao. automation construction algorithm of MD5 difference and the difference path [J]. Journal of sichuan university:engineering science，2010，42（6）:133-137.