Rijndael優(yōu)化實(shí)現研究

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