跳转到内容

高级加密标准

本页使用了标题或全文手工转换
维基百科,自由的百科全书
AES
SubBytes是AES演算法四步骤之一。
概述
设计者Vincent Rijmen英语Vincent RijmenJoan Daemen英语Joan Daemen
首次发布1998年
衍生自Square英语Square (cipher)
继承算法Anubis英语Anubis (cipher)Grand Cru英语Grand Cru (cipher)Kalyna英语Kalyna (cipher)
密码细节
密钥长度128、192或者256位元[a]
分组长度128位元[b]
结构置换排列网络
重复回数10, 12或14(视密钥长度而定)
最佳公开破解
关联密码攻击英语Related-key attack可以破解9个加密回圈/256位元(密钥)的AES。另外选择明文攻击可以破解8个加密回圈,192或256位元(密钥)的AES,或7个加密回圈、128位元(密钥)的AES。(Ferguson et al., 2000)

进阶加密标准(英语:Advanced Encryption Standard缩写AES),又称Rijndael加密法荷兰语发音:[ˈrɛindaːl],音似英文的“Rhine doll”),是美国联邦政府采用的一种区块加密标准。这个标准用来替代原先的DES,已经被多方分析且广为全世界所使用。经过五年的甄选流程,进阶加密标准由美国国家标准与技术研究院(NIST)于2001年11月26日发布于FIPS PUB 197,并在2002年5月26日成为有效的标准。现在,进阶加密标准已然成为对称密钥加密中最流行的演算法之一。

该演算法为比利时密码学家Joan Daemen和Vincent Rijmen所设计,结合两位作者的名字,以Rijndael为名投稿进阶加密标准的甄选流程。

沿革

Rijndael是由Daemen和Rijmen早期所设计的Square英语Square (cipher)改良而来;而Square则是由SHARK发展而来。

不同于它的前任标准DES,Rijndael使用的是代换-置换网络,而非Feistel架构

密码说明

严格地说,AES和Rijndael加密法并不完全一样(虽然在实际应用中两者可以互换),因为Rijndael加密法可以支援更大范围的区块密钥长度:AES的区块长度固定为128位元,密钥长度则可以是128,192或256位元;而Rijndael使用的密钥和区块长度均可以是128,192或256位元。加密过程中使用的密钥是由Rijndael密钥生成方案产生。

大多数AES计算是在一个特别的有限域完成的。

AES加密过程是在一个4×4的位元组矩阵上运作,这个矩阵又称为“体(state)”,其初值就是一个明文区块(矩阵中一个元素大小就是明文区块中的一个Byte)。(Rijndael加密法因支援更大的区块,其矩阵的“列数(Row number)”可视情况增加)加密时,各轮AES加密回圈(除最后一轮外)均包含4个步骤:

  1. AddRoundKey矩阵中的每一个位元组都与该次回合金钥英语Key schedule(round key)做XOR运算;每个子密钥由密钥生成方案产生。
  2. SubBytes—透过一个非线性的替换函数,用查找表的方式把每个字节替换成对应的字节。
  3. ShiftRows—将矩阵中的每个横列进行循环式移位。
  4. MixColumns—为了充分混合矩阵中各个直行的操作。这个步骤使用线性转换来混合每行内的四个字节。最后一个加密回圈中省略MixColumns步骤,而以另一个AddRoundKey取代。

AddRoundKey步骤

AddRoundKey步骤中,将每个状态中的位元组与该回合金钥做异或(⊕)。

AddRoundKey步骤,回合金钥将会与原矩阵合并。在每次的加密回圈中,都会由主密钥产生一把回合金钥(透过Rijndael密钥生成方案产生),这把金钥大小会跟原矩阵一样,以与原矩阵中每个对应的位元组作异或(⊕)加法。

SubBytes步骤

SubBytes步骤中,矩阵中各字节被固定的8位查找表中对应的特定字节所替换,S; bij = S(aij.

SubBytes步骤中,矩阵中的各字节透过一个8位元的S-box进行转换。这个步骤提供了加密法非线性的变换能力。S-box上的乘法反元素有关,已知具有良好的非线性特性。为了避免简单代数性质的攻击,S-box结合了乘法反元素及一个可逆的仿射变换矩阵建构而成。此外在建构S-box时,刻意避开了不动点反不动点英语opposite fixed point,即以S-box替换字节的结果会相当于错排的结果。Rijndael S-box英语Rijndael S-box条目有针对S-box的详细描述。

ShiftRows步骤

ShiftRows步骤中,矩阵中每一列的各个位元组循环向左方位移。位移量则随著列数递增而递增。

ShiftRows描述矩阵的行操作。在此步骤中,每一行都向左循环位移某个偏移量。在AES中(区块大小128位元),第一行维持不变,第二行里的每个位元组都向左循环移动一格。同理,第三行及第四行向左循环位移的偏移量就分别是2和3。128位元和192位元的区块在此步骤的循环位移的模式相同。经过ShiftRows之后,矩阵中每一竖列,都是由输入矩阵中的每个不同列中的元素组成。Rijndael演算法的版本中,偏移量和AES有少许不同;对于长度256位元的区块,第一行仍然维持不变,第二行、第三行、第四行的偏移量分别是1位元组、2位元组、3位元组。除此之外,ShiftRows操作步骤在Rijndael和AES中完全相同。

MixColumns步骤

MixColumns步骤中,每个直列都在modulo 之下,和一个固定多项式c(x)作乘法。

MixColumns步骤,每一列的四个位元组透过线性变换互相结合。每一列的四个元素分别当作的系数,合并即为中的一个多项式,接著将此多项式和一个固定的多项式在模下相乘。此步骤亦可视为Rijndael有限域英语Finite field arithmetic之下的矩阵乘法。MixColumns函数接受4个位元组的输入,输出4个位元组,每一个输入的位元组都会对输出的四个位元组造成影响。因此ShiftRowsMixColumns两步骤为这个密码系统提供了扩散性英语diffusion(cryptograohy)

以下条目有对MixColumns更加详细的描述:Rijndael mix columns英语Rijndael mix columns

加密演算法优化

使用32或更多位元定址的系统,可以事先对所有可能的输入建立对应表,利用查表来实作SubBytesShiftRowsMixColumns步骤以达到加速的效果。这么作需要产生4个表,每个表都有256个格子,一个格子记载32位元的输出;约占去4KB(4096位元组)记忆体空间,即每个表占去1KB的记忆体空间。如此一来,在每个加密回圈中,只需要查16次表,作12次32位元的XOR运算,以及AddRoundKey步骤中4次32位元XOR运算。若使用的平台记忆体空间不足4KB,也可以利用循环交换的方式一次查一个256格32位元的表。

然而,实际实作中应避免使用这样的对应表,否则可能因为产生快取命中与否的差别而使旁道攻击成为可能。

安全性

截至2006年,针对AES唯一的成功攻击是旁道攻击社会工程学攻击。美国国家安全局审核了所有的参与竞选AES的最终入围者(包括Rijndael),认为他们均能够满足美国政府传递非机密文件的安全需要。2003年6月,美国政府宣布AES可以用于加密机密文件:

The design and strength of all key lengths of the AES algorithm(i.e., 128, 192 and 256)are sufficient to protect classified information up to the SECRET level. TOP SECRET information will require use of either the 192 or 256 key lengths. The implementation of AES in products intended to protect national security systems and/or information must be reviewed and certified by NSA prior to their acquisition and use.[1]

(译:AES加密演算法(使用128,192,和256位元密钥的版本)的安全性,在设计结构及密钥的长度上俱已到达保护机密资讯的标准。最高机密资讯的传递,则至少需要192或256位元的密钥长度。用以传递国家安全资讯的AES实作产品,必须先由国家安全局审核认证,方能被发放使用。)

这标志着,由美国国家安全局NSA批准在最高机密资讯上使用的加密系统首次可以被公开使用。许多大众化产品只使用128位元密钥当作预设值;由于最高机密文件的加密系统必须保证数十年以上的安全性,故推测NSA可能认为128位元太短,才以更长的密钥长度为最高机密的加密保留了安全空间。

通常破解一个区块加密系统最常见的方式,是先对其较弱版本(加密回圈次数较少)尝试各种攻击。AES中128位元密钥版本有10个加密回圈,192位元密钥版本有12个加密回圈,256位元密钥版本则有14个加密回圈。至2006年为止,最著名的攻击是针对AES 7次加密回圈的128位元密钥版本,8次加密回圈的192位元密钥版本,和9次加密回圈的256位元密钥版本所作的攻击。[2]

由于已遭破解的弱版的AES,其加密回圈数和原本的加密回圈数相差无几,有些密码学家开始担心AES的安全性:要是有人能将该著名的攻击加以改进,这个区块加密系统就会被破解。在密码学的意义上,只要存在一个方法,比穷举法还要更有效率,就能被视为一种“破解”。故一个针对AES 128位元密钥的攻击若“只”需要2120计算复杂度(少于穷举法2128),128位元密钥的AES就算被破解了;即便该方法在目前还不实用。从应用的角度来看,这种程度的破解依然太不切实际。最著名的暴力攻击法distributed.net英语distributed.net针对64位元密钥RC5所作的攻击。

其他的争议则著重于AES的数学结构。不像其他区块加密系统,AES具有相当井然有序的代数结构。[3]虽然相关的代数攻击尚未出现,但有许多学者认为,把安全性建立于未经透彻研究过的结构上是有风险的。Ferguson,Schroeppel和Whiting因此写道:“...我们很担心Rijndael演算法应用在机密系统上的安全性。”[4]

2002年,Nicolas Courtois英语Nicolas CourtoisJosef Pieprzyk英语Josef Pieprzyk发表名为XSL攻击英语XSL attack的理论性攻击,试图展示AES一个潜在的弱点。但该攻击的数学分析有点问题,推测应是作者的计算有误。因此,这种攻击法是否对AES奏效,仍是未解之谜。就现阶段而言,XSL攻击AES的效果不十分显著,故将之应用于实际情况的可能性并不高。

旁道攻击

旁道攻击,又称旁路攻击、侧信道攻击,是一种基于从密码系统的物理实现中获取的信息的攻击方式。它不攻击加密算法本身,而是攻击那些基于不安全系统(会在不经意间泄漏资讯)上的加密系统。

2005年4月,D.J. Bernstein英语D.J. Bernstein公布了一种缓存时序攻击法,他以此破解了一个装载OpenSSL AES加密系统的客户伺服器[5]。为了设计使该伺服器公布所有的时序资讯,攻击算法使用了2亿多条筛选过的明码。对于需要多个跳跃的国际互联网而言,这样的攻击方法并不实用[6]Bruce Schneier称此攻击为“好的时序攻击法”[7]

2005年10月,Eran Tromer页面存档备份,存于互联网档案馆)和另外两个研究员发表了一篇论文,展示了数种针对AES的缓存时序攻击法[8]

注释

  1. ^ 密码长度128, 160, 192, 224,与256位元为Rijndael演算法所支援,然而只有128, 192,与256位元长度密码为AES标准所明定。
  2. ^ 区块长度128, 160, 192, 224,与256位元为Rijndael演算法所支援,不过只有128位元区块长度为AES标准所明定。

参考文献

引用

  1. ^ 存档副本 (PDF). [2006-12-25]. (原始内容 (PDF)存档于2007-09-27). 
  2. ^ Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner, and Doug Whiting, Improved Cryptanalysis of Rijndael, Fast Software Encryption, 2000 pp213–230 [1]页面存档备份,存于互联网档案馆
  3. ^ 存档副本. [2006-12-25]. (原始内容存档于2009-01-31). 
  4. ^ Niels Ferguson, Richard Schroeppel, Doug Whiting. A simple algebraic representation of Rijndael. Proceedings of Selected Areas in Cryptography, 2001, Lecture Notes in Computer Science. Springer Verlag: pp. 103–111. 2001 [2006-10-06]. (原始内容 (PDF/PostScript)存档于2006-11-04). 
  5. ^ Daniel J. Bernstei. Cache-timing attacks on AES (PDF). Citeseer. 2005年4月 [2011-05-16]. (原始内容 (PDF)存档于2011-06-07). 
  6. ^ Lou Scheffer. Successful remote AES key extraction. 2005-04-17 [2011-05-16]. (原始内容存档于2011-11-06). 
  7. ^ Bruce Schneier. AES Timing Attack. 2005-05-17 [2011-05-16]. (原始内容存档于2007-02-12). 
  8. ^ Eran Tromer , Dag Arne Osvik and Adi Shamir. Efficient Cache Attacks on AES, and Countermeasures (PDF). Journal of cryptology. 2010, 23 (1): 37–71. 

书目

  • Nicolas Courtois, Josef Pieprzyk, "Cryptanalysis of Block Ciphers with Overdefined Systems of Equations". pp267–287, ASIACRYPT 2002.
  • Joan Daemen, Steve Borg and Vincent Rijmen, "The Design of Rijndael: AES - The Advanced Encryption Standard." Springer-Verlag, 2002. ISBN 3-540-42580-2.

外部链接

实现

参见