MD5算法的快速硬件實(shí)現(xiàn)

1、MD5算法的快速硬件實(shí)現(xiàn)                         摘  要 文章介紹了一種在FPGA上快速實(shí)現(xiàn)MD5算法的新方法，給出了優(yōu)化設(shè)計(jì)的原理、實(shí)現(xiàn)的具體方法及其重要模塊的設(shè)計(jì)實(shí)現(xiàn)方案。     關(guān)鍵詞 MD5；FPGA；Verilog語(yǔ)言；集成電路；關(guān)鍵路徑 1  引言&

2、#160;   隨著電子商務(wù)和網(wǎng)絡(luò)通信的發(fā)展，網(wǎng)絡(luò)信息安全的重要性越來(lái)越顯著，信息加密、數(shù)字簽名、數(shù)據(jù)的完整性認(rèn)證、身份驗(yàn)證等成為信息安全領(lǐng)域的重要內(nèi)容。MD5算法本身是為數(shù)字簽名應(yīng)用而設(shè)計(jì)的，隨后也應(yīng)用在信息驗(yàn)證技術(shù)當(dāng)中。作為應(yīng)用最廣泛的安全散列算法，MD5算法的高效實(shí)現(xiàn)就成為研究的需要，MD5算法本身可以采用軟件實(shí)現(xiàn)，但其性能受到處理器件性能的制約不能滿足網(wǎng)絡(luò)通信帶寬日益增長(zhǎng)的要求，因而通過(guò)硬件實(shí)現(xiàn)高速M(fèi)D5 運(yùn)算就成為需要。2  MD5算法介紹    MD5 算法可以對(duì)任何長(zhǎng)度不超過(guò) 264二進(jìn)制位的消息產(chǎn)生128 位的單向散列

3、消息摘要輸出， RFC1321 標(biāo)準(zhǔn)中的MD5 算法主要步驟如下：    在一些初始化處理后，MD5以512位分組來(lái)處理輸入文本，每一分組又劃分為16個(gè)32位子分組。算法的輸出由四個(gè)32位分組組成，將它們級(jí)聯(lián)形成一個(gè)128位散列值。    （1）附加填充比特：填充消息使其長(zhǎng)度恰好為一個(gè)比512位的倍數(shù)僅小64位的數(shù)。即對(duì)報(bào)文進(jìn)行填充使報(bào)文的長(zhǎng)度(比特?cái)?shù))與448模512同余。填充方法是附一個(gè)在消息后面接所要求的多個(gè)比特。    （2）附加長(zhǎng)度值：在其后附上64位的消息長(zhǎng)度（填充前）。如果消息長(zhǎng)度大于 26

4、4，僅使用該長(zhǎng)度的低64比特。這樣，該域包含的長(zhǎng)度值為初始長(zhǎng)度模264 的值。這兩步的作用是使消息長(zhǎng)度恰好是512位的整數(shù)倍（算法的其余部分要求如此），同時(shí)確保不同的消息在填充后不相同。    （3）初始化寄存器：四個(gè)32位初始化變量為：                它們也被稱為鏈接變量（chaining variable）    （4）進(jìn)行算法的主循環(huán)：這一步是算法的核心，它是一個(gè)包含四個(gè)大循

5、環(huán)的64步函數(shù)，四個(gè)大循環(huán)結(jié)構(gòu)相同，但每次使用的邏輯函數(shù)不同，每一個(gè)大循環(huán)由對(duì)512比特的16步操作組成，即每16步為一輪大循環(huán)。    每次操作如下(設(shè) Ai+1、Bi+1 、Ci+1 、Di+1 為第 +1個(gè)時(shí)鐘周期時(shí)打入寄存器的值)：         以一下是每輪中用到的四個(gè)非線性函數(shù)（每輪一個(gè)）。        常數(shù)ti可以如下選擇：在第i步中，ti是4294967296*abs(sin(i)的整數(shù)部分，i的單位是弧度。Wi是5

6、12位消息分組中的一個(gè)，Si是每次循環(huán)移位的次數(shù)。對(duì)每次而言也是固定的常數(shù)。    （5）結(jié)果輸出：所有64步完成之后，將第64步的輸出加到四個(gè)初始化變量上作為新的初始化變量，進(jìn)行下一個(gè)512比特分組的運(yùn)算，直到所有分組處理完畢，單次操作圖如下：圖1.  MD5算法單步操作圖                        

7、60;     3  算法優(yōu)化    由上圖可以看到，硬件實(shí)現(xiàn)時(shí)，MD5算法每一步操作中的關(guān)鍵路徑在于B的求?。ㄆ渌齻€(gè)變量都是直接傳遞），這個(gè)關(guān)鍵路徑包括了四個(gè)模 232加法運(yùn)算、三輸入變量的邏輯運(yùn)算、"兩個(gè)查找表運(yùn)算及一個(gè)循環(huán)左移運(yùn)算，而在FPGA設(shè)計(jì)中，加法運(yùn)算最為耗時(shí)，四個(gè)加法運(yùn)算至少需要三個(gè)加法器級(jí)聯(lián)完成，加法運(yùn)算嚴(yán)重制約了整個(gè)操作的速度，可見(jiàn)要加快算法運(yùn)行速度就必須在簡(jiǎn)化這一關(guān)鍵路徑上下工夫，經(jīng)過(guò)觀察我們發(fā)現(xiàn)，在中Ai是第時(shí)鐘周期里寄存器D 的值，而 Di的值又是第i-1周期里的Ci

8、-1 ，即Ai 的值是第i-1周期里Ci-1的值。    若在第周期設(shè)中間寄存器變量 ，并令    那么在第i+1周期，    就可以表示為操作就可以用下面幾個(gè)式子代替：        其中， Ai+1沒(méi)有參與任何運(yùn)算，因此上式可以接著化簡(jiǎn)為    這樣一來(lái)，原來(lái)一個(gè)周期內(nèi)需要完成三級(jí)加法和相應(yīng)的組合邏輯，現(xiàn)在只需要完成兩級(jí)加法和部分組合邏輯就行了，大大提高了算法速度，只要在運(yùn)算開(kāi)始時(shí)加個(gè)周期的初始化即可，簡(jiǎn)化后的系

9、統(tǒng)框圖如下：圖2.改進(jìn)后的單步操作圖4  結(jié)果比較    由上文中的算法分析部分不難看出，傳統(tǒng)的實(shí)現(xiàn)方式關(guān)鍵路徑是3級(jí)32比特加法器延遲和組合邏輯的延遲，而改進(jìn)的實(shí)現(xiàn)方式減少了一級(jí)加法器的延遲，并把組合邏輯的延遲分散到不同路徑上，因此，采用改進(jìn)的實(shí)現(xiàn)方式大約可以將速度提高到原來(lái)的1.5倍左右。同時(shí)，為了實(shí)現(xiàn)數(shù)據(jù)的初始化，需要提前一個(gè)周期計(jì)算出寄存器A的值，因此整個(gè)算法的實(shí)現(xiàn)需要65個(gè)周期。我們采用 VerilogHDL 描述，選擇Altera Stratix II EP2S15F672C5  FBGA芯片，在QuartusII6.0上驗(yàn)證通過(guò)。

10、由于在FPGA中，連線延時(shí)也很關(guān)鍵，而這部分延時(shí)不能像加法延時(shí)那樣通過(guò)預(yù)先計(jì)算并存儲(chǔ)在寄存器中來(lái)消除一部分，所以實(shí)際的MD5改進(jìn)算法與傳統(tǒng)型相比較，速度的提高約為1.3，資源方面由于只是增加了一個(gè)時(shí)鐘節(jié)拍，寄存器數(shù)量和組合邏輯并沒(méi)有增加，所以改進(jìn)型在資源方面和傳統(tǒng)型相當(dāng)。下表為算法改進(jìn)前后在資源、頻率、流量上的比較。表1. 改進(jìn)前后資源比較5  結(jié)束語(yǔ)    由表1可見(jiàn)，改進(jìn)型MD5算法實(shí)現(xiàn)，使用的資源并沒(méi)有明顯增加，但速度的改善十分明顯，基本實(shí)現(xiàn)了用較少的資源得到較高速率的目標(biāo)，證明了結(jié)構(gòu)的正確性和合理性。實(shí)驗(yàn)結(jié)果也說(shuō)明，這種利用寄存器來(lái)減少加法器級(jí)聯(lián)

11、從而減少關(guān)鍵路徑的實(shí)現(xiàn)方法也可用于一般的FPGA硬件設(shè)計(jì)中。參考文獻(xiàn)1 R.Rivest. The MD5 Message-Digest Algorithm，RFC1321 1992。2  Jarvinen K， Tommiska M，Skytta J.Hardware implementation analysis of the MD5 hash algorithm.System Sciences，2005.HICSS05.Proceedings of the 38th Annual Hawaii International conference on 03-06 Jan.2005:2983   Bruce Schneier. 應(yīng)用密碼學(xué).北京：機(jī)械工業(yè)出版社，2000：