加密算法s-box的分析與改進

加密算法s-box的分析與改進

aes（高級別的抗編碼標準）是指密鑰編碼技術，即密鑰編碼技術的高級加密標準，代表最新的編碼技術，也被廣泛用于現(xiàn)在的社會領域。它是一種對稱密鑰的加密算法,其密鑰長度可達256bit,且用128bit分組加密和解密數(shù)據(jù)。S-box(substitutionbox)作為實現(xiàn)數(shù)據(jù)非線性置換的組件在AES密碼設計中有著重要地位,S-box為分組密碼算法提供混合層,同時對抵抗各種攻擊起關鍵性的作用。在對長度為128bit的明文加密運算中,S-box共用到160次,所以它的安全性直接影響到整個密碼的安全性。1在gf28上的非線性表示為保證整個密碼系統(tǒng)的安全性,以抵抗各種可能的攻擊,S-box在設計時考慮到差分密碼分析和線性密碼分析的要求。雖然S-box的設計原理是保密的,但它滿足4個方面的條件:(1)可逆變換;(2)輸入比特和輸出比特的線性組合之間的最大非平凡相關性極小化;(3)異或差分表中的最大非平凡值的極小化;(4)在GF(28)上的代數(shù)表示的復雜性。AES中S-box主要運算是獨立地對狀態(tài)中的每個字節(jié)進行非線性字節(jié)變換。具體有2個步驟:(1)求GF(28)有限域內(nèi)各元素的乘法逆元。aij代表狀態(tài)中的第i行第j列的一個字節(jié),aij-1則是aij在GF(28)上的乘法逆。將狀態(tài)中的每個字節(jié)aij看作GF(28)上的元素,映射到自己的乘法逆aij-1,0字節(jié)映射到它自身。(2)做仿射變換。將字節(jié)做(GF(2)上可逆的)仿射變換,為了便于敘述,給出GF(28)中表示方法在AES中取仿射變換對為(143,99)。常量(01100011)2的選擇確保了S-box沒有不動點S-box(a)=a和對立不動點。輸入比特的線性組合與輸出比特的線性組合之間的最大非平凡相關性是2-3,異或差分表的非平凡最大輸出差分概率是2-6,S-box具有抵抗線性攻擊和差分攻擊的能力。S-box變換S143,99:GF(28)→GF(28)后每個元的對應值見表1。2aes的周期對GF(28)的每個元做S-box循環(huán)迭代,即Sk143,99(m),m=0,1,…,255,n為循環(huán)迭代次數(shù)。例如,若m為3,那么{Sn143,99(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次S:GF(28)→GF(28143,99)的循環(huán)迭代,對應元重新回到3,形成了一個周期為59的循環(huán)迭代。同理,當m為不同的元時,得到下列循環(huán)迭代:{Sn143,99(143):n=1,2}={115,143},經(jīng)過2次迭代,對應元回到143,周期為2。{Sn143,99(97):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次迭代,對應元回到97,周期為27。由以上分析可得,每個元只屬于2,27,59,81,87中的一個周期,最短周期為2,最長周期為87,對于GF(28)的256個空間來說,周期太短。這就像DES(dataencryptionstandard,DES)算法的S-box迭代輸出不能遍歷所有的可能值,而導致有力的差分攻擊一樣。雖然AES加密算法的其他層可以掩蓋S-box迭代短周期的特點,但是隨著技術的進步和密碼破譯算法的發(fā)展,這種周期性的缺點可能被密碼分析所利用,AES的短周期一樣存在著差分攻擊的可能。所以,S-box的短周期性應該被完善。3改進的迭代循環(huán)針對S-box存在迭代短周期的問題,本文提出了改進的方案。為了得到所有可能值的S-box的迭代輸出,就要求每個元在GF(28)空間中的迭代循環(huán)周期數(shù)都達到GF(28)空間的容量256,即在GF(28)空間中所有元只屬于一個迭代循環(huán)。本文改進設計,得到如下改進后的仿射變換。經(jīng)過256次S′n155,154:GF(28)→GF(28)的循環(huán)迭代,對應元重新回到9,形成了一個周期為256的循環(huán)迭代,遍歷了空間中的每一個值,經(jīng)過測試,其他元循環(huán)迭代周期也為256。改進的S-box變換后對應值如表2所示。4以建立前懸的u型，方法計算s-box仿真S-box作為AES加密算法中唯一的非線性元件,其安全性能的好壞直接決定著整個分組密碼性能的好壞,一個良好的S-box能提高加密算法抵抗各種密碼分析攻擊的能力。本文對AES的S-box設計進行了分析,指出其循環(huán)迭代輸出周期過短的特性,并且提出一種切實可行的方案,使得迭代周期擴大到256整個空間,從而提高了算法的安全性。即{Sn143,99(1):n=1,2,…,81}={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次迭代,對應元回到1,周期為81。{Sn143,99(9):n=1,2,…,87}={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次迭代,對應元回到9,周期為87。m(x)=x8+1不變,改進取即取u=155,v=154,用仿射變換對(155,154)替換原來S-box的仿射變換對(143,99),先求乘法逆元后進行仿射變換。(1)將字節(jié)看作GF(28)上的元素,映射到自己的乘法逆,0字節(jié)映射到它自身。(2)將字節(jié)做GF(2)上的仿射變換。迭代周期為{S′n155,154(9):n=1,2,…,256}={107,131,1,173,175,223,81,65,82,113,17,72,98,219,84,50,28,101,85,160,185,10,242,182,123,40,251,231,181,41,77,151,172,199,166,90,18,48,25,51,212,39,66,138,153,53,129,201,249,23,24,157,218,16,30,33,186,112,76,248,237,36,207,152,171,128,88,80,120,38,94,134,159,165,45,139,49,188,198,246,195,190,179,22,177,42,203,70,178,213,95,108,86,132,192,122,191,161,167,238,226,13,29,87,168,206,130,254,96,91,89,4,44,15,73,109,43,2,83,27,169,117,127,111,239,205,60,71,63,103,14,193,197,99,230,240,196,104,133,155,184,12,148,6,34,243,211,232,35,110,75,176,255,140,220,32,216,174,209,31,250,144,180,222,114,247,100,217,225,200,105,210,236,118,67,52,0,154,78,164,61,116,233,92,19,183,245,229,145,102,189,241,37,5,74,7,136,146,97,47,162,119,106,69,56,55,5