基于FPGA的RC4加密算法設(shè)計及實現(xiàn)

苗三立，左金印，宋宇飛

(1.華北計算機系統(tǒng)工程研究所，北京 100083； 2.北京大學，北京 100083)

0 引言

隨著計算機網(wǎng)絡(luò)和通信技術(shù)的發(fā)展，信息作為一種重要的資源已經(jīng)成為促進社會進步和經(jīng)濟増長的重要力量。但是，信息的存儲、傳遞、處理等過程通常需要通過公開的計算機網(wǎng)絡(luò)進行操作，容易遭受到竊聽、篡改、偽造等多種攻擊方式的威脅，因此信息安全是計算機網(wǎng)絡(luò)領(lǐng)域中的一個重要的課題方向[1]。眾多加密算法也應(yīng)運而生，典型的有DES，RC4，RSA，AES，IDEA等，其中加密算法RC4以其實現(xiàn)容易、加密速度快、安全性較高，得到廣泛的認可與應(yīng)用。該算法的速度可以達到DES加密算法的10倍左右，且具有較高級別的非線性[2]。隨著計算機網(wǎng)絡(luò)的普及，傳統(tǒng)的軟件加密已經(jīng)逐漸不能滿足日常工作的需求，傳統(tǒng)軟件加密的局限性也逐漸暴露出來，在眾多計算機信息安全系統(tǒng)中，各種高速數(shù)據(jù)密碼機、密碼卡、智能卡等硬件加密手段被應(yīng)用到各種系統(tǒng)設(shè)備中，用來提高密碼運算速度和系統(tǒng)的安全性、可靠性。當前，以密碼設(shè)備為核心的硬件加密系統(tǒng)已成為構(gòu)筑信息安全平臺的重要屏障。本文給出了一種基于FPGA的RC4加密算法實現(xiàn)方案，相比軟件實現(xiàn)，該方案加密速度更快，安全性更高，可以應(yīng)用于多種不同的信息傳輸通信系統(tǒng)[3]。

1 RC4算法介紹

RC4是一種流密碼算法，是現(xiàn)代通信領(lǐng)域通用的基于非線性變換的算法，該算法被廣泛用于SSL/TLS協(xié)議、WEP協(xié)議和WPA協(xié)議，Lotus Notes、Windows、Oracle Secure SQL、Apple(AOCE)等多種通訊協(xié)議，現(xiàn)如今RC4算法也被用作蜂窩數(shù)字數(shù)據(jù)包規(guī)范[4]。RC4加密算法是由Ron Rivest，一名美國的密碼學家于1987年設(shè)計完成實現(xiàn)，起初RC4算法被用于數(shù)據(jù)庫(MySQL)安全以及網(wǎng)絡(luò)安全等領(lǐng)域上，一直到1994年該算法被發(fā)布到了互聯(lián)網(wǎng)上，開源公布給大家[5]。對RC4算法的改進分別是Paul 和Prenecl于2005年提出的RCA算法和Bartosz于同年提出的VMPC算法[6]。

該算法是一種流密碼加密算法，是基于非線性變換的算法，主要包括兩個方面的內(nèi)容：

1)密鑰編制算法(Key Schedule Algorithm)：用變長的密鑰進行隨機排序產(chǎn)生密鑰流的初始狀態(tài)；

2)偽隨機序列生成算法PRGA(pseudo random generation algorithm)：參照初始狀態(tài)生成相應(yīng)的密鑰流序列，然后與明文相異或生成相應(yīng)的密文。

RC4加密算法加密原理如下：第一步，按照既定的算法初始化兩個向量寄存器S和T；第二步，對寄存器S進行重排列(亂序排列)；第三步，按照既定的算法產(chǎn)生相應(yīng)的密鑰流k，然后存儲并參與之后的明文加密操作[7]。加密流程如圖1所示。

圖1 加密流程

2 硬件設(shè)計

本文采用Verilog HDL語言以同步有限狀態(tài)機(FSM)的設(shè)計方法，實現(xiàn)了基于FPGA的RC4加密處理流程。在計算機信息安全系統(tǒng)中，硬件加密手段被應(yīng)用到設(shè)備中來提高密碼運算速度和系統(tǒng)的安全性。RC4加密算法的FPGA實現(xiàn)方案，相比軟件實現(xiàn)方案，硬件加密方案速度更快，安全性更高[8]。

系統(tǒng)設(shè)計由3部分組成，分別是時序邏輯控制模塊、運算控制模塊及存儲模塊三部分組成，其中存儲模塊包括密鑰流存儲模塊和內(nèi)部寄存器存儲模塊。明文數(shù)據(jù)由外部輸入，暫存于明文寄存器，與存儲模塊存儲的密鑰流共同參與運算模塊的處理。運算模塊產(chǎn)生的密文暫存于密文寄存器中，供后續(xù)模塊的使用。其中，系統(tǒng)內(nèi)使用的時鐘由時序處理模塊產(chǎn)生，通過FPGA配置AD9516芯片輸出低抖動、穩(wěn)定的時鐘[9]。首先將密鑰信息K存儲在密鑰存儲模塊(RAM)中，然后根據(jù)地址信息從密鑰存儲模塊(RAM)中提取密鑰信息K，本文中規(guī)定明文數(shù)據(jù)為3字節(jié)(24 bit)，經(jīng)過RC4加密處理模塊產(chǎn)生相應(yīng)的密鑰流k信息，完成密鑰流的生成，用以生成相應(yīng)的密文信息[10]。邏輯框圖如圖2所示。

圖2 邏輯框圖

1)時序邏輯控制模塊：時序邏輯控制模塊采用AD9516-3芯片，AD9516-3是ADI公司發(fā)布的AD9516系列時鐘產(chǎn)品，可以提供高質(zhì)量、低抖動的時鐘信號，適用于無線和有線的基礎(chǔ)設(shè)施、WIMAX基地、光網(wǎng)站、自助測試設(shè)備、醫(yī)學圖像處理等儀器儀表裝置。AD9516系列集成了1個整數(shù)N分頻的頻率合成器、1個軋空振蕩器(VCO)、2個參考輸入端、可編程驅(qū)動器、可調(diào)延遲線和14個時鐘驅(qū)動器，包括LVPECL、LVDS和CMOS輸出。AD9516芯片由系統(tǒng)FPGA芯片通過串行控制端口來進行相關(guān)的參數(shù)配置及輸入[11]。模塊結(jié)構(gòu)圖如圖3所示。

圖3 時序邏輯控制模塊結(jié)構(gòu)圖

2)運算控制模塊：采用有限狀態(tài)機的方式對各個邏輯狀態(tài)進行控制和操作，時鐘采用AD9516芯片輸出的低抖動、高質(zhì)量的時鐘信號。詳細的狀態(tài)流程才加軟件設(shè)計部分。

3)存儲模塊：存儲模塊采用Block RAM存儲，相較與FIFO存儲而言，優(yōu)勢在于可以通過訪問地址選取不同的數(shù)據(jù)信息。為解決并行系統(tǒng)高效進行大量數(shù)據(jù)傳輸和交換的實時性要求，本文采用了一種基于FPGA的四口RAM，四口RAM由1個雙口RAM模塊、2個控制模塊和4個緩存模塊組成[12]?？傮w設(shè)計架構(gòu)如圖4所示。

圖4 四口RAM存儲模塊中體設(shè)計架構(gòu)圖

3 軟件設(shè)計

在本設(shè)計系統(tǒng)中，流程設(shè)計采用狀態(tài)機的規(guī)范進行編寫，總體流程為：消息信息進入設(shè)計系統(tǒng)，首先進行CRC編碼，經(jīng)過編碼后的消息信息進行RC4編碼加密處理，然后進行消息信息的傳遞。

3.1 CRC校驗設(shè)計

循環(huán)冗余校驗碼(cyclic redundancy check， CRC)又稱CRC校驗，是一種能力非常強的檢錯、糾錯碼，相比于更加穩(wěn)定、精確的RS校驗算法，具有實現(xiàn)編碼和檢碼的電路比較簡單、編碼易于實現(xiàn)等優(yōu)勢，通常用于串行傳輸?shù)妮o助存儲器與主機的信息數(shù)據(jù)通信和計算機網(wǎng)絡(luò)中。CRC檢驗是一種在數(shù)據(jù)通信系統(tǒng)和其它串行傳輸系統(tǒng)中廣泛使用的錯誤檢測手段。通用的CRC標準有CRC-8、CRC-16、CRC-32、CRC-CCIT，其中在設(shè)備信息傳輸通信系統(tǒng)中應(yīng)用最廣泛的是CRC-16標準。傳統(tǒng)手段是采用串行的編碼方式進行CRC編碼，速度比較慢，處理并行數(shù)據(jù)電路較為復雜；本系統(tǒng)將采用一種新的CRC-16并行編碼方式，采用并行處理的方式進行對并行信息數(shù)據(jù)進行CRC編碼。相比于串行CRC編碼方式，消耗時鐘減少，硬件電路簡化等優(yōu)勢。

進行CRC編碼要采用模2運算法則，具體描述一下模2運算法則。首先模2運算是一種二進制運算法則，同時也包括相應(yīng)的模2加、模2減、模2乘、模2除4種運算。模2運算用“+”表示加法運算，用“-”、“×”或“.”、“/”分別表示減法、乘法和除法運算。因此，模2運算是類似于四則運算的一種二進制算法。但是模2運算不同于四則運算的是，模2減法為不帶借位的二進制減法，模2加法是不帶進位的二進制加法。同理，模2乘法在中間的累加運算時也是不帶進位的二進制加法；模2除法在中間結(jié)果的減法時也是不帶借位的二進制減法。由此看來，模2運算的加減法相當于兩個二進制數(shù)的按位異或運算操作。同理，模2除法運算的，如果余數(shù)的首位為1，那么商就為1，其他操作按照模2減法運算；如果余數(shù)的首位為0，那么商就為0。

CRC碼校驗的基本思路是：利用線性反饋移位寄存器(linear feedback shift register, LFSR)和線性編碼的原理。LFSR是指，首先給定前一狀態(tài)的輸出，將該輸出的線性函數(shù)再用作輸入的移位寄存器。其中文章中采用的異或運算是最常見的單比特線性函數(shù)：對寄存器中的某些位進行異或運算后作為后面狀態(tài)的輸入端，然后再對整個寄存器進行移位操作。具體運算如下：再輸出端按照要發(fā)送的k位二進制數(shù)據(jù)序列，采用模2運算的法則產(chǎn)生一個r位的監(jiān)督碼，即校驗用的CRC碼，然后將其添加到k位二進制信息碼的低位處，組成一個k+r位的新的二進制數(shù)據(jù)序列，此產(chǎn)生二進制數(shù)據(jù)序列的過程便是CRC編碼。在檢驗時，使用CRC編碼與生成多項式G(x)進行模2除法運算，運算結(jié)果如果余數(shù)為0，那么說明在傳輸過程中k位二進制數(shù)據(jù)序列沒有發(fā)生錯誤或丟失；如果運算結(jié)果不為0，說明在傳輸過程中k位二進制數(shù)據(jù)序列發(fā)生錯誤或產(chǎn)生丟失。因此，采用余數(shù)是否為0來判斷數(shù)據(jù)在傳輸過程中是否發(fā)生變化。

CRC碼的檢錯糾錯原理：在接收端收到數(shù)據(jù)后若如果有一位數(shù)據(jù)出現(xiàn)錯誤，結(jié)果則為余數(shù)不為0，并且不同位出錯，其余數(shù)不但不為0并且也不同。假設(shè)循環(huán)碼有一位出錯，用G(x)作模2除將得到一個不為0的余數(shù)。如果對余數(shù)補0繼續(xù)除下去，將出現(xiàn)一個有趣的現(xiàn)象：余數(shù)會按照001,010,100,011,111,101循環(huán)下去，分別對應(yīng)出錯位第1,2,3,4,5,6,7位。例如第一位出錯，余數(shù)將為001，余數(shù)后面補0后再除(補0后如果數(shù)據(jù)的最高位為1，則用除數(shù)做模2減法然后取余數(shù)；如果最高位為0，則其最低3位就是余數(shù))，計算后得到第二次余數(shù)為010。之后繼續(xù)補0作模2除，依次得到余數(shù)為100,011,111,101,循環(huán)下去。

本系統(tǒng)采用的是并行處理的CRC校驗，相比串行CRC校驗消耗的時鐘減少，電路結(jié)構(gòu)簡化。輸入數(shù)據(jù)為十六進制數(shù)據(jù)A7，串行處理結(jié)果圖5所示，經(jīng)過8個時鐘周期后結(jié)果為十六進制數(shù)據(jù)83D1。并行處理結(jié)果如圖6所示，系統(tǒng)經(jīng)過1個時鐘周期后輸出結(jié)果為十六進制數(shù)據(jù)83D1。

圖5 串行CRC編碼時序仿真圖

圖6 并行CRC編碼時序仿真圖

3.2 算法設(shè)計流程

在本系統(tǒng)設(shè)計中，F(xiàn)PGA芯片采用Xilinx廠家生產(chǎn)的Spartan6 XC6SLX45T型號，RC4算法程序采用Verilog編寫。RC4算法程序流程圖如圖7所示。

圖7 RC4算法程序流程圖

RC4算法具體流程為，首先從RAM中提取密鑰k，然后初始化數(shù)組S、T，系統(tǒng)內(nèi)設(shè)定數(shù)組容量為256位；然后對數(shù)組S進行重排序，進而產(chǎn)生32位的密鑰，存入RAM模塊，與明文進行異或操作產(chǎn)生密文。

在設(shè)計中采用同步有限狀態(tài)機(FSM)實現(xiàn)，其狀態(tài)轉(zhuǎn)移圖如圖4所示。idle為初始化數(shù)組S和T狀態(tài)，arrange為重新排列數(shù)組S狀態(tài)，produce為產(chǎn)生密鑰流狀態(tài)；remainder為對j取余狀態(tài)，swap_1為交換數(shù)組S狀態(tài)；remainder_i為對i取余狀態(tài)，remainder_j為對j取余狀態(tài)，remainder_t為對t取余狀態(tài)，swap_2為交換數(shù)組S狀態(tài)，myflow為產(chǎn)生密鑰流狀態(tài)。

圖8 RC4算法狀態(tài)轉(zhuǎn)移圖

當明文數(shù)據(jù)有效時，程序RC4算法加密模塊控制信號有效，程序采用異步復位信號控制，當復位信號為無效信號(即低電平)時，在FPGA_CLK時鐘上升沿的控制下，進入idle狀態(tài)，定義兩個位寬為8位，深度為256的一維數(shù)組S和T，在該狀態(tài)下進行對一維數(shù)組S和T的初始化。對一維數(shù)組S按照順序進行初始化賦值，對一維數(shù)組T按照給定的密鑰K來進行初始化賦值，此處需要256個時鐘周期。當下一個FPGA_CLK時鐘上升沿到來時，state進入arrange狀態(tài)，進行對一維數(shù)組S進行重排序，如圖4所示。注意進入該狀態(tài)時，要對寄存器j進行清零操作。state信號進入同步有限狀態(tài)機(FSM)state1，首先進入remainder狀態(tài)，對寄存器j進行取余操作；然后隨著FPGA_CLK上升沿的到來，進入swap_1狀態(tài)，對一維數(shù)組S進行“任意”的交換處理操作，保證每一個一維數(shù)組S都進行交換處理操作，在該狀態(tài)下需要256次循

環(huán)，共消耗(512)個時鐘周期。當下一個FPGA_CLK時鐘信號的上升沿到來后，state進入produce狀態(tài)，生成密鑰流，如圖8所示。進入該狀態(tài)時，分別對寄存器i，j分別進行清零操作。state信號進入同步有限狀態(tài)機(FSM)state2，首先進入remainder_i狀態(tài)，對寄存器i進行取余操作；當FPGA_CLK時鐘上升沿到來時，進入remainder_j狀態(tài)，對寄存器j進行取余操作；在swap_2狀態(tài)下，“任意”交換一維數(shù)組S；在remainder_t狀態(tài)下，對寄存器t進行取余操作；在myflow狀態(tài)下，生成密鑰流k。至此，一幀明文數(shù)據(jù)對應(yīng)的密鑰流k生成完成，當FPGA_CLK時鐘下一個上升沿到來時，state進入下一次循環(huán)中。在produce狀態(tài)下，循環(huán)次數(shù)與一幀明文數(shù)據(jù)中有效數(shù)據(jù)信息的字節(jié)數(shù)相關(guān)，在本設(shè)計中，有效數(shù)據(jù)信息假定為3字節(jié)，因此在produce狀態(tài)下，共循環(huán)3次，消耗15個時鐘周期。在本設(shè)計中，生成對應(yīng)的密鑰流k共消耗783個FPGA_CLK時鐘周期。

4 實驗方法步驟、驗證及結(jié)果分析

根據(jù)上述RC4算法的設(shè)計方案，本系統(tǒng)采用Xilinx公司的ISE 14.7軟件對其進行編譯綜合，并在Modelsim SE 10.1a軟件中進行時序仿真。RC4算法時序仿真圖如圖9所示，仿真時假定輸入明文有效數(shù)據(jù)信息sv_data_i為24'h33aa55，當異步復位信號sl_rst_i有效(高電平)時，輸出密文數(shù)據(jù)sv_data_o為24'h000000，當done_sig信號為高電平時，產(chǎn)生RC4算法加密模塊結(jié)束提示信號，當下一個FPGA_CLK時鐘上升沿到來時，生成的密鑰流k為24'h2fb7f6，進行異或操作后輸出密文數(shù)據(jù)24'h1c1da3，并存儲在寄存器sv_data_o中。

圖9 RC4算法加密時序仿真圖

通過Xilinx公司的chipscope軟件，上板測試程序的可執(zhí)行性，相關(guān)的信號波形如圖10所示。

圖10 測試波形圖

從上述測試結(jié)果可以看出，RC4算法加密模塊可以滿足本系統(tǒng)的需求，且其工作狀態(tài)正常，相比軟件加密方式，時鐘消耗更低；相比普通RC4加密算法消耗時鐘降低。根據(jù)相關(guān)文獻[1]中RC4算法消耗的時鐘約在 (明文數(shù)據(jù)字節(jié)數(shù))時鐘數(shù)，本系統(tǒng)中RC4消耗(明文數(shù)據(jù)字節(jié)數(shù))個時鐘數(shù)，相比之前的算法設(shè)計減少256個時鐘，且消耗硬件資源占比更低。在ISE 14.7中完成該模塊的綜合并下載到FPGA開發(fā)板上進行驗證。結(jié)果表明，本設(shè)計滿足系統(tǒng)設(shè)計需求。

5 結(jié)語

本文用Verilog HDL語言以有限狀態(tài)機(FSM)的形式設(shè)計了一種基于FPGA的RC4加密傳輸數(shù)據(jù)幀的系統(tǒng)，比通常設(shè)計中時鐘的需求更少，并在仿真軟件Modelsim SE 10.1a中進行了仿真測試，得到的仿真波形滿足設(shè)計需求。并且通過ISE 14.7中進行綜合并下載到FPGA開發(fā)板中實現(xiàn)了功能驗證，證實了系統(tǒng)運行的可靠性。本系統(tǒng)可應(yīng)用于通信數(shù)據(jù)傳輸中，具有一定的實際應(yīng)用價值。

[1] 楊 梅,張耀文,等.RC4流密碼原理與硬件實現(xiàn)[J].信息通信,2009(6):40-43.

[2] 候整風，孟毛廣,等.RC4流密碼算法的分析與改進[J].計算機工程與應(yīng)用,2015(24):50-53.

[3] 黃道林,楊 軍,等.RC4加密算法的FPGA設(shè)計與實現(xiàn)[J].云南大學學報,2009(51):80-83.

[4] 張 開,陸洪毅,等.RC4加解密算法的硬件實現(xiàn)[M].中國會議,2010(10).

[5] 宮大力,黃玉劃,等.RC4算法研究與改進[M].中國會議,2011.

[6] 連至助.序列密碼的設(shè)計與分析研究[D].西安:西安電子科技大學,2012,10.

[7] 劉志巍.密碼算法的隨機性測試研究[D].西安:西安電子科技大學,2011.08.

[8] 胡 亮，遲 令,等.RC4算法的密碼分析與改進[J].吉林大學學報,2012,50(3):511-516.

[9] 王 誠,吳繼華,等.Altera FPGA/CPLD 設(shè)計(基礎(chǔ)篇)[M].北京:人民郵電出版社,2005.

[10] 高為民,朱凌志,等.混沌加密算法在J2ME平臺中的應(yīng)用研究[J].計算機仿真,2013(03).

[11]張洪福，楊小梅,等.基于AD9516的寬帶高動態(tài)數(shù)字中頻系統(tǒng)采樣時鐘設(shè)計與應(yīng)用[J].電子器件，2009,32(6).

[12]呂 波，張 涌,等.基于FPGA的四口RAM設(shè)計與實現(xiàn)[J].儀表技術(shù)與傳感器，2017(1):34-37.