基于FPGA的改進(jìn)DES算法的實(shí)現

為了解決數據在網(wǎng)絡(luò )通信中的安全傳輸問(wèn)題，通常采用分組加密技術(shù)對數據信息進(jìn)行加密保護，其中最具有代表性的是數據加密標準DES。DES加密算法已成為應用非常廣泛的一種分組對稱(chēng)加密算法,該算法具有極高的安全性。到目前為止，除了窮舉搜索法對DES算法進(jìn)行攻擊外，還沒(méi)有發(fā)現更有效的方法。目前，DES算法廣泛應用于衛星通信、網(wǎng)關(guān)服務(wù)器、網(wǎng)絡(luò )通信設備、智能卡（IC卡）等領(lǐng)域[1]。其實(shí)現方法通常分為軟件實(shí)現和硬件實(shí)現兩種，由于軟件實(shí)現時(shí)速度較慢，最快速度不到150 Mb/s[2]，且利用軟件實(shí)現DES算法在安全性方面也存在隱患，而應用硬件實(shí)現則可以克服以上的問(wèn)題?，F場(chǎng)可編程門(mén)陣列(FPGA)在算法實(shí)現方面具有靈活性、物理安全性，相對于軟件實(shí)現，在速度和性能上具有明顯的優(yōu)勢。
DES算法是以多輪的密鑰變換輪函數、子密鑰和數據異或運算的輪函數為特征，相應的硬件實(shí)現方法有兩種：一種是通過(guò)輪函數的16份硬件拷貝，達到深度細化的流水線(xiàn)處理，實(shí)現性能最優(yōu)；另一種是通過(guò)時(shí)分復用，重復調用1份輪函數的硬件拷貝，以時(shí)間換空間，從而得到硬件資源占用的最小化。通過(guò)對系統的性能和資源占用進(jìn)行綜合考慮，本文采用資源優(yōu)先方案。
采用此方案系統消耗的資源較少，但運行速度受限。改進(jìn)的方法是采取在輪函數內部設置流水線(xiàn)結構來(lái)提高整體處理的速度，同時(shí)子密鑰變換輪函數提供子密鑰，應與迭代輪函數保持同步工作狀態(tài)，以減少迭代運算帶來(lái)的等待延遲。通過(guò)設置迭代輪計數器產(chǎn)生的算法狀態(tài)執行指示位，控制輪函數的輸入和反饋，實(shí)現輪函數的復用。
1 DES算法概述與原理
　　DES是一種分組加密算法,將64 bit的明文模塊輸入用64 bit密鑰加密得到64 bit密文輸出。其64 bit密鑰中有效密鑰只有56 bit，其余8 bit為奇偶校驗位，不參與運算。同時(shí)，它也是對稱(chēng)加密算法，其加密和解密運算過(guò)程是一樣的，區別僅僅在于迭代時(shí)子密鑰的使用順序，算法本身并沒(méi)有任何變化。DES算法的處理流程如圖1所示。

圖1(a)是整個(gè)算法的實(shí)現處理流程，64 bit的明文輸入模塊經(jīng)過(guò)初始置換IP后，改變了分組中每個(gè)bit的順序,并把置換輸出分為L(cháng)0、R0兩部分；進(jìn)入16輪迭代運算,每一輪迭代都要用到輪函數f,第16輪迭代兩輸出左右互換的結果R16、L16作為逆初始置換IP-1的輸入；64 bit的R16、L16經(jīng)過(guò)逆初始置換得到64 bit的密文輸出,IP·IP-1=I。
圖1(b)是單輪迭代運算過(guò)程，也是一非線(xiàn)性變換的作用過(guò)程。第i輪迭代過(guò)程的具體描述可表示為[3]：

其中,㈩表示2 bit串的“異或”(按位模2加)。
輪函數f是迭代運算的核心部分，正是在密鑰控制下多次利用論函數進(jìn)行加密變換，才達到實(shí)現擴散和混淆的效果。輪函數f的功能由四個(gè)部分按順序完成:(1)將32 bit Ri-1輸入通過(guò)擴展E變換擴展為48 bit的數據； (2)將擴展后的48 bit數據與對應的48 bit子密鑰Ki“異或”； (3)將異或結果分成8個(gè)6 bit分組，8個(gè)分組在8個(gè)不同的非線(xiàn)性S盒的作用下被轉變?yōu)?個(gè)4 bit分組,其中每個(gè)S盒都將6 bit輸入映射為4 bit輸出;(4)將S盒的輸出結果經(jīng)過(guò)P盒的換位置換,得到f(Ri-1,Ki)的32 bit輸出。
DES實(shí)際有效的密鑰長(cháng)度為56 bit，對于56 bit的密碼信息，每7 bit擴充1 bit奇偶校驗位,從而得到64 bit外部密鑰。外部密鑰輸入后，首先經(jīng)過(guò)重排PC-1表(剔除奇偶校驗位，打亂密碼信息順序)得到56 bit原始密鑰，并分成兩部分28 bit的輸出。每部分按循環(huán)移位次數表[4]移位，并按重排PC-2表置換得到每輪迭代所需的48位子密鑰。
2 DES算法的FPGA實(shí)現
本設計選用資源優(yōu)先方案,即僅用硬件實(shí)現單輪密鑰變換和密鑰加數據運算的輪函數,通過(guò)重復16次調用這一功能模塊來(lái)實(shí)現一次DES加/解密運算。該設計方案原理圖如圖2所示。當數據裝載信號置為高電平時(shí)，待加/解密數據通過(guò)數據選擇器送到輪函數的入口。同時(shí)在輪計數器的控制下，算法狀態(tài)執行位置1。在第一個(gè)時(shí)鐘到來(lái)時(shí),將數據(B1、B2)通過(guò)輪函數實(shí)現第一輪變換，經(jīng)過(guò)第一輪變換后的數據被寄存器鎖存。在下一個(gè)時(shí)鐘到來(lái)時(shí)，與相應輪的子密鑰一起再次被送到輪函數的輸入端，這樣循環(huán)16輪后，算法狀態(tài)執行位置0，輸出最終數據。

本文在對DES算法進(jìn)行建模時(shí)，將整個(gè)算法分為子密鑰生成模塊、S盒非線(xiàn)性變換模塊、單輪迭代運算模塊和頂層模塊四個(gè)部分。其中，單輪迭代運算模塊調用子密鑰生成模塊和S盒模塊實(shí)現了一輪迭代運算功能。
2.1子密鑰的生成
DES算法每一輪次迭代都需要一個(gè)子密鑰參與“異或”運算。傳統的硬件實(shí)現時(shí)，通過(guò)對外部密鑰的換位重組，以及每次迭代對應的不同次數的循環(huán)移位，預先生成子密鑰。這樣不僅語(yǔ)言描述復雜，占用的硬件資源較多，而且每輪密鑰移位次數也不同，需要的運算時(shí)間不同，會(huì )給算法的迭代運算帶來(lái)更大的等待延遲。
外部密鑰先后經(jīng)過(guò)置換重排1、第n輪的循環(huán)移位和置換重排2這三個(gè)步驟得到第n輪的子密鑰。通過(guò)分析可知這一系列處理都只是位的置換，每輪迭代需要每一位子密鑰，相對于外部密鑰的每一位存在一定固定的對應關(guān)系。為了降低資源消耗，提高算法執行速度，設計中可將三個(gè)步驟合并成一次位的置換。采用硬件描述語(yǔ)言Verilog HDL對子密鑰生成模塊進(jìn)行組合邏輯設計,其仿真結果如圖3所示。圖中，mode為工作方式（=0時(shí),加密；=1時(shí),解密);外部密鑰為十六進(jìn)制數133457799bbcdff1時(shí)，prekey為外部密鑰被剔除奇偶校驗位生成的56 bit有效密鑰重排PC-1得到的原始密鑰，newkey為經(jīng)過(guò)重排PC-2置換的48 bit子密鑰。只要改變迭代輪數ki，就會(huì )預先生成子密鑰。迭代輪數的變化是通過(guò)輪計數器來(lái)控制。