一種優化的MD5 算法與硬件實現

王鎮道，李妮

（湖南大學物理與微電子科學學院湖南長沙 410082）

互聯網技術的高速發展給人們帶來了許多便利的同時，也帶來了諸多的問題.人們的生產和社會活動與網絡密切相關，隨時隨地都在利用網絡進行數據交互.提供一個高效性、隱私性和完整性的信息生存環境是時代的需求，是迫切需要解決的問題.

在信息安全的研究領域中，密碼學以及相關技術發揮著越來越關鍵的作用.加密哈希函數在密碼學中扮演著至關重要的角色.它廣泛應用于電子商務、信息安全和電子政務等安全性要求比較高的領域中［1］，同時也是實現數字簽名、消息的完備性和消息可認證性的重要工具.

MD5 算法是MD 結構的典型代表，是密碼學中應用廣泛的一種哈希函數［2］.由Ronald Rivest 在1991 年提出［3］.MD5 算法可以將任意長度的數據輸入壓縮成128 bit 的輸出，具有不可逆性、數據完整性、不可抵賴性等特點［4］，可以防止數據被篡改和數據丟失.

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

1 算法介紹

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

1.1 消息擴展

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

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

1.2 消息分組

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

1.3 循環運算

首先定義好每輪運算的邏輯函數，即：

其中包含了四個非線性基本函數為：

ti表示4294967296*abs（sin（i））的整數部分［11-12］；Mj表示512-bit的消息的第j個子分組；s表示循環左移s位.

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

1.4 摘要輸出

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

2 優化MD5算法設計

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

2.1 縮短關鍵路徑

在循環迭代方面將邏輯函數FF、GG、HH、II 的數據計算流程優化設計如圖1所示.

圖1 MD5算法的邏輯函數計算流程圖Fig.1 MD5 algorithm logic function calculation flow chart

1）利用一個加法器替代實現兩個加法器的操作，四級加法器操作優化成三級加法器.

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

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

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

利用流水線設計實現一個時鐘周期內輸出邏輯函數運算的結果，并對應地輸出給緊接的兩組FF數據.其余輪的運算與此類似，得到的a，b，c，d的值向右輪換輸出給下一輪計算使用.

2）優化循環移位操作.

由于64 步循環步驟中分成F、G、H、I 四輪操作，且每輪中循環移位的位數s按固定的4 個數字進行循環移位，一共循環4 次，各占16 步操作.其中F 輪操作中循環移位的位數s為7、12、17、22；G 輪操作中循環移位的位數s為5、9、14、10；H 輪操作中循環移位的位數s為4、11、16、23；I 輪操作中循環移位的位數s為6、10、15、21；由于位數固定，取消32-bit 數據進行循環移位的操作，替代的是直接將移位的結果作為加法器的加數相加.

利用以上兩種方式縮短單步運算的關鍵路徑，有效提高MD5算法運算速度.

2.2 流水線設計

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

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

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

圖2 頂層模塊示意圖Fig.2 Top-level module diagram

圖3 MD5算法硬件結構圖Fig.3 MD5 algorithm hardware structure diagram

2.2.1 MD5 Pipeline Core子模塊

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

2.2.2 MD5 Pipeline Control子模塊

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

圖4 多個消息分組時序圖Fig.4 Multiple message grouping sequence diagram

圖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值，仿真結果表明該設計功能正確.

圖5 功能仿真圖Fig.5 Functional simulation diagram

使用Arria10 FPGA 開發板進行了板級驗證，驗證了該設計的正確性.該設計使用了1 1903個ALUTs，最大的時鐘頻率173 MHz，占用寄存器為12 883 個，數據吞吐量最大為81.31 Gbps.表1列出了同類設計的資源消耗和性能比較.

表1 FPGA結果對比Tab.1 FPGA result comparison

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

圖6 芯片版圖Fig.6 Chip layout

4 結語

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