基于FPGA的改進型MD5算法的設計與實現

田 野

(忻州師范學院計算機系，山西忻州 034000)

0 引言

MD5是在二十世紀九十年代由Rivest開發，經MD2、MD3和MD4發展而來.MD5算法在信息安全領域得到了十分普遍的運用.其具有以下特點：(1)壓縮性能較好：不管明文長度多少，生成的都是長度固定的MD5值.(2)計算的簡易性突出：從明文算出MD5值的方法十分簡易.(3)抗篡改性強：原始的數據哪怕是發生了極細微的改動，所得到的MD5值都會改動前的原始值產生異常大的區別.(4)抗碰撞性能突出：作為加密算法，抗碰撞性能顯得非常重要，假設知道明文還有MD5值均已知，但是要找出另外一個和已知MD5值一模一樣的明文仍然是異常艱難的[1].

雖然MD5存在以上諸多優點，但在實際的使用中MD5算法仍暴露出了兩個主要問題，第一個問題是“彩虹表”撞庫的問題威脅著MD5算法的安全性，所以MD5加密的明文加“Salt”成為需要.彩虹表撞庫的思想就是建立一個原明文與密文之間對應的hash表.這樣在獲得密文后通過比較，查詢或者計算，可以快速定位出原明文.防止彩虹表撞庫攻擊的有效方法是將擬加密明文加“Salt”，這個“Salt”值是由系統隨機生成的，這樣即使在彩虹表中建立了源數據和加密數據的對應，由于擬加密明文加入了系統生成的“Salt”值，使散列值發生了改變，這樣就無法通過原有對應關系推出明文，有效的降低了MD5算法被彩虹表撞庫的風險.第二個問題是MD5大多數情況下由軟件實現，但是隨著通信領域對帶寬的要求越來越高，軟件實現在性能上并不能很好的滿足高帶寬的需求，所以MD5算法的硬件實現在高帶寬背景下成為必需.因為FPGA是一種具有良好的重構性，較高的可靠性和較好的實時性的硬件實現技術，所以該設計基于FPGA技術實現[2].

1 MD5算法理論介紹

MD5的具體思想簡述如下：首先以16個分組來處理輸入的擬加密的明文，每個分組大小為32位，通過一系列運算處理后，可以推出所需要的信息，該信息值有4個分組級聯組合而成，每組32位[3].MD5算法主要分為以下5個步驟實現：

第一步：填充信息m使其比特數b滿足b≡448 mod 512，補充的內容除去第一位填充1，其他各位都用0填充，填充長度為1到512；

第二步：增加64 bit用來表示原明文m大小，假如m原來的大小多于264bit，則將多余長度刪去，保存低階64 bit即可；

第三步：使用寄存器，其中每個寄存器大小32 bit，共使用4個，寄存器空間總和為128 bit，并且用十六進制表示寄存器初始值.

第四步：用一個含有4輪“循環”的壓縮函數實現數據變換，每一輪分別具有一個邏輯函數而且結構相似，NN,OO,PP,QQ分別表示了4輪“循環”壓縮函數每一輪的變換，

其中符號“<<

圖1 MD5算法四輪變換

第五步：輸出最終結果.

以上是傳統MD5的基本實現方法，但是在實際使用中生成的密文面臨著被彩虹表撞庫的風險，通過對擬加密明文加入偽隨機數改變生成密碼的散列值可以降低通過彩虹表撞庫推出明文的風險.

2 基于FPGA的加“Salt”MD5算法設計和實現

根據MD5算法的原理以及FPGA的技術實現特點，整個設計大致上分成偽隨機數生成模塊，擬用加密明文前期處理模塊、數據存儲模塊、算法實現模塊、狀態機模塊、輸出密文模塊六部分[4]，以下簡要介紹各模塊設計：

(1)偽隨機數生成模塊：若干個異或門以及n個D觸發器組成了偽隨機數生成模塊，如圖2.

圖2 偽隨機數生成原理圖

Kn是取值只能為0和1反饋系數，取1時表明這個反饋路徑是存在的，反之為不存在.n個D觸發器可以最多提供不包括全0狀態下的2n-1個狀態[5].為測試偽隨機數發生模塊，利用Verilog HDL產生一個n=8，k0k1k2k3k4k5k6k7k8=101110001的偽隨機數發生器，在Modelsim上對其進行了仿真測試：首先將load信號置位，讓其在255個狀態中運行，得到偽隨機數255、143、111、222、205、235、…….仿真波形如圖3所示.

圖3 偽隨機數發生器波形圖

(2)明文前期處理模塊：該模塊具體實現包括：①為了使添加后明文的長度達到512位的倍數，明文前期處理模塊加入了數據填充子模塊負責填充位的添加和長度的添加；②為了方便計算和存儲原始明文的長度，前期處理模塊內加入了明文長度計數器.當valid信號輸入為有效時，每當1個字節的數據被輸入后，相應計數器執行加8的操作，反之valid信號輸入為無效狀態時，計數中止工作；③為了統計一共有多少個512位的明文分組，前期處理模塊加入了明文分組計數器[6].

(3)數據存儲模塊：該模塊有兩個存儲器構成，包括一個用于保存512位明文分組的地址寬度為16的雙端口隨機存取存儲器和一個用于保存常數組T值查找表的數據寬度為32，地址寬度為64的只讀存儲器[7].

(4)算法實現模塊：該模塊主要有三個基本功能，即加法運算操作、循環移位操作和非線性函數運算.Quartus II 8.0中集成了可以調用的，可用于加法運算操作以及循環移位的模塊，在非線性函數N/O/P/Q的實現中，先假設輸出函數為w，則其輸出：

whenround=2'b10,w=P(b,c,d)=b⊕c⊕d,

(5)狀態機模塊：該模塊借鑒分層思想，自上而下分三層分別用狀態機嵌套實現了各類狀態關系.其中，控制完成明文(偽偽隨機數+輸入明文)的處理由上層狀態機實現；中層狀態機負責完成每一個512位明文分組的處理；下層狀態機負責每一步的處理控制[8].具體功能設計如下：

①上層狀態機存在有4種不同的狀態：空閑狀態(reset=1)；start=1時處理明文，轉入等待狀態；ack=1時轉入工作狀態；當狀態機離開工作狀態時就表示完成了一個明文分組的操作，若檢查發現不是最后一個分組則等待，否則輸出；等輸出狀態輸出結果后，狀態機自主轉入空閑狀態為下一段擬加密明文的操作做好準備[9]；

②中層狀態機有5個狀態：開始狀態、就緒狀態(等待輸入)、前期處理狀態、循環處理狀態(完成每輪16步共4輪處理)、最后處理狀態(完成處理后的A，B，C，D與初始摘要值的相加)；

③下層狀態機包含有2個狀態機.其中一個狀態機表示4輪操作，另外一個狀態機表示16步處理為一輪.兩個狀態機均在中層狀態機執行循環處理時開始工作.

(6)輸出密文模塊：該模塊由摘要寄存器和4個加法器組成，前者用于保存每個分組的初始摘要，后者用于完成操作后的A、B、C、D與初始摘要的相加.

綜上所述：總體設計如圖4所示，其中，偽隨機數模塊主要完成偽隨機數的生成.預處理模塊主要負責完成將偽隨機數模塊生成的數字放在明文之前以及填充位的填充和長度的填充.因為添加了偽隨機數后的擬加密明文以及常量數組的查找表均需要保存，所以增加了存儲模塊.在狀態機模塊發出信號后，進行了每輪16步共計4輪的循環處理.輸出密文模塊將算法實現模塊循環處理后的A、B、C、D與初始摘要值相加，輸出最后的結果.控制整個系統運行的控制信號由狀態機模塊通過其他模塊反饋信號和輸入信號產生[10].

圖4 總體設計示意圖

如圖5所示，用Verilog HDL語言進行優化設計，由QuartusII編譯生成的MD5密文生成模塊圖，包括偽隨機數生成、預處理、存儲、狀態機、算法操作和輸出各子模塊功能[11].

圖5 MD5密文生成模塊圖

3 系統仿真測試

系統采用Verilog HDL編寫實現.目標原器件是FPGA EP2C35F672C6芯片為基礎的DE2系統板.該芯片由Altera公司開發.圖6為改進后MD5算法的仿真圖.

圖6 改進MD5加密算法仿真圖

由圖6可知，明文為“123”，生成偽隨機數為“255”，加密明文為“255123”，處理后得到的32位散列值為“cb881061c30f2d49c3817b03f2e731b0”，和MD5軟件求得的32位散列值一致.證明了本設計是正確的，合理的.

從結果分析來看，該設計理論最大時鐘頻率可以達到50 MHz，使用了4 895個邏輯單元，占總邏輯單元的12%.從以上仿真結果可知，每經過52個時鐘頻率的延時可以處理一個512 bit的消息分組，于是可以計算出理論處理速度為：50×512÷52≈492.3(Mbit/s).

4 總結

本設計基于FPGA技術，利用Verilog語言完成編程設計，通過加入偽隨機數生成模塊降低了傳統MD5在實際使用中被“彩虹表”撞庫的風險，在提高MD5加密速度的同時提高了MD5算法的安全性.因為MD5算法與很多現在比較流行的數據摘要算法相比有許多類似之處,同時FPGA靈活可編程特點使其可以適用于不同的系統，因此本文提出的設計可以根據其他摘要算法的特點進行重構以便運用于其他摘要算法的硬件實現，經過實驗驗證，該設計具有一定的理論和實用價值.