基于FPGA的RC4加密算法设计及实现

苗三立，左金印，宋宇飞

(1.华北计算机系统工程研究所，北京 100083； 2.北京大学，北京 100083)

0 引言

随着计算机网络和通信技术的发展，信息作为一种重要的资源已经成为促进社会进步和经济増长的重要力量。但是，信息的存储、传递、处理等过程通常需要通过公开的计算机网络进行操作，容易遭受到窃听、篡改、伪造等多种攻击方式的威胁，因此信息安全是计算机网络领域中的一个重要的课题方向[1]。众多加密算法也应运而生，典型的有DES，RC4，RSA，AES，IDEA等，其中加密算法RC4以其实现容易、加密速度快、安全性较高，得到广泛的认可与应用。该算法的速度可以达到DES加密算法的10倍左右，且具有较高级别的非线性[2]。随着计算机网络的普及，传统的软件加密已经逐渐不能满足日常工作的需求，传统软件加密的局限性也逐渐暴露出来，在众多计算机信息安全系统中，各种高速数据密码机、密码卡、智能卡等硬件加密手段被应用到各种系统设备中，用来提高密码运算速度和系统的安全性、可靠性。当前，以密码设备为核心的硬件加密系统已成为构筑信息安全平台的重要屏障。本文给出了一种基于FPGA的RC4加密算法实现方案，相比软件实现，该方案加密速度更快，安全性更高，可以应用于多种不同的信息传输通信系统[3]。

1 RC4算法介绍

RC4是一种流密码算法，是现代通信领域通用的基于非线性变换的算法，该算法被广泛用于SSL/TLS协议、WEP协议和WPA协议，Lotus Notes、Windows、Oracle Secure SQL、Apple(AOCE)等多种通讯协议，现如今RC4算法也被用作蜂窝数字数据包规范[4]。RC4加密算法是由Ron Rivest，一名美国的密码学家于1987年设计完成实现，起初RC4算法被用于数据库(MySQL)安全以及网络安全等领域上，一直到1994年该算法被发布到了互联网上，开源公布给大家[5]。对RC4算法的改进分别是Paul 和Prenecl于2005年提出的RCA算法和Bartosz于同年提出的VMPC算法[6]。

该算法是一种流密码加密算法，是基于非线性变换的算法，主要包括两个方面的内容：

1)密钥编制算法(Key Schedule Algorithm)：用变长的密钥进行随机排序产生密钥流的初始状态；

2)伪随机序列生成算法PRGA(pseudo random generation algorithm)：参照初始状态生成相应的密钥流序列，然后与明文相异或生成相应的密文。

RC4加密算法加密原理如下：第一步，按照既定的算法初始化两个向量寄存器S和T；第二步，对寄存器S进行重排列(乱序排列)；第三步，按照既定的算法产生相应的密钥流k，然后存储并参与之后的明文加密操作[7]。加密流程如图1所示。

图1 加密流程

2 硬件设计

本文采用Verilog HDL语言以同步有限状态机(FSM)的设计方法，实现了基于FPGA的RC4加密处理流程。在计算机信息安全系统中，硬件加密手段被应用到设备中来提高密码运算速度和系统的安全性。RC4加密算法的FPGA实现方案，相比软件实现方案，硬件加密方案速度更快，安全性更高[8]。

系统设计由3部分组成，分别是时序逻辑控制模块、运算控制模块及存储模块三部分组成，其中存储模块包括密钥流存储模块和内部寄存器存储模块。明文数据由外部输入，暂存于明文寄存器，与存储模块存储的密钥流共同参与运算模块的处理。运算模块产生的密文暂存于密文寄存器中，供后续模块的使用。其中，系统内使用的时钟由时序处理模块产生，通过FPGA配置AD9516芯片输出低抖动、稳定的时钟[9]。首先将密钥信息K存储在密钥存储模块(RAM)中，然后根据地址信息从密钥存储模块(RAM)中提取密钥信息K，本文中规定明文数据为3字节(24 bit)，经过RC4加密处理模块产生相应的密钥流k信息，完成密钥流的生成，用以生成相应的密文信息[10]。逻辑框图如图2所示。

图2 逻辑框图

1)时序逻辑控制模块：时序逻辑控制模块采用AD9516-3芯片，AD9516-3是ADI公司发布的AD9516系列时钟产品，可以提供高质量、低抖动的时钟信号，适用于无线和有线的基础设施、WIMAX基地、光网站、自助测试设备、医学图像处理等仪器仪表装置。AD9516系列集成了1个整数N分频的频率合成器、1个轧空振荡器(VCO)、2个参考输入端、可编程驱动器、可调延迟线和14个时钟驱动器，包括LVPECL、LVDS和CMOS输出。AD9516芯片由系统FPGA芯片通过串行控制端口来进行相关的参数配置及输入[11]。模块结构图如图3所示。

图3 时序逻辑控制模块结构图

2)运算控制模块：采用有限状态机的方式对各个逻辑状态进行控制和操作，时钟采用AD9516芯片输出的低抖动、高质量的时钟信号。详细的状态流程才加软件设计部分。

3)存储模块：存储模块采用Block RAM存储，相较与FIFO存储而言，优势在于可以通过访问地址选取不同的数据信息。为解决并行系统高效进行大量数据传输和交换的实时性要求，本文采用了一种基于FPGA的四口RAM，四口RAM由1个双口RAM模块、2个控制模块和4个缓存模块组成[12]。总体设计架构如图4所示。

图4 四口RAM存储模块中体设计架构图

3 软件设计

在本设计系统中，流程设计采用状态机的规范进行编写，总体流程为：消息信息进入设计系统，首先进行CRC编码，经过编码后的消息信息进行RC4编码加密处理，然后进行消息信息的传递。

3.1 CRC校验设计

循环冗余校验码(cyclic redundancy check， CRC)又称CRC校验，是一种能力非常强的检错、纠错码，相比于更加稳定、精确的RS校验算法，具有实现编码和检码的电路比较简单、编码易于实现等优势，通常用于串行传输的辅助存储器与主机的信息数据通信和计算机网络中。CRC检验是一种在数据通信系统和其它串行传输系统中广泛使用的错误检测手段。通用的CRC标准有CRC-8、CRC-16、CRC-32、CRC-CCIT，其中在设备信息传输通信系统中应用最广泛的是CRC-16标准。传统手段是采用串行的编码方式进行CRC编码，速度比较慢，处理并行数据电路较为复杂；本系统将采用一种新的CRC-16并行编码方式，采用并行处理的方式进行对并行信息数据进行CRC编码。相比于串行CRC编码方式，消耗时钟减少，硬件电路简化等优势。

进行CRC编码要采用模2运算法则，具体描述一下模2运算法则。首先模2运算是一种二进制运算法则，同时也包括相应的模2加、模2减、模2乘、模2除4种运算。模2运算用“+”表示加法运算，用“-”、“×”或“.”、“/”分别表示减法、乘法和除法运算。因此，模2运算是类似于四则运算的一种二进制算法。但是模2运算不同于四则运算的是，模2减法为不带借位的二进制减法，模2加法是不带进位的二进制加法。同理，模2乘法在中间的累加运算时也是不带进位的二进制加法；模2除法在中间结果的减法时也是不带借位的二进制减法。由此看来，模2运算的加减法相当于两个二进制数的按位异或运算操作。同理，模2除法运算的，如果余数的首位为1，那么商就为1，其他操作按照模2减法运算；如果余数的首位为0，那么商就为0。

CRC码校验的基本思路是：利用线性反馈移位寄存器(linear feedback shift register, LFSR)和线性编码的原理。LFSR是指，首先给定前一状态的输出，将该输出的线性函数再用作输入的移位寄存器。其中文章中采用的异或运算是最常见的单比特线性函数：对寄存器中的某些位进行异或运算后作为后面状态的输入端，然后再对整个寄存器进行移位操作。具体运算如下：再输出端按照要发送的k位二进制数据序列，采用模2运算的法则产生一个r位的监督码，即校验用的CRC码，然后将其添加到k位二进制信息码的低位处，组成一个k+r位的新的二进制数据序列，此产生二进制数据序列的过程便是CRC编码。在检验时，使用CRC编码与生成多项式G(x)进行模2除法运算，运算结果如果余数为0，那么说明在传输过程中k位二进制数据序列没有发生错误或丢失；如果运算结果不为0，说明在传输过程中k位二进制数据序列发生错误或产生丢失。因此，采用余数是否为0来判断数据在传输过程中是否发生变化。

CRC码的检错纠错原理：在接收端收到数据后若如果有一位数据出现错误，结果则为余数不为0，并且不同位出错，其余数不但不为0并且也不同。假设循环码有一位出错，用G(x)作模2除将得到一个不为0的余数。如果对余数补0继续除下去，将出现一个有趣的现象：余数会按照001,010,100,011,111,101循环下去，分别对应出错位第1,2,3,4,5,6,7位。例如第一位出错，余数将为001，余数后面补0后再除(补0后如果数据的最高位为1，则用除数做模2减法然后取余数；如果最高位为0，则其最低3位就是余数)，计算后得到第二次余数为010。之后继续补0作模2除，依次得到余数为100,011,111,101,循环下去。

本系统采用的是并行处理的CRC校验，相比串行CRC校验消耗的时钟减少，电路结构简化。输入数据为十六进制数据A7，串行处理结果图5所示，经过8个时钟周期后结果为十六进制数据83D1。并行处理结果如图6所示，系统经过1个时钟周期后输出结果为十六进制数据83D1。

图5 串行CRC编码时序仿真图

图6 并行CRC编码时序仿真图

3.2 算法设计流程

在本系统设计中，FPGA芯片采用Xilinx厂家生产的Spartan6 XC6SLX45T型号，RC4算法程序采用Verilog编写。RC4算法程序流程图如图7所示。

图7 RC4算法程序流程图

RC4算法具体流程为，首先从RAM中提取密钥k，然后初始化数组S、T，系统内设定数组容量为256位；然后对数组S进行重排序，进而产生32位的密钥，存入RAM模块，与明文进行异或操作产生密文。

在设计中采用同步有限状态机(FSM)实现，其状态转移图如图4所示。idle为初始化数组S和T状态，arrange为重新排列数组S状态，produce为产生密钥流状态；remainder为对j取余状态，swap_1为交换数组S状态；remainder_i为对i取余状态，remainder_j为对j取余状态，remainder_t为对t取余状态，swap_2为交换数组S状态，myflow为产生密钥流状态。

图8 RC4算法状态转移图

当明文数据有效时，程序RC4算法加密模块控制信号有效，程序采用异步复位信号控制，当复位信号为无效信号(即低电平)时，在FPGA_CLK时钟上升沿的控制下，进入idle状态，定义两个位宽为8位，深度为256的一维数组S和T，在该状态下进行对一维数组S和T的初始化。对一维数组S按照顺序进行初始化赋值，对一维数组T按照给定的密钥K来进行初始化赋值，此处需要256个时钟周期。当下一个FPGA_CLK时钟上升沿到来时，state进入arrange状态，进行对一维数组S进行重排序，如图4所示。注意进入该状态时，要对寄存器j进行清零操作。state信号进入同步有限状态机(FSM)state1，首先进入remainder状态，对寄存器j进行取余操作；然后随着FPGA_CLK上升沿的到来，进入swap_1状态，对一维数组S进行“任意”的交换处理操作，保证每一个一维数组S都进行交换处理操作，在该状态下需要256次循

环，共消耗(512)个时钟周期。当下一个FPGA_CLK时钟信号的上升沿到来后，state进入produce状态，生成密钥流，如图8所示。进入该状态时，分别对寄存器i，j分别进行清零操作。state信号进入同步有限状态机(FSM)state2，首先进入remainder_i状态，对寄存器i进行取余操作；当FPGA_CLK时钟上升沿到来时，进入remainder_j状态，对寄存器j进行取余操作；在swap_2状态下，“任意”交换一维数组S；在remainder_t状态下，对寄存器t进行取余操作；在myflow状态下，生成密钥流k。至此，一帧明文数据对应的密钥流k生成完成，当FPGA_CLK时钟下一个上升沿到来时，state进入下一次循环中。在produce状态下，循环次数与一帧明文数据中有效数据信息的字节数相关，在本设计中，有效数据信息假定为3字节，因此在produce状态下，共循环3次，消耗15个时钟周期。在本设计中，生成对应的密钥流k共消耗783个FPGA_CLK时钟周期。

4 实验方法步骤、验证及结果分析

根据上述RC4算法的设计方案，本系统采用Xilinx公司的ISE 14.7软件对其进行编译综合，并在Modelsim SE 10.1a软件中进行时序仿真。RC4算法时序仿真图如图9所示，仿真时假定输入明文有效数据信息sv_data_i为24'h33aa55，当异步复位信号sl_rst_i有效(高电平)时，输出密文数据sv_data_o为24'h000000，当done_sig信号为高电平时，产生RC4算法加密模块结束提示信号，当下一个FPGA_CLK时钟上升沿到来时，生成的密钥流k为24'h2fb7f6，进行异或操作后输出密文数据24'h1c1da3，并存储在寄存器sv_data_o中。

图9 RC4算法加密时序仿真图

通过Xilinx公司的chipscope软件，上板测试程序的可执行性，相关的信号波形如图10所示。

图10 测试波形图

从上述测试结果可以看出，RC4算法加密模块可以满足本系统的需求，且其工作状态正常，相比软件加密方式，时钟消耗更低；相比普通RC4加密算法消耗时钟降低。根据相关文献[1]中RC4算法消耗的时钟约在 (明文数据字节数)时钟数，本系统中RC4消耗(明文数据字节数)个时钟数，相比之前的算法设计减少256个时钟，且消耗硬件资源占比更低。在ISE 14.7中完成该模块的综合并下载到FPGA开发板上进行验证。结果表明，本设计满足系统设计需求。

5 结语

本文用Verilog HDL语言以有限状态机(FSM)的形式设计了一种基于FPGA的RC4加密传输数据帧的系统，比通常设计中时钟的需求更少，并在仿真软件Modelsim SE 10.1a中进行了仿真测试，得到的仿真波形满足设计需求。并且通过ISE 14.7中进行综合并下载到FPGA开发板中实现了功能验证，证实了系统运行的可靠性。本系统可应用于通信数据传输中，具有一定的实际应用价值。

[1] 杨 梅,张耀文,等.RC4流密码原理与硬件实现[J].信息通信,2009(6):40-43.

[2] 候整风，孟毛广,等.RC4流密码算法的分析与改进[J].计算机工程与应用,2015(24):50-53.

[3] 黄道林,杨 军,等.RC4加密算法的FPGA设计与实现[J].云南大学学报,2009(51):80-83.

[4] 张 开,陆洪毅,等.RC4加解密算法的硬件实现[M].中国会议,2010(10).

[5] 宫大力,黄玉划,等.RC4算法研究与改进[M].中国会议,2011.

[6] 连至助.序列密码的设计与分析研究[D].西安:西安电子科技大学,2012,10.

[7] 刘志巍.密码算法的随机性测试研究[D].西安:西安电子科技大学,2011.08.

[8] 胡 亮，迟 令,等.RC4算法的密码分析与改进[J].吉林大学学报,2012,50(3):511-516.

[9] 王 诚,吴继华,等.Altera FPGA/CPLD 设计(基础篇)[M].北京:人民邮电出版社,2005.

[10] 高为民,朱凌志,等.混沌加密算法在J2ME平台中的应用研究[J].计算机仿真,2013(03).

[11]张洪福，杨小梅,等.基于AD9516的宽带高动态数字中频系统采样时钟设计与应用[J].电子器件，2009,32(6).

[12]吕 波，张 涌,等.基于FPGA的四口RAM设计与实现[J].仪表技术与传感器，2017(1):34-37.