加密算法s-box的分析與改進(jìn)

加密算法s-box的分析與改進(jìn)

aes（高級(jí)別的抗編碼標(biāo)準(zhǔn)）是指密鑰編碼技術(shù)，即密鑰編碼技術(shù)的高級(jí)加密標(biāo)準(zhǔn)，代表最新的編碼技術(shù)，也被廣泛用于現(xiàn)在的社會(huì)領(lǐng)域。它是一種對(duì)稱密鑰的加密算法,其密鑰長(zhǎng)度可達(dá)256bit,且用128bit分組加密和解密數(shù)據(jù)。S-box(substitutionbox)作為實(shí)現(xiàn)數(shù)據(jù)非線性置換的組件在AES密碼設(shè)計(jì)中有著重要地位,S-box為分組密碼算法提供混合層,同時(shí)對(duì)抵抗各種攻擊起關(guān)鍵性的作用。在對(duì)長(zhǎng)度為128bit的明文加密運(yùn)算中,S-box共用到160次,所以它的安全性直接影響到整個(gè)密碼的安全性。1在gf28上的非線性表示為保證整個(gè)密碼系統(tǒng)的安全性,以抵抗各種可能的攻擊,S-box在設(shè)計(jì)時(shí)考慮到差分密碼分析和線性密碼分析的要求。雖然S-box的設(shè)計(jì)原理是保密的,但它滿足4個(gè)方面的條件:(1)可逆變換;(2)輸入比特和輸出比特的線性組合之間的最大非平凡相關(guān)性極小化;(3)異或差分表中的最大非平凡值的極小化;(4)在GF(28)上的代數(shù)表示的復(fù)雜性。AES中S-box主要運(yùn)算是獨(dú)立地對(duì)狀態(tài)中的每個(gè)字節(jié)進(jìn)行非線性字節(jié)變換。具體有2個(gè)步驟:(1)求GF(28)有限域內(nèi)各元素的乘法逆元。aij代表狀態(tài)中的第i行第j列的一個(gè)字節(jié),aij-1則是aij在GF(28)上的乘法逆。將狀態(tài)中的每個(gè)字節(jié)aij看作GF(28)上的元素,映射到自己的乘法逆aij-1,0字節(jié)映射到它自身。(2)做仿射變換。將字節(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)。輸入比特的線性組合與輸出比特的線性組合之間的最大非平凡相關(guān)性是2-3,異或差分表的非平凡最大輸出差分概率是2-6,S-box具有抵抗線性攻擊和差分攻擊的能力。S-box變換S143,99:GF(28)→GF(28)后每個(gè)元的對(duì)應(yīng)值見表1。2aes的周期對(duì)GF(28)的每個(gè)元做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)迭代,對(duì)應(yīng)元重新回到3,形成了一個(gè)周期為59的循環(huán)迭代。同理,當(dāng)m為不同的元時(shí),得到下列循環(huán)迭代:{Sn143,99(143):n=1,2}={115,143},經(jīng)過2次迭代,對(duì)應(yīng)元回到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次迭代,對(duì)應(yīng)元回到97,周期為27。由以上分析可得,每個(gè)元只屬于2,27,59,81,87中的一個(gè)周期,最短周期為2,最長(zhǎng)周期為87,對(duì)于GF(28)的256個(gè)空間來說,周期太短。這就像DES(dataencryptionstandard,DES)算法的S-box迭代輸出不能遍歷所有的可能值,而導(dǎo)致有力的差分攻擊一樣。雖然AES加密算法的其他層可以掩蓋S-box迭代短周期的特點(diǎn),但是隨著技術(shù)的進(jìn)步和密碼破譯算法的發(fā)展,這種周期性的缺點(diǎn)可能被密碼分析所利用,AES的短周期一樣存在著差分攻擊的可能。所以,S-box的短周期性應(yīng)該被完善。3改進(jìn)的迭代循環(huá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)后的仿射變換。經(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所示。4以建立前懸的u型，方法計(jì)算s-box仿真S-box作為AES加密算法中唯一的非線性元件,其安全性能的好壞直接決定著整個(gè)分組密碼性能的好壞,一個(gè)良好的S-box能提高加密算法抵抗各種密碼分析攻擊的能力。本文對(duì)AES的S-box設(shè)計(jì)進(jìn)行了分析,指出其循環(huán)迭代輸出周期過短的特性,并且提出一種切實(shí)可行的方案,使得迭代周期擴(kuò)大到256整個(gè)空間,從而提高了算法的安全性。即{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次迭代,對(duì)應(yīng)元回到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次迭代,對(duì)應(yīng)元回到9,周期為87。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)上的仿射變換。迭代周期為{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