指數(shù)域上的aes算法

1指數(shù)域和線性世界空間下的密碼分析自提出標(biāo)準(zhǔn)dea的文件以來(lái)，研究dea的方法一直在進(jìn)行。例如，文件攻擊減少了輪數(shù)的aes，文件跟蹤了aes加密過(guò)程中比特模型的發(fā)展，文件試圖將aes的安全性等于任何時(shí)代的計(jì)算難度，并在文獻(xiàn)中討論了所謂的xss攻擊。盡管評(píng)估專家的結(jié)果表明，dea的分析并沒(méi)有結(jié)束。因?yàn)槊荑€學(xué)的一項(xiàng)重要任務(wù)是持續(xù)分析每個(gè)實(shí)際密碼，并探索潛在的薄弱環(huán)節(jié)。直到密碼退役。在密碼學(xué)實(shí)踐中,專家的論證是建立在某些前提假定之下的,比如僅考慮已知的攻擊,所以真正的安全性信心是由時(shí)間累積而成的.而時(shí)間的含義則是不斷出現(xiàn)的新的分析角度.人們已知AES對(duì)差分攻擊或者線性攻擊是安全的,但是從未有人斷言它對(duì)任何攻擊都具有免疫力.因此,將密碼置于新的框架下考察是有益的,它可以提示新的角度.密碼分析的第2項(xiàng)任務(wù)是發(fā)現(xiàn)密碼設(shè)計(jì)者未公布的考慮.比如設(shè)計(jì)者宣稱AES的仿射子層是為了消除逆元子層的不動(dòng)點(diǎn),但是我們?cè)谥笖?shù)域上發(fā)現(xiàn)其作用更強(qiáng).不動(dòng)點(diǎn)在256數(shù)中僅占兩數(shù),但是仿射子層攪亂的比特?cái)?shù)遠(yuǎn)大于此.本文通過(guò)對(duì)數(shù)映射,將明文、密文及中間結(jié)果表示在指數(shù)域上,以考察AES加密過(guò)程在指數(shù)域上的表現(xiàn).自然的結(jié)果是AES原先的非線性層(即乘法逆元運(yùn)算)在指數(shù)域上變成線性運(yùn)算,而原先的線性層則可能成為非線性層.我們觀察到指數(shù)域上的重要的非線性運(yùn)算是log(exp(x)+1).這個(gè)運(yùn)算的非線性復(fù)雜度是比較弱的.雖然這并不必然意味著AES的安全性的減弱,但是,這確實(shí)提供了一個(gè)新的觀察角度.本文對(duì)該運(yùn)算做了較系統(tǒng)的考察,發(fā)現(xiàn)了它的一些規(guī)律.本文假定讀者熟悉AES算法.否則可從文獻(xiàn)閱讀AES的完整表述.為方便計(jì),本文僅考慮128bit明文和128bit密鑰.2數(shù)學(xué)基礎(chǔ)本節(jié)為AES的數(shù)學(xué)基礎(chǔ),可參照文獻(xiàn).為讀者方便計(jì),簡(jiǎn)述如下:2.1z988.x[x]的模mx剩余域記Z為整數(shù)集,Z2?為模2剩余域,Z2?[x]為Z2?上多項(xiàng)式環(huán).令m(x)=x8+x4+x3+x+1∈Z2?[x],則可以定義Z2?[x]的模m(x)剩余域如下:又記Z8228[x]為Z2?上所有次數(shù)小于8的多項(xiàng)式全體之集,即那么作為集合,Z8228[x]與Z2?[x]modm(x)有相同的元素.將Z8228[x]與Z2?[x]modm(x)視為等同,或者等價(jià)地說(shuō),用Z2?[x]modm(x)的加法和乘法在Z8228[x]上定義加法和乘法,則Z8228[x]構(gòu)成有限域.2.2階段a—字節(jié)整數(shù)域BYTE記BYTE∶={a∈Z|0≤a<256},則BYTE中的元素稱為字節(jié)整數(shù).這個(gè)名稱來(lái)源于這樣的事實(shí):BYTE中的元素恰好可以被計(jì)算機(jī)用一個(gè)字節(jié)存儲(chǔ).對(duì)BYTE中的任意元素a,存在惟一的二進(jìn)制分解:由此分解式可以建立BYTE到Z8228[x]的一一對(duì)應(yīng)p:于是,原Z2?[x]modm(x)的加法和乘法誘導(dǎo)了BYTE上的加法和乘法,即對(duì)任意a,b∈BYTE,由此BYTE構(gòu)成有限域.2.3型的ayte指數(shù)域型記BYTE*∶={a≠0|a∈BYTE},人們已經(jīng)證明它對(duì)式(6)定義的乘法形成循環(huán)群,特別是3∈BYTE是循環(huán)群的生成元.對(duì)BYTE的任意元素a和任意自然數(shù)i,我們定義指數(shù)運(yùn)算如下:其中,乘法由式(6)定義.則BYTE*={3i|0≤i<255}.這自然誘導(dǎo)了整數(shù)環(huán)Z255?與BYTE*之間的一一對(duì)應(yīng):將此對(duì)應(yīng)擴(kuò)充成Z255?∪{-∞}與BYTE之間的一一對(duì)應(yīng),為此只須定義exp(-∞)=0.將集合Z255?∪{-∞}稱為BYTE的指數(shù)域,并記為AYTE.為了方便,將-∞記為十六進(jìn)制的FF(即十進(jìn)制255).這樣,AYTE的元素在形式上就與BYTE相同了.但是,AYTE的元素與BYTE的元素服從不同的運(yùn)算,特別是FF∈AYTE實(shí)際上代表-∞.在AYTE中,如果a,b≠FF,則其加法和乘法是整數(shù)環(huán)Z255?上的模255整數(shù)運(yùn)算,當(dāng)涉及FF時(shí),有既然exp是AYTE到BYTE的一一對(duì)應(yīng),自然可以定義其逆運(yùn)算:當(dāng)然,log(0)=FF.于是,BYTE上的乘法誘導(dǎo)AYTE上的模255加法,BYTE上的加法誘導(dǎo)AYTE上的新運(yùn)算,定義如下:對(duì)任意a,b∈AYTE,3aes算法的構(gòu)成對(duì)于128bit的明文和密鑰,AES將其分別寫成4×4陣列,也就是BYTE上的4×4矩陣,分別記為E=(Eij),K=(Kij),其中,Eij,Kij∈BYTE,i,j∈Z4?={0,1,2,3},即整數(shù)的模4剩余環(huán).下標(biāo)i,j在后面有參與運(yùn)算,其加法和乘法也是Z4?上模4剩余加法和乘法.對(duì)于128bit的明文和密鑰,AES有10輪,每輪分AddRoundKey,ByteSub,ShiftRow,MixColumn四步,最后一輪缺MixColumn.每一步在AES提案中稱為層(layer),其中ByteSub又可分為兩個(gè)子層,用矩陣分量Eij表示如下:逆元子層:仿射子層:其余各層的矩陣分量表示為其中,下標(biāo)i,j的運(yùn)算是Z4?上模4剩余加法,矩陣L和向量b見(jiàn)文獻(xiàn),為節(jié)約篇幅不予贅述.在式(12)～(16)中,等號(hào)左邊為本步操作完成后Eij的值,等號(hào)右邊為本步操作前Eij的值.由上述各層構(gòu)成AES算法如下:算法AES;AddRoundKey(E,RK);{加初始密鑰}fori=1to9{前9輪:}ByteSub(E);ShiftRow(E);MixColumn(E);AddRoundKey(E,RK);end{for}{第10輪:}ByteSub(E);ShiftRow(E);AddRoundKey(E,RK);END{算法AES}其中,RK是輪密鑰,由KeySchedule從K=(Kij)計(jì)算而得.令:則算法AES各步在BYTE上的狀態(tài)被映射成AYTE上4×4矩陣,其中l(wèi)og函數(shù)由式(10)定義.AES在F∶=(Fij)上構(gòu)成并行的狀態(tài)軌跡.AES在F上的狀態(tài)與E上的狀態(tài)一一對(duì)應(yīng),所以安全性相同,但是它們的運(yùn)算性質(zhì)卻不同.對(duì)式(12)～(16)取log,得到各層在指數(shù)域AYTE上的表達(dá)式:AddRoundKey層:ShiftRow層:MixColumn層:ByteSub逆元子層:其中,式(22)中的減法實(shí)際是模255剩余加法.ByteSub的仿射子層比較復(fù)雜,原線性變換式(13)即Eij∶=LEij+b也可以表示成:其中,函數(shù)LS(x)是BYTE上的循環(huán)左移,LSk(Eij)∶=LS(LSk-1(Eij)).如果把BYTE視為Z2?上的8維矢量空間,則LS(x)當(dāng)然是矢量空間上的線性變換,但是從有限域角度講,LS(x)卻不是線性的,它定義為這里+和×是BYTE域上的加法和乘法.于是在AYTE上自然地表示為其中,L是LS在AYTE上的誘導(dǎo)運(yùn)算.容易驗(yàn)證,所以,仿射子層基本上也可以(但是不能完全)歸結(jié)為AYTE上的加法運(yùn)算和∨運(yùn)算.注記:式(24)～(26)中的若干數(shù)據(jù)來(lái)源如下:在AES的提案說(shuō)明中,仿射子層被淡化為輔助層,僅僅起掩蓋逆元子層不動(dòng)點(diǎn)的作用.但是,如果將仿射子層修改成Eij∶=Eij+99或者Eij∶=13Eij+99,同樣可以掩蓋逆元子層的不動(dòng)點(diǎn),只不過(guò)在AYTE域上的非線性強(qiáng)度會(huì)削弱.這說(shuō)明密碼的設(shè)計(jì)者是有所考慮的.這也是密碼分析者的任務(wù),密碼設(shè)計(jì)者未必會(huì)公布所有設(shè)計(jì)原理,以保持其領(lǐng)先的設(shè)計(jì)地位.盡管算法是公開(kāi)的,但是,當(dāng)其他設(shè)計(jì)者在仿效現(xiàn)有算法以研制新的算法時(shí),掌握較少設(shè)計(jì)原理的設(shè)計(jì)者將可能提供強(qiáng)度較低的密碼.比如在仿效DES的密碼中,一些仿制的S盒就不如DES原有的S盒安全.因此,密碼分析的第2項(xiàng)任務(wù)不是證明現(xiàn)有密碼不安全,而是發(fā)掘現(xiàn)有密碼的設(shè)計(jì)中未公布的想法.4為非線性運(yùn)算.本節(jié)考察BYTE域上的線性運(yùn)算+在AYTE域上誘導(dǎo)的非線性運(yùn)算∨.其中,第4.1節(jié)將運(yùn)算∨歸結(jié)為更本質(zhì)的非線性運(yùn)算:星對(duì)偶運(yùn)算.第4.2節(jié)討論運(yùn)算∨的一般性質(zhì)以及與log運(yùn)算、仿射子層的循環(huán)左移的關(guān)系.4.1星對(duì)偶運(yùn)算third定義1.對(duì)任意i∈AYTE,記稱為i的星對(duì)偶.引理1.i*=j當(dāng)且僅當(dāng)i∨j=0.下面的定理揭示了運(yùn)算∨由星對(duì)偶運(yùn)算與線性運(yùn)算混合而成;定理1.對(duì)任意i,j∈AYTE,其中+、-為AYTE上的模255加減法.證明.對(duì)3i+3j=3i(1+3j-i)兩邊取log運(yùn)算即得.證畢.關(guān)于星對(duì)偶運(yùn)算的具體值,限于篇幅,在此不予贅述.我們提供簡(jiǎn)短的C語(yǔ)言片段如下,由讀者自行生成數(shù)據(jù):unsignedchare={1},ie={255};unsignedcharx,y;unsignedinti;for(i=1;i<255;i++){x=e[i-1];y=x∧(x<<1);if(x>>7)y∧=27;e[i]=y;ie[y]=i;}for(i=0;i<256;i++){if(i%8==0)printf(“

”);printf(“%3d*=%3d”,i,ie[e[i]∧1]);}注意運(yùn)算∨是雙目運(yùn)算,運(yùn)算結(jié)果的枚舉是256×256的數(shù)據(jù)表,而星對(duì)偶運(yùn)算是單目運(yùn)算,運(yùn)算結(jié)果的枚舉僅需256個(gè)數(shù)據(jù).這表明運(yùn)算∨的非線性本質(zhì)被包含在256個(gè)數(shù)據(jù)內(nèi).這實(shí)際上是非線性強(qiáng)度的一種度量,用于刻畫非線性的數(shù)據(jù)越少,非線性強(qiáng)度就越弱.下面的2個(gè)定理表明,用來(lái)刻畫運(yùn)算∨的非線性的數(shù)據(jù)個(gè)數(shù)實(shí)際比256更少.定理2.星對(duì)偶運(yùn)算滿足如下性質(zhì):①對(duì)偶律:如果i*=j,則j*=i;②二倍律:如果i*=j,則(2i)*=2j;③負(fù)斜線性律:如果i*=j,則(-i)*=j-i,(-j)*=i-j.證明.注意在BYTE域上的加法實(shí)為按位異或運(yùn)算,因而有a+a=0,對(duì)任意a∈BYTE.于是:①i*=j??3i+1=3j?3i=3j+1?j*=i;②3i+1=3j?32j=(3i+1)2=32i+3i+3i+1=32i+1?(2i)*=2j;③3i+1=3j?1+3-i=3j-i?(-i)*=j-i.另一式類似.證畢.推論.對(duì)任意i∈AYTE,i*-(-i)*=i.證明.這是負(fù)斜線性律的等價(jià)表述.證畢.注記1.在AYTE上的二倍律有一個(gè)直觀的解釋:對(duì)任意a∈AYTE,2a實(shí)際上是a的循環(huán)左移.換言之,若a的二進(jìn)制是(a7a6a5a4a3a2a1a0),則2a的二進(jìn)制是(a6a5a4a3a2a1a0a7).所以二倍律的含義就是循環(huán)左移保持星對(duì)偶關(guān)系.此外,二倍律可以自然地推廣為:如果i*=j,則(2ki)*=2kj,0≤k≤7.當(dāng)k=8時(shí),2k=256=1(mod255),重復(fù)k=0的情形.注記2.對(duì)偶律和二倍律都是線性律,這表明星對(duì)偶運(yùn)算仍然包含相當(dāng)多的線性成份.注意線性運(yùn)算的一個(gè)重要特點(diǎn)是整個(gè)映射由基的像確定.星對(duì)偶運(yùn)算有類似的性質(zhì).定理3.如果有AYTE上的映射p(i)適合定理2的三律,即①p(p(i))=i;②p(2i)=2p(i);③p(i)-p(-i)=i,且指定p在AYTE上9個(gè)元素的值:p(1)=25,p(5)=138,p(15)=33,p(45)=31,p(27)=104,p(49)=197,p(17)=68,p(85)=170,p(0)=FF,則p就是星對(duì)偶運(yùn)算,即p(i)=i*.證明.由對(duì)偶律,p(85)=170和p(0)=FF確定了p(170)=85和p(FF)=0,從而獲得4個(gè)數(shù)的值;類似地,根據(jù)定理2的三律,由p(17)=68可以推算出12個(gè)數(shù)的值;由p(15)=33和p(45)=31可以各自推算出24個(gè)數(shù)的值(共48個(gè)數(shù)的值);由p(1)=25,p(5)=138,p(27)=104和p(49)=197各自可以推算出48個(gè)數(shù)的值(共192個(gè)數(shù)的值).所以總共獲得4+12+48+192=256個(gè)數(shù)的值.一方面用三律從9個(gè)元素的值計(jì)算出所有這些值,另一方面用我們前面提供的C代碼求出星對(duì)偶運(yùn)算的所有值,兩相對(duì)照,二者完全一致,所以命題成立.證畢.我們?cè)跇?gòu)造密碼學(xué)意義上的非線性映射時(shí),其實(shí)還包括“隨機(jī)性”的含義.這個(gè)“隨機(jī)性”很難定義,因?yàn)榘凑諅鹘y(tǒng)的理解,映射本身是確定性的.但是有一個(gè)著名的定義認(rèn)為,如果在描述一個(gè)映射的各種方式中,枚舉式描述所需要的字符個(gè)數(shù)最少,那么這個(gè)映射就是“隨機(jī)”的.定理2,3給出了類似的刻畫.如果一個(gè)映射可以從一個(gè)子集上通過(guò)若干定律推廣到整個(gè)集合上,那么子集的大小和定律的繁簡(jiǎn)程度給出了“隨機(jī)性”的直觀度量.星對(duì)偶運(yùn)算的枚舉式描述是定義在256個(gè)數(shù)上的,而定理3指出,這個(gè)運(yùn)算可以從9個(gè)數(shù)通過(guò)定理2的三律拓展到256個(gè)數(shù)上.而定理2的三律相當(dāng)接近線性律,因此,星對(duì)偶運(yùn)算的“隨機(jī)性”是較弱的.同樣,運(yùn)算∨的“隨機(jī)性”也是較弱的.4.2準(zhǔn)ayteayte的假設(shè)根據(jù)運(yùn)算∨的定義,對(duì)任意i,j,k∈AYTE,等式k=i∨j等價(jià)于BYTE上的等式3k=3i+3j.由此容易驗(yàn)證,運(yùn)算∨滿足交換律、結(jié)合律,此不贅述.眾所周知,一般情況下,有限域上的指數(shù)運(yùn)算有多項(xiàng)式時(shí)間的算法,但是離散對(duì)數(shù)運(yùn)算則沒(méi)有.本節(jié)對(duì)離散對(duì)數(shù)建立基于運(yùn)算∨和星對(duì)偶運(yùn)算的多項(xiàng)式時(shí)間算法,并討論了仿射子層用運(yùn)算∨表示的問(wèn)題.對(duì)BYTE中的任意元素a,其二進(jìn)制分解是由此獲得log(a)的表達(dá)式.定理4.其中,ifak=0thenc(ak)=FF,證明.注意log(a+b)=log(a)∨log(b),log(2)=25,log(ak2k)=log(ak)+25k,以及l(fā)og(1)=0,log(0)=FF,0+25k=25k,FF+25k=FF,故命題成立.證畢.注記:對(duì)運(yùn)算∨來(lái)說(shuō),FF可以讀做無(wú)(NULL),因?yàn)閷?duì)任意i∈AYTE,i∨FF=i.在表達(dá)式中可以略去.比如,log(9)=log(8)∨log(1)=(25×3)∨0