可重构平台下AES算法的流水线性能优化
发布时间：2010-1-23 15:20
发布者：李宽
|
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％。经分析，轮间流水线结构加入了模块问寄存器，所需资源应该增加，而实际综合结果却是减少。为此我们详细分析了两模块中各结构的综合报告。从报告的数据看，应该是逻辑综合软件对设计的优化，使得轮间流水线结构所需资源反而减少。 
为了达到极高的加密速度，将轮内流水线和轮外流水线结合使用，设计了混和轮内外流水线结构。混合轮内外流水线结构具有极短的流水线单级延迟，因而时钟频率可以提高到212．5 MHz。同时，混合轮内外流水线结构能够在每一时钟周期内完成一个数据分组的加密，这样，加密的速度就可以达到27．1 Gb／s。这一速度是目前有关AES的高速加密芯片实现的报告中数据较高的。为了达到这样高的加密速度，所需要的资源也是相当可观的。逻辑综合结果显示，完成这一设计需要17 887个逻辑单元，如图4所示。这相当于4块Xilinx XC2V1000 FPGA的容量。同时，我们也评估了各种实现结构的效率，用速率资源比，即每秒所能进行加密的Mb数除以设计所需的逻辑单元数目得到的比值作为结构的效率。从图5可以看到，轮内循环结构是最高效的一种设计，其比值为3．49；而循环展开结构效率最低，仅0．12。因此，在逻辑资源相对有限的条件下，选择使用轮内循环是比较合适的。 
3 结论 综上所述，除对AES加密算法基本运算变换的优化外，算法的整体实现结构对其加密性能的影响是很重要的一个方面。一般情况下，在对效率要求不是很高的环境中，迭代结构实现简单，所需资源最少，因而较为合适；但要达到更高的加密效率，并且希望实现代价较低的情况下，采用轮内流水线结构是一个较为合理的折中方案；只有当有大量资源可用并且追求最高的加密性能时，才有必要采用轮内轮间多级混合流水线结构。 参考文献 1. NIST Advanced Encryption Standard (AES) 2001 2. Fu Yongzhi.Hao Lin.Yang Rujin Design of An Extremely High Performance Counter Mode AES Reconfigurable Processor 2005 3. Elbirt Adam Reconfigurable Computing for Symmertric-Key Algorithms 2002 4. Pawel Chodowiec Comparison of the Hardware Performance of the AES Candidates Using Reconfigurable Hardware 2002 作者：西南林学院 付勇智 刘琳 来源：《单片机与嵌入式系统应用》 2009 （6） |
网友评论