Rijndael優(yōu)化實現(xiàn)研究韋寶典劉東蘇王新梅(西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)國家重點實驗室西安710071)E-mail xmwang@xidian.edu.cn摘要Rijndael作為美國高級加密標(biāo)準(zhǔn)算法將在未來30年里代替DES在各領(lǐng)域得到廣泛應(yīng)用。與其安全性已經(jīng)并正在得到廣泛而全面的討論分析相比其優(yōu)化實現(xiàn)方面的研究則比較少見文章給出了Rijndael主要部件S盒、列變換及其逆運算以及整個圈變換的優(yōu)化及其原理,從運算單位、數(shù)據(jù)訪問時間和簡化矩陣運算等方面提高算法的實現(xiàn)效率。關(guān)鍵詞Rijndael AES S盒列變換優(yōu)化文章編號1002-8331-< 2002 )20-0004- -03文獻(xiàn)標(biāo)識碼 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!"作為美國高級加密標(biāo)準(zhǔn)叱(AES)算法在未來30所有值,反過來就是對數(shù)表。實現(xiàn)中要注意的是x乘是帶進(jìn)年里將代替使用了20多年的DES對聯(lián)邦政府敏感非機密信位"的左移}p x=(p>7)as| a| ama&m3))),其中((a )&m2X<1將4個字節(jié)的低7位同時左移-ag | a7| anansan2 as | au4|ays位u((u>>7)Xxm3)是各字節(jié)帶進(jìn)位的并行的x乘。圖1 Rijndael 狀態(tài)圖2 Rijndael 狀態(tài)轉(zhuǎn)置列變換的逆運算需要將每一列模乘一個特定的多項式d(x )=06x*+0d2x2+09x+0e(滿足d(x)(x )=01' ),對應(yīng)的矩在大多數(shù)高級編程語言(如C)中二維數(shù)組的存取是以行陣運算為:為順序進(jìn)行的,即存取完一行再存取下一行。因此如果按圖1「Oe0bOd09Tb形式存放數(shù)據(jù)則存取狀態(tài)的一列將對應(yīng)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所示則存取轉(zhuǎn)(((1+4+8))<2)(((1+8)%)<<1) .(6)置狀態(tài)的一行(對應(yīng)原狀態(tài)的一列)僅須1次行訪問行地址之需要進(jìn)行多次的倍乘運算使得解密速度大大慢于加密速后是連續(xù)的四個列地址其過程如下圖4所示。顯然存取效率度。若將(5式寫成如(7 )式的形式列變換逆運算就可以變得大大提高了。這里假設(shè)第5節(jié)也是在這樣的優(yōu)化之上實現(xiàn)的，很簡單。為了理解的方便仍以原算法中的形式進(jìn)行討論。計算機工程與應(yīng)用2002.20 5[abKab都是8比特字節(jié))對應(yīng)(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存取狀態(tài)的一行as | an| an3|ans ay ay auanoau| a2| an10a4| a2 a6 |asa| an|i5aasa|5圈變 換的優(yōu)化文獻(xiàn)[1]中給出用表實現(xiàn)圈變換的方案將整個圈變換集中圖5未換行 前的狀態(tài)圖6換行后的狀態(tài)到四個列運算中進(jìn)行,每個列運算都包含了S盒運算、行移位、列變換和圈密鑰加,如(9式所示。這樣有三列運算只須作3次查表和3次異或?qū)φ麄€狀eo;|「027)3~ 101 1態(tài)而言只需13次查表和13次異或運算。相對于(9成計算量e1i _)1|)2 |)3|有37.5%的減少代價是構(gòu)造To[ab]需要額外的256KB存儲空間。對分組長度為192、256比特的情況這種優(yōu)化不能直接使e2;|01 I用。如果將這兩種情況下的行移位量C3分別改為5和7并且Les,」J)3」01」L01.調(diào)換狀態(tài)的第二、四行位置,如圖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該式可用預(yù)先構(gòu)造的四個表T{[a]~T[a]快速實現(xiàn)(a為8比ao14a18ana|a6aoauasa2sa特字節(jié))-對每一 列只須作4次查表和4次異或運算:圖7調(diào)整后的192比特狀態(tài)圖8調(diào)整后的256比特狀態(tài)TS[a] 02-「S[a] 03T[a]=S[a]S[a} 026結(jié)束語| S[LS[a] 03文章研究Rijndael算法S盒、列混合及其逆變換和整個圈變換的優(yōu)化實現(xiàn)。在不改變算法本質(zhì)的前提下將算法的代數(shù)S[a] 03運算轉(zhuǎn)換成適應(yīng)硬件平臺的形式改變數(shù)據(jù)存放方式使之與硬T{[a]=|S[a] 02| S[a} 03件存取數(shù)據(jù)特點相符,從而以較小的空間代價換取速度上較大.S[alS[a]02.的提高。需要指出的是第二節(jié)給出的是S盒的求法實際應(yīng)用上式加法(即異或)具有交換律,可將第二項與第四項位置中會將求出的值存放于RAM中(占256字節(jié))直接加以使用;互換而不影響結(jié)果,這就有第三節(jié)以列為單位優(yōu)化矩陣運算,在以字節(jié)為單位的平臺上可eo; 1「02「01 :以構(gòu)造倍乘表D[a]=2a和三倍乘表η[a]=3a使得列變換運算僅01)1 |，0需進(jìn)行8次查表和12次異或,這樣運行效率也很高,代價僅為=S[a,]0+s[as.103 I512字節(jié)的存儲空間。(收稿日期2002年6月))2」L01Les;」「031「 S[ao}] 02+S[a,j-3] 01參考文獻(xiàn)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 )式分別對應(yīng)如圖5.6行移位后的狀態(tài)其中圖65.Stefan LuclHC N M H Gael under 192-bit and是圖5二、四行換位的結(jié)果。256-bit keys[C].In :The third Advanced Encryption Standard Candi-可以看到換行后的狀態(tài)中有三組連續(xù)的雙字節(jié)(16比特date Conference ,NIST 2000 215-229字和avay和ag以及an和a120每一組字都可-次性訪問6.N Ferguson J Kelsey B Schneier et al.Improved Cryptanalysis of Ri-到,在進(jìn)行如( 10)式的計算時，可以事先為之構(gòu)造一個表Tojndael[C].In Fast Software Encryption 2000 Springer LNCS6 2002.20 計算機工程與應(yīng)用