可重构平台下AES算法的流水线性能优化

摘要 AES-Rijndael算法是美国取代DES的新一代分组加密算法标准，也是事实上的国际标准。本文在可重构平台上针对 128位密钥长度AES算法的流水线性能优化技术进行了研究，通过对基本运算优化、循环展开、轮内流水线、轮间流水线、混合多级流水线结构优化等方法的讨论和实现，对比不同优化方法的优缺点及适用环境。实验表明，不同结构的设计，其加密性能存在很大差异。其中，混合多级流水线结构的加密性能达到27．1 Gb／s的速率，为目前国内外相关研究的较好结果。
关键词 高级加密标准 可重构计算 流水线 结构优化 AES-Rijndael算法

1 AES-RijndaeI算法总体结构
AES-Rijndael算法是一个替换一置换网络结构的分组密码算法。它的设计基于有限域上的多项式运算，密码算法的主体结构由4部分组成：SubBytes，进行S-盒非线性变换；ShiftRows，状态矩阵的水平置换；MixCol-umns，执行有限域GF(28)上的矩阵乘运算；AddRoundK-eys，通过简单异或运算使子密钥与状态矩阵发生联系。算法经过Nr轮变换，将一个128位明文分组加密成为一个128位的密文分组。这里Nr是一个与密钥长度相关的常数。对于128位密钥的情况，Nr的值为 10。除了最后一轮外，其他每一轮加密过程都相同。最后一轮加密中省去了 MixColumns变换，以抵抗某些特殊密码分析。

2 循环展开和流水线优化
对于前述AES加密过程的实现，如图1(a)所示，我们针对可重构平台下4个变换函数的实现方法进行了优化，优化后的加密过程时钟频率达到了127．9 MHz。这样，对于一个128位明文分组的加密需要11个时钟周期，因此，其加密速率为1．49 Gb／s。这一速率已经能满足绝大多数应用的需要，然而为了满足一些更高速应用的需要，可以通过改变加密处理过程体系结构进一步优化相应设计。要提高加密速率，最简单的方法是使用循环展开技术将迭代加密的结构展开，并将多份加密轮变换电路的输入输出首尾相连，如图1(b)所示。这样可以节省寄存器建立延迟和选路器的传输延迟时间，从而加快加密变换处理的速度。然而，这种方法会消耗大量的逻辑资源，并且性能提高得不多。根据我们的实验，循环展开后的芯片速度比迭代结构增加了17％，然而所消耗的逻辑资源却是迭代结构的6倍。因此，这一优化方法的效率是极其低的；只有在对性能要求很高，但资源又充分的情况下才能采用。
另外一种优化方法是使用流水线技术。它是将关键执行路径切分为多级短的执行步，并在各执行步电路间插入寄存器存储上一级执行结果。这样，虽然关键执行路径没有变短，但电路可以在一个较少的时钟周期内同时处理多个数据块的加密，从而提高了并发程度，因此，加密速率也就能大大提高。在设计加密算法处理流水线的过程中，最常用的是轮间流水线技术。轮问流水线技术是将循环展开结构按各加密轮切分为一系列的流水线，其中每一轮加密变换为一级。在流水线的各级之间插入寄存器，寄存器由同步时钟来控制，每次时钟触发，寄存器就保存上一次的变换结果，同时将之前保存的结果送流水线处理部件处理并将结果保存到下一级寄存器中，如图1(c)所示。根据我们的实验结果(见图3)，轮间流水线结构的设计，加密速率是迭代结构的12倍；同时资源消耗也大量增长，是迭代结构的7倍。由实验结果可见，轮间流水线技术是一种对分组加密算法很有效的优化技术。特别是当算法中加密轮函数较为简单的情况下，轮间流水线技术是相当适用的；但是，对于一些轮函数复杂，加密轮数较少的算法，轮问流水线技术的优化效果就不是很突出了。

Chodowiec等人提出了轮内流水线技术，以优化这类加密变换轮较为复杂的算法。轮内流水线将加密轮分割为多级，在每一级间插入寄存器，以实现流水线，如图2(a)所示。这种方法的优点在于所增加的资源消耗很少，仅需多级寄存器；然而也存在缺点，轮内流水线很难平衡各级间的延迟，而整体时钟的频率只能由最长流水线的延迟决定。我们的实验将AES加密函数按其组成模块分割为4级流水线，要将其分为更多级也是可以做到的，但较为困难，因为类似S一盒这样的长结构很难再分，而它们的延迟将决定总体时钟的频率。

根据图3所示实验结果，轮内流水线结构的执行效率比迭代结构的执行效率高5倍，而所需资源反而比迭代结构减少11％。经分析，轮间流水线结构加入了模块问寄存器，所需资源应该增加，而实际综合结果却是减少。为此我们详细分析了两模块中各结构的综合报告。从报告的数据看，应该是逻辑综合软件对设计的优化，使得轮间流水线结构所需资源反而减少。

为了达到极高的加密速度，将