MD5 加密算法改進及其特征碼在殺毒軟件中的應用

賈曉強

（渭南師范學院數學與信息科學學院信息工程系， 陜西 渭南 714099）

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

1 MD5 加密算法的安全性分析及改進

1.1 MD5 加密算法的原理

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

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

第一步：消息的填充

在MD5 算法中，開始需要對信息進行補充，使其字節長度對512 取余數的結果為448。 必須保證所有的信息對512 取余數的結果為448 這樣就需要對與512 取余結果不為448 的數進行填充，填充的值為“1”以及若干個0 附加在消息的末尾。

第二步:記錄消息長度

在上一步填充處理的基礎上， 附上64 比特的填充前消息長度的二進制表示.（將填充前的信息的長度用二進制表示后附在其后作為附加信息以示區別）。

第三步：加載初始標準數據

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

第四步：四輪運算

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

通過MD5 算法運算后，可以將任意長度的文件，轉換成一個不可逆的整數，此整數非常大長度為128 bit；通常情況下所有的字符組合卻有無窮多個，MD5[4]所運算出來的數字值域并不能完全的一對一的表示所有的字符組合。 所以就有可能有多個字符串計算出來的128 bit的特征碼是一樣的，也即是發生了碰撞。

1.2 MD5 加密算法的改進意見

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

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

第一輪

（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）

其中常數tj可以如下選擇：

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

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

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

即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

首先計算出

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

其次計算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轉換為二進制為1001 0100 0110 1010 1010 0100 0111 1011

FF（a，b，c，d，M0，d76aa478）結果為

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.

其他函數計算相似。

1.3 MD5 算法改進后的安全性分析

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

1.4 MD5 算法改進后性能分析

加鹽值提高加密的可靠性有以下特點：

1）算法結構不用改變，繼承了原有算法的穩定性。

2）算法的時間復雜度并沒有因為算法的改進而增加（四輪共進行了64 次運算算法復雜度T（n）=O（n）。

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

4）增加了參數之后，哈希函數的碰撞概率更近一步減小了，由于T 是根據文件時間動態生成的，在原消息摘要加上T再進行哈希運算，其計算空間加大，對原消息的保護強度大大增強。

2 MD5 應用現狀以及MD5 特征碼原理的殺毒軟件的實現

2.1 MD5 的一個實際應用：MD5 特征碼原理的殺毒軟件

主要功能模塊如下：

1）MD5 算法函數的實現與封裝

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

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

4）病毒文件的刪除以及病毒進程的結束

5）文件完整性檢測模塊

2.2 算法流程圖

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

2.3 殺毒軟件測試

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

根據MD5 碼的特征，構造了MD5 特征庫配置文件，配置文件如圖2 所示。 通過遍歷匹配MD5 值，能成功的刪除可疑文件。 測試效果如圖3、圖4 所示。

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

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

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

3 結 論

從MD5 算法的誕生、發展、破解危機入手，研究了MD5算法的原理及其實際應用意義，并對其做了改進，在不改變時空復雜度的情況下，增強了算法的安全性，并通過MD5 特征碼將其應用在殺毒軟件中。

[1] 廖海生，趙躍龍. 基于MD5算法的重復數據刪除技術的研究與改進[J]. 計算機測量與控制，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]. 計算機科學，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 算法破譯過程解析[J]. 計算機工程與應用，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] 王衍波，薛通.應用密碼學[M].北京：機械工業出版社，2013.

[5] 毛熠，陳娜. MD5算法的研究與改進[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] 周林，王政，韓文報. MD5 差分和差分路徑的自動化構造算法[J]. 四川大學學報:工程科學版，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.