AES加密算法的Sbox設(shè)計(jì)分析及其改進(jìn)＊－

汪培芬

（淮安市廣播電視大學(xué) 信息工程系，江蘇 淮安 223002）

AES（advanced encryption standard，AES）加密算法即密碼學(xué)中的高級(jí)加密標(biāo)準(zhǔn)，代表著最新的編碼技術(shù)［1］，又稱Rijndael加密算法，已在現(xiàn)今社會(huì)各個(gè)領(lǐng)域中得到廣泛應(yīng)用。它是一種對(duì)稱密鑰的加密算法，其密鑰長度可達(dá)256bit，且用128bit分組加密和解密數(shù)據(jù)。S－box（substitution box）作為實(shí)現(xiàn)數(shù)據(jù)非線性置換的組件在AES密碼設(shè)計(jì)中有著重要地位，S－box為分組密碼算法提供混合層，同時(shí)對(duì)抵抗各種攻擊起關(guān)鍵性的作用。在對(duì)長度為128 bit的明文加密運(yùn)算中，S－box共用到160次，所以它的安全性直接影響到整個(gè)密碼的安全性［2］。

1 S－box設(shè)計(jì)分析

為保證整個(gè)密碼系統(tǒng)的安全性，以抵抗各種可能的攻擊，S－box在設(shè)計(jì)時(shí)考慮到差分密碼分析和線性密碼分析的要求。雖然S－box的設(shè)計(jì)原理是保密的，但它滿足4個(gè)方面的條件：①可逆變換；②輸入比特和輸出比特的線性組合之間的最大非平凡相關(guān)性極小化；③ 異或差分表中的最大非平凡值的極小化；④ 在GF（28）上的代數(shù)表示的復(fù)雜性。

AES中S－box主要運(yùn)算是獨(dú)立地對(duì)狀態(tài)中的每個(gè)字節(jié)進(jìn)行非線性字節(jié)變換。具體有2個(gè)步驟：① 求GF（28）有限域內(nèi)各元素的乘法逆元。aij代表狀態(tài)中的第i行第j列的一個(gè)字節(jié)，ai－j1則是aij在GF（28）上的乘法逆。將狀態(tài)中的每個(gè)字節(jié)aij看作GF（28）上的元素，映射到自己的乘法逆ai－j1，0字節(jié)映射到它自身。② 做仿射變換。將字節(jié)做（GF（2）上可逆的）仿射變換，

即

為了便于敘述，給出GF（28）中表示方法

在AES中取

仿射變換對(duì)為（143，99）。常量（01100011）2的選擇確保了S－box沒有不動(dòng)點(diǎn)S－box（a）＝a和對(duì)立不動(dòng)點(diǎn)S－box（a）＝。輸入比特的線性組合與輸出比特的線性組合之間的最大非平凡相關(guān)性是2－3，異或差分表的非平凡最大輸出差分概率是2－6，S－box具有抵抗線性攻擊和差分攻擊的能力。

S－box變換S143，99：GF（28）→GF（28）后每個(gè)元的對(duì)應(yīng)值見表1。

表1 S－box對(duì)應(yīng)值表Table 1 Corresponding S－box value table

2 S－box的循環(huán)迭代周期分析

對(duì)GF（28）的每個(gè)元做 S－box循環(huán)迭代，即，m＝0，1，…，255，n為循環(huán)迭代次數(shù)。例如，若m為3，那么：n＝ 1，2，…，59｝＝ ｛123，33，253，84，32，183，169，211，102，51，195，46，49，199，198，180，141，93，76，41，165，6，111，168，194，37，63，117，157，94，88，106，2，119，245，230，142，25，212，72，82，0，99，251，15，118，56，7，197，166，36，54，5，107，127，210，181，213，3｝，由此可見，經(jīng)過 59 次S143，99：GF（28）→GF（28）的循環(huán)迭代，對(duì)應(yīng)元重新回到3，形成了一個(gè)周期為59的循環(huán)迭代。

同理，當(dāng)m為不同的元時(shí)，得到下列循環(huán)迭代：，經(jīng)過2次迭代，對(duì)應(yīng)元回到143，周期為2。n＝1，2，…，27｝＝ ｛239，223，158，11，43，241，161，50，35，38，247，104，69，110，159，219，185，86，177，200，232，155，20，250，45，216，97｝，經(jīng)過27次迭代，對(duì)應(yīng)元回到97，周期為27。＝ ｛124，16，202，116，146，79，132，95，207，138，126，243，13，215，14，171，98，170，172，145，129，12，254，187，234，135，23，240，140，100，67，26，162，58，128，205，189，122，218，87，91，57，18，201，221，193，120，188，101，77，227，17，130，19，125，255，22，71，160，224，225，248，65，131，236，206，139，61，39，204，75，179，109，60，235，233，30，114，64，9，1｝，經(jīng)過81次迭代，對(duì)應(yīng)元回到1，周期為81。＝ ｛103，133，151，136，196，28，156，222，29，164，73，59，226，152，70，90，190，174，228，105，249，153，238，40，52，24，173，149，42，229，217，53，150，144，96，208，112，81，209，62，178，55，154，184，108，80，83，237，85，252，176，231，148，34，147，220，134，68，27，175，121，182，78，47，21，89，203，31，192，186，244，191，8，48，4，242，137，167，92，74，214，246，66，44，113，163，9｝，經(jīng) 過87次迭代，對(duì)應(yīng)元回到9，周期為87。

由以上分析可得，每個(gè)元只屬于2，27，59，81，87中的一個(gè)周期，最短周期為2，最長周期為87，對(duì)于GF（28）的256個(gè)空間來說，周期太短。這就像DES（data encryption standard，DES）算法的S－box迭代輸出不能遍歷所有的可能值，而導(dǎo)致有力的差分攻擊一樣。雖然AES加密算法的其他層可以掩蓋S－box迭代短周期的特點(diǎn)，但是隨著技術(shù)的進(jìn)步和密碼破譯算法的發(fā)展，這種周期性的缺點(diǎn)可能被密碼分析所利用，AES的短周期一樣存在著差分攻擊的可能。所以，S－box的短周期性應(yīng)該被完善［4］。

3 S－box的改進(jìn)方案

針對(duì)S－box存在迭代短周期的問題，本文提出了改進(jìn)的方案。

為了得到所有可能值的S－box的迭代輸出，就要求每個(gè)元在GF（28）空間中的迭代循環(huán)周期數(shù)都達(dá)到GF（28）空間的容量256，即在GF（28）空間中所有元只屬于一個(gè)迭代循環(huán)。本文改進(jìn)設(shè)計(jì)，得到如下改進(jìn)后的仿射變換。

m（x）＝x8＋1不變，

改進(jìn)取即取u＝155，v＝154，用仿射變換對(duì)（155，154）替換原來S－box的仿射變換對(duì)（143，99），先求乘法逆元后進(jìn)行仿射變換。

（1）將字節(jié)看作GF（28）上的元素，映射到自己的乘法逆，0字節(jié)映射到它自身。

（2）將字節(jié)做GF（2）上的仿射變換。

經(jīng)過256次S′n155，154：GF（28）→GF（28）的循環(huán)迭代，對(duì)應(yīng)元重新回到9，形成了一個(gè)周期為256的循環(huán)迭代，遍歷了空間中的每一個(gè)值，經(jīng)過測(cè)試，其他元循環(huán)迭代周期也為256。

改進(jìn)的S－box變換后對(duì)應(yīng)值如表2所示。

表2 改進(jìn)的S－box替換表Table 2 Improved S－box substitution table

4 結(jié)束語

S－box作為AES加密算法中唯一的非線性元件，其安全性能的好壞直接決定著整個(gè)分組密碼性能的好壞，一個(gè)良好的S－box能提高加密算法抵抗各種密碼分析攻擊的能力。本文對(duì)AES的S－box設(shè)計(jì)進(jìn)行了分析，指出其循環(huán)迭代輸出周期過短的特性，并且提出一種切實(shí)可行的方案，使得迭代周期擴(kuò)大到256整個(gè)空間，從而提高了算法的安全性。

［1］ 趙雪梅.AES加密算法的實(shí)現(xiàn)及應(yīng)用［J］.常熟理工學(xué)院學(xué)報(bào)，2010，24（2）：105－110.

［2］ 吳文玲，馮登國，張文.分組密碼的設(shè)計(jì)與分析［M］.北京：清華大學(xué)出版社，2009.

［3］ 王衍波.AES的結(jié)構(gòu)及其S－box分析［J］.解放軍理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2002，3（3）：13－17.

［4］ BASSHAM L.NIST efficiency testing of ANSI Cimp lamentations of round 2AES candidate algorithms for the advanced encryption standard［C］／／The Third AES Candidate Conference.Gaithersburg，MD：the National Institute of Standards and Technology，2000：136－148.

［5］ 孫愛娟.基于AES加密算法的改進(jìn)及其 MATLAB實(shí)現(xiàn)［D］.哈爾濱：哈爾濱理工大學(xué)，2009.