關(guān)于MD5算法的分析及其性能優(yōu)化

崔永輝+徐鵬+陽(yáng)征鵬

摘 要：本文主要介紹了MD5算法的實(shí)現(xiàn)原理和對(duì)源數(shù)據(jù)信息的加密流程，然后從算法實(shí)現(xiàn)的角度，依據(jù)當(dāng)前CPU計(jì)算機(jī)制，對(duì)MD5算法的計(jì)算時(shí)間的消耗進(jìn)行分析，并提出了相應(yīng)的性能優(yōu)化建議，從而提升MD5算法的計(jì)算速度。

關(guān)鍵詞：MD5;優(yōu)化;性能優(yōu)化

DOI：10.16640/j.cnki.37-1222/t.2015.21.200

1 概述

隨著科學(xué)技術(shù)的發(fā)展以及互聯(lián)網(wǎng)絡(luò)的不斷應(yīng)用，信息安全的重要性已經(jīng)成為繼大數(shù)據(jù)、云計(jì)算之后的IT行業(yè)熱門發(fā)展方向。在信息安全體系中，信息加密是其中非常重要的部分，也是應(yīng)對(duì)各種網(wǎng)絡(luò)攻擊或者暴力破解工具很好的應(yīng)對(duì)手段。MD5算法是目前應(yīng)用較為廣泛的一種算法，它允許應(yīng)用系統(tǒng)將不同數(shù)據(jù)信息加密成固定128位的加密字符串，從而有效地保證了數(shù)據(jù)信息的保密性、完整性和可用性。然而MD5算法過程繁瑣、算法復(fù)雜，在具體實(shí)現(xiàn)時(shí)必須考慮其計(jì)算性能，如果加密時(shí)間過長(zhǎng)，將會(huì)為實(shí)際應(yīng)用帶來非常差的用戶體驗(yàn)。所以對(duì)于MD5算法的研究以及對(duì)其計(jì)算性能的優(yōu)化分析，對(duì)于MD5算法實(shí)現(xiàn)來說，具有非常大的現(xiàn)實(shí)意義。

2 MD5算法

MD5是Riverst在之前MD2，MD3，MD4的基礎(chǔ)上，經(jīng)過升級(jí)優(yōu)化開發(fā)而來。采用MD5算法，可以讓任意長(zhǎng)度的數(shù)據(jù)信息，變成一個(gè)128位固定長(zhǎng)度的大整數(shù)的加密形式，從而實(shí) 現(xiàn)了數(shù)據(jù)信息的加密，而MD5算法的加密過程是一個(gè)不可逆的過程，在一定程度上保證了數(shù)據(jù)信息的安全性，對(duì)于一些暴力破解、密碼嗅探的工具來說，對(duì)MD5算法加密的數(shù)據(jù)解密將是一個(gè)工作量非常大的過程。

MD5算法的處理過程需要經(jīng)過以下幾個(gè)階段：字符填充，長(zhǎng)度加長(zhǎng)，塊分解，變量初始化，塊處理。

其中，MD5算法的字符填充，因?yàn)镸D5算法最終是對(duì)512位的數(shù)據(jù)塊進(jìn)行處理，所以對(duì)于整體數(shù)據(jù)源長(zhǎng)度不是512倍數(shù)的，需要將其字符填充，是最終的長(zhǎng)度為512位長(zhǎng)度的倍數(shù)減去64位。然后信息源長(zhǎng)度加長(zhǎng)，即用64位長(zhǎng)度表示字符填充之前原信息源長(zhǎng)度，填充到最后64位，最終使得到的字符串長(zhǎng)度為512位的倍數(shù)。第三步，塊分解，將最終得到的字符串以512位長(zhǎng)度為單位，對(duì)其進(jìn)行劃分，形成最終的數(shù)據(jù)塊，第四步，生成變量，即生成四個(gè)32位長(zhǎng)的十六進(jìn)制變量。得到這四個(gè)初始化變量之后，就可以對(duì)生成的數(shù)據(jù)塊進(jìn)行MD5算法處理。

塊處理的過程，是使用MD5算法的過程，假如有四個(gè)變量A，B，C，D，其值與上述四個(gè)初始化值一一對(duì)應(yīng)，然后將ABCD組合成一個(gè)128為長(zhǎng)度的數(shù)值放到一個(gè)寄存器中。將第一個(gè)512位長(zhǎng)度的數(shù)據(jù)塊，以32位長(zhǎng)度為單位，平均分成16個(gè)小塊，從而得到了從0到15的字塊。假如存在一個(gè)常量數(shù)組，其元素個(gè)數(shù)為64，每個(gè)元素為32位長(zhǎng)度的常量數(shù)值。

首先使用第一個(gè)非線性函數(shù)對(duì)變量B，C，D進(jìn)行計(jì)算，將結(jié)果到存儲(chǔ)128位數(shù)據(jù)的寄存器中，然后將A加入到該寄存器，將第0個(gè)消息加入到128位寄存器中，將常量數(shù)組的第0個(gè)常量元素加入到寄存器中，然后將寄存器左移某個(gè)值（該值是不斷變化的）位，然后將變量B加入到128位寄存器中。然后從頭開始，循環(huán)16次，將512位長(zhǎng)度的16個(gè)子塊都進(jìn)行相同處理。

然后依次使用第二個(gè)、第三個(gè)、第四個(gè)非線性函數(shù)開始，按照上面的方法，對(duì)該數(shù)據(jù)塊進(jìn)行處理，最終將得到128位寄存器的值。最后，將A，B，C，D變量的值分別自加，按照上述算法，依次對(duì)一下組512位的數(shù)據(jù)進(jìn)行相同的算法處理，最終得到的128位寄存器的值即為源信息數(shù)據(jù)的MD5算法加密的最終結(jié)果。

3 MD5算法的性能優(yōu)化

3.1 展開MD5算法的循環(huán)過程

由于MD5算法需要很多循環(huán)，而且很多時(shí)候采用多層循環(huán)嵌套來實(shí)現(xiàn)。對(duì)于計(jì)算機(jī)體系來說，多次的循環(huán)與多層次的循環(huán)嵌套，加上變量的地址尋址，自身在CPU執(zhí)行時(shí)，會(huì)浪費(fèi)大量的時(shí)間，加上多次循環(huán)和多層循環(huán)嵌套，與變量地址尋址使得CPU指令流水線的預(yù)取與阻斷的機(jī)制失效，從而增加了大量的計(jì)算時(shí)間。對(duì)于大數(shù)量級(jí)和多層循環(huán)嵌套的MD5算法來說，可以通過展開循環(huán)過程來提升其計(jì)算時(shí)間。所以在編程實(shí)現(xiàn)MD5算法時(shí)，盡量將每個(gè)循環(huán)體采用5到10次的循環(huán)次數(shù)，通過多個(gè)循環(huán)程序塊來完成整個(gè)MD5算法。同時(shí)，為了減少內(nèi)存尋址的時(shí)間浪費(fèi)，能夠采用常量的變量，盡量在預(yù)定義時(shí)采用常量的形式定義。

3.2 避免指令跳轉(zhuǎn)

在當(dāng)前CPU的計(jì)算機(jī)制中，執(zhí)行固定內(nèi)存塊的指令速度是最塊的，如果發(fā)生程序地址指針改變，則CPU將會(huì)浪費(fèi)一部分時(shí)間去內(nèi)存尋址或從虛擬交換空間或磁盤中讀取數(shù)據(jù)，而這將會(huì)浪費(fèi)大量的計(jì)算時(shí)間。對(duì)于常見的編程語(yǔ)言，if…else或者for、while循環(huán)，甚至是goto語(yǔ)句，都是常見的指令跳轉(zhuǎn)語(yǔ)句，在實(shí)現(xiàn)MD5算法時(shí)，盡量避免使用產(chǎn)生指令跳轉(zhuǎn)的語(yǔ)句，從而減少CPU執(zhí)行代碼時(shí)的尋址時(shí)間。

3.3 變量長(zhǎng)度CPU寄存器匹配

不同計(jì)算機(jī)的CPU寄存器大小是不一樣的。對(duì)于長(zhǎng)度大于CPU寄存器長(zhǎng)度的變量，CPU將會(huì)分多次進(jìn)行計(jì)算，最后將結(jié)果進(jìn)行整合來完成計(jì)算。如果變量長(zhǎng)度小于CPU寄存器長(zhǎng)度，那么CPU將會(huì)在寄存器后附加其他的數(shù)據(jù)或者執(zhí)行來完成計(jì)算。對(duì)于一個(gè)32位寄存器的CPU來說，對(duì)一個(gè)32位變量的計(jì)算時(shí)間將比對(duì)一個(gè)16位變量的計(jì)算時(shí)間塊近一倍，所以在復(fù)雜繁瑣的MD5算法實(shí)現(xiàn)過程中，定義變量或常量時(shí)，盡量與當(dāng)前執(zhí)行算法的CPU寄存器長(zhǎng)度一致，從而增加整個(gè)代碼中數(shù)值的計(jì)算速度。

3.4 減少變量個(gè)數(shù)

由于操作系統(tǒng)對(duì)于變量的存放機(jī)制，使得CPU在對(duì)某個(gè)變量進(jìn)行計(jì)算時(shí)，需要按照變量指針從內(nèi)存中尋址讀取，存放到寄存器中進(jìn)行計(jì)算。整個(gè)計(jì)算機(jī)框架CPU從內(nèi)存讀取和寫入的時(shí)間對(duì)于CPU計(jì)算來說慢很多，所以在MD5算法實(shí)現(xiàn)時(shí)，盡量減少變量的個(gè)數(shù)。此外，常量與變量的存放機(jī)制也有所不同，所以對(duì)于固定不變的數(shù)據(jù)盡量使用常量類型代替。

4 總結(jié)

MD5算法是對(duì)按照固定的循環(huán)和計(jì)算對(duì)源數(shù)據(jù)信息進(jìn)行加密，最終生成128位的加密數(shù)據(jù)。由于整個(gè)過程計(jì)算量非常大，而且過程非常繁瑣，所以在算法實(shí)現(xiàn)時(shí)，會(huì)耗費(fèi)大量的時(shí)間。對(duì)于MD5算法實(shí)現(xiàn)的性能優(yōu)化的機(jī)制非常多，主要是考慮當(dāng)前系統(tǒng)的CPU計(jì)算機(jī)制，采用最匹配的方式，最終減少加密運(yùn)算的時(shí)間，更塊地得到128位加密數(shù)據(jù)。

參考文獻(xiàn)：

[1]毛熠，陳娜.MD5算法的研究與改進(jìn)[D].計(jì)算機(jī)工程，2012（24）.

[2]么麗穎.MD5算法的分析和改進(jìn)[J].哈爾濱師范大學(xué)自然科學(xué)學(xué)報(bào)，2011（05）.endprint