基于FPGA的AES硬件实现及优化

于松林，王文工，陈 博，陈 祥，张 霞

（国家数字交换系统工程技术研究中心 河南 郑州450002）

基于FPGA的AES硬件实现及优化

于松林，王文工，陈 博，陈 祥，张 霞

（国家数字交换系统工程技术研究中心 河南 郑州450002）

AES（Advanced Encryption Standard）是一种非常流行的对称加密算法，字节替换是AES算法中十分重要的部分。针对采用复合域方法来实现字节替换吞吐率小的问题，本文利用先计算的方法进行了5级轮内流水线设计，去除关键路径上的一些计算来降低关键路径延迟提高吞吐率。在FPGA器件Virtex-6 XC6VLX240T上，通过Xilinx ISE 14.7进行仿真实验，结果表明在面积增加相对不大的情况下，提高了吞吐率以及吞吐率/面积比。

AES；字节替换；复合域；先计算方法

二十一世纪是一个互联网快速发展的时代，每天数以万计的人都在使用互联网进行电子邮件的收发、信息的查询、商业资料传输等。互联网的开放性给人们带来便利的同时，也给人们带来了一些信息泄露和篡改的威胁，用户对信息的安全存储，安全传输、安全处理的需求越来越迫切。加密算法是加密技术进行安全防护行之有效的一种手段，DES加密算法保护了人们的信息安全将近20年，由于其弱密钥性，在1999年的时候被攻破，美国开始向全世界征集AES，这时候Rijndael在15个候选算法中脱颖而出[1]，成为新的AES。

自AES提出以后，被广泛的应用于数据库中的数据加密、视频加密、IC卡和存储数据的硬盘加密等方面。因为AES的易推广型，所以软件和硬件都可以实现，在软件方面，容易升级，但吞吐量低，安全问题也是一种隐患；与软件相比，硬件实现安全性好，不易被攻破，吞吐量高，是软件的1000倍左右；一般来说，硬件实现有FPGA（Field Programmable Gate Array）和 ASIC（Application Specific Integrated Circuit）两种方式，FPGA具有可编程性，可配置性，ASCI缺乏灵活性，开发周期长，因此本文选用FPGA作为实现AES算法的硬件平台。

AES[2]算法是一个对称加密算法，主要有加密，解密，以及密钥扩展3个部分组成。AES限定明文分组长度只能是128比特，密钥长度可以为128、192或者256比特中的任意一种，与轮密钥相关的迭代轮数Nr分别为10、12、14轮，文中设计了一种192比特密钥长度的结构。在第1轮到第Nr-1轮变换中，主要包含字节替换/逆字节替换、行变换/逆行变换、列混合/逆列混合、轮密钥加，在第N轮的轮变换中，去除了列混合/逆列混合。

字节替换/逆字节替换是AES算法中十分重要的一部分，一般可以用下面几种方法实现，第一种可以用复合域组合逻辑的方法实现[3-4]，这种方法主要使用流水线的方法来降低关键路径和增加吞吐率，劣势是硬件复杂度高；第二种可以用不同的存储器来实现[5-6]，比如使用ROM（Read Only Memory），BRAM （Block Random Access Memory），以及LUT（Look Up Table）来存储S盒，这种方法可以降低面积，但是由于存储器的延迟不可避免的降低了吞吐率；第三种方法使用SOP（Sum of Products），POS（Product of Sums），BDD（Binary Decision Diagram），PPM（Positive Polarity Reed-Muller）来增加吞吐率[7-8]，但是面积增加很大。考虑到吞吐率以及面积，本文决定采用第一种方法来实现字节替换/逆字节替换。

1 AES算法原理分析

字节替换是一个砖匠的置换过程，是AES算法中唯一的一个非线性变换[8-9]，在对抗已知攻击中扮演重要的角色。文中采用复合域组合逻辑电路进行字节替换；公式（1）是状态矩阵在有限域GF（28）乘法逆变换和仿射变换，公式（2）是仿射变换的方式。需要注意的是，在乘法逆中，”00”的映射是还是”00”。

行变换是对状态矩阵的行进行循环的移位操作，对于一个4*4的状态矩阵，第0/1/2/3行向左移动0/1/2/3个字节；对于逆行变换，第0/1/2/3行向右移动0/1/2/3个字节。

列混合变换是对状态矩阵中列的线性变换[10]，状态矩阵中的每一列都被看做有限域GF（28）上的一个四次多项式，每一列都乘上一个不可约多项式a（x）=（03）x3+（01）x2+（01）x+（02），如公式（3）所示：

化简公式（3）可得公式（4）

轮密钥加就是列混合变化后的矩阵与密钥矩阵的异或，得到新的状态矩阵，如公式（5）:

由公式（4）和公式（5）可得公式（6）：

密钥扩展是加解密重要的组成部分[11]，通过对初始的192位密钥进行扩展，产生每轮轮变换中需要的密钥。具体的方法是先输入初始密钥，分别为w [0]、w[1]、w[2]、w[3]，然后根据初始密钥得到每轮轮变化所需要的密钥w[i]，其中w[i]和w[i-4]、w[i-1]（i＞=4）有关。

当i为4的倍数时，密钥扩展只需要进行简单的异或，如公式（7）所示：

当i不为4的倍数时，则进行如下处理：

1）RotWord（）:对w[i-1]进行移位处理，循环左移一个字节

2）SubWord（）:进行字节替换

3）进行字节替换后的数值与轮常量Rcon[i/4]相异或

4）将步骤3）的结果与w[i-4]进行异或

2 AES算法改进

文献[12]采用复合域组合逻辑实现一个紧凑且速度快的字节替换，但是各级流水线关键路径划分不够优化，仍具有降低关键路径的空间。由于关键路径决定硬件的最高工作频率，所以轮内流水线需要进行合理的划分，平衡各级流水线的路径长度。传统的复合域字节替换有五个子状态，如图1所示。本文所要达到的目标是合并X2和λ来减少硬件资源和关键路径延迟，应用先计算方法[12]去除关键路径中的第三、四个子状态来提高吞吐量，改进后的字节替换如图2所示。

图1 复合域上传统的字节替换结构

图2 改进后的字节替换

有限域GF（28）中的任意元素a都可以等价到有限域GF（（（22）2）2）中的元素，采用X2+X+λ为不可约多项式，元素a的乘法逆就可以转换为在有限域GF（24）中求解，具体计算如下所示：

设 a=nx+m，a-1=ex+f，那么通过计算得到 e= n（n2λ+m（n+m））-1，f=（n+m）（n2λ+m（n+m））-1则：

其中λ=[1100]2，是个已知的值，那么就可以合并X2和λ来减少计算降低关键路径延迟。具体分析如下：

在 GF（24）[13]中 X2，假设 m=n2，=[m3，m2，m1，m0]，n=[n3，n2，n1，n0]，进行多项式运算后结果如下：

由上可知，在GF（24）中X2单元中用到4个XOR，最长路径延迟为2个XOR。

在GF（24）中xλ，假设m=nλ，m=[m3，m2，m1，m0]，n=[n3，n2，n1，n0]，进行多项式运算后结果如下：

由上可知，在GF（24）中X2单元中用到3个XOR，最长路径延迟为2个XOR。

在GF（24）中X2xλ，假设m=λ[X（n2）]，m=[m3，m2，m1， m0]，n=[n3，n2，n1，n0]，进行多项式运算后结果如下：

由上可知，在GF（24）中X2单元中用到4个XOR，最长路径延迟为2个XOR。综上所述，对X2和xλ进行合并后运算，硬件资源由原来的7个XOR减少为现在的4个XOR，关键路径延迟由原来的4个XOR变为现在的2个XOR。

图1中的两个乘法器M1、M2的输入数据分别为来自第二个子状态的A1、A2以及来自第3个子状态的B1、B2。为了不让已经计算好的数据A1、A2等待，文中应用先计算技术消除关键路径中的乘法器M1、M2，如图2所示。因为逆变换X-1的结果是有限域GF（24）中的一个元素，数值为0-F（16进制），所以只要逆变换的结果一出来，就能在选择器中做出选择，马上输出结果，减少了计算时间，如图3所示。

图3 去除乘法器的字节替换

按照上面的思想，我们可以消除第3个子状态中复杂的逆变换运算，只是现在的结果为原来数值的转置，.因为在复合域GF（24）中，逆变换的值是一一对应的关系，如表1所示。

表1 有限域GF（24）上数值转置表

3 仿真实现

文中采用 Xilinx公司的 ISE14.7工具，对所设计的加解密系统进行仿真测试，并将仿真得到的结果与所得到的测试数据进行比较，图4、图5给出了该系统在加解密过程中的仿真结果。

仿真得到的结果说明本文所设计的加解密系统能够准确无误的执行AES算法。文中设计在Xilinx Virtex-5 XC5VLX110T FPGA器件上工作频率为319.29Mhz，吞吐率比文献 [14]增长24%；在Virtex-6 XC6VLX75T器件上工作频率为 324.29 MHz，吞吐率比文献[15]中增加了12%，吞吐率/面积比为11.44，；在Virtex-6 XC6VLX240T器件上工作频率为357.3 MHz，吞吐率比文献 [16]中增加了11.92，吞吐率/面积比为12.61，如表2所示。

图4 192位密钥加密

图5 192位密钥解密

表2 优化后的吞吐率，最大频率和吞吐率/面积对比

4 结束语

文中采用先计算方法对AES模块中的字节替换进行了优化，利用Xilinx ISE14.7进行仿真，实验数据表明，优化后的结构在面积增加不大的情况下，提高了吞吐率，减少了关键路径，提高了吞吐率/面积比。

[1]吴文玲.冯登国.卿斯汉.简评美国公布的15个AES候选算法[J].软件学报，1999，19（3）：1-8.

[2]郑行.AES算法的硬件优化实现及应用研究[D].厦门：厦门大学，2014.

[3]Mozaffari-Kermani M，Reyhani-Masoleh A.A low-power high-performance concurrent fault detection approach for the composite field S-Box and inverse S-Box [J].Computers， IEEE Transactions on，2011，60（9）:1327-1340.

[4]Shastry P V S，Agnihotri A，Kachhwaha D，et al. A combinational logic implementation of S-box of AES[C].Circuits and Systems（MWSCAS），2011 IEEE 54th International Midwest Symposium on. IEEE，2011:1-4.

[5]Zhang Y，Wang X.Pipelined implementation of AES encryption based on FPGA[C]//Information Theory and Information Security （ICITIS），2010 IEEE International Conference on.IEEE，2010: 170-173.

[6]Hoang T.An efficient FPGA implementation of the Advanced Encryption Standard algorithm[C]// Computing and Communication Technologies，Research，Innovation，and Vision for the Future（RIVF），2012 IEEE RIVF International Conference on.IEEE，2012:1-4.

[7]Rashidi B，Rashidi B.Implementation of an optimized and pipelined combinational logic rijndael s-box on fpga [J].International Journal of Computer Network and Information Security，2013，5（1）:41-48.

[8]Rahimunnisa K，Karthigaikumar P，Christy NA，et al.Psp:parallel sub-pipelined architecture for high throughput aes on fpga and asic[J].Open Computer Science.2013，3（4）:173-186.

[9]Rais MH，Qasim SM.Efficient hardware realization of advanced encryption standard algorithm using virtex-5 fpga[J].International Journal of Computer Science and Network Security，2009，9（9）:59-63.

[10]Singh G，Mehra R.Fpga based high speed and area efficient aes encryption for data security[J]，International Journal of Research and Innovation in Computer Engineering（IJCTA），2011，1（2）:53-56.

[11]Abolfazl Soltani，Saeed Sharifian.An ultra-high throughput and fully pipelined implementation of AES algorithm on FPGA [J].Microprocessors and Microsystems，2015，9（7）:480-493.

[12]Liu R，Parhi K K.Fast composite field S-box architectures for advanced encryption standard[C]. Proceedings ofthe 18th ACM GreatLakes symposium on VLSI.ACM，2008:65-70.

[13]Sharma V K，Kumar S，Mahapatra K K.Iterative and Fully Pipelined High Throughput Efficient Architectures of AES in FPGA and ASIC[J]，Journal of Circuits， Systems， and Computers，2016，25（5）：1-29.

[14]Banu J S，Vanitha M，Vaideeswaran J，et al. Loop parallelization and pipelining implementation of AES algorithm using OpenMP and FPGA[C]. Emerging Trends in Computing，Communication and Nanotechnology（ICE-CCN），2013 International Conference on IEEE，2013:481-485.

[15]Rahimunnisa K，Karthigaikumar P，Rasheed S，et al.FPGA implementation of aes algorithm for high throughput using folded parallel architecture[J]. Security and Communication Networks，2014，7（11）:2225-2236.

[16]Wang Y，Ha Y.Fpga-based 40.9-gbits/s masked aes with area optimization for storage area network [J].Circuits and Systems II:Express Briefs，IEEE Transactions on，2013，60（1）:36-40.

Implement and optimization of AES using hardware based on FPGA

YU Song-lin，WANG Wen-gong，CHEN Bo，CHEN Xiang，ZHANG Xia
（Nation Digital Switching System Engineering&Technological Research Center，Zhengzhou 450002，China）

AES（Advanced Encryption Standard）is a very popular symmetric encryption algorithm.Byte substitution （S-Box）is an important part in AES.However，S-Box which uses the method of the composite field to implement suffers from extremely low throughput rate.In this paper，a 5-stage pipelined structure，by applying pre-computation method，some computation on the critical data path can be eliminated so as to reduce the critical path delay.The results show that the throughput rate and the ratio of data throughout and area is increased at the expense of a fairly modest increase in area.

AES；Byte substitution（S-Box）；the composite field；pre-computation method

TN918

：A

：1674－6236（2017）06-0075-04

2016-05-24稿件编号：201605222

国家科技支撑计划项目（2014BAH30B01）；国家自然科学基金创新群体项目（61521003）

于松林（1988—），男，河南驻马店人，硕士研究生。研究方向：网络安全。