Rijndael优化实现研究

Rijndael优化实现研究韦宝典刘东苏王新梅(西安电子科技大学综合业务网国家重点实验室西安710071)E-mail xmwang@xidian.edu.cn摘要Rijndael作为美国高级加密标准算法将在未来30年里代替DES在各领域得到广泛应用。与其安全性已经并正在得到广泛而全面的讨论分析相比其优化实现方面的研究则比较少见文章给出了Rijndael主要部件S盒、列变换及其逆运算以及整个圈变换的优化及其原理,从运算单位、数据访问时间和简化矩阵运算等方面提高算法的实现效率。关键词Rijndael AES S盒列变换优化文章编号1002-8331-< 2002 )20-0004- -03文献标识码 A中图分类 号TP309The Optimized Implementation of RijndaelWei Baodian Liu Dongsu Wang Xinmei( National Key Lab of Integrated Service Networks ,Xidian Univ. ,Xi'an 710071 )Abstract: As the Advanced Encryption Standard of United States Rijndael will be used to replace DES for the follow-ing 30 years.It will of course have a wide use in various aspects.Its security has been discussed in depth while the op-timization in its implementation are studied much less.It gives the optimization and the corresponding principle of thekey components such as S box ,MixColumn and its inverse as well as that of the whole round transformation.Keywords : Rijndael AES S box MixColumn Optimization1引言这两个表。g"=01' g'=03'用递归式g*"=g( x+1何求得幂表的Rijndal!"作为美国高级加密标准叱(AES)算法在未来30所有值,反过来就是对数表。实现中要注意的是x乘是带进年里将代替使用了20多年的DES对联邦政府敏感非机密信位"的左移}p x=(p>7)as| a| ama&m3))),其中((a )&m2X<1将4个字节的低7位同时左移-ag | a7| anansan2 as | au4|ays位u((u>>7)Xxm3)是各字节带进位的并行的x乘。图1 Rijndael 状态图2 Rijndael 状态转置列变换的逆运算需要将每一列模乘一个特定的多项式d(x )=06x*+0d2x2+09x+0e(满足d(x)(x )=01' ),对应的矩在大多数高级编程语言(如C)中二维数组的存取是以行阵运算为:为顺序进行的,即存取完一行再存取下一行。因此如果按图1「Oe0bOd09Tb形式存放数据则存取状态的一列将对应4次行访问其过程090e Ob 0d|b,(5)如图3所示(图中只画出两次行访问)..aOd09OeOb124,」Lob 0d09 0e b,、+存储器访问-存储器访问一 4_行访问时钟如果按列变换思想将(5成写成:「b。7「b,]「b2] 「b列访问时钟a|b.,b2| .b3 bXC 行地址 X列地址X间隔入行地址X列地址X回隔X。=e。+b, d +9||a|b2| 63b0 |b中国煤化工=( 2+4+8 )>+((( 1+2+8》)<<3 )+如果以.MYHCNMHG图2所示则存取转(((1+4+8))<2)(((1+8)%)<<1) .(6)置状态的一行(对应原状态的一列)仅须1次行访问行地址之需要进行多次的倍乘运算使得解密速度大大慢于加密速后是连续的四个列地址其过程如下图4所示。显然存取效率度。若将(5式写成如(7 )式的形式列变换逆运算就可以变得大大提高了。这里假设第5节也是在这样的优化之上实现的，很简单。为了理解的方便仍以原算法中的形式进行讨论。计算机工程与应用2002.20 5[abKab都是8比特字节)对应(10)式的第--项。存储器访问存储器访问卉储器访问存储器访问「S[a] 02+S[b] 01| S[a] 01+S[B] 01行访问时钟To[ab]=S[a] 01+S[b] 03列访问时钟LS[a} 03+S[b] 02.二X行地址X列地址入列地址不列地址X_列地址 X不御asasanaa4aga12图4存取状态的一行as | an| an3|ans ay ay auanoau| a2| an10a4| a2 a6 |asa| an|i5aasa|5圈变 换的优化文献[1]中给出用表实现圈变换的方案将整个圈变换集中图5未换行 前的状态图6换行后的状态到四个列运算中进行,每个列运算都包含了S盒运算、行移位、列变换和圈密钥加,如(9式所示。这样有三列运算只须作3次查表和3次异或对整个状eo;|「027)3~ 101 1态而言只需13次查表和13次异或运算。相对于(9成计算量e1i _)1|)2 |)3|有37.5%的减少代价是构造To[ab]需要额外的256KB存储空间。对分组长度为192、256比特的情况这种优化不能直接使e2;|01 I用。如果将这两种情况下的行移位量C3分别改为5和7并且Les,」J)3」01」L01.调换状态的第二、四行位置,如图78所示则计算量分别降低20.8%、21.8% !)1|k,;|+S[asjr303 [2,|(9)。1 aagapanan2)84 asa2 16822 ay23 a37| an als ayl ag a3 ara ansa1gas azs|aan3|ara21aa5 ay a3| an| a2)| aga0 a该式可用预先构造的四个表T{[a]~T[a]快速实现(a为8比ao14a18ana|a6aoauasa2sa特字节)-对每一 列只须作4次查表和4次异或运算:图7调整后的192比特状态图8调整后的256比特状态TS[a] 02-「S[a] 03T[a]=S[a]S[a} 026结束语| S[LS[a] 03文章研究Rijndael算法S盒、列混合及其逆变换和整个圈变换的优化实现。在不改变算法本质的前提下将算法的代数S[a] 03运算转换成适应硬件平台的形式改变数据存放方式使之与硬T{[a]=|S[a] 02| S[a} 03件存取数据特点相符,从而以较小的空间代价换取速度上较大.S[alS[a]02.的提高。需要指出的是第二节给出的是S盒的求法实际应用上式加法(即异或)具有交换律,可将第二项与第四项位置中会将求出的值存放于RAM中(占256字节)直接加以使用;互换而不影响结果,这就有第三节以列为单位优化矩阵运算,在以字节为单位的平台上可eo; 1「02「01 :以构造倍乘表D[a]=2a和三倍乘表η[a]=3a使得列变换运算仅01)1 |，0需进行8次查表和12次异或,这样运行效率也很高,代价仅为=S[a,]0+s[as.103 I512字节的存储空间。(收稿日期2002年6月))2」L01Les;」「031「 S[ao}] 02+S[a,j-3] 01参考文献S[ao} 01+Sa,n.} 011J Daemon ,V Rijmen.AES proposal Rijndael.Version 2 ,1999SIao] 01+S[a,.s31 032.National Institute of Standard and Technology .Advanced Encryption01 」L的,」[S[ao} 03+S[a,-31 02Standard[S].FIPS197 2001-113.Henri Gilbert ,Marine Minier.A ollisin atack on 7 rounds of Rijn-)1 1「0|hdaeI[C].In :The third Advanced Encryption Standard Candidate Con-+S[azm-2”01的,( 10)ference .NIST ,2000 230-2414.Eli Biham Nathan. Kellery Crvntanalvsis. nf Reduced Variants of Ri-jndelLhttp;中国煤化工2/conf3/ aes3papers.html(9 )( 10 )式分别对应如图5.6行移位后的状态其中图65.Stefan LuclHC N M H Gael under 192-bit and是图5二、四行换位的结果。256-bit keys[C].In :The third Advanced Encryption Standard Candi-可以看到换行后的状态中有三组连续的双字节(16比特date Conference ,NIST 2000 215-229字和avay和ag以及an和a120每一组字都可-次性访问6.N Ferguson J Kelsey B Schneier et al.Improved Cryptanalysis of Ri-到,在进行如( 10)式的计算时，可以事先为之构造一个表Tojndael[C].In Fast Software Encryption 2000 Springer LNCS6 2002.20 计算机工程与应用