基于多核的Rijndael算法的并行优化与实现

钱晓捷，师攀攀，王建辉

（郑州大学 信息工程学院，河南 郑州450001）

0 引 言

IBM公司在1977年研制的一种加密算法，被美国国家标准局（NIST）公布并批准为非机要部门使用的数据加密标准（data encryption standard，DES）。然而，传统的数据加密标准DES已经不能满足现有的安全需求，从1997年起，NIST通过发布公告来公开征集新的加密标准，即高级加密标准（advanced encryption standard，AES），以取代DES。通过对各候选算法的多轮筛选，NIST于2000年10月2日正式宣布Rijndael算法为新的高级加密标准［1］，并且未对Rijndael算法做任何修改。

多核处理器以其高性能、低功耗优势正逐步取代传统的单核处理器成为市场的主流［2］，然而，在计算机安全领域，多核处理器的应用刚刚开始，利用多核多线程技术对加密算法进行并行优化研究，对于提高网络通信速度、强化计算机网络安全有着重要的理论意义和实际价值。通过对Rijndael算法的轮变换进行分析，分别采用基于数据分解和数据流分解两种方式对Rijndael算法进行并行化改造，充分利用硬件资源，通过多核多线程技术，将串行加密程序轮变换环节并行化实现，从而提高Rijndael算法的执行效率。

1 Rijndael算法描述

AES的分组长度为128比特，密钥长度有3种：128比特、192比特、256比特；Rijndael算法的分组长度和密钥长度都是可变的，可以分别独立地设为128比特、192比特、256比特［3－4］。

1.1 Rijndael算法的结构

Rijndael算法是一个分组迭代密码算法，其加密和解密的所有操作都在被称为状态（state）的中间结果上进行，状态可以用图1所示的矩阵阵列图来表示，该图的元素为字节［5］。该阵列的行数为4，列数为Nb，而Nb的大小由分组长度决定，等于分组长度除以除以32。

密码密钥的列数记为Nk，等于密钥长度除以32。Ri－jndael算法的分组长度和密钥长度均可独立地设定为128、192、256位，所以Nb和Nk均可独立取值为4、6、8。用Nr表示Rijndael算法迭代的轮数，Nr依赖于分组长度和密钥长度。表1列出了作为Nb和Nk函数的Nr的值。

图1 Nb＝6时的状态

表1 对不同的Nb和Nk轮的个数值Nr

Rijndael算法的加密过程为：首先进行一次初始密钥加法AddRoundKey，然后进行Nr－1次轮变换Round，最后执行一次轮变换FinalRound，Rijndael算法各轮轮变换都作用在状态State上［6］。128位Rijndael的流程图如图2所示。

从图2可以看出，128位Rijndael算法是一个10轮迭代密码算法。输入是一个数据块和初始密钥。每一个轮变换作用于前一个轮变换之后的中间结果，是一个由以下4个变换构成的序列：SubBytes、ShiftRows、MixColumns和AddRoundKey。最后一个轮变换稍有不同，相比其它轮少了MixColumns。输出是经过10轮变换后的加密数据块［7］。

图2 Rijndael算法流程

1.2 Rijndael算法的实现

1.2.1 密钥编排

密钥编排方案包括两个组成部分，即密钥的扩展和轮密钥的选取［8］。

（1）密钥扩展

密钥扩展指的是在知道密码密钥的条件下获取ExpandedKey，而不是直接指定ExpandedKey。在密钥扩展阶段，将密钥扩展成4行Nb（Nr＋1）列的扩展密钥数组，用 W ［Nb×（Nr＋1）］表示［8］，最先 Nk个字包含了加密密钥，所有其他字用最小下标递归地定义，密钥扩展函数依赖于Nk的值。

当Nk≤6时，密钥扩展函数的C＋＋语言代码描述如下：

当Nk＞6时，密钥扩展函数的C＋＋语言代码描述如下：

（2）轮密钥的选取

第i轮子密钥是由 W ［Nb＊i］到 W ［Nb＊（i＋1）］间的位构成。以Nb＝4，Nk＝4为例，如图3所示。

图3 轮密钥的选取

1.2.2 轮变换

轮变换Round的每一轮都包含以下4个阶段的代换，SubBytes（字节变换）、ShiftRows（行移位变换）、MixColumns（列混合变换）、AddRoundKey（轮密钥加变换）［9］。

（1）SubBytes变换

字节变换SubBytes是Rijndael密码中唯一的非线性变换［10］，它独立地作用于每个状态字节。字节替换由以下2个步骤组成：首先求出每个字节在GF（28）中的乘法逆元素，其中 “00”和 “01”的逆是它们自身［11］；然后将该逆元字节作GF（2）上的如下仿射变换

（2）ShiftRows变换

行移位变换ShiftRows是一线性组合，它能导致多轮循环的各个位之间的扩散［12］。根据不同的分组长度和密钥长度，行移位变换会做出不同的旋转，假设不同的状态中每行的移位字节数分别为C0，C1，C2，C3，则C1，C2，C3跟分组长度Nb有关，具体分组长度对应的移位字节数如表2所示［13］。

表2 不同分组长度对应的移位偏移量

（3）MixColumns变换

列混合变换MixColumns把状态中的每一列都看作是GF（28）上的多项式a（x）与一个固定多项式的模乘，假设b（x）＝c（x）·a（x）（modx4＋1），用矩阵乘法的形式可以表示如下［14］

（4）AddRoundKey变换

该变换主要是把通过以上3个变换得到的数据与该轮的轮密钥进行异或运算，得到的数据再进行下一轮的轮变换。

2 Rijndael算法的并行优化实现

2.1 设计思想

2.1.1 工作模式

AES工作模式主要分为串行模式和并行模式两类。

串行模式的主要特点是各个分组的加密和解密过程依赖于其前序分组，并且影其响后序分组的加密结果，如果分组不存在规律变化，这一类模式基本上找不到可并行的计算方法［15］。该模式主要包括密码分组连接（CBC）模式和密码反馈（CFB）模式。

并行模式的主要特点是各个分组在加密和解密过程的输入输出不和其它分组产生关联，故该模式能够在时间优先的策略下实现并行计算，以获得较高的系统性能［15］。并行模式主要包括电子密码本（ECB）模式、输出反馈（OFB）模式。由于流水线结构不适用于反馈模式，为了达到较高的运算速度，本文对Rijndael算法进行并行优化采用的模式为电子密码本（ECB）模式。

2.1.2 并行编程中的任务分解模式

并行编程使用线程来使得多个操作能够同时运行。在面向多核平台设计多线程应用程序的时候，开发人员必须采取与面向单核平台时不同的设计思想。在单CPU下，是多个线程在同一个CPU上并发地执行，而在多核下，则是由多个线程在多个核上并行地执行。但目前的程序设计中对于多核的利用并没有达到预期的效果。因此，在多核的环境下设计出更适合多核系统的程序，既是一个机遇又是一个挑战。

要做到这一点，应该将应用程序看作是众多相互依赖的任务的集合，将应用程序划分成多个独立的任务，并确定这些任务之间的相互依赖关系，这就称为分解（decomposition）［16］。分解的方式主要有3种：任务分解、数据分解和数据流分解。表3给出了这3种分解方式之间的对比。

表3 各分解方式之间的对比

2.2 基于多核的Rijndael并行化

随着多核处理器的普及，充分利用现有的多核资源用于Rijndael加解密对于提高加解密效率有着重要的实际意义。

由于Rijndael算法轮变换中的4个构成变换之间存在相关性，即后一个变换执行前要知道前一个变换的结果，各个变换不能够同时执行，故该算法不宜采用基于任务分解的方式进行并行化。下面从数据分解和数据流分解两个方面对Rijndael算法进行并行优化。

2.2.1 基于数据分解方式的并行化

Rijndael算法中轮变换的4个构成变换都是独立的作用于状态的字节、行或者列之上的，故可以把构成变换对整个状态的作用分割成对状态的每一个组成单元（字节、行或列）的作用［17］。构成变换对状态作用的独立性，也就决定了各个构成变换对状态的每一个组成单元的作用都能够以并行进行。

假设处理器内核数为N，分组长度、密钥长度均为128位，则Nb＝Nk＝4。由于SubBytes变换独立地作用于每一个状态字节之上，所以该构成变换可以并行执行。假定对每一个状态字节作一次SubBytes变换需要1个时间单位，则所有状态字节串行模式下执行完SubBytes变换需要16个时间单位，而在并行模式下，只需要16/N个时间单位即可执行完该变换［17］。同理，假定一行状态字节作一次ShiftRows变换需要1个时间单位，串行模式下整个ShiftRows变换需要3个时间单位，并行模式下只需要3/N个时间单位；假定对一列状态字节作MixColumns变换需要1个时间单位，串行模式下整个MixColumns变换需要4个时间单位，并行模式下只需要4/N个时间单位；假定每个状态字节作一次AddRoundKey变换需要1个时间单位，串行模式下整个AddRoundKey变换需要16个时间单位，并行模式下只需要16/N个时间单位。

2.2.2 基于数据流分解方式的提出

Rijndael算法轮变换由4个构成变换组成，从第2个变换开始，每个变换在执行之前，都需要知道前一个变换执行后的结果，即前一个变换的输出是后一个变换的输入。如果将两个变换采用不同的线程并行执行，那么处理后一个变换的线程需要一直等到前一个变换完成变换工作之后才能开始执行。

通过对SubBytes变换和ShiftRows变换的分析，ShiftRows变换独立地作用于状态矩阵的每一行，故每当状态矩阵的某一行执行完SubBytes变换后，即可开始对该行执行ShiftRows变换，而不必等到所有的状态字节全部执行SubBytes变换后才执行ShiftRows变换。记状态矩阵第N行执行SubBytes变换为SB（N），执行ShiftRows变换为SR（N），基于以上分析，通过基于数据流的分解方式，可对轮变换的前两个构成变换执行过程进行如图4所示的描述。

图4 前两个构成变换的数据流分解

假定对状态矩阵的一行字节执行SubBytes变换需要a个时间单位，对状态矩阵的一行字节执行ShiftRows变换需要b个时间单位，则前两个变换执行完毕需要消耗（4a＋4b）个时间单位。采用基于数据流的分解方式并行化之后，若a＞b，则前两个变换只需要（4a＋b）个时间单位；若a＜b，则前两个变换只需要（a＋4b）个时间单位。

由于ShiftRows变换是逐行对状态矩阵进行操作，MixColumns变换是逐列对状态矩阵进行操作，故必须等到状态矩阵的所有状态字节执行完ShiftRows变换后才执行MixColumns变换，因次，MixColumns变换和ShiftRows变换之间无法采用基于基于数据流的分解方式进行并行优化。

继而对MixColumns变换和AddRoundKey变换进行分析，发现这两个变换同样可以通过基于数据流分解的方式并行优化。状态矩阵的每一列执行完MixColumns变换之后，即可对该列执行AddRoundKey变换，而不必等到整个状态矩阵的所有字节都执行MixColumns变换后才执行AddRoundKey变换。记状态矩阵第N列执行MixColumns变换为 MC（N），执行AddRoundKey变换为ARK（N），在以上分析的基础上，再通过基于数据流的分解方式，可以将轮变换的后两个构成变换执行过程进行如图5所示的描述。

图5 后两个构成变换的数据流分解

假定状态矩阵的一列字节执行MixColumns变换需要消耗c个时间单位，对状态矩阵的一列字节执行AddRound－Key变换需要消耗d个时间单位，则状态矩阵的全部状态字节在串行模式下执行完后两个变换共需消耗（4c＋4d）个时间单位。通过基于数据流分解方式的并行化之后，若c＞d，则后两个变换只需要（4c＋d）个时间单位；若c＜d，则后两个变换只需要（c＋4d）个时间单位。

3 实验结果分析

实 验 采 用 Intel Core 2Duo E7200（双 核， 主 频2.53GHZ），2GB RAM PC机，Windows XP操作系统平台，使用Visual C＋＋6.0作为开发平台。

对Rijndael算法采用基于数据分解方式并行化实现后的实验结果进行分析，发现采用此分解方式并行后的算法并没有提高加密性能，反而降低了加密性能，这是因为这4个构成变换的函数主体均为二重循环，本身计算量都很小，并行化产生的收益远远小于并行化付出的代价。因此，通过基于数据分解的方式对Rijndael算法并行优化的方案是不可行的。

文献 ［18］给出Rijndael算法轮变换的4个构成变换的时间消耗比为4a：4b：4c：4d＝31：63：266：31，串行模式下4个构成变换共消耗4a＋4b＋4c＋4d＝31＋63＋266＋31＝391个时间单位，由于a＜b，c＞d，则采用基于数据流的分解方式并行化之后共消耗a＋4b＋4c＋d＝31＊0.25＋63＋266＋31＊0.25＝344.5个时间单位。

本文采用加速比来衡量并行程序设计所带来的性能收益，即用串行算法的执行时间除以并行程序的执行时间。对比采用数据流分解方式对Rijndael算法轮变换4个构成变换并行化前后所消耗的时间可知，串行算法的执行时间/并行程序的执行时间＝（4a＋4b＋4c＋4d）/（a＋4b＋4c＋d）＝391/344.5＝1.135，即理论加速比为1.135，或者说理论上性能可以提高13.5%。

表4是对Rijndael算法采用基于数据流分解方式并行化前后的加解密测试结果，显示了当密钥长度和分组长度均为128位时，串行和并行的运行消耗时间的比较。输入明文字节总数记为N，数据流分解前串行程序运行时间记为T1，基于数据流分解后并行程序运行时间T2，时间单位是10－6s，实验结果如表4所示。为了保证测试的普遍性与准确性，实验采用大数据量明文分别对Rijndael算法进行串行和并行测试，表4中的运行时间T1和T2都是通过对十次测试结果取平均值得到的。

表4 性能对比数据

通过对表4中串行和并行时间对比分析可知，采用基于数据流分解方式对Rijndael算法轮变换Round的各个构成变换的分解，分解之后的Rijndael算法并行实现程序运行时间较分解之前串行程序运行时间有了缩短。

并行后的Rijndael算法所获得的平均加速比＝（1.054＋1.065＋1.079＋1.071＋1.068）/5＝1.0674，性能较并行前有了6.74%的提升，虽然距理论值13.5%还有一些差距，综合多种因素来看，并行后的性能提升还是可以接受的。因此，对Rijndael算法并行优化所带来的性能提升基本符合实验预期要求。

4 结束语

本文通过对Rijndael算法轮变换的各构成变换进行分析，采用基于数据流的分解方式对各构成变换进行分解，把各构成变换对整个状态的作用分割成对状态的每个组成单元的作用，使得各构成变换可以并行进行。通过实验对该优化方案进行了验证，在保证安全性和对内存空间需求基本不变的情况下获得了较为明显的性能提升效果。对于强化计算机网络安全和提高网络通信效率有着重要的理论意义和实际价值。

［1］JIANG Chuan，HAN Wei，FANG Xiangyan.Design and implementation of high－speed configurable rijndael algorithm ［J］.Computer＆ Digital Engineering，2009，37（1）：91－95（in Chinese）.［江川，韩威，方湘艳.高速可配置Rijndael算法的设计与实现［J］.计算机与数字工程，2009，37（1）：91－95.］

［2］HUANG Guorui，ZHANG Ping，WEI Guangbo.Key techniques of multi－core processor and its development trends ［J］.Computer Engineering and Design，2009，30（10）：2414－2418（in Chinese）.［黄国睿，张平，魏广博.多核处理器的关键技术及其发展趋势 ［J］.计算机工程与设计，2009，30（10）：2414－2418.］

［3］LU Zhengding，LIAO Zhensong.Research on the Rijndael algorithm ［J］.Computer Engineering ＆ Science，2005，27（6）：72－74（in Chinese）.［卢正鼎，廖振松.Rijndael算法的研究［J］.计算机工程与科学，2005，27（6）：72－74.］

［4］YE Jian，LI Lixin.Fast implementation of AES based on GPU［J］.Computer Engineering and Design，2010，31（2）：256－259（in Chinese）.［叶剑，李立新.基于GPU的AES快速实现 ［J］.计算机工程与设计，2010，31（2）：256－259.］

［5］TONG Xiaojun，AI Guangping，JIANG Wei，et al.Realization of data encryption and digital signature based on rijndael algorithm atc ［J］.Microprocessors，2007，（2）：80－86（in Chinese）.［佟晓筠，艾广平，姜伟，等.基于Rijndael算法的数据加密与签名技术实现 ［J］.微处理机，2007，（2）：80－86.］

［6］FU Desheng，WANG Jiesong.A high－speed arithmetic and application of rijndael ［J］.Microcomputer Applications，2007，28（10）：1112－1116（in Chinese）.［傅德胜，王洁松.一种快速Rijndael算法及其应用 ［J］.微计算机应用，2007，28（10）：1112－1116.］

［7］LE Deguang.Parallel AES algorithm for fast data encryption on GPU ［C］.Chengdu：2nd International Conference on Computer Engineering and Technology，2010：V6－1－V6－6.

［8］HE Minwei，LIU Rui.An improved method based on AES Rijndael algorithm ［J］.Control ＆ Automation，2008，22（6－3）：94－96（in Chinese）.［贺敏伟，刘睿.高级加密标准 RIjndael算法的 一 种 改 进 ［J］.微 计 算 机 信 息，2008，22（6－3）：94－96.］

［9］WU Xiaobo.Analysis of AES encipher algorithm and its C＋＋language implementation ［J］.Network ＆ Computer Security，2007，7（12）：44－46（in Chinese）.［吴小博.AES加密算法分析与C＋＋ 编程实现 ［J］.计算机安全，2007，7（12）：44－46.］

［10］YIN Xinchun，YANG Jie.Scheme of replacement of S－box in AES Rijndael algorithm ［J］.Computer Engineering，2006，32（21）：173－176（in Chinese）.［殷新春，杨洁.高级加密标准Rijndael算法中S盒的替换方案 ［J］.计算机工程，2006，32（21）：173－176.］

［11］GE Honghua，DING Xiuhuan.A hybrid cryptosystem based on AES and ECC ［J］.Science ＆ Technology Information，2011，28（9）：455－457（in Chinese）.［葛宏华，丁秀欢.基于AES和ECC的混合密码体制 ［J］.科技信息，2011，28（9）：455－457.］

［12］LIU Zhihui，LIU Jianhui.Research of data encryption transmission based on AES and RSA ［J］.Network ＆ Computer Security，2007，7（11）：39－41（in Chinese）.［刘志会，刘建辉.基于AES和RSA的数据加密传送方案研究 ［J］.计算机安全，2007，7（11）：39－41.］

［13］WANG Xuemei，SUN Xiaodong，CHEN Haoming，et al.The introduction and pipeline designing study of AES ［J］.Network ＆ Computer Security，2007，7（10）：5－8（in Chinese）.［王雪梅，孙晓东，陈昊明，刘艳.AES算法介绍及其流水线设计研究 ［J］.计算机安全，2007，7（10）：5－8.］

［14］LIU Hongyan，YUAN Ping，WU Hengbai.Design strategy research on realizing scheme of Rijndael algorithm ［J］.Computer Engineering and Design，2008，29（23）：5958－5961（in Chinese）.［刘鸿雁，袁平，吴恒柏.Rijndael算法实现方案的设计策略研究 ［J］.计算机工程与设计，2008，29（23）：5958－5961.］

［15］HAN Qiang，FENG Yi，DING Jing.The design and characteristics of the working modules based on the advanced encryption standard ［J］.Joumal of Yunnan Nationalities University（Natural Sciences Edition），2008，17（4）：362－365（in Chinese）.［韩强，冯翼，丁静.高级加密标准工作模式的设计与特性分析 ［J］.云南民族大学学报（自然科学版），2008，17（4）：362－365.］

［16］Shameem Akhter，Jason Roberts，TransLation，et al.Multi－Core programming－increasing performance through software multi－threading ［M］.Beijing：Publishing House of Electronics Industry，2007（in Chinese）.［Shameem Akhter，Jason Roberts，李宝峰，等.多核程序设计技术－通过软件多线程提升性能 ［M］.北京：电子工业出版社，2007.］

［17］ZHANG Chao，LU Langru，CHU Zefu，et al.AES algorithms and its implementation technology ［J］.Computer and Communications，2001，19（2）（in Chinese）.［张超，陆浪如，楚泽甫，等.AES算法及其实现技术 ［J］.交通与计算机，2001，19（2）.］

［18］XU Xiaolong.The parallelization research of ECC and AES based on multi－core ［D］.Chendu：University of Electronic Science and Technology of China，2010（in Chinese）.［许小龙.基于多核平台椭圆曲线算法和AES算法的并行化研究［D］.成都：电子科技大学，2010.］