一種優(yōu)化的MD5算法與硬件實現(xiàn)

王鎮(zhèn)道 李妮

摘要：MD5算法是應用非常廣泛的一種Hash算法，在數(shù)字簽名和驗簽中占有重要地位，算法的效率會直接影響到簽名和驗簽的速度.本文提出一種優(yōu)化的MD5算法，采用三級加法器替代四級加法器、優(yōu)化循環(huán)移位操作的方式縮短MD5算法單步運算的關鍵路徑，并用VERILOGHDL語言進行硬件實現(xiàn).通過仿真和FPGA驗證，結果表明該設計功能正確，硬件資源消耗少，數(shù)據(jù)吞吐量大.該設計應用于一款密碼安全芯片，采用0.18μm工藝進行MPW流片，芯片面積為6mm2.時鐘頻率為150MHz，電壓3.3V時，功耗約為10.7mW.

關鍵詞：MD5算法;hash算法;簽名和驗簽;散列函數(shù)

中圖分類號：TN335

文獻標志碼：A

互聯(lián)網(wǎng)技術的高速發(fā)展給人們帶來了許多便利的同時，也帶來了諸多的問題.人們的生產(chǎn)和社會活動與網(wǎng)絡密切相關，隨時隨地都在利用網(wǎng)絡進行數(shù)據(jù)交互.提供一個高效性、隱私性和完整性的信息生存環(huán)境是時代的需求，是迫切需要解決的問題.在信息安全的研究領域中，密碼學以及相關技術發(fā)揮著越來越關鍵的作用.加密哈希函數(shù)在密碼學中扮演著至關重要的角色.它廣泛應用于電子商務、信息安全和電子政務等安全性要求比較高的領域中[1]，同時也是實現(xiàn)數(shù)字簽名、消息的完備性和消息可認證性的重要工具.

MD5算法是MD結構的典型代表，是密碼學中

應用廣泛的一種哈希函數(shù)[2].由Ronald Rivest在1991年提出[3].MD5算法可以將任意長度的數(shù)據(jù)輸入壓縮成128bit的輸出，具有不可逆性、數(shù)據(jù)完整性、不可抵賴性等特點[4]，可以防止數(shù)據(jù)被篡改和數(shù)據(jù)丟失.

MD5算法可通過軟件和硬件的方式實現(xiàn).軟件實現(xiàn)的算法極其依賴計算機硬件平臺，算法運算時間長，效率低，不能滿足物聯(lián)網(wǎng)高速發(fā)展的需求.傳統(tǒng)的MD5算法一般采用軟件或計算機硬件平臺的方式實現(xiàn)，算法效率難以滿足物聯(lián)網(wǎng)高速發(fā)展的需求.本文提出一種優(yōu)化的MD5算法，在循環(huán)迭代模式上利用三級加法器替代四級加法器、優(yōu)化循環(huán)移位操作方式縮短關鍵路徑，在流水線模式下采用32級流水線設計去搭建算法實現(xiàn)架構.最后通過VERILOGHDL語言進行硬件實現(xiàn).

1算法介紹

MD5算法以任意位的消息作為輸入，將消息經(jīng)過系列處理后以512位分組形式來處理輸入消息，且每一分組會被分割成16個32位子分組，經(jīng)過一系列的計算處理得到新的四個32位分組，將這四個32位分組級聯(lián)后生成一個128位散列值就是所求的MD5算法加密的摘要值[5].

1.1消息擴展

首先對輸入消息進行填充，使其消息長度對512求余數(shù)的值為448.故消息長度擴展至N*512+448bits（N為正整數(shù)）[6-7].

填充的方法如下：在消息后面填充一個1和無數(shù)個0，直至滿足對512求余得448才停止對信息進行填充.然后再在其后加上一個以64位二進制表示的填充前的消息長度.經(jīng)過這兩步的處理，填充后的消息長度為N*512+448+64=（N+1）*512bits，長度恰好是512的整數(shù)倍，以便后續(xù)分組[8-9].

1.2消息分組

將每512-bit的消息劃分成16組，每組32-bit，同時給出MD5中四個32位作為鏈接變量（ChainingVariable）的整數(shù)參數(shù)，分別為：A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210[10].本文中填充好的消息數(shù)據(jù)以及鏈接變量均采用小端字節(jié)序的方式進行計算處理.

1.3循環(huán)運算

首先定義好每輪運算的邏輯函數(shù)，即：FF（a，b，c，d，Mj，s，t）i為

a=b+（（a+F（b，c，d）+Mj+t）i<<<s）（1）GG（a，b，c，d，Mj，s，ti）為a=b+（（a+G（b，c，d）+Mj+t）i<<<s）（2）HH（a，b，c，d，Mj，s，t）i為a=b+（（a+H（b，c，d）+Mj+t）i<<<s）（3）H（a，b，c，d，Mj，s，t）i為

a=b+（（a+（Ib，c，d）+Mj+t）i<<<s）（4）其中包含了四個非線性基本函數(shù)為：F（x，y，z）=（xy）（|～x&z）（5）G（x，y，z）=（xy）（|～x&z）（6）H（x，y，z）=（x^y^z）（7）（Ix，y，z）=y（^x|～z）（8）ti表示4294967296*abs（sin（i））的整數(shù)部分[11-12];Mj表示512-bit的消息的第j個子分組;s表示循環(huán)左移s位.

當MD5算法進行運算時，先將鏈接變量A，B，C，D寄存到a，b，c，d中，再進入四輪循環(huán)，每輪操作非常相似.其中每輪操作就是計算對應輪的邏輯函數(shù)的值且每輪的循環(huán)次數(shù)為16次.

1.4摘要輸出

四輪計算完后，將A，B，C，D加上對應的a，b，c，d得到新的A，B，C，D.如果還有512-bit分組，則可作為下一分組數(shù)據(jù)運算的鏈接變量，最終輸出的A，B，C和D，A是低位，D為高位，DCBA組成128位輸出結果，即MD5算法計算得出的消息的摘要值.

2優(yōu)化MD5算法設計

硬件實現(xiàn)MD5算法有兩種模式，其一為循環(huán)迭代模式，其二為流水線設計[13].首先在循環(huán)迭代模式上對64步循環(huán)運算的單步運算關鍵路徑進行優(yōu)化，利用三級加法器替代四級加法器、優(yōu)化循環(huán)移位操作的方式縮短MD5算法單步運算的關鍵路徑.其次采用流水線設計實現(xiàn)64步循環(huán)運算并行化，一個時鐘周期內(nèi)實現(xiàn)2步運算，實現(xiàn)縮短單步運算關鍵路徑，提高時鐘頻率，而且32個通道可同時進行MD5運算，提高數(shù)據(jù)處理速度，增大數(shù)據(jù)吞吐量.具體優(yōu)化設計如下.

2.1縮短關鍵路徑

在循環(huán)迭代方面將邏輯函數(shù)FF、GG、HH、II的數(shù)據(jù)計算流程優(yōu)化設計如圖1所示.

1）利用一個加法器替代實現(xiàn)兩個加法器的操作，四級加法器操作優(yōu)化成三級加法器.

以單步函數(shù)FF計算為例：算法的第1、2步在創(chuàng)建激勵時將任意位寬的消息拓展成所需的數(shù)個512-bit數(shù)據(jù).每組512-bit輸入數(shù)據(jù)劃分為16個子分組數(shù)據(jù)，Mj視為常數(shù)，tj表示4294967296*abs（sin（i））的整數(shù)部分視為已知常數(shù)[14-15]，故可先預處理兩組中間值

temp（i）=c（i）+M（i+2）+（tI+2）

temp（i+1）=b（i）+M（i+2）+（ti+2）

利用流水線設計實現(xiàn)一個時鐘周期內(nèi)輸出邏輯

函數(shù)運算的結果，并對應地輸出給緊接的兩組FF數(shù)據(jù).其余輪的運算與此類似，得到的a，b，c，d的值向右輪換輸出給下一輪計算使用.

2）優(yōu)化循環(huán)移位操作.

由于64步循環(huán)步驟中分成F、G、H、I四輪操作，且每輪中循環(huán)移位的位數(shù)s按固定的4個數(shù)字進行循環(huán)移位，一共循環(huán)4次，各占16步操作.其中F輪操作中循環(huán)移位的位數(shù)s為7、12、17、22;G輪操作中循環(huán)移位的位數(shù)s為5、9、14、10;H輪操作中循環(huán)移位的位數(shù)s為4、11、16、23;I輪操作中循環(huán)移位的位數(shù)s為6、10、15、21;由于位數(shù)固定，取消32-bit數(shù)據(jù)進行循環(huán)移位的操作，替代的是直接將移位的結果作為加法器的加數(shù)相加利用以上兩種方式縮短單步運算的關鍵路徑，有效提高MD5算法運算速度.

2.2流水線設計

MD5算法的運算過程是串行執(zhí)行，每一個邏輯函數(shù)計算的結果都要作為下一步邏輯函數(shù)計算的初始值，寄存器大部分時間都處于等待狀態(tài)，故運算速度慢，數(shù)據(jù)吞吐量小.文獻[5]以并行計算為基礎，優(yōu)化MD5算法實現(xiàn)的硬件架構，采用三級、四級流水線進行模塊設計.文獻[7]首先分析了1、4、32級多種流水線設計的吞吐性能，最終利用32級流水線設計，盡管實現(xiàn)了數(shù)據(jù)吞吐量達到32Gbps，但整個設計只對流水線結構進行擴展，電路結構非常復雜.文獻[6]對數(shù)據(jù)流進行優(yōu)化，提出多種方案實現(xiàn)MD5算法，最終實驗結果表明：最佳方案數(shù)據(jù)吞吐量達到了66.56Gbps;但資源占用率較高，實現(xiàn)MD5算法對硬件要求高，不易實現(xiàn).本文在算法實現(xiàn)結構上進行優(yōu)化，構建新的32級流水線設計，極大提升了運算速度，并且面積相對較小.

在設計過程中將兩步運算作為流水線的一級，構建一個32級的流水線，來完成MD5的64步運算.在占用相對較少資源的基礎上提高算法的運算速度，35個時鐘周期可以完成一次消息摘要值的計算.

MD5算法的架構設計如圖2所示.頂層模塊名為MD5_Accelerate，功能是可同時計算32個通道消息分組（512-bit）的MD5摘要值.由于輸入消息數(shù)據(jù)長度不一，算法第1、2步填充數(shù)據(jù)創(chuàng)建激勵在驗證平臺實現(xiàn)，輸入數(shù)據(jù)是按照512-bit位寬進行輸入.同一個消息可能有多個消息分組（512-bit）組成，對屬于同一個消息的不同消息分組，利用輸入該消息分組（512-bit）的通道編號（tid），以及開始（隱含）和結束（tlast）的標志來進行判別.整個模塊包括2個子模塊md5_pipe_ctrl和md5_pipe_core，他們的主從關系如圖3所示.

2.2.1MD5PipelineCore子模塊

子模塊MD5PipelineCore實現(xiàn)消息分組（512-bit）的Hash運算，共包括4輪，每輪包括16步運算，共64步.為了兼顧吞吐量與延時，將2步作為流水線的一級，構建一個32級流水線，完成MD5的64步運算.32級流水線可以同時處理32個消息分組，對于屬于同一個消息的不同消息分組，比如M0和M1，由于M1的Hash運算依賴于M0的Hash結果，所以32個流水級中不允許出現(xiàn)同一個消息的不同消息分組.

2.2.2MD5PipelineControl子模塊

子模塊MD5_Pipeline_Control接收至多32個通道的消息分組（512-bit），發(fā)送到MD5PipelineCore子模塊進行Hash運算，同時接收MD5PipelineCore子模塊的Hash結果進行輸出.該模塊提供MD5PipelineCore處理的消息分組（512-bit）的工作狀態(tài)msg_blk_active[31：0]，msg_blk_active[i]表示通道i消息分組（512-bit）的工作狀態(tài)，‘1’表示被處理中，‘0’表示空閑狀態(tài).由于MD5算法的運算依賴關系，消息分組（512-bit）的輸入需要依據(jù)msg_blk_active[31：0]，即如果msg_blk_active[i]等于‘0’，那么可以輸入通道i的消息分組（512-bit）.對于同一個消息有多個消息分組（512-bit）組成的情況，如果輸入數(shù)據(jù)的tid相同、且上一個tid對應的tlast不為0，即上一個輸入的數(shù)據(jù)不是對應tid的最后一個消息分組，此時輸入數(shù)據(jù)依然是同一消息的一個分組.如果該消息分組（512-bit）的結束標志（tlast）為‘1’，那么經(jīng)過35個流水線延時后，輸出該消息的MD5摘要值.具體時序如圖4所示.

圖4表示3個消息分別輸入通道0，1和7，第一個消息包含2個消息分組：M00和M01，直到msg_blk_active[0]等于0，通道0才能輸入下一個消息分組M01：msg_blk_tvalid有效并且msg_blk_tlast等于1，表示該消息分組是最后一個分組.從輸入消息分組M01到輸出摘要MD0的時間間隔是35個時鐘周期.

3實驗結果與分析

通過ModelSim對該電路進行功能仿真，如圖5所示.MD5運算完后拉高md5_tvalid信號，對應的md5_tdata即為Hash值，仿真結果表明該設計功能正確.

使用Arria10FPGA開發(fā)板進行了板級驗證，驗證了該設計的正確性.該設計使用了11903個ALUTs，最大的時鐘頻率173MHz，占用寄存器為12883個，數(shù)據(jù)吞吐量最大為81.31Gbps.表1列出了同類設計的資源消耗和性能比較.

該設計應用于一款密碼安全芯片，圖6為該芯片的版圖，采用0.18μm工藝進行MPW流片，該芯片面積為6mm2，工作電壓3.3V，時鐘頻率為150MHz時，功耗約為10.7mW，測試結果表明，該設計功能正確.

4結語

MD5算法廣泛應用于數(shù)字簽名和驗簽，傳統(tǒng)的軟件或計算機硬件平臺實現(xiàn)方法難以滿足互聯(lián)網(wǎng)時代對算法性能的要求.本文提出了一種通過優(yōu)化加法器設計、循環(huán)移位操作縮短單步運算的關鍵路徑，減少MD5運算的時鐘周期的硬件實現(xiàn)方法;通過流水線設計，可同時計算32個通道消息的摘要值，且滿載時每個時鐘周期都可輸出數(shù)據(jù)，大幅度提高了數(shù)據(jù)吞吐量.該設計使用VERILOGHDL語言實現(xiàn)，最后使用0.18μm工藝進行流片.

參考文獻

[1] HE D J，XUE Z.Multi-parallel architecture for MD5 implementa?tions on FPGA with gigabit-level throughput[C]//2010 Interna?tional Symposium on Intelligence Information Processing and Trusted Computing.Huanggang，China：IEEE，2010：535-538.

[2] IGNATIUS MOSES SETIADI D R，F(xiàn)AISHAL NAJIB A， RACHMAWANTO E H，et al. A comparative study MD5 and SHA1 algorithms to encrypt REST API authentication on mobile- based application[C]//2019 International Conference on Informa?tion and Communications Technology（ICOIACT）. Yogyakarta， I n d o n e s i a ：I E E E ，2 0 1 9 ：2 0 6 - 2 1 1 .

[3] MOHAMMED ALI A，KADHIM FARHAN A.A novel improve?ment with an effective expansion to enhance the MD5 hash func?tion for verification of a secure E-document[J].IEEE Access， 2 0 2 0 ，8 ：8 0 2 9 0 - 8 0 3 0 4 .

[4] JARVINEN K，TOMMISKA M，SKYTTA J. Hardware implemen?tation analysis of the MD5 hash algorithm[C]//Proceedings of the 38th Annual Hawaii International Conference on System Sciences. Big Island，HI，USA：IEEE，2005：298a.

[5] HOANG A T，YAMAZAKI K，OYANAGI S.Multi-stage pipelin?ing MD5 implementations on FPGA with data forwarding[C]// 2008 16th International Symposium on Field-Programmable Cus?tom Computing Machines. Stanford，CA，USA：IEEE，2008： 271-272.

[6] WANG Y L，ZHAO Q X，JIANG L H，et al.Ultra high throughput implementations for MD5 hash algorithm on FPGA[C]//High Per?formance Computing and Applications，shanghai，China. lncs，

2 0 1 0 ：4 3 3 - 4 4 1 .

[7]韓津生，林家駿，葉建武，等.基于FPGA的MD5高速處理模型設計[J].北京理工大學學報，2012，32（12）：1258-1261.

[8] KHATRI V，AGARWAL V.Modified MD5 algorithm for low end IoT Edge devices[C]//2019 10th International Conference on Com?puting，Communication and Networking Technologies（ICCCNT）. K a n p u r ，I n d i a ：I E E E ，2 0 1 9 ：1 - 6 .

[9]王孟釗.安全散列算法的應用研究與實現(xiàn)[J].信息技術，2018，42（7）：159-161.

[10] KAREEM S M，RAHMA A M S.A new hybrid（MD5 and RC4） cryptography algorithm using multi-logic states[C]//2019 Ninth International Conference on Intelligent Computing and Information S y s t e m s （ I C I C I S ）. C a i r o ，E g y p t ：I E E E ，2 0 1 9 ：2 8 5 - 2 9 2 .

[11] SHADAB AHMAD Khan. FPGA implementation of MD5 algo?rithm for password storage[J]. International Journal of Science and Research，2013，4（6）：136-139

[12]王波濤，韓國棟，張效軍.基于FPGA的MD5算法設計與實現(xiàn)[J].通信技術，2010，43（1）：69-71.

[13] SUNYH，WEILF，LIP.FasthardwareimplementationofMD5 algorithm[J]. Computer and Information Technology，2007（5）： 14-15.

[14] TAN J，ZHOU Q L. Implementation and improvement of MD5 al?gorithm in mimicry computer based on full pipeline architecture [J]. Small and Micro Computer System，2017，38（6）：1216-1220.

[15] WANG Y L，ZHAO Q X，JIANG L H，et al.Ultra high throughput implementations for MD5 hash algorithm on FPGA[M]//Lecture Notes in Computer Science. Berlin，Heidelberg：Springer Berlin H e i d e l b e r g ，2 0 1 0 ：4 3 3 - 4 4 1 .

[16]王臣，袁焱.超高吞吐量MD5算法的FPGA實現(xiàn)[J].信息技術，2011，35（9）：55-58.