面向密码流处理器的AES算法软件流水实现方法

王寿成，徐进辉，严迎建，李功丽,2，贾永旺

(1.信息工程大学 密码工程学院，郑州 450001； 2.河南师范大学 计算机信息工程学院， 河南 新乡 453002)

面向密码流处理器的AES算法软件流水实现方法

王寿成1*，徐进辉1，严迎建1，李功丽1,2，贾永旺1

(1.信息工程大学 密码工程学院，郑州 450001； 2.河南师范大学 计算机信息工程学院， 河南 新乡 453002)

(*通信作者电子邮箱jeremy_419@163.com)

针对轮函数在分组密码实现过程中耗时过长的问题，提出了面向可重构密码流处理器(RCSP)的高级加密标准(AES)算法软件流水实现方法。该方法将轮函数操作划分为若干流水段，不同流水段对应不同的并行密码资源，通过并行执行多个轮函数的不同流水段，从而开发指令级并行性提高轮函数执行速度，进而提升分组密码的执行性能。在RCSP的单簇、双簇和四簇运算资源下分析了AES算法的流水线划分过程和软件流水映射方法，实验结果表明，该软件流水实现方法使得单分组或多分组不同数据分块的操作并行执行，不仅能够提升单分组串行执行性能，还能够通过开发分组间的并行性来提高多分组并行执行性能。

分组密码；高级加密标准算法；软件流水；指令级并行性；吞吐率

0 引言

随着网络与信息安全地位的不断提升，分组密码算法广泛应用于数据加密、数字签名/认证及密钥管理等领域。分组密码算法的高效实现直接影响网络与信息通信系统的性能，如何高效实现分组密码算法已经成为重要的研究方向。

实现分组密码的结构主要有四种：专用集成电路(Application Specific Integrated Circuit, AISC)结构[1]、专用指令处理器结构[2-3]、阵列处理器结构[4-5]和多核处理器系统[6-7]。专用ASIC密码处理器是针对一种或几种特定算法的定制芯片，具有较高的密码处理性能和最小的硬件资源，但其兼容性差,可扩展性和应用领域均受限。专用指令处理器以密码指令驱动系统运行，通过指令编程来实现密码算法，具有灵活性高、控制简单、开发便捷的特点，但目前专用指令处理器实现密码算法的吞吐率普遍较低。阵列处理器将大量密码运算单元通过总线或片上网络(Network-on-Chip, NoC)连接起来构成密码处理系统，通过配置信息将运算单元与互连网络重构为算法数据路径以完成密码算法，其密码实现性能普遍很高，但其面积和功耗较大，算法映射困难，同时资源利用率较低。多核密码处理器集成了多个密码运算核心和任务调度器，多核间通过任务调度可实现密码处理的任务级并行，能够有效提升密码运算性能，但存在着面积较大、任务调度较复杂的问题。

可重构密码流处理器(Reconfigurable Cipher Stream Processor, RCSP)[8]融合了可重构技术和流体系结构[9]，使得密码运算的性能、灵活性和资源利用率都得到巨大提升。本文将软件流水技术[10]应用于分组密码算法的轮函数执行过程中，通过映射AES-128在可重构密码流处理器RCSP的单簇、双簇和四簇运算资源的软件流水实现，分析了相应的软件流水段的划分及算法映射过程，并进行了顺序执行、串行/并行模式下吞吐率比较。

1 AES算法概述

高级加密标准(Advanced encryption standard, AES)是美国国家标准与技术研究所(National Institute of Standards and Technology, NIST)主持开发的算法公开、免费使用和世界通用的高级数据加密标准算法。AES属于迭代型分组密码算法，其分组长度为128 b，密钥长度可设置为128 b、192 b或256 b，迭代圈数取决于密钥长度，其中AES-128的迭代圈数为10圈。

AES采用的是SP(代替-线性变换)网络结构，待加密的128比特明文分组首先进行初始圈密钥加法，然后进行算法迭代，除最后一圈没有列混合变换外，每圈迭代的变换有字节代替变换、行移位变换、列混合变换和圈密钥加法。硬件实现时，AES算法可映射为S盒操作(Substitution)、字节置换操作(Permutation)、有限域(Galois Field, GF)乘法和异或操作(XOR)。以AES-128为例，其加密数据路径如图1所示，其中:S盒操作的运算粒度为8 b，有限域乘法和异或操作的运算粒度为32 b，字节置换操作的运算粒度为128 b。

图1 AES-128的加密数据路径

2 软件流水技术

软件流水技术是一种重组循环体的技术，通过调度使得不同循环体的指令能够并行执行，从而提高运算效率。软件流水技术把不同循环间的指令交织在一起执行，但每个循环的指令依然是串行执行的，从而在提高并行性的同时保证指令间的相关性。

软件流水的原理如图2所示，软件流水技术将每个循环体分成若干段Stage，每个段中包括若干操作(一个流水段也可能不包含任何操作)，不同的段能够并行执行。相邻循环体的启动间隔称为启动间距(Initiation Interval, II)，每个流水段的执行时间都等于II，本文中II均为1。软件流水被分为3个阶段：填充、核心和排空。

图2 软件流水技术原理

在填充阶段，每隔II个周期启动一个新的循环体。在核心阶段，软件流水线完全填满，以其最大生产能力并行执行所有Stage，最高效情况下核心段能够在一个周期内遍历所有Stage。在排空阶段，不再有新的循环体启动，但处于流水线中的循环仍在执行，直到全部执行完毕。

3 AES-128算法的软件流水实现

AES-128的轮函数较为规整，通过软件流水技术重组单个分组的轮函数或多个分组的轮函数，能够挖掘不同操作间的指令级并行性，在提高功能单元利用率的同时有效提升算法执行效率。

软件流水技术非常依赖硬件结构的支持，它要求功能单元能够并行执行，同时循环体的重叠执行增加了寄存器需求。本文中的算法映射平台RCSP支持功能单元并行执行，且有足够寄存器满足需求。在RCSP处理器的单簇、双簇和四簇结构下进行了AES-128的软件流水实现及算法映射，不同运算簇数目时使用的功能单元数目也不同，具体的实现过程如下文所述。

3.1 单簇的软件流水实现

单簇运算时数据位宽为32 b，此时AES-128的顺序执行、串行/并行工作模式下软件流水执行如图3所示。单簇运算时使用到的运算单元有1个32 b的异或单元、4个8—8并行的S盒单元、1个128 b的字节置换单元和1个32 b的有限域矩阵乘法单元，128 b的分组分为4个32 b的数据分块，每个数据分块依次执行上述功能单元。

AES-128顺序执行过程如图3(a)所示，每个数据分块依次执行同一操作后，再执行下一操作。此时的轮函数由4个S盒操作、1个字节置换操作、4个有限域矩阵乘法操作和4个异或操作完成。在顺序执行时，操作之间无法并行执行，功能单元利用率和执行效率都比较低。

在AES-128串行工作模式时，密码分组无法并行执行。其软件流水实现过程如图3(b)所示，在填充阶段，填充软件流水线，即每经过1个时钟周期启动一个数据分块去填充软件流水线，由于P操作需要在4个分块都完成S操作后才能启动，故在前3个数据分块完成S操作后插入NOP来填充流水线。此时的循环核心由S、P、GF、XOR和3个NOP操作组成7段Stage，由于串行模式下只能并行处理4个数据分块，故软件流水线无法填满。在排空阶段，循环核心段循环执行9轮后软件流水线开始“排水”，此时不再启动新的数据分块操作，继续完成尚未完成操作的数据分块。

在AES-128并行工作模式时，密码分组能够并行执行。其软件流水实现过程如图3(c)所示，此时同一分组的不同数据分块的操作能够并行执行，同时不同分组的不同数据分块的操作也能够并行执行。在循环核心阶段，软件流水线以其完全最大生产能力并行执行四种操作，值得注意的是由于P操作必须在S操作全部完成后才能启动，故需要在等待周期内插入空操作NOP，最高效情况下循环核心段能够在一个时钟周期内遍历所有的操作，即同一时钟周期完成四个不同操作。此时的循环核心由S、P、GF、XOR和4个NOP操作组成8段Stage，并且并行处理8个数据分块，完全填充软件流水线。

3.2 双簇的软件流水实现

双簇运算时数据位宽为64 b，此时AES-128的顺序执行、串行/并行工作模式下软件流水执行如图4所示。双簇运算时使用到的运算单元有2个32 b的异或单元、8个8—8并行的S盒单元、1个128 b的字节置换单元和2个32 b的有限域矩阵乘法单元，128 b的分组分为2个64 b的数据分块，每个数据分块依次执行上述功能单元。

图3 单簇时顺序执行、串行/并行模式软件流水实现

图4 双簇的顺序执行、串行/并行模式软件流水实现

AES-128顺序执行过程如图4(a)所示，每个数据分块依次执行同一操作后，再执行下一操作。此时的轮函数由2个S盒操作、1个字节置换操作、2个有限域矩阵乘法操作和2个异或操作完成。在顺序执行时，操作之间无法并行执行，功能单元利用率和执行效率都比较低。

AES-128串行工作模式软件流水实现过程如图4(b)所示，在填充阶段，只能够启动2个数据分块填充软件流水线。每个数据分块的循环核心由S、P、GF、XOR和NOP操作组成5段Stage，此时软件流水无法填满。在排空阶段，循环核心段循环执行9轮后软件流水线开始“排水”。

AES-128并行工作模式软件流水实现过程如图4(c)所示，此时每个数据分块的循环核心由S、P、GF、XOR和2个NOP操作组成6段Stage，并且并行处理6个数据分块，完全填充软件流水线，使得功能单元的利用率得到较大提升。

软件流水把不同数据分块的加密操作交织在一起执行，而单个数据分块的操作依然按图1所示的加密数据路径串行执行，这样，既保证了每个数据分块的指令相关依赖关系，又提高了指令级并行性和执行效率。

3.3 四簇的软件流水实现

四簇运算时数据位宽为32 b，此时AES-128的顺序执行、串行/并行工作模式下软件流水执行如图5所示。四簇运算时使用到的运算单元有4个32 b的异或单元、16个8—8并行的S盒单元、1个128 b的字节置换单元和4个32 b的有限域矩阵乘法单元，128 b的分组作为1个数据分块依次执行上述功能单元。

图5 四簇的串行/并行模式软件流水实现

如图5(a)所示，AES-128顺序执行过程和串行工作模式软件流水实现过程相同。此时128 b的分组数据按图1所示的加密数据路径遍历所有操作完成密码运算，分组在执行所有操作时完全并行，故无法开发不同操作间的并行性。

AES-128并行工作模式软件流水实现过程如图5(b)所示，此时每个数据分块的循环核心由S、P、GF和XOR组成4段Stage，能够并行处理4个分组，充分填充软件流水线。值得注意的是由于末轮变换少1个GF，导致分组1的最后1个XOR操作与分组4的第10个XOR操作产生资源冲突，故4个分组的最后1个XOR前均插入NOP操作。

4 性能分析与对比

本文分析了AES-128的顺序执行、串行/并行模式下的软件流水实现过程，并在可重构密码流处理器RCSP的单簇、双簇和四簇资源下进行了AES算法的映射，结果如表1所示。其中RCSP在65 nm互补金属氧化物半导体(Complementary Metal Oxide Semiconductor, CMOS)工艺下的工作频率为500 MHz。

表1 AES在RCSP处理器的映射结果 Gb/s

从表1中可知，当算法处理数据位宽较小时，各操作的数据级并行性开发较小，通过软件流水技术能够较大幅度提高算法的吞吐率。当算法处理数据位宽较大时，各操作的数据级并行性得到较大开发，此时通过软件流水在减小执行周期的同时扩展并行执行分组数，从而提高在并行工作模式下的算法吞吐率。

为了充分说明本文提出的AES算法软件流水实现方法的优势，本节选择了3款处理器结构进行了吞吐率的对比。其中，BCORE[11]由16×32的可重构单元构成，每个单元的运算粒度为8 b，涵盖了分组密码算法所需的基本运算。RCCPA[12]采用分簇式设计，包含4个处理簇，可根据密码处理需要，灵活配置簇内和簇间的互连结构，充分适应密码处理的并行及流水特性，其运算资源规模与3.3节四簇结构相当。CCproc[13]有4个密码运算簇，每个簇的数据位宽为32 b，其运算资源规模也与3.3节四簇结构相当。各结构AES算法的吞吐率对比如图6所示。

图6 AES算法吞吐率对比

通过图6对比可以看出，通过软件流水技术来重组轮函数，不仅能够减小单分组的执行周期数，而且能够扩展并行执行分组数来提高多分组执行性能，同时还能够提升功能单元利用率。

5 结语

分组密码算法大多是迭代型，通过多次调用轮函数从而实现数据的混乱和扩散，进而达到隐蔽数据的目的。本文通过软件流水技术来开发单分组或多分组不同数据分块的轮函数的指令级并行度，提高算法的执行效率。AES-128的算法映射结果证明，软件流水技术能够有效提升密码算法的执行性能。由于不同的分组密码算法结构存在较大的差异性，其软件流水实现过程也有所不同。下一步，将对分组密码算法的结构特征进行分析总结，并提出面向可重构密码流处理器RCSP的分组密码算法软件流水实现算法，使得密码算法的映射过程更加自动快速。

References)

[1] LIU B, BAAS B M. Parallel AES encryption engines for many-core processor arrays [J].IEEE Transactions on Computers, 2013, 62(3): 536-547.

[2] FRONTE D, PEREZ A, PAYRAT E. Celator: a multi-algorithm cryptographic co-processor [C] // Proceedings of the 2008 International Conference on Reconfigurable Computing and FPGAs. Piscataway, NJ: IEEE, 2008: 438-443.

[3] WANG S C, XU J H, YAN Y J, et al. A high-efficiency reconfigurable cryptographic processor [C]// Proceedings of the 2016 International Conference on Integrated Circuits and Microsystems. Piscataway, NJ: IEEE, 2016: 200-204.

[4] SAYILAR G, CHIOU D. Cryptoraptor: high throughput reconfigurable cryptographic processor [C]// ICCAD’14: Proceedings of the 2014 IEEE/ACM International Conference on Computer-Aided Design. Piscataway, NJ: IEEE, 2014: 154-161.

[5] WANG B, LIU L B. A flexible and energy-efficient reconfigurable architecture for symmetric cipher processing [C]// Proceedings of the 2015 IEEE International Symposium on Circuits and Systems. Piscataway, NJ: IEEE, 2015: 1182-1185.

[6] GRAND M, BOSSUET L, GAL B L, et al. Design and implementation of a multi-core crypto-processor for software defined radios [C]// ARC’11: Proceedings of the 7th International Conference on Reconfigurable Computing: Architectures, Tools and Applications, LNCS 6578. Berlin: Springer, 2011: 29-40.

[7] BOSSUET L, GRAND M, GASPAR L, et al. Architectures of flexible symmetric key crypto engines — a survey: from hardware coprocessor to multi-crypto-processor system on chip [J]. ACM Computing Surveys, 2013, 45(4): Article No. 41.

[8] 王寿成,严迎建,徐进辉,等.可重构密码流体系结构模拟器设计与实现[J].计算机工程与设计,2016,37(11):2923-2927.(WANG S C, YAN Y J, XU J H, et al. Design and implementation of reconfigurable cipher stream processor simulator [J]. Computer Engineering and Design, 2016, 37(11): 2923-2927.)

[9] 严迎建,王寿成,徐进辉,等.面向密码流体系结构的超长指令字可重构研究[J].电子与信息学报,2017,39(1):206-212.(YAN Y J, WANG S C, XU J H, et al. Research of reconfigurable very large instruction word on cipher stream architecture [J]. Journal of Electronics & Information Technology, 2017, 39(1): 206-212.)

[10] IQBAL N, SIDDIQUE M A, HENKEL J. RMOT: recursion in model order for task execution time estimation in a software pipeline [C]// DATE’10: Proceedings of the 2010 IEEE Conference on Design, Automation & Test in Europe. Leuven, Belgium: European Design and Automation Association, 2010: 953-956.

[11] 郭岩松,刘雷波.一种面向分组密码的粗粒度可重构阵列及AES算法映射[J].微电子学与计算机,2015,32(9):1-5.(GUO Y S, LIU L B. A block cipher oriented coarse-grained reconfigurable array and AES algorithm mapping [J]. Microelectronics & Computer, 2015, 32(9): 1-5.)

[12] 李校南,王雪瑞,戴紫彬,等.可重构分簇式分组密码处理架构[J].计算机应用与软件,2014,31(1):315-318.(LI X N, WANG X R, DAI Z B, et al. Reconfigurable clustered block cipher processing architecture [J]. Computer Applications and Software, 2014, 31(1): 315-318.)

[13] THEODOROPOULOS D, PAPAEFSTATHIOU I, PNEVMATIKATOS D. CCproc: an efficient cryptography coprocessor [C]// Proceedings of 16th IFIP/IEEE International Conference on Very Large Scale Integration. Piscataway, NJ: IEEE, 2008: 160-163.

This work is partially supported by the National Natural Science Foundation of China (61404175).

WANG Shoucheng, born in 1992, M. S. candidate. His research interests include design of application specific processor architecture.

XU Jinhui, born in 1978, Ph. D., lecturer. His research interests include reconfigurable computing.

YAN Yingjian, born in 1973, Ph. D., professor. His research interests include design of safety specific chip.

LI Gongli, born in 1981, Ph. D. candidate. Her research interests include information security.

JIA Yongwang, born in 1992, M. S. candidate. His research interests include information security.

Software pipelining realization method of AES algorithm based on cipher stream processor

WANG Shoucheng1*, XU Jinhui1, YAN Yingjian1, LI Gongli1,2, JIA Yongwang1

(1.CollegeofCryptogramEngineering,InformationEngineeringUniversity,ZhengzhouHenan450001,China; 2.CollegeofComputer&InformationEngineering,HenanNormalUniversity,XinxiangHenan453002,China)

Aiming at the excessively long time consumption of round function in block cipher implementation, a new software pipelining realization method of Advanced Encryption Standard (AES) algorithm based on Reconfigurable Cipher Stream Processor (RCSP) was proposed. The operations of round function were divided into several pipelining segments. The different pipelining segments corresponded to different cipher resources. The instruction level parallelism was developed to accelerate the execution speed of round function by executing different pipelining segments of multiple round functions in parallel. The execution efficiency of block cipher algorithm was improved. The separation processes of pipelining segments and software pipelining mapping methods of AES algorithm were analyzed with the computing resources of single cluster, two clusters and four clusters of RCSP. The experimental results show that, the proposed software pipelining realization method, which makes different data fragments of one block or multiple blocks processed in parallel, can not only improve the performance of a block serial execution, but also improve the performance of multiple blocks parallel execution by developing the parallelism between the blocks.

block cipher; Advanced Encryption Standard (AES) algorithm; software pipelining; instruction level parallelism; throughput

2016- 12- 02;

2017- 01- 29。 基金项目:国家自然科学基金资助项目(61404175)。

王寿成(1992—)，男，甘肃金昌人，硕士研究生，主要研究方向：专用处理器体系结构设计； 徐进辉(1978—)，男，江西赣州人，讲师，博士，主要研究方向：可重构计算； 严迎建(1973—)，男，河南周口人，教授，博士，主要研究方向：安全专用芯片设计； 李功丽(1981—)，女，河南信阳人，博士研究生，主要研究方向：信息安全； 贾永旺(1992—)，男，河北邯郸人，硕士研究生，主要研究方向：信息安全。

1001- 9081(2017)06- 1620- 05

10.11772/j.issn.1001- 9081.2017.06.1620

TP309.7

A