0 引言

    密码学在保证数据传送的安全中扮演了重要角色。1997年1月，美国国家标准及技术研究所（NIST）发起征集高级加密标准（AES）的活动，以替换数据加密算法（DES）。在对15个候选加密算法进行两轮测试和评比后，NIST最终于2000年10月选择Rijindael算法作为高级加密标准算法。

    目前，AES算法在智能卡、移动电话、万维网服务器、ATM机以及云存储等领域有着广泛的应用。同软件实现相比，AES算法的硬件实现提供了更好的物理安全性，而且处理的速度也更快。在大数据时代，AES已经广泛地用于保护云存储数据的安全，为了满足数千万用户的同时需求，与减少芯片面积、减小消耗相比，提高AES算法的吞吐率就变得更为重要。本文主要研究利用流水线结构提高硬件上的AES加密算法的吞吐率。

    目前有3种主流的AES结构优化方法可以提高其在硬件上的处理速度：轮外流水线结构，轮内流水线结构，循环迭代结构。流水线结构是在各级运算中间插入寄存器。内部流水线与其相似，是在轮运算内部复合域逻辑运算中插入寄存器。

    Zhang^[1]利用等价的复合域GF(((2)²)²)²算法来实现一个快而紧凑的AES字节代换操作所要求的复合域乘法逆，但其设计的轮内各级流水线路径长度划分不够最优。Hodjat^[3]利用完全环展开的高度轮内流水线架构，提出两种字节代换方案：一个是对于字节代换操作利用BlockRAMs来实现查找表，另一个是利用复合域GF((2)⁴)²算法。利用复合域算法是由Rijmen^[2]建议并且由Wolkerstorfer^[3]证明。同样Hodjat^[4]在7级流水线设计中各级关键路径划分也不是最优，并且循环展开结构导致AES的吞吐率/面积比率比较小。Zambreno^[5]同样采用完全环展开流水线设计，其中最深流水线设计是完全展开3级流水线，关键路径相对比较长。Good^[6]根据级联的FPGA查找表(LUT)数来划分关键路径，进行完全环展开流水线设计，虽然增加了吞吐率，但更多的流水级划分增加了更多的寄存器而增加了面积。本文同样采取复合域GF((2)⁴)²算法替换查表法，而在轮内运算中重新划分展开为6级的流水线，从而更好地平衡了吞吐率和面积的关系。

1 AES高级加密标准

1.1 加密主体

    AES算法是一种对称加密算法，加密服务器和解密服务器运用相同的密钥进行加密和解密，一次数据位加密长度是128 bit，128 bit的数据加密长度可以被分成一个的状态矩阵，其中每一个字节可以用S_ij(0<i<4，0<j<4)表示。AES所有的算法均可视作基于对这个状态矩阵进行操作。

    AES算法由主体迭代部分和密钥扩展算法构成。每一次的迭代运算称为一轮，而AES算法的总轮数可以为10轮、12轮或14轮，分别对应128 bit、196 bit或256 bit的密钥长度。每一轮迭代运算分为4个不同的步骤，分别是S盒置换、行位移、列混合和密钥加法。AES算法加密解密流程图如图1所示。

1.1.1 S盒置换

    S盒置换是将状态矩阵中每一个元素视作有限域GF(2⁸)中的一个元素，首先进行求逆变换，再将其在GF(2⁸)域中的逆元素进行一次仿射变换，得到新的状态矩阵。由于在GF(2⁸)域中求逆运算过于复杂，所以在具体实现中，通常会使用查表法实现S盒置换，从而减少运算时间。

1.1.2 行位移

    行位移描述矩阵的行操作。在此步骤中，每一行都向左循环位移某个偏移量。在AES中(区块大小128 bit)，第一行维持不变，第二行里的每个字节都向左循环移动一格。同理，第三行及第四行向左循环位移的偏移量就分别是2和3。128 bit和192 bit的区块在此步骤的循环位移的模式相同。经过行位移之后，矩阵中每一竖列，都是由输入矩阵中的每个不同列中的元素组成。对于长度256 bit的区块，第一行仍然维持不变，第二行、第三行、第四行的偏移量分别是1 B、3 B、4 B。

1.1.3 列混合

    在列混合步骤，每一列的4个字节通过线性变换互相组合。每一列的4个元素分别当作1、x、x²、x³的系数，合并即为GF(2⁸)中的一个多项式，接着将此多项式和一个固定的多项式c(x)=3x³+x²+x+2在mod(x⁴)+1下相乘。列混合函数接收4个字节的输入，输出4个字节，每一个输入的字节都会对输出的4个字节造成影响。

1.1.4 轮密钥加法

    轮密钥加步骤，回合密钥将会与原矩阵合并。在每次的加密循环中，都会由主密钥产生一把回合密钥，这把密钥大小会跟原矩阵一样，以与原矩阵中每个对应的字节作异或()加法。

1.1.5 密钥扩展算法

    密钥扩展算法主要进行密钥扩展操作，初始密钥和扩展后的整个密钥表可以看作是一个字序列。在密钥扩展过程中完成了字旋转和字替代两个操作。字旋转操作时将字的4个字节循环右移一个单位，如(W[0]，W[1]，W[2]W[3])经过旋转后得到字(W[3]，W[0]，W[1]W[2])。

1.2 复合域计算法实现S盒置换

    由于S盒置换的数学过程十分复杂，所以这个过程通常采用查表法实现，这样虽然执行速度快，但是会消耗的大量硬件资源，而且查表法无法细分为更小的过程。单纯地在GF(2⁸)有限域中计算S盒置换的结果至少要使用620个门，同样会消耗大量的硬件资源。然而，通过使用复合域算法可以显著地降低运算中所需要逻辑门的数量，即将GF(2⁸)中的运算转换到GF((2⁴)²)中。在复合域运算中，实现将GF(2⁸)域中的元素转换到GF((2⁴)²)域中的同构映射可以用12个异或门实现，关键路径上只有4个异或门。同时，同构映射的逆变换，以及仿射变换都只需要19个异或门来实现，关键路径上也只有4个异或门。在复合域GF((2⁴)²)中，一个元素可以被表示为s_hx+s_l，s_h，sl∈GF(2⁴)。

    使用扩展欧几里得算法，s_hx+s_l的逆变换可以计算得：

    所以S盒置换可以由图2结构通过运算来代替，因为通过复合域运算将GF(2⁸)中的运算转换到GF((2⁴)²)中，GF((2⁴)²)中的运算可以进一步分解到GF(2²)中，进而被分解至GF(2)中。在GF(2)域中一次乘法运算就是一个简单的逻辑与运算，减轻了电路的开销。同时这样的结构也为接下来内部流水线的建立提供了可能。

2 内外混合流水线

    流水线技术就是在逻辑电路中插入流水线寄存器，以缩短组合逻辑路径长度，达到提高工作频率、实现高吞吐率的目的。由于总体的延时取决于延时最长的一级，因此要使流水线结构的功能最优化，就必须使得流水线中各级的延迟时间相等。下面分别阐述本文实现内外流水线的方法。

2.1 外部流水线结构

    外部循环流水线结构由循环展开结构发展而来。具体方法是在组合电路与每一轮加密运算对应的部件之间都插入额外的寄存器。该方法可以在同一时刻处理多个数据分组，提高系统在单位时间内处理数据的速度。图3为外部10轮流水线流程图。

    根据AES算法结构，容易发现该算法具有以下几个显著的特点：

    (1)AES算法加解密过程的核心是10次轮操作，前一轮操作的输出是下一轮操作的输入。

    (2)AES算法每次轮操作需要一组子密钥，而一组子密钥的产生仅与上一组子密钥相关。

    根据上述特点可知，AES算法可以采用流水线形式实现，把子密钥的生成插入到每一次轮操作的过程中，将10次轮操作解开为一个10级的流水线。用外部循环结构实现的加解密算法，模块的面积与流水线级数成正比。AES加密算法展开为10级的流水线后效率提高为原来的10倍。 

2.2 内部流水线

    内部流水线是在内部复合域逻辑运算中插入寄存器，可以使其逻辑长度更为缩短，从而大大提高吞吐率。采用轮内流水线技术进行高性能AES硬件实现设计的关键就是如何利用最简单的组合电路实现AES的轮单元及如何进行流水线划分使得关键路径最短。本文对每一轮加密过程进行改动，做如图4划分，分成6级的流水线。

    由表1可以看出，轮内划分的六部分的关键路径都基本相等，所以各部分延时也基本相同，因而将轮内操作分成6轮是合理的。与文献[1]中将轮内流水分成7轮相比，分成6轮虽然损失了部分速度，但是面积利用率更高。

3 测试方法和结果

3.1 仿真与测试

    本文采用硬件描述语言Verilog HDL代码编写了128 bit的AES算法，经过外部10轮流水线改进以后的加密算法，改进S盒置换步骤后的AES算法，实现内部流水线后的AES算法和内外混合流水线的AES算法，并用Modelsim对每个算法逐个进行仿真。

    本文采用Altera Quarters II工具在芯片为Cyclone IV的FPGA上进行验证，所获得的数据已在表1中给出。

3.2 性能分析

    测试所得结果与同类论文研究结果的比较见表2。

    由表2可以看出，本文完成的工作使得吞吐率较同类论文结果平均提升197.5%，最高提升241.3%，取得显著进步。同时，就内外流水线而言，使用外部10轮流水线的吞吐率较原始结果提升10倍。同时使用内外流水线相比只使用外部流水线而言，吞吐率增加5.5倍。这与理论基本相符。当然，吞吐率的增加伴随着面积的增加，但可以看出，由于增加内部流水线省去了占据面积巨大的S盒查找表，一定程度上抑制了面积的增加。因而，使用内外混合流水线，对于提升吞吐率面积比，也有积极的作用。

4 结论

    本文提出了一种可以高效地实现AES算法的流水线结构，不同于以往采用查找表的方法实现S盒转换，本文采用组合逻辑电路实现这一步骤。采用查找表的方法，虽然可以使处理速度得到提升，但是占用硬件面积过大；采用组合逻辑电路，虽然增加了电路的复杂程度，但是可以显著减少占用的硬件面积，此外，通过使用复合域算法化简域内的转换，电路的复杂度也可以得到降低。为了获得更高的处理速度，本文在用于S盒转换的组合逻辑电路内部进行了内部流水线划分，最终设计了6段流水线，进一步提高了处理速度。

参考文献

[1] Zhang Xinmiao，Keshab K.Parhi.High-speed VLSI architectures for the AES algorithm[J].IEEE Transactions on Very Large Scale Integration(VLSI) Systms，2004，12(9)：957-967.

[2] RIJMEN V.Efficient implementation of the rijindael S-box[J].Katholieke Universiteit Leuven，Dept.ESAT.Belgium，2000.

[3] WOLKERSTORFER J，OSWALD E，LAMBERGER M.An ASIC implementation of the AES SBoxes[M].Topics in  Cryptology-CT-RSA 2002.Springer Berlin Heidelberg，2002：67-68.

[4] HODJAT A，VERBAUWHEDE I.A 21.54 Gbits/s fully pipelined AES processor on FPGA[C].Field-Programmable Custom Computing Machines，2004.FCCM 2004.12th Annual IEEE Symposium on.IEEE，2004：308-309.

[5] ZAMBRENO J，NGUYEN D，CHOUDHARY A.Exploring area/delay tradeoffs in an AES FPGA implementation[M].Field Programmable Logic and Application.Springer Berlin Heidelberg，2004：575-585.

[6] GOOD T，BENAISSA M.Pipelined AES on FPGA with support for feedback modes(in a multi-channel environment)[J].IET Information Security，2007，1(1)：1-10.

[7] FU Y，HAO L，ZHANG X，et al.Design of an extremely high performance counter mode AES reconfigurable processor[C].Embedded Software and Systems，2005.Second International Coference on IEEE，2005：7.

[8] FAN C P，HWANG J K.Implementations of high throughput sequential and fully pipelined AES processors on FPGA[C].Intelligent Signal Processing and Communication Systems，2007.ISPACS 2007.International Symposium on.IEEE，2007：353-356.

[9] VANITHA M，SAKTHIVEL R，SUBHA S.Highly secured high throughput VLSI architecture for AES algorithm[C].Devices，Circuits and Systems(ICDCS)，2012 International Conference on IEEE，2012：403-407.