基于可配置处理器的AES算法设计

黄光红,洪一,2,耿锐

(1.华东电子工程研究所,合肥230031;2.中国科学技术大学)

黄光红(助理工程师)、耿锐(工程师),主要研究方向为体系结构;洪一(博士生导师),主要研究方向为数字信号处理、体系结构。

1 概 述

随着集成电路技术的快速发展,通用处理器的性能急剧提高。但通用处理器面对的是各种不同的应用需求,当它应用于特定领域时,可能很难获得极高性能,无法体现其优势。ASIC处理器能解决这个问题,但其设计周期较长、风险较大,复用性很差。

有一种新的方法——可配置处理器,能高效地解决这个难题。其两个特点是:用户的可配置性和系统的自动生成。用户的可配置性是指,可以通过参数设置、删除、增加处理器功能,用户还能根据需求增加一些特殊指令。系统的自动生成是指,能根据配置信息自动生成处理器硬件逻辑及其软件开发工具。可配置处理器方案很好地满足了特定应用需求。本文采用可配置处理器设计并实现特定应用——AES加密解密算法。

2 可配置处理器

本文采用Tensilica公司的可配置处理器Xtensa。该处理器基于32位RISC内核,具有可配置性、可扩展性和可集成性。用户可根据各种不同应用,配置处理器各参数以达到最佳性能、最低成本。可配置项目有:寄存器堆宽度和深度、各数据通路宽度、执行单元数目和类型、外围设备的数目和类型、读取存储单元和存储器端口的数目和大小、指令长度、指令操作数数目等[1]。

可配置的Xtensa处理器具有一个基本核,支持80条基本指令,这些指令支持C语言和操作系统。Xtensa处理器采用5级或7级流水线,指令集宽度为24位或16位压缩编码方式。对于特定应用,通常需要经过分析增加新的指令和寄存器来提高性能。TIE(Tensilica Instruction Extension)语言,为设计者提供了一种通过指令集扩展描述来扩展Xtensa处理器指令集的方法。指令集扩展描述是指,通过TIE编译器的编译生成处理器扩展部分的Verilog或VHDL描述,并且更新该处理器的软件工具链(编译器、汇编器、仿真器和调试器)来支持新的指令集。处理器和软件工具链的自动化生成为设计者提供了极大的方便[2]。可配置处理器的设计流程如图1所示。

图1 可配置处理器设计流程

3 AES算法与优化设计

3.1 算法及热点分析

AES(Advanced Encryption Standard,高级加密标准)是美国NIST颁布的数据加密标准,采用新的Rijndael分组加密算法,具有更高的安全性和易实现性[3]。AES算法的分组长度Nb和密钥长度Nk可分别取值为4字、6字或8字(字为32位),不同的参数对应算法中不同轮循环次数Nr。该算法将分组看成4×Nb的二维字节数组,或Nb字的一维数组,并称分组为State。加解密就是对State进行多次变换以获得密文或明文的过程。AES算法主要由密钥扩展(KeyExpansion)和轮循环组成,每轮由SubBytes(字节替换)、ShiftRows(行位移)、MixColumns(列混合变换)和AddRoundKey(加轮密钥)组成。解密算法是加密算法的逆过程,每轮由InvSubBytes(逆字节替换)、InvShiftRows(逆行位移)、InvMixColumns(逆列混合变换)和 AddRoundKey组成[4]。加密、解密流程如图 2所示。

图2 AES算法加密和解密流程

用C/C++语言实现AES算法。分析其程序执行热点,即分析程序各个部分占用处理器执行时间的百分比。经过分析,在加密算法中 MixColumns、ShiftRows、Sub-Bytes和KeyExpansion都是程序的执行热点,可以通过在可扩展处理器中增加相应的专用指令和硬件查找表方法提高程序执行速度。解密算法与其类似。

3.2 指令设计与优化

发现程序的执行热点后,就可以利用可扩展处理器提供的方法优化热点的执行效率。对每个热点进行分析,设计优化的实施方案,并用TIE语言实现。

KeyExpansion是加密解密前的准备工作,根据原始密钥生成密钥序列供轮循环使用。当加密解密的数据量很小时,KeyExpansion占用相当的处理器时间,需进行优化获得更高的性能。KeyExpansion中有对密钥某行4字节替换操作,其中的替换字节表在轮循环中使用频率更高。对于经常使用的常数表,TIE语言提供优化方法,即硬件常数表table。本文设计了2个table——SBox和InvSBox,分别用于加密解密,每个表大小为 16×16字节。设计专用指令SUBWORD,可一次替换密钥行的4字节。KeyExpansion有一个操作序列:4字节循环右移、字节替换、与常数表异或。采用融合技术将序列操作融合为一条复杂的专用指令ROTSUBXORWORD。指令流程如图3所示。

图3 ROTSUBXORWORD指令流程

加密轮的SubBytes对State进行字节替换,使用字节替换表SBox。为了节约硬件资源,可复用专用指令SUBWORD。

ShiftRows操作是将State中的4行字节数分别循环左移0、1、2、3字节位。本文将 State看作字的一维数组,移位操作涉及一维数组中的所有字。因为ShiftRows在每轮中都被调用,优化加速比很高。ShiftRows操作简单,但被操作的数很多,一般指令的输入参数少。TIE语言提供状态寄存器,可用于任何指令操作。它不出现在指令的汇编代码的参数表中,而是被指令隐式地使用。设置读写属性后处理器生成器自动生成指令,负责状态寄存器和通用寄存器之间的数据传输。根据Nb大小,设计8个32位宽的状态寄存器保存分组State。设计指令SHIFTROWS实现行移,输入参数为Nb。在指令SHIFTROWS操作前将State写入各状态寄存器,操作后再读出。

在优化前,MixColumns是占用处理器时间最多的操作。列混合变换是将State中的每列乘以矩阵A:

这里的乘法和加法是GF(28)域上的运算[5]。耗时的矩阵乘法应通过设计专用指令进行优化。为实现矩阵乘法需实现字节乘2、乘3运算,可借助TIE语言中的function关键字实现。function定义一个功能模块,TIE文件中每次调用都重新复制硬件逻辑。本文定义2个function——GFMultBy02和GFMultBy03,分别表示乘 2和乘3操作。定义列混合变换专用指令MIXCOLUMN,它调用GFMultBy02和GFMultBy03实现列变换功能,流程如图4所示。

图4 MIXCOLUMN指令流程

解密算法中的InvSubBytes采用替换表InvSBox进行字节替换,设计专用指令 INVSUBWORD实现。Inv-ShiftRows是将State中的4行字节数分别循环右移0、1、2、3字节。同理,为其设计专用指令INVSHIFTROWS。

解密中的列混合变换InvMixColumns是加密的逆过程,它是将State中的每列乘矩阵B。同理,用function实现GFMultBy0E、GFMultBy0B、GFMultBy0D 和 GFMult-By09,定义逆列混合变换专用指令INVMIXCOLUMN。

4 实验与性能分析

本文用C/C++语言实现了未优化的AES算法。在优化设计后,用TIE语言实现了专用指令和相关模块,再用C/C++语言实现优化后的算法。实验程序相关参数设置为:Nk为4,Nb为6,Nr为12。加密解密程序分别循环调用分组加密解密100次,即总共分别加解密2 400字节。相关的实验结果如表1所列。

表1 实验结果

从实验结果可以看出,使用TIE语言设计多条专用指令后,算法的优化效果相当明显。函数ShiftRows、MixColumns、InvShiftRows和 InvMixColumns优化后获得很高的加速比,因为优化前操作的通用指令执行序列占大量的处理器时钟周期,而采用专用指令后时钟周期大大减少。尤其是InvMixColumns,由于含有乘 9等操作(通过乘2和加操作实现),因此优化后的加速比非常高。

结 语

本文介绍了可配置处理器的优点和利用可配置处理器实现特定应用的流程;分析了AES加解密算法的特定应用,研究其优化方案并用 TIE语言实现了多条专用指令。实验证明,采用可配置处理器方法可大大提高 AES算法的执行性能。在AES算法中,含有大量的可并行执行的循环。可配置处理器可通过SIMD技术和VLIW技术实现高度的并行计算,采用这些技术将进一步提高执行性能,这是下一步的研究工作。

[1]陈双燕,张铁军,王东辉,等.基于一种可配置可扩展处理器的M ELP语音算法的改进与实现[J].微电子学与计算机,2006,23(6):42-43.

[2]Chris Rowen.复杂SOC设计[M].吴武臣,等译.北京:机械工业出版社,2006.

[3]黄智颖,冯新喜,张焕国.高级加密标准AES及其实现技巧[J].计算机工程与应用,2002(9):112-115.

[4]Daemem J,Rijmem V.AES Proposal:Rijndael[OL].[2009-11].http://www.Daemen.j@banksys.

[5]张德学,郭立,傅忠谦.一种基于 FPGA的 AES加解密算法设计与实现[J].中国科技大学学报,2007,37(12):1461-1464.