基于FPGA的改進型MD5算法的設(shè)計與實現(xiàn)

田 野

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

0 引言

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

雖然MD5存在以上諸多優(yōu)點，但在實際的使用中MD5算法仍暴露出了兩個主要問題，第一個問題是“彩虹表”撞庫的問題威脅著MD5算法的安全性，所以MD5加密的明文加“Salt”成為需要.彩虹表撞庫的思想就是建立一個原明文與密文之間對應(yīng)的hash表.這樣在獲得密文后通過比較，查詢或者計算，可以快速定位出原明文.防止彩虹表撞庫攻擊的有效方法是將擬加密明文加“Salt”，這個“Salt”值是由系統(tǒng)隨機生成的，這樣即使在彩虹表中建立了源數(shù)據(jù)和加密數(shù)據(jù)的對應(yīng)，由于擬加密明文加入了系統(tǒng)生成的“Salt”值，使散列值發(fā)生了改變，這樣就無法通過原有對應(yīng)關(guān)系推出明文，有效的降低了MD5算法被彩虹表撞庫的風(fēng)險.第二個問題是MD5大多數(shù)情況下由軟件實現(xiàn)，但是隨著通信領(lǐng)域?qū)挼囊笤絹碓礁撸浖崿F(xiàn)在性能上并不能很好的滿足高帶寬的需求，所以MD5算法的硬件實現(xiàn)在高帶寬背景下成為必需.因為FPGA是一種具有良好的重構(gòu)性，較高的可靠性和較好的實時性的硬件實現(xiàn)技術(shù)，所以該設(shè)計基于FPGA技術(shù)實現(xiàn)[2].

1 MD5算法理論介紹

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

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

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

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

第四步：用一個含有4輪“循環(huán)”的壓縮函數(shù)實現(xiàn)數(shù)據(jù)變換，每一輪分別具有一個邏輯函數(shù)而且結(jié)構(gòu)相似，NN,OO,PP,QQ分別表示了4輪“循環(huán)”壓縮函數(shù)每一輪的變換，

其中符號“<<

圖1 MD5算法四輪變換

第五步：輸出最終結(jié)果.

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

2 基于FPGA的加“Salt”MD5算法設(shè)計和實現(xiàn)

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

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

圖2 偽隨機數(shù)生成原理圖

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

圖3 偽隨機數(shù)發(fā)生器波形圖

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

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

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

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

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

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

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

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

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

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

圖4 總體設(shè)計示意圖

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

圖5 MD5密文生成模塊圖

3 系統(tǒng)仿真測試

系統(tǒng)采用Verilog HDL編寫實現(xiàn).目標(biāo)原器件是FPGA EP2C35F672C6芯片為基礎(chǔ)的DE2系統(tǒng)板.該芯片由Altera公司開發(fā).圖6為改進后MD5算法的仿真圖.

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

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

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

4 總結(jié)

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