王鎮(zhèn)道 李妮

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

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

中圖分類號(hào)：TN335

文獻(xiàn)標(biāo)志碼：A

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

MD5算法是MD結(jié)構(gòu)的典型代表，是密碼學(xué)中

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

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

1算法介紹

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

1.1消息擴(kuò)展

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

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

1.2消息分組

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

1.3循環(huán)運(yùn)算

首先定義好每輪運(yù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）其中包含了四個(gè)非線性基本函數(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個(gè)子分組;s表示循環(huán)左移s位.

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

1.4摘要輸出

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

2優(yōu)化MD5算法設(shè)計(jì)

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

2.1縮短關(guān)鍵路徑

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

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

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

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

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

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

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

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

由于64步循環(huán)步驟中分成F、G、H、I四輪操作，且每輪中循環(huán)移位的位數(shù)s按固定的4個(gè)數(shù)字進(jìn)行循環(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ù)進(jìn)行循環(huán)移位的操作，替代的是直接將移位的結(jié)果作為加法器的加數(shù)相加利用以上兩種方式縮短單步運(yùn)算的關(guān)鍵路徑，有效提高M(jìn)D5算法運(yùn)算速度.

2.2流水線設(shè)計(jì)

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

在設(shè)計(jì)過(guò)程中將兩步運(yùn)算作為流水線的一級(jí)，構(gòu)建一個(gè)32級(jí)的流水線，來(lái)完成MD5的64步運(yùn)算.在占用相對(duì)較少資源的基礎(chǔ)上提高算法的運(yùn)算速度，35個(gè)時(shí)鐘周期可以完成一次消息摘要值的計(jì)算.

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

2.2.1MD5PipelineCore子模塊

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

2.2.2MD5PipelineControl子模塊

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

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

3實(shí)驗(yàn)結(jié)果與分析

通過(guò)ModelSim對(duì)該電路進(jìn)行功能仿真，如圖5所示.MD5運(yùn)算完后拉高md5_tvalid信號(hào)，對(duì)應(yīng)的md5_tdata即為Hash值，仿真結(jié)果表明該設(shè)計(jì)功能正確.

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

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

4結(jié)語(yǔ)

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

參考文獻(xiàn)

[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高速處理模型設(shè)計(jì)[J].北京理工大學(xué)學(xué)報(bào)，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]王孟釗.安全散列算法的應(yīng)用研究與實(shí)現(xiàn)[J].信息技術(shù)，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]王波濤，韓國(guó)棟，張效軍.基于FPGA的MD5算法設(shè)計(jì)與實(shí)現(xiàn)[J].通信技術(shù)，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實(shí)現(xiàn)[J].信息技術(shù)，2011，35（9）：55-58.