摘 要 文章介紹了一種在FPGA上快速實現MD5演算法的新方法，給出了優化設計的原理、實現的具體方法及其重要模組的設計實現方案。
關鍵詞 MD5；FPGA；Verilog語言；積體電路；關鍵路徑
1 引言
隨著電子商務和網路通訊的發展，網路資訊保安的重要性越來越顯著，資訊加密、數字簽名、資料的完整性認證、身份驗證等成為資訊保安領域的重要內容。MD5演算法本身是為數字簽名應用而設計的，隨後也應用在資訊驗證技術當中。作為應用最廣泛的安全雜湊演算法，MD5演算法的高效實現就成為研究的需要，MD5演算法本身可以採用軟體實現，但其效能受到處理器件效能的制約不能滿足網路通訊頻寬日益增長的要求，因而通過硬體實現高速MD5 運算就成為需要。
2 MD5演算法介紹
MD5 演算法可以對任何長度不超過 264二進位制位的訊息產生128 位的單向雜湊訊息摘要輸出， RFC1321 標準中的MD5 演算法主要步驟如下：
在一些初始化處理後，MD5以512位分組來處理輸入文字，每一分組又劃分為16個32位子分組。演算法的輸出由四個32位分組組成，將它們級聯形成一個128位雜湊值。
（1）附加填充位元：填充訊息使其長度恰好為一個比512位的倍數僅小64位的數。即對報文進行填充使報文的長度(位元數)與448模512同餘。填充方法是附一個１在訊息後面接所要求的多個位元０。
（2）附加長度值：在其後附上64位的訊息長度（填充前）。如果訊息長度大於 264，僅使用該長度的低64位元。這樣，該域包含的長度值為初始長度模264 的值。
這兩步的作用是使訊息長度恰好是512位的整數倍（演算法的其餘部分要求如此），同時確保不同的訊息在填充後不相同。
（3）初始化暫存器：四個32位初始化變數為：
它們也被稱為連結變數（chaining variable）
（4）進行演算法的主迴圈：這一步是演算法的核心，它是一個包含四個大迴圈的64步函式，四個大迴圈結構相同，但每次使用的邏輯函式不同，每一個大迴圈由對512位元的16步操作組成，即每16步為一輪大迴圈。
每次操作如下(設 Ai+1、Bi+1 、Ci+1 、Di+1 為第 +1個時鐘週期時打入暫存器的值)：
以一下是每輪中用到的四個非線性函式（每輪一個）。
常數ti可以如下選擇：在第i步中，ti是4294967296*abs(sin(i))的整數部分，i的單位是弧度。Wi是512位訊息分組中的一個，Si是每次迴圈移位的次數。對每次而言也是固定的常數。
（5）結果輸出：所有64步完成之後，將第64步的輸出加到四個初始化變數上作為新的初始化變數，進行下一個512位元分組的運算，直到所有分組處理完畢，單次操作圖如下：
圖1. MD5演算法單步操作圖
3 演算法優化
由上圖可以看到，硬體實現時，MD5演算法每一步操作中的關鍵路徑在於B的求取（其他三個變數都是直接傳遞），這個關鍵路徑包括了四個模 232加法運算、三輸入變數的邏輯運算、"兩個查詢表運算及一個迴圈左移運算，而在FPGA設計中，加法運算最為耗時，四個加法運算至少需要三個加法器級聯完成，加法運算嚴重製約了整個操作的速度，可見要加快演算法執行速度就必須在簡化這一關鍵路徑上下工夫，經過觀察我們發現，在
中 對每個週期都是已知的常數，是輸入的512位元的一個32位分組，這樣，在512位元輸入初始化完成後，也可看作固定常數，
Ai是第ｉ時鐘週期裡暫存器D 的值，而 Di的值又是第i-1週期裡的Ci-1 ，即Ai 的`值是第i-1週期裡Ci-1的值。
若在第ｉ週期設中間暫存器變數 ，並令
那麼在第i+1週期，
就可以表示為
操作就可以用下面幾個式子代替：
其中， Ai+1沒有參與任何運算，因此上式可以接著化簡為
這樣一來，原來一個週期內需要完成三級加法和相應的組合邏輯，現在只需要完成兩級加法和部分組合邏輯就行了，大大提高了演算法速度，只要在運算開始時加－個週期的初始化即可，簡化後的系統框圖如下：
圖2. 改進後的單步操作圖
4 結果比較
由上文中的演算法分析部分不難看出，傳統的實現方式關鍵路徑是3級32位元加法器延遲和組合邏輯的延遲，而改進的實現方式減少了一級加法器的延遲，並把組合邏輯的延遲分散到不同路徑上，因此，採用改進的實現方式大約可以將速度提高到原來的1.5倍左右。同時，為了實現資料的初始化，需要提前一個週期計算出暫存器A的值，因此整個演算法的實現需要65個週期。我們採用 VerilogHDL 描述，選擇Altera Stratix II EP2S15F672C5 FBGA晶片，在QuartusII6.0上驗證通過。由於在FPGA中，連線延時也很關鍵，而這部分延時不能像加法延時那樣通過預先計算並存儲在暫存器中來消除一部分，所以實際的MD5改進演算法與傳統型相比較，速度的提高約為1.3，資源方面由於只是增加了一個時鐘節拍，暫存器數量和組合邏輯並沒有增加，所以改進型在資源方面和傳統型相當。下表為演算法改進前後在資源、頻率、流量上的比較。
表1. 改進前後資源比較
5 結束語
由表1可見，改進型MD5演算法實現，使用的資源並沒有明顯增加，但速度的改善十分明顯，基本實現了用較少的資源得到較高速率的目標，證明了結構的正確性和合理性。實驗結果也說明，這種利用暫存器來減少加法器級聯從而減少關鍵路徑的實現方法也可用於一般的FPGA硬體設計中。
參考文獻
[1] st. The MD5 Message-Digest Algorithm，RFC1321 1992。
[2] Jarvinen K， Tommiska M，Skytta ware implementation analysis of the MD5 hash em Sciences，S’eedings of the 38th Annual Hawaii International conference on 03-06 Jan.2005:298
[3] Bruce Schneier. 應用密碼學.北京：機械工業出版社，2000：188～194
[4] William Stallings. 密碼編碼學與網路安全：原理與實踐.北京：電子工業出版社，2001: 216～222。
[5] 夏宇聞log 數字系統設計教程.航空航天大學出版社，2005