AES算法的文献综述2006集成电路工程 061121298薛小铃1引言计算机网络的广泛普及与使用，电子信息技术已经渗透到了人们口常生活的 各行各业，在金融、电信、政府机构等更为重要。人们越来越意识到信息安全的 重要性。密码学作为信息安全领域的一项重要技术，被普遍认为是解决信息安全 保护最有效的方法。现在网络应用的信息安全技术(如数据加密技术、数字签名 技术、消息论证与身份识别技术、防火墙技术以及反技术等)都是以密码学为基 础的。分组密码以其高效率、低开销、实现简单和易于标准化等特点在现代密码 学研究中占据重要地位。2000年10月2日，美国国家标准技术研究所(NIST)在 综合考虑了安全性、性能效率和灵活性的基础上，将分组密码Rijndael算法确定 为高级加密标准(AES),取代广泛使用了 20多年的数据加密标准(DES)O2 AES算法的历史背景自20世纪70年代以来一直被广泛使用的数据加密标准DES算法的有效密 钥只有56比特，即256 7X1016种可能的密钥值。然而，随着更快的处理器的 出现和大规模并行处理系统的发展，使得计算机比以前的计算速度快得多。因此, 这个数字并不像以前那样巨大，在某种意义上说，它是很小的。另一方面，有些 人觉得DES算法中替换的合理性从來就没有完全解释清憩。他们的担心是在替 换中可能有些东西会损坏密文的完整性，或者在DES算法中存在不为人知的“后 门”。进入上卅纪九十年代后，另一种由DES衍生出来的算法一三重DES,被广 泛使用。但是它的安全性并不意味着建立在168位的密钥之上，研究表明，可以 将其转化为对108位密钥的攻击。最重要的是，三重DES的加密和解密时间消 耗较大，不能很好的适用飞速增长的实时信息加密需求。所有这些，都使得人们 开始期待一种更安全、更为公开的加密标准的出现。1997年4月15 H, NIST发起了征集AES算法的活动,并成立了专门的AES 工作组，冃的是为了确定一个非保密的公开披露的全球免费使用的分组密码算 法，用于保护下一世纪政府的敏感信息，并希望成为秘密和公开部门的数据加密 标准。1997年9月12 口在联邦登记处公布了征集AES候选算法的通告。AES 的基本要求是：比三重DES快，而且至少和三重DES-样安全，分组长度128 比特，密钥长度为128/192/256比特。1998年8月20 口，NIST召开了第一次候 选大会并公布了 15个候选算法。1999年3月22日，举行了第二次AES候选会 议，从中选出5个AES将成为新的公开的联邦信息处理标准(FIPSFederal Information Processing Standard),用于美国政府组织保护敏感信息的一种特殊的 加密算法。NIST预测，AES会被广泛地应用于组织学院及个人。入选AES的五 种算法是 MARs、Rc6、Serpent Twofish 和 Rijndael。2000 年 10 月 2 口，美国 商务部部长NormanY.Mineta宣布，经过三年来世界著名密码专家之间的竞争， 助Rijndael数据加密算法最终获胜。为此而在全球范围内角逐了数年的激烈竞争 宣告结束。这一新加密标准的问世将取代DES数据加密标准成为21卅纪保护国 家敏感信息的高级算法。3 AES算法研究现状分析目前对高级加密标准算法的研究主要集中在三个方面：设计原理、安全性能 分析和统计性能分析。设计原理方而主要研究算法在设计时所遵循的原则、算法 釆用的整体结构以及各组成部分的数学基础和性能。安全性能研究主要集中在分 析抵抗现有已知密码攻击方法上，主要包括强力攻击、差分密码分析、线性密码 分析、专用攻击和插值攻击。目前对差分密码分析和线性密码分析研究得比较深 入，对专用攻击主要集中在基本攻击原理上，对插值攻击的研究主要集中在寻找 算法的代数表示。统计性能主要是研究算法随机化数据的能力，冃前有关Rijndael 算法的统计性能方面的研究还较少，所见统计测试在测试项目的选择和测试数据 的构造上也尽相同，但大多数测试都基于NIST统计测试工具包进行。3.1 AES算法国内研究现状国内对Rijndael算法研究分析的热情不亚于国际同行。早在AES终选算法 确定之前，中国科学院软件研究所研究员吴文玲等人就深入分析了 Rijndael算法 的密钥生成过程，使用能量攻击对三种密钥长度的算法进行分析，攻击复分别为 267、299和2131,大大降低了 Rijndael密钥攻击的规模。信息工程大学的研究 牛李娜及其导师陈卫红教授通过研究q多项式的性质给出求解S盒代数表达式 一种简易的算法，具有可预先计算、操作简单的特点和一定的通用性，对曾祥勇 等提出的一类S盒进行了仿射等价划分，进一步明确了这些S盒间的相互关系。 国防科技大学博士冯国柱等人对Rijndael算法作了变动和改进，使新算法在不降 低抗差分攻击性能的情况下提高统计效果，并可部分抵抗Square攻击，代价是 牺牲少许密钥装填速度。北京理工大学胡辛征等人研究发现Rijndael算法S盒在 有限域GF(28)的迭代循环周期过短，仅有2、27、59、81、87等五种可能，并 设计了一种新的仿射变换加以改进，使有限域上所有元素的迭代循环周期达到最 大，即256。信息工程大学戚文峰等人调整Rijndael算变换的顺序，采用密 钥的变形形式，通过合理安排求取密钥的顺序，利用密钥相关性将五轮简化算法 的密钥穷尽量由原來的4X24()减少至IJ 240+232+216+9X28o在国内对Rijndael硬件研究除了对其硬件实现的优化设计之外，由于受有关 条件的限制，AISC的实现还未见诸报端。而对基于其他硬件的Rijndael实现己 经有了一定的研究，如曾毅使用Xilinx的FPGA Virtexll XC2V3000-4对Rijndael 密码算法进行了实现和验证，其采用一种优化的非流水线加密/解密数据路径， 同时提出了一种新的可配置的动态密钥调度结构，使得该设计支持128、192和 256比特的密钥，而且其设计可以配置Rijndael算法的四种工作模式。陈作新提 出“动态密码补位法”对算法进行补偿，应用于在要求密文长度与明文长度相等 的场合，以提高明文加密的安全性并应用于IC卡的关键数据的加密中。梅迎春 设计的高性能智能安全卡是基于AVR单片机、结合USB接口技术、采用Rinjdael 算法和分布式CA认证体制的一种硬件实现。沈启峰等给出了有限域加法和乘法 运算的优化的方法，为实现FPGA高速设计提供了设计思路。3. 2 AES算法国外研究现状从应征为侯选算法，到被选为终选算法，到最后被确定为AES标准，直至 现在，Rijndael算法一直经受着世界各国密码机构和专家的强化攻击。但是，冃 前尚未存在对完整Rijndael算法的成功攻击，只提出了几种对减少轮数化算法的 攻击方法。最有名的当数密码设计者自己提出的Square攻击，其主要思想是利 用第四轮字节替换前后平衡性的改变来猜测密钥字节，对128比特密钥下四到六 轮简化算法有效。ELI BIHAM和NATHAN KENER对四到六轮简化算法的Square攻击进行了 改进，攻击的时间复杂度降低一倍并认为如果把Rijndael算密钥的顺序颠倒 过来，攻击复杂度将还可降低28o Stefan Lucks利用密钥生成算法的弱点，将 Square攻击的密钥长度扩展到192和256比特的情况，用此方法攻击七轮简化算 法比穷尽搜索快。NIELS FERGUSON等人利用部分和技术将六轮Square攻击的 复杂度从272降到244并将之推广到七轮和八轮简化算法，展示密钥生成算法中 几个违背设计准则的特性，利用其慢扩散性设计了一个针对256比特密钥下九轮 简化算法的密钥相关攻击方案。HENRI GILBERT和MARINE MINIER利用由算 法本身推导出的某些局部函数之间的冲突特性对四到七轮简化算法进行了攻击。 JUNG HEE CHEON等人将五轮不可能差分攻击推广到六轮，虽然复朵度高于相 应的Squre攻击，但仍快于密钥穷尽搜索oJOAN DAEMEN和VINCENT RIJMEN 在文中研究AES候选算法在智能卡上实现时抵抗计时和能量攻击的情况，评估 这些算法抵抗这两种攻击的难度。FRANCOIS KOEUNE和JEAN-JACQUES QUISQUATER描述了一种针对Rijndael算法的计时攻击，展现了攻破一个粗心 的实现设计的过程，基本方法是对每个密钥数千次的测量。密码代数结构的任何弱点都将有利于密码分析新方案的设计。因此，在对简 化Rijndael算法进行攻击尝试的同时，人们也把相当多的精力集中到Rijndael算 法内部结构各种性质的研究上。NIELS FERGUSON等人给岀了 Rijndael算法一个直观而紧凑的代数表示形 式，但尚未有用此表达式进行攻击的例子。ERIC FILIOL将Rijndael算法的每一 输出比特看作以明文比特和密钥比特为变量的布尔函数fi(pl,p2,pn,kl,kn), 并用Mohius变换将之计算出来，观察其低次项(如单项式piki)的分布情况。通过 比较fi代数止规式与完全随机的布尔函数代数止规式的差异考察fi是否具有随 机特性结果发现Rijndael算法布尔函数的随机特性并不十分理想。Elad Barkan 和Eli Biharm通过替换Rijndael算法中的所有不变常量，如既约多项式、列混合 运算中的系数和S盒中的仿射变换等，产牛许多新的等价对偶密码，有平方对 偶、对数对偶和自对偶等数百种之多。一方面，对偶密码有其可利用之处，如通 过选择比原算法更快的对偶算法来优化密码速度，甚至加解密使用不同的对偶密 码;又如实现加解密时每次随机选择不同的密码以抵抗错谋攻击和能量攻击。另 一方面，由于对偶密码的结构也许更容易分析,可能会有助于施差分或线性攻击, 而对偶密码又可以很容易转地换成原算法，所以对偶密码的存在可能是Rijndael 算法一种潜在的威胁。2005年8月15日，加利福尼亚州萨尼维尔市Juniper网络公司宣布，采用 同时支持 3-DES 和 Rijndael 算法的 GigaScreen3 ASIC 的 Netscreen-5000 系列防火 墙和虚拟专网(VPN)系统产品，可以提供15Gbps的ASIC加速的VNP吞吐量。 但是，ASIC实现缺乏算法和参数更换的灵活性，而FPGA实现不但具有软件实 现的灵活性、成本效益以及算法更换能力，还具有ASIC实现的高效性和物理安 全性，随着研究的深入，基于FGPA的硬件实现向更高速、小而积的ASIC方向 在发展。随着经济社会的发展，无论是组织还是个人对于信息安全盒保密的要求都会 提高，密码产品的需求必然大热，密码理论在信息科学研究中地位肯定也会不断 增强。4 AES算法实现技术简介4.1软件实现AES算法在设计之初就将软件实现的高效性、灵活性作为一个目标。事实 证明，Rijndael算法在通用处理器上能获得相当不错的性能。4. 2硬件实现在虚拟专用网(VPN)和波分复用系统的光纤链路、视频加密、Internet高端路 由器等高速应用中，硬件实现才是最佳解决方案。硬件实现能确保加密算法及其 密钥扩展的物理安全，因为硬件实现通常不容易被外部攻击者接触或修改。加密 速度最大化和占用而积最小化的冃标可由专用集成电路(ASIC)和现场可编程门 阵列(FPGA)实现。ASIC实现是为给定算法专门设计的，速度快、效率高，在占 用面积和功耗方面具有优势。对于海量应用來说，ASIC解决方案具有最好的性 能价格比。硬件设计不同于软件设计，在硬件资源允许的范围内，应充分发挥其并行性 的特点，并且用硬件完成某算法的设计其时间是固定的，这一特点在一些应用中 有重要作用。AES算法硬件设计是应考虑适合多种不同硬件、处理器