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

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

1指數(shù)域和線性世界空間下的密碼分析自提出標準dea的文件以來，研究dea的方法一直在進行。例如，文件攻擊減少了輪數(shù)的aes，文件跟蹤了aes加密過程中比特模型的發(fā)展，文件試圖將aes的安全性等于任何時代的計算難度，并在文獻中討論了所謂的xss攻擊。盡管評估專家的結(jié)果表明，dea的分析并沒有結(jié)束。因為密鑰學(xué)的一項重要任務(wù)是持續(xù)分析每個實際密碼，并探索潛在的薄弱環(huán)節(jié)。直到密碼退役。在密碼學(xué)實踐中,專家的論證是建立在某些前提假定之下的,比如僅考慮已知的攻擊,所以真正的安全性信心是由時間累積而成的.而時間的含義則是不斷出現(xiàn)的新的分析角度.人們已知AES對差分攻擊或者線性攻擊是安全的,但是從未有人斷言它對任何攻擊都具有免疫力.因此,將密碼置于新的框架下考察是有益的,它可以提示新的角度.密碼分析的第2項任務(wù)是發(fā)現(xiàn)密碼設(shè)計者未公布的考慮.比如設(shè)計者宣稱AES的仿射子層是為了消除逆元子層的不動點,但是我們在指數(shù)域上發(fā)現(xiàn)其作用更強.不動點在256數(shù)中僅占兩數(shù),但是仿射子層攪亂的比特數(shù)遠大于此.本文通過對數(shù)映射,將明文、密文及中間結(jié)果表示在指數(shù)域上,以考察AES加密過程在指數(shù)域上的表現(xiàn).自然的結(jié)果是AES原先的非線性層(即乘法逆元運算)在指數(shù)域上變成線性運算,而原先的線性層則可能成為非線性層.我們觀察到指數(shù)域上的重要的非線性運算是log(exp(x)+1).這個運算的非線性復(fù)雜度是比較弱的.雖然這并不必然意味著AES的安全性的減弱,但是,這確實提供了一個新的觀察角度.本文對該運算做了較系統(tǒng)的考察,發(fā)現(xiàn)了它的一些規(guī)律.本文假定讀者熟悉AES算法.否則可從文獻閱讀AES的完整表述.為方便計,本文僅考慮128bit明文和128bit密鑰.2數(shù)學(xué)基礎(chǔ)本節(jié)為AES的數(shù)學(xué)基礎(chǔ),可參照文獻.為讀者方便計,簡述如下:2.1z988.x[x]的模mx剩余域記Z為整數(shù)集,Z2?為模2剩余域,Z2?[x]為Z2?上多項式環(huán).令m(x)=x8+x4+x3+x+1∈Z2?[x],則可以定義Z2?[x]的模m(x)剩余域如下:又記Z8228[x]為Z2?上所有次數(shù)小于8的多項式全體之集,即那么作為集合,Z8228[x]與Z2?[x]modm(x)有相同的元素.將Z8228[x]與Z2?[x]modm(x)視為等同,或者等價地說,用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ù).這個名稱來源于這樣的事實:BYTE中的元素恰好可以被計算機用一個字節(jié)存儲.對BYTE中的任意元素a,存在惟一的二進制分解:由此分解式可以建立BYTE到Z8228[x]的一一對應(yīng)p:于是,原Z2?[x]modm(x)的加法和乘法誘導(dǎo)了BYTE上的加法和乘法,即對任意a,b∈BYTE,由此BYTE構(gòu)成有限域.2.3型的ayte指數(shù)域型記BYTE*∶={a≠0|a∈BYTE},人們已經(jīng)證明它對式(6)定義的乘法形成循環(huán)群,特別是3∈BYTE是循環(huán)群的生成元.對BYTE的任意元素a和任意自然數(shù)i,我們定義指數(shù)運算如下:其中,乘法由式(6)定義.則BYTE*={3i|0≤i<255}.這自然誘導(dǎo)了整數(shù)環(huán)Z255?與BYTE*之間的一一對應(yīng):將此對應(yīng)擴充成Z255?∪{-∞}與BYTE之間的一一對應(yīng),為此只須定義exp(-∞)=0.將集合Z255?∪{-∞}稱為BYTE的指數(shù)域,并記為AYTE.為了方便,將-∞記為十六進制的FF(即十進制255).這樣,AYTE的元素在形式上就與BYTE相同了.但是,AYTE的元素與BYTE的元素服從不同的運算,特別是FF∈AYTE實際上代表-∞.在AYTE中,如果a,b≠FF,則其加法和乘法是整數(shù)環(huán)Z255?上的模255整數(shù)運算,當涉及FF時,有既然exp是AYTE到BYTE的一一對應(yīng),自然可以定義其逆運算:當然,log(0)=FF.于是,BYTE上的乘法誘導(dǎo)AYTE上的模255加法,BYTE上的加法誘導(dǎo)AYTE上的新運算,定義如下:對任意a,b∈AYTE,3aes算法的構(gòu)成對于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).下標i,j在后面有參與運算,其加法和乘法也是Z4?上模4剩余加法和乘法.對于128bit的明文和密鑰,AES有10輪,每輪分AddRoundKey,ByteSub,ShiftRow,MixColumn四步,最后一輪缺MixColumn.每一步在AES提案中稱為層(layer),其中ByteSub又可分為兩個子層,用矩陣分量Eij表示如下:逆元子層:仿射子層:其余各層的矩陣分量表示為其中,下標i,j的運算是Z4?上模4剩余加法,矩陣L和向量b見文獻,為節(jié)約篇幅不予贅述.在式(12)～(16)中,等號左邊為本步操作完成后Eij的值,等號右邊為本步操作前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)計算而得.令:則算法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)一一對應(yīng),所以安全性相同,但是它們的運算性質(zhì)卻不同.對式(12)～(16)取log,得到各層在指數(shù)域AYTE上的表達式:AddRoundKey層:ShiftRow層:MixColumn層:ByteSub逆元子層:其中,式(22)中的減法實際是模255剩余加法.ByteSub的仿射子層比較復(fù)雜,原線性變換式(13)即Eij∶=LEij+b也可以表示成:其中,函數(shù)LS(x)是BYTE上的循環(huán)左移,LSk(Eij)∶=LS(LSk-1(Eij)).如果把BYTE視為Z2?上的8維矢量空間,則LS(x)當然是矢量空間上的線性變換,但是從有限域角度講,LS(x)卻不是線性的,它定義為這里+和×是BYTE域上的加法和乘法.于是在AYTE上自然地表示為其中,L是LS在AYTE上的誘導(dǎo)運算.容易驗證,所以,仿射子層基本上也可以(但是不能完全)歸結(jié)為AYTE上的加法運算和∨運算.注記:式(24)～(26)中的若干數(shù)據(jù)來源如下:在AES的提案說明中,仿射子層被淡化為輔助層,僅僅起掩蓋逆元子層不動點的作用.但是,如果將仿射子層修改成Eij∶=Eij+99或者Eij∶=13Eij+99,同樣可以掩蓋逆元子層的不動點,只不過在AYTE域上的非線性強度會削弱.這說明密碼的設(shè)計者是有所考慮的.這也是密碼分析者的任務(wù),密碼設(shè)計者未必會公布所有設(shè)計原理,以保持其領(lǐng)先的設(shè)計地位.盡管算法是公開的,但是,當其他設(shè)計者在仿效現(xiàn)有算法以研制新的算法時,掌握較少設(shè)計原理的設(shè)計者將可能提供強度較低的密碼.比如在仿效DES的密碼中,一些仿制的S盒就不如DES原有的S盒安全.因此,密碼分析的第2項任務(wù)不是證明現(xiàn)有密碼不安全,而是發(fā)掘現(xiàn)有密碼的設(shè)計中未公布的想法.4為非線性運算.本節(jié)考察BYTE域上的線性運算+在AYTE域上誘導(dǎo)的非線性運算∨.其中,第4.1節(jié)將運算∨歸結(jié)為更本質(zhì)的非線性運算:星對偶運算.第4.2節(jié)討論運算∨的一般性質(zhì)以及與log運算、仿射子層的循環(huán)左移的關(guān)系.4.1星對偶運算third定義1.對任意i∈AYTE,記稱為i的星對偶.引理1.i*=j當且僅當i∨j=0.下面的定理揭示了運算∨由星對偶運算與線性運算混合而成;定理1.對任意i,j∈AYTE,其中+、-為AYTE上的模255加減法.證明.對3i+3j=3i(1+3j-i)兩邊取log運算即得.證畢.關(guān)于星對偶運算的具體值,限于篇幅,在此不予贅述.我們提供簡短的C語言片段如下,由讀者自行生成數(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]);}注意運算∨是雙目運算,運算結(jié)果的枚舉是256×256的數(shù)據(jù)表,而星對偶運算是單目運算,運算結(jié)果的枚舉僅需256個數(shù)據(jù).這表明運算∨的非線性本質(zhì)被包含在256個數(shù)據(jù)內(nèi).這實際上是非線性強度的一種度量,用于刻畫非線性的數(shù)據(jù)越少,非線性強度就越弱.下面的2個定理表明,用來刻畫運算∨的非線性的數(shù)據(jù)個數(shù)實際比256更少.定理2.星對偶運算滿足如下性質(zhì):①對偶律:如果i*=j,則j*=i;②二倍律:如果i*=j,則(2i)*=2j;③負斜線性律:如果i*=j,則(-i)*=j-i,(-j)*=i-j.證明.注意在BYTE域上的加法實為按位異或運算,因而有a+a=0,對任意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.另一式類似.證畢.推論.對任意i∈AYTE,i*-(-i)*=i.證明.這是負斜線性律的等價表述.證畢.注記1.在AYTE上的二倍律有一個直觀的解釋:對任意a∈AYTE,2a實際上是a的循環(huán)左移.換言之,若a的二進制是(a7a6a5a4a3a2a1a0),則2a的二進制是(a6a5a4a3a2a1a0a7).所以二倍律的含義就是循環(huán)左移保持星對偶關(guān)系.此外,二倍律可以自然地推廣為:如果i*=j,則(2ki)*=2kj,0≤k≤7.當k=8時,2k=256=1(mod255),重復(fù)k=0的情形.注記2.對偶律和二倍律都是線性律,這表明星對偶運算仍然包含相當多的線性成份.注意線性運算的一個重要特點是整個映射由基的像確定.星對偶運算有類似的性質(zhì).定理3.如果有AYTE上的映射p(i)適合定理2的三律,即①p(p(i))=i;②p(2i)=2p(i);③p(i)-p(-i)=i,且指定p在AYTE上9個元素的值: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就是星對偶運算,即p(i)=i*.證明.由對偶律,p(85)=170和p(0)=FF確定了p(170)=85和p(FF)=0,從而獲得4個數(shù)的值;類似地,根據(jù)定理2的三律,由p(17)=68可以推算出12個數(shù)的值;由p(15)=33和p(45)=31可以各自推算出24個數(shù)的值(共48個數(shù)的值);由p(1)=25,p(5)=138,p(27)=104和p(49)=197各自可以推算出48個數(shù)的值(共192個數(shù)的值).所以總共獲得4+12+48+192=256個數(shù)的值.一方面用三律從9個元素的值計算出所有這些值,另一方面用我們前面提供的C代碼求出星對偶運算的所有值,兩相對照,二者完全一致,所以命題成立.證畢.我們在構(gòu)造密碼學(xué)意義上的非線性映射時,其實還包括“隨機性”的含義.這個“隨機性”很難定義,因為按照傳統(tǒng)的理解,映射本身是確定性的.但是有一個著名的定義認為,如果在描述一個映射的各種方式中,枚舉式描述所需要的字符個數(shù)最少,那么這個映射就是“隨機”的.定理2,3給出了類似的刻畫.如果一個映射可以從一個子集上通過若干定律推廣到整個集合上,那么子集的大小和定律的繁簡程度給出了“隨機性”的直觀度量.星對偶運算的枚舉式描述是定義在256個數(shù)上的,而定理3指出,這個運算可以從9個數(shù)通過定理2的三律拓展到256個數(shù)上.而定理2的三律相當接近線性律,因此,星對偶運算的“隨機性”是較弱的.同樣,運算∨的“隨機性”也是較弱的.4.2準ayteayte的假設(shè)根據(jù)運算∨的定義,對任意i,j,k∈AYTE,等式k=i∨j等價于BYTE上的等式3k=3i+3j.由此容易驗證,運算∨滿足交換律、結(jié)合律,此不贅述.眾所周知,一般情況下,有限域上的指數(shù)運算有多項式時間的算法,但是離散對數(shù)運算則沒有.本節(jié)對離散對數(shù)建立基于運算∨和星對偶運算的多項式時間算法,并討論了仿射子層用運算∨表示的問題.對BYTE中的任意元素a,其二進制分解是由此獲得log(a)的表達式.定理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,故命題成立.證畢.注記:對運算∨來說,FF可以讀做無(NULL),因為對任意i∈AYTE,i∨FF=i.在表達式中可以略去.比如,log(9)=log(8)∨log(1)=(25×3)∨0