3DES算法的FPGA高速實(shí)現

　　從技術(shù)角度講，網(wǎng)絡(luò )安全除了依賴(lài)安全的網(wǎng)絡(luò )通信協(xié)議及應用協(xié)議外，更多地取決于網(wǎng)絡(luò )設備如交換機、路由器等所提供的加/解密功能。目前，基于DES算法的加/解密硬件仍在廣泛應用于國內衛星通信、網(wǎng)關(guān)服務(wù)器、機頂盒、視頻傳輸以及其它大量的數據傳輸業(yè)務(wù)中。

　　然而，隨著(zhù)密碼分析技術(shù)的不斷發(fā)展，超期服役的DES算法已被攻破，隨即美國商業(yè)部提出采用以Rijndael算法的AES作為新一代的加密算法。在不對原有應用系統作大的改動(dòng)的情況下，3-DES算法有了很大的生存空間，被大量用來(lái)替換已不安全的DES算法。所以對3-DES算法的高速實(shí)現，仍具有一定的實(shí)際應用意義。

1 3-DES算法介紹

　　1999年，NIST將3-DES指定為過(guò)渡的加密標準。3-DES是DES的一個(gè)更安全的變形（關(guān)于DES算法的詳細資料，可見(jiàn)參考文獻[1]、[2]）。DES算法運算的框圖如圖1。其中S盒是3-DES（DES）算法的心臟，靠它實(shí)現非線(xiàn)性變換。

　　　　　　
　　3-DES算法可以描述如下：設ek(x)和dk(x)表示用DES算法對64位的位串的加密和解密，密鑰為K；則64位的密文c是通過(guò)執行下面的運算得到的：

　　　　　　　　　　　　　　
　　其中K1、K2、K3是56位的DES密鑰。從密文c導出明文x的3-DES的解密過(guò)程是加密過(guò)程的反過(guò)程，其描述如下：

　　　　　　　　　　　　　　　
　　其結構如圖2。

　　　　
　　為了獲得更高的安全性，三個(gè)密鑰應該是互不相同的。這樣，本質(zhì)上就相當于用一個(gè)長(cháng)為168位的密鑰進(jìn)行加密。多年來(lái)，它在對付強力攻擊時(shí)是比較安全的。對安全性需要不那么高的數據，K1可以等于K3。在這種情況下，密鑰的有效長(cháng)度為112位。

　　在通常使用的所有64位的分組密碼中，3-DES是最安全的；但是，如果用軟件來(lái)實(shí)現，它也是這些分組密碼中最慢的。通過(guò)硬件設計，3-DES的性能勝過(guò)大多數其它用軟件實(shí)現的分組密碼。

2 FPGA實(shí)現設計

　　本設計采用實(shí)驗室現有試驗開(kāi)發(fā)板上Xilinx公司SPARTANII結構的XC2S100作為算法載體，在其中實(shí)現控制器和三個(gè)DES模塊以及密鑰的生成，通過(guò)控制器實(shí)現加、解密功能。從上邊的介紹可以看到，3-DES（DES）算法沒(méi)有大量的復雜數學(xué)計算（如乘、帶進(jìn)位的加、模等），在加/解密過(guò)程和密鑰生成過(guò)程中僅有邏輯運算和查表運算。這些特點(diǎn)為采用FPGA進(jìn)行高速設計提供了契機。

2.1 DES模塊的設計結構

　　每個(gè)DES模塊的實(shí)現是用一個(gè)輪函數實(shí)現的16份拷貝通過(guò)深度細化的流水線(xiàn)處理來(lái)完成的，以獲得最高的性能。

　　采用循環(huán)全部打開(kāi)和流水線(xiàn)結構來(lái)設計。循環(huán)全部打開(kāi)后，實(shí)現全部16輪結構并串在一起，只要一個(gè)時(shí)鐘周期就可以完成一個(gè)數據塊的加密或解密；通過(guò)多占很大的空間來(lái)?yè)Q得速度上的大幅度提高，然后再在每輪的中間加上寄存器來(lái)實(shí)現流水線(xiàn)。在第一時(shí)鐘周期，第一塊數據經(jīng)過(guò)第一輪處理存入寄存器1中。在下一個(gè)時(shí)鐘周期，寄存器1中的結果經(jīng)過(guò)第二輪處理存入寄存器2中；同時(shí)，第二塊數據可以經(jīng)過(guò)第一輪處理存入寄存器1。這樣，多塊數據實(shí)現了同時(shí)處理。另外，在設計中通過(guò)使用16個(gè)寄存器，使得加/解密速度可以提高近16倍。在DES模塊的每一輪中設計3級流水線(xiàn)，盡管這樣增加了48個(gè)周期的時(shí)延，但卻進(jìn)一步提高了整體處理的速度性能；同時(shí)，將數據加/解密部分和密鑰生成部分分開(kāi)單獨設計，可以減少相鄰流水線(xiàn)級間的邏輯層數目。

2.2 S盒設計

　　通過(guò)時(shí)間分析發(fā)現，S盒在整個(gè)設計中占了很大的比重。S盒性能的提高對于整個(gè)設計性能會(huì )有很大的改善，因此S盒是整個(gè)設計優(yōu)化的重點(diǎn)。

　　DES的8個(gè)S盒分別是一個(gè)滿(mǎn)足特殊性能的6~4位的變換。在VHDL或Verilog語(yǔ)言中，可以直接用CASE語(yǔ)句來(lái)實(shí)現。這是最簡(jiǎn)單的實(shí)現方法，但是HDL語(yǔ)言都屬于高級語(yǔ)言，它們強烈依賴(lài)于編譯器的優(yōu)化能力，往往對設計者來(lái)說(shuō)，涉及得越少、編程越簡(jiǎn)單，代碼效率越不高，這對于高速實(shí)現來(lái)說(shuō)是不可取的。在實(shí)現過(guò)程中通過(guò)分析工具也發(fā)現，依賴(lài)于編譯器的實(shí)現不但復雜，而且占用大量的空間。這樣，S盒成了速度的瓶頸，為此，采用ROM來(lái)實(shí)現。XC2S100的LUT可以配置為16×1位的ROM，把輸入的6位作為地址，對應的地址空間里存放的就是輸出的4位，從而實(shí)現了6~4位的查找表LUT，所需時(shí)間只是FPGA中CLB的傳輸時(shí)間加上傳輸線(xiàn)上的延時(shí)，如圖3。

　　　　　　
2.3 密鑰生成器設計

　　密鑰生成器的設計是獨立于DES輪函數運算實(shí)現的，采用3級流水線(xiàn)來(lái)與輪函數中的流水線(xiàn)相平衡，單輪的實(shí)現如圖4。

　　
　　其中，3級流水線(xiàn)由移位寄存器（SR）和1個(gè)觸發(fā)器(FF)構成，在SR中完成兩級流水線(xiàn)，在FF中實(shí)現第三級。XC2S100的LUT中的每個(gè)查找表LUT可以用來(lái)生成1～16個(gè)移位寄存器，而且在一個(gè)單獨的可配置邏輯功能塊CLB中連接8個(gè)移位寄存器來(lái)構成一個(gè)128位的移位寄存器。

2.4 3-DES的實(shí)現

　　將上述所設計的三份DES模塊在FPGA中組合，實(shí)現如圖5所示的完整連接。整個(gè)時(shí)延約為單個(gè)DES模塊的三倍。

結 語(yǔ)

　　我們在Xilinx的開(kāi)發(fā)平臺Foundation 4.2i下用Verilog HDL完成設計，并進(jìn)行了綜合和仿真；成功下載到我們實(shí)驗室的試驗板上的XC2S100中，用VC++ 6.0編寫(xiě)了測試程序；在Windows98下運行，均 能正確實(shí)現加/解密功能。在試驗板上晶振為25MHz的情況下，大致評測出加密速度為520Mb/s。

　　　　　　　　　　　　　　　　　　參考文獻

1 王育民， 何大可. 保密學(xué)——基礎及應用. 西安：西安電子科技大學(xué)出版社，1990
2 National Institute of Standard and Technology. Data Encryption Standard ( DES ). Federal Information Processing Standards Publication 46-3 ( FIPS PUB 46-3 ), 1999
3 李廣軍，孟憲元. 可編程ASIC設計及應用. 成都：電子科技大學(xué)出版社，2000
4 夏宇聞. 復雜數字電路與系統的Verilog HDL設計技術(shù). 北京：北京航空航天大學(xué)出版社，1999