AES算法的密码分析与快速实现

摘要：高级加密标准(AES) 确定分组密码Rijndael为其算法，取代广泛使用了20多年的数据加密标准(DES)，该算法将在各行业各部门获得广泛的应用。文章以DES为参照对象，阐述了Rijndael算法的设计特色，介绍了AES在密码分析方面国内外已有的一些理论分析成果，描述了AES算法采用软件和硬件的快速实现方案。
关键词：高级加密标准；Rijndael算法；密码分析；快速实现
Abstract:Rijndael is defined as the algorithm for the advanced encryption standard (AES). With broad applications in various industries, AES has been superseded the data encryption standard (DES) that has a twenty-year application history. This paper describes the design characteristics of Rijndael, in comparison with that of DES. Then, it introduces the latest academic research achievements in AES cryptanalysis at home and abroad. Finally, primary techniques for various fast implementations of AES on hardware and software platforms are introduced.
Key words:AES; Rijndael algorithm; cryptanalysis; fast implementation


    密码学是保障信息安全的核心技术，应用涉及军事、国防、商贸及人们日常生活的各个方面。分组密码以其高效率、低开销、实现简单和易于标准化等特点在现代密码学研究中占据重要地位。2000年10月2日，美国国家标准技术研究所(NIST)在综合考虑了安全性、性能效率和灵活性的基础上，将分组密码Rijndael算法确定为高级加密标准(AES)[1]，取代广泛使用了20多年的数据加密标准(DES)


1 AES算法的密码分析
    一个密码算法的有效性首先体现在可靠的安全性上。Rijndael算法设计采用针对差分和线性密码分析提出的宽轨迹策略(WTS)，其最大优势是可以给出算法最佳差分特征的概率以及最佳线性逼近偏差的界；使用简单的部件组织成清晰的结构，便于算法安全性的分析。当然，在密码学界永远没有绝对的安全，Rijndael算法也不例外，如其明显的代数结构对安全性的潜在威胁已经受到一些学者的质疑。本文从简化算法攻击、算法结构性质分析以及密码分析的进展等方面对AES算法的密码分析状况进行讨论。

1.1 简化算法攻击
    目前尚未出现对完整Rijndael算法的成功攻击，只提出了几种针对简化算法的攻击方法。最有名的当数密码设计者自己提出的Square攻击，其主要思想是利用第4轮字节替换前后平衡性的改变来猜测密钥字节，对128比特密钥下4到6轮简化算法有效。Biham[2]等对Square攻击进行改进，时间复杂度降为原来的1半，并认为颠倒轮密钥的顺序可将攻击复杂度降低28。Lucks[3]利用密钥生成算法的弱点，将Square攻击的密钥长度扩展到192和256比特，攻击7轮简化算法比穷尽搜索快。Ferguson[4]利用“部分和”技术将6轮Square攻击的复杂度从272降到244，并推广到7轮和8轮简化算法，指出密钥生成算法中几个违背设计准则的特性，利用慢扩散性设计了一个针对256比特密钥下9轮简化算法的密钥相关攻击方案。
    Gilbert[5]利用局部函数间的冲突特性对4到7轮简化算法进行了攻击。Cheon等将5轮不可能差分攻击推广到6轮，复杂度高于相应的Square攻击，但仍快于密钥穷尽搜索。Koeune[6]描述了一种计时攻击，通过对每个密钥数千次的测量，展现攻破一个不良的现实设计的过程。Golic[7]则指出AES算法虽然能够通过乘法掩盖来抵抗简单能量攻击(SPA)，对差分能量攻击(DPA)却无能为力。

1.2 算法结构性质分析
    密码代数结构的任何弱点都将有利于密码的分析和破译。因此，在对Rijndael简化算法进行攻击尝试的同时，人们也把相当多的精力集中到算法内部结构各种性质的研究上。Ferguson[8]给出了Rijndael算法一个直观而紧凑的代数表示形式；Filiol[9]则将算法的每一输出比特看作以明文比特和密钥比特为变量的布尔函数fi (p 1,…,pn ,k1,…,kn´)，用Mōbius变换将之计算出来，研究其低次项的分布情况，比较fi与完全随机的布尔函数代数正规式的差异，结果发现Rijndael算法布尔函数的随机特性并不十分理想。
Barkan[10] 替换算法中的不变常量(如既约多项式、列混合运算中的系数和S盒中的仿射变换)，产生新的等价对偶密码(平方对偶、对数对偶和自对偶等数百种之多)。在此基础上，可以选择比原算法快的对偶算法，在加解密中使用不同的对偶密码或每次随机选择不同的对偶密码以抵抗错误攻击和能量攻击。但是，由于对偶密码的结构容易分析，并易于转换成原算法，可能会有助于实施差分或线性攻击，所以对偶密码的存在也可能是对Rijndael算法的一种潜在威胁。
    Song[11]为SPN分组密码引入了替换差分的概念，研究S盒替换距离的分布特性，并认为，如果知道给定分组密码S盒的替换距离，便可在密码分析中选择有一定输入差分的明文来确定可能的密钥，这种分析方法不依赖于密钥，可用于分析Rijndael算法的第1轮。Fuller[12]等指出Rijndael算法S盒的分量函数之间存在等价关系si (x )=sj (Dijx+a)+bx+c。这种等价关系有助于降低S盒硬件实现成本，但从安全角度看，可能会引发对Rijndael算法的攻击。他们利用布尔函数局部结构中的相邻特性，通过寻找等价参数Dij、a、b和c的方法间接证明了分量函数之间的等价关系。Youssef[13]则将S盒分量函数间的等价关系推广到整个轮函数。
    Murphy[14]发现任何明文或明文差分经过Rijndael算法线性扩散层16轮迭代后会重现，Wernsdorf[15]则指出Rijndael算法的轮函数构成交换群。

1.3 AES算法密码分析的进展
    2002年亚洲密码分析研讨会上，Courtois[16]提出一种称为XSL攻击的分组密码分析新方法，主要思想是用一系列次数低、方程数大于变元数的超定方程组来描述密码系统，通过解方程组来破解分组密码。同年美洲密码分析研讨会上，Murphy[17]设计了一种新的算法BES(Big Encryption System)，将AES中GF(28)和GF(2)上的两种域运算归结为域GF(28)上的运算，使AES成为某种消息空间和密钥空间下的BES，通过研究形式更为简洁的BES，可以更清晰地了解AES算法内部的数学结构。2002年第297期《科学》杂志[18]高度评价了这两个最新分析成果。

1.4 中国AES算法研究现状
    中国的研究人员也对AES算法进行了大量研究分析。吴文玲[19]用能量攻击对Rijndael算法进行了分析，攻击复杂度在267到2131之间，大大降低了攻击的规模；曾祥勇[20]等用布尔函数的迹表示给出置换函数的表达式，对由幂函数合成可逆仿射变换产生的S盒间的关系进行了研究；李娜[21]通过研究q-多项式的性质给出了一种求解S盒代数表达式的简易算法，具有可预先计算、操作简单的特点和一定的通用性，并对曾祥勇提出的一类S盒进行了仿射等价划分，明确了这些S盒间的相互关系；冯国柱[22]对Rijndael算法作了变动和改进，使新算法在不降低抗差分攻击性能、牺牲少许密钥装填速度的情况下提高统计效果，并可部分抵抗Square攻击；胡辛征[23]研究发现Rijndael算法S盒在有限域GF(28)上的迭代循环周期过短，设计了一种新的仿射变换对之加以改进；曾游[24]调整Rijndael算法轮变换的顺序，采用密钥的变形形式，通过合理安排求取密钥的顺序，利用密钥相关性将5轮简化算法的密钥穷尽量减少到240+232+216+9×28。
    韦宝典[25]利用Walsh谱理论分析Rijndael算法S盒的严格雪崩特性、扩散特性和相关免疫性等密码性质，提出了广义自相关函数的概念，解决了严格雪崩准则和扩散准则阶数的确定问题；基于等价类的划分、线性方程组的求解和标准基之对偶基的计算，给出了域元素分量代数表达式的3种求法，提出了一种基于生日悖论、利用活动性进行攻击的新方法；指出了Square-6攻击是不成功的，并给出了修正攻击方案。


2 AES算法的快速实现
    良好的安全性固然是Rijndael算法在AES角逐中获胜的先决条件，但Rijndael算法的中选主要还是因为其在安全、性能、效率、执行的简易性与灵活性等方面优势明显。下面介绍AES的典型软硬件实现采用的主要技术。

2.1 软件实现
    Rijndael算法在设计之初就将软件实现的高效性、灵活性作为一个目标。事实证明，Rijndael算法在通用处理器上能获得相当不错的性能。文献[26]在933 MHz Pentium III处理器上用C语言和汇编语言实现了AES算法，128、192和256比特密钥下的吞吐量分别达到325、275和236 Mb/s。文献[27]的方案使用比特滑动术处理256比特数据，仅花费170个时钟周期(相当于1 GHz Pentium III处理器上1.6 Gb/s的数据吞吐量)。比特滑动技术利用高带宽处理器内在的并行处理能力，将W比特带宽的处理器看成一个能同时处理W个单比特操作的单指令多数据(SIMD)并行处理器，操作数包含来自W个不同进程的W个比特。开始先读取并存放好W个输入，第一个操作数包含所有输入的第一比特，第二个操作数包含各输入的第二比特，以此类推。比特滑动计算就相当于W个硬件电路的模拟，其设计首先是硬件电路的设计，然后才是W个比特寄存器的模拟。该方案还利用复合域来进行设计的优化，在基于查表的数学运算中，子域运算经常用来降低查表成本，提高诸如乘法、取逆和求幂等运算的性能。通过复合域的映射运算，在硬件电路设计中可以减少电路面积，在软件设计中可以减少指令数量和查表规模。由于电路设计中只涉及异或、与、非和查表等简单操作，此方案获得了每秒上吉比特的高性能。

2.2 硬件实现
    在虚拟专用网(VPN)和波分复用系统的光纤链路、视频加密、Internet高端路由器等高速应用中，硬件实现才是最佳解决方案。硬件实现能确保加密算法及其密钥扩展的物理安全，因为硬件实现通常不容易被外部攻击者接触或修改。
    加密速度最大化和占用面积最小化的目标可由专用集成电路(ASIC)和现场可编程门阵列(FPGA)实现。ASIC实现是为给定算法专门设计的，速度快、效率高，在占用面积和功耗方面具有优势。对于海量应用来说，ASIC解决方案具有最好的性能价格比。文献[28]通过对S盒的优化，使用0.13 μm CMOS技术在780 MHz标准库下实现了包括密码分组链接(CBC)模式在内10 Gb/s的加密速度。但是，ASIC实现缺乏算法和参数更换的灵活性，而FPGA实现不但具有软件实现的灵活性、成本效益以及算法更换能力，还具有ASIC实现的高效性和物理安全性。FPGA实现具有如下优点：


(1)算法切换的灵活性
    使用过程中实现算法的切换灵活性好。


(2)算法可装载性
    可用设计之初不存在或不是标准的新算法进行更新替换。Rijndael算法成为新标准之后将频繁地被装载到当前的安全产品中。


(3)算法可更改性
    能满足某些应用修改标准算法中某些部件的要求。


(4)特设结构的有效性
    可为特定参数设计，优化专门的实现结构。专门设计的整数乘法或域上的常量乘法一般都比通用乘法部件的效率高得多。


(5)吞吐量高
    运行速度远远高于相应的软件实现，能达到甚至超过ASIC。


(6)效率高
    相对ASIC方案开发周期短，实现成本低。


    无论是ASIC方案还是FPGA方案，性能的提高都离不开优化技术，包括算法轮函数和设计结构的优化。AES算法的优化包括S盒实现的技巧(如使用复合域、查表方法等)、列混合与密钥加的结合等。结构设计上的优化主要有以下几种：


(1)迭代循环结构
    迭代循环结构实现一个轮函数，循环迭代n次输出结果。这是硬件实现最小化的有效方法，寄存器延时短，但整体过程时钟数多。


(2)开环结构
    开环结构实现多个轮函数，迭代次数为n的因子。全开环结构占用面积最大，寄存器延时也最大，系统时钟长。


(3)流水线结构
    流水线结构实现流程中加入寄存器和相应的逻辑电路，将整个过程划分为前后相连的多级实体，一个时钟内有多个数据块同时在各级中处理。流水线技术通过同时处理多个数据块的方法提高吞吐量，其代价是硬件资源的增加。流水线结构只能用于非反馈加密模式。
文献[29]采用轮函数完全展开的开环结构，将轮函数划分成5级流水线，在158 MHz时钟下获得20.3 Gb/s的吞吐量。表1列出了几种典型的AES算法快速实现方案。