現(xiàn)代密碼學(xué)第4章6：AES算法

1、1分組密碼：分組密碼： AESAES算法算法現(xiàn)代密碼學(xué)現(xiàn)代密碼學(xué)第第4章章(6)2本節(jié)主要內(nèi)容本節(jié)主要內(nèi)容n1 1、AESAES候選算法產(chǎn)生過(guò)程候選算法產(chǎn)生過(guò)程n2 2、Rijndael的數(shù)學(xué)基礎(chǔ)和設(shè)計(jì)思想的數(shù)學(xué)基礎(chǔ)和設(shè)計(jì)思想n3 3、Rijndael的算法說(shuō)明的算法說(shuō)明n4 4、習(xí)題、習(xí)題3n背景背景 從各方面來(lái)看，從各方面來(lái)看，DESDES已走到了它生命的盡頭。已走到了它生命的盡頭。其其56比特密鑰實(shí)在太小，比特密鑰實(shí)在太小，雖然三重雖然三重DESDES可以解決密鑰長(zhǎng)度的可以解決密鑰長(zhǎng)度的問(wèn)題，但是問(wèn)題，但是DESDES的設(shè)計(jì)主要針對(duì)硬件實(shí)現(xiàn)，而今在許多的設(shè)計(jì)主要針對(duì)硬件實(shí)現(xiàn)，而今在許多領(lǐng)

2、域，需要用軟件方法來(lái)實(shí)現(xiàn)它，在這種情況下，它領(lǐng)域，需要用軟件方法來(lái)實(shí)現(xiàn)它，在這種情況下，它的效率相對(duì)較低。鑒于此，的效率相對(duì)較低。鑒于此，19971997年年4 4月月1515日美國(guó)國(guó)家標(biāo)日美國(guó)國(guó)家標(biāo)準(zhǔn)和技術(shù)研究所（準(zhǔn)和技術(shù)研究所（NISTNIST）發(fā)起征集）發(fā)起征集AESAES（AESAESAdvanced Encryption StandardAdvanced Encryption Standard）算法的活動(dòng)，并成）算法的活動(dòng)，并成立了立了AESAES工作組。目的是為了確定一個(gè)非保密的、公開(kāi)工作組。目的是為了確定一個(gè)非保密的、公開(kāi)披露的、全球免費(fèi)使用的加密算法，用于保護(hù)下一世披露的、全球

3、免費(fèi)使用的加密算法，用于保護(hù)下一世紀(jì)政府的敏感信息。也希望能夠成為保密和非保密部紀(jì)政府的敏感信息。也希望能夠成為保密和非保密部門(mén)公用的數(shù)據(jù)加密標(biāo)準(zhǔn)（門(mén)公用的數(shù)據(jù)加密標(biāo)準(zhǔn)（DESDES）。）。1. AES候選算法產(chǎn)生過(guò)程候選算法產(chǎn)生過(guò)程4 1997年4月15日，美國(guó)ANSI發(fā)起征集AES（advanced encryption standard）的活動(dòng)，并為此成立了AES工作小組。此次活動(dòng)的目的是確定一個(gè)非保密的、可以公開(kāi)技術(shù)細(xì)節(jié)的、全球免費(fèi)使用的分組密碼算法，以作為新的數(shù)據(jù)加密標(biāo)準(zhǔn)。1997年9月12日，美國(guó)聯(lián)邦登記處公布了正式征集AES候選算法的通告。對(duì)AES的基本要求是： 比三重DES快、

4、至少與三重DES一樣安全、數(shù)據(jù)分組長(zhǎng)度為128比特、密鑰長(zhǎng)度為128/192/256比特。1. AES候選算法產(chǎn)生過(guò)程候選算法產(chǎn)生過(guò)程5n評(píng)選過(guò)程中采用的方法評(píng)選過(guò)程中采用的方法1.1.用量化的或定性的尺度作為選擇的標(biāo)準(zhǔn)用量化的或定性的尺度作為選擇的標(biāo)準(zhǔn)；2.2.選擇一種以上的算法；選擇一種以上的算法；3.3.選擇一個(gè)備用算法；選擇一個(gè)備用算法；4.考慮公眾的建議以改進(jìn)算法?？紤]公眾的建議以改進(jìn)算法。1. AES候選算法產(chǎn)生過(guò)程候選算法產(chǎn)生過(guò)程6 1998年8月12日，在首屆AES候選會(huì)議（first AES candidate conference）上公布了AES的15個(gè)候選算法，任由全世界

5、各機(jī)構(gòu)和個(gè)人攻擊和評(píng)論，這15個(gè)候選算法是CAST256、CRYPTON、E2、DEAL、FROG、SAFER+、RC6、MAGENTA、LOKI97、SERPENT、MARS、Rijndael、DFC、Twofish、HPC。1999年3月，在第2屆AES候選會(huì)議（second AES candidate conference）上經(jīng)過(guò)對(duì)全球各密碼機(jī)構(gòu)和個(gè)人對(duì)候選算法分析結(jié)果的討論，從15個(gè)候選算法中選出了5個(gè)。1. AES候選算法產(chǎn)生過(guò)程候選算法產(chǎn)生過(guò)程7 這5個(gè)是RC6、Rijndael、SERPENT、Twofish和MARS。2000年4月13日至14日，召開(kāi)了第3屆AES候選會(huì)議（t

6、hird AES candidate conference），繼續(xù)對(duì)最后5個(gè)候選算法進(jìn)行討論。2000年10月2日，NIST宣布Rijndael作為新的AES。至此，經(jīng)過(guò)3年多的討論，Rijndael終于脫穎而出。1. AES候選算法產(chǎn)生過(guò)程候選算法產(chǎn)生過(guò)程8 Rijndael 由比利時(shí)的Joan Daemen和Vincent Rijmen設(shè)計(jì)，算法的原型是Square算法，它的設(shè)計(jì)策略是寬軌跡策略（wide trail strategy）。寬軌跡策略是針對(duì)差分分析和線性分析提出的，它的最大優(yōu)點(diǎn)是可以給出算法的最佳差分特征的概率及最佳線性逼近的偏差的界；由此，可以分析算法抵抗差分密碼分析及線性

7、密碼分析的能力。1. AES候選算法產(chǎn)生過(guò)程候選算法產(chǎn)生過(guò)程9 在宣布最后的在宣布最后的5個(gè)候選算法后，個(gè)候選算法后，NIST再次再次懇請(qǐng)公眾參與對(duì)這些算法的評(píng)論。懇請(qǐng)公眾參與對(duì)這些算法的評(píng)論。公眾對(duì)這五公眾對(duì)這五種候選算法的評(píng)閱期于種候選算法的評(píng)閱期于20002000年年5 5月月1515日結(jié)束。日結(jié)束。NIST發(fā)布的發(fā)布的AES主頁(yè)主頁(yè)2提供了大量的關(guān)于算提供了大量的關(guān)于算法描述、源程序、有關(guān)法描述、源程序、有關(guān)AES3的論文以及其他的論文以及其他公眾評(píng)論的信息。公眾評(píng)論的信息。2000年年4月開(kāi)始進(jìn)行第三階月開(kāi)始進(jìn)行第三階段（段（AES3）的評(píng)選，）的評(píng)選，AES3共收到共收到37篇提交

8、篇提交給給NIST的論文，并采用了其中的的論文，并采用了其中的24篇。在這篇。在這一階段的討論中，這些算法得到了非常深入的一階段的討論中，這些算法得到了非常深入的分析。分析。NIST的的AES小組綜合所有公眾對(duì)候選小組綜合所有公眾對(duì)候選算法的評(píng)價(jià)和分析作了一個(gè)非常徹底的評(píng)論。算法的評(píng)價(jià)和分析作了一個(gè)非常徹底的評(píng)論。1. AES候選算法產(chǎn)生過(guò)程候選算法產(chǎn)生過(guò)程10 經(jīng)過(guò)長(zhǎng)時(shí)間的評(píng)審和討論之后，經(jīng)過(guò)長(zhǎng)時(shí)間的評(píng)審和討論之后，NIST在在2000年年5月宣布選擇月宣布選擇Rijndael作為作為AES的算法。該算法的開(kāi)發(fā)者提出以下幾種發(fā)音的算法。該算法的開(kāi)發(fā)者提出以下幾種發(fā)音供選擇供選擇Reign D

9、ah1，Rain doll和和 Rhine Dah1。1. AES候選算法產(chǎn)生過(guò)程候選算法產(chǎn)生過(guò)程11n結(jié)果結(jié)果 NIST最終選擇了最終選擇了Rijndael作為作為AES的標(biāo)的標(biāo)準(zhǔn)，因?yàn)槿娴乜紤]，準(zhǔn)，因?yàn)槿娴乜紤]，Rijndael匯聚了安全，匯聚了安全，性能好，效率高，易用和靈活等優(yōu)點(diǎn)。性能好，效率高，易用和靈活等優(yōu)點(diǎn)。 Rijndael使用非線性結(jié)構(gòu)的使用非線性結(jié)構(gòu)的S-boxes，表，表現(xiàn)出足夠的安全余地；現(xiàn)出足夠的安全余地；Rijndael在無(wú)論有無(wú)反在無(wú)論有無(wú)反饋模式的計(jì)算環(huán)境下的硬，軟件中都能顯示出饋模式的計(jì)算環(huán)境下的硬，軟件中都能顯示出其非常好的性能；它的密鑰安裝的時(shí)間很好，

10、其非常好的性能；它的密鑰安裝的時(shí)間很好，也具有很高的靈活性；也具有很高的靈活性；Rijndael的非常低的內(nèi)的非常低的內(nèi)存需求也使它很適合用于受限的環(huán)境；存需求也使它很適合用于受限的環(huán)境；1. AES候選算法產(chǎn)生過(guò)程候選算法產(chǎn)生過(guò)程12 Rijndael的操作簡(jiǎn)單，并可抵御時(shí)間的操作簡(jiǎn)單，并可抵御時(shí)間和能量攻擊，此外，它還有許多未被特和能量攻擊，此外，它還有許多未被特別強(qiáng)調(diào)的防御性能；別強(qiáng)調(diào)的防御性能；Rijndael在分組長(zhǎng)在分組長(zhǎng)度和密鑰長(zhǎng)度的設(shè)計(jì)上也很靈活，算法度和密鑰長(zhǎng)度的設(shè)計(jì)上也很靈活，算法可根據(jù)分組長(zhǎng)度和密鑰長(zhǎng)度的不同組合可根據(jù)分組長(zhǎng)度和密鑰長(zhǎng)度的不同組合提供不同的迭代次數(shù)，雖然這

11、些特征還提供不同的迭代次數(shù)，雖然這些特征還需更深入地研究，短期內(nèi)不可能被利用，需更深入地研究，短期內(nèi)不可能被利用，但最終，但最終，Rijndael內(nèi)在的迭代結(jié)構(gòu)會(huì)顯內(nèi)在的迭代結(jié)構(gòu)會(huì)顯示良好的潛能來(lái)防御入侵行為。示良好的潛能來(lái)防御入侵行為。1. AES候選算法產(chǎn)生過(guò)程候選算法產(chǎn)生過(guò)程1314n不屬于不屬于Feistel結(jié)構(gòu)結(jié)構(gòu)n加密、解密相似但不對(duì)稱(chēng)加密、解密相似但不對(duì)稱(chēng)n支持支持128/32=Nb數(shù)據(jù)塊大小數(shù)據(jù)塊大小n支持支持128/192/256(/32=Nk)密鑰長(zhǎng)度密鑰長(zhǎng)度n有較好的數(shù)學(xué)理論作為基礎(chǔ)有較好的數(shù)學(xué)理論作為基礎(chǔ)n結(jié)構(gòu)簡(jiǎn)單、速度快結(jié)構(gòu)簡(jiǎn)單、速度快Rijndael 特點(diǎn)特點(diǎn)15K

12、ey Length(Nk words)Block Size(Nb words)Number of Rounds (Nr)AES-1284410AES-1926412AES-2568414AES參數(shù)參數(shù)16域的概念：一個(gè)域的概念：一個(gè)field 是一個(gè)是一個(gè)group并且滿足下面的性質(zhì)并且滿足下面的性質(zhì)（1）乘法封閉性：如果a,b屬于G，則ab屬于G.（2）乘法結(jié)合律：如果a,b,c 屬于G，則有a(bc)=(ab)c恒成立。（3）分配律：如果a,b,c 屬于G,則有a(b+c)=ab+ac。（4）乘法交換律：如果a,b屬于G,則有ab=ba。（5）沒(méi)有0的除法：如果a,b屬于G,并且ab=0,

13、不能得出a=0 or b=0（6）存在乘法單位元：aI=Ia=a.（7）存在乘法逆元：如果a屬于G,且a不等于0,則有ba=ab=I. 給定一個(gè)素?cái)?shù)，則必存在一個(gè)有限域，域中的元素個(gè)數(shù)為：這類(lèi)有限域用 來(lái)表示。np)(npGF2. Rijndael的數(shù)學(xué)基礎(chǔ)和設(shè)計(jì)思想的數(shù)學(xué)基礎(chǔ)和設(shè)計(jì)思想171. 有限域有限域GF(28) 有限域中的元素可以用多種不同的方式表示。對(duì)于任意素?cái)?shù)的方冪，都有惟一的一個(gè)有限域，因此GF(28)的所有表示是同構(gòu)的，但不同的表示方法會(huì)影響到GF(28)上運(yùn)算的復(fù)雜度，本算法采用傳統(tǒng)的多項(xiàng)式表示法。2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)18 將b7b6b5b4b3b2

14、b1b0構(gòu)成的字節(jié)b看成系數(shù)在0,1中的多項(xiàng)式b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0 例如： 十六進(jìn)制數(shù)57對(duì)應(yīng)的二進(jìn)制為01010111，看成一個(gè)字節(jié)，對(duì)應(yīng)的多項(xiàng)式為x6+x4+x2+x+1。 AES的理論基礎(chǔ)定義在GF(28) ,其基本的運(yùn)算有三種，分別為加法，乘法和乘x。2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)19（1）加法）加法在AES算法中，若兩個(gè)多項(xiàng)式進(jìn)行加法運(yùn)算（加法運(yùn)算的符號(hào)定義為 ）運(yùn)算的方法為兩個(gè)多項(xiàng)式對(duì)應(yīng)的系數(shù)相加后，在取模2運(yùn)算。 此加法運(yùn)算可以有XOR運(yùn)算進(jìn)行處理，即相加的兩個(gè)數(shù)進(jìn)行異或運(yùn)算。2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)

15、學(xué)基礎(chǔ)20 在多項(xiàng)式表示中，GF(28)上兩個(gè)元素的和仍然是一個(gè)次數(shù)不超過(guò)7的多項(xiàng)式，其系數(shù)等于兩個(gè)元素對(duì)應(yīng)系數(shù)的模2加（比特異或）。 例如： 57+83=D4，用多項(xiàng)式表示為(x6+x4+x2+x+1)+(x7+x+1)=x7+x6+ x4+ x2 (mod m(x) 用二進(jìn)制表示為 01010111+10000011=11010100 由于每個(gè)元素的加法逆元等于自己，所以減法和加法相同。2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)21（2）乘法）乘法在AES算法中，若兩個(gè)多項(xiàng)式進(jìn)行乘法運(yùn)算（乘法運(yùn)算的符號(hào)定義為 ）運(yùn)算的方法為兩個(gè)多項(xiàng)式相乘。若運(yùn)算的結(jié)果超過(guò)8次方，則必須對(duì)此結(jié)果對(duì)一個(gè)多項(xiàng)

16、式m(x)進(jìn)行模運(yùn)算。AES算法中定義m(x)多項(xiàng)式為：例如：運(yùn)算過(guò)程如下：2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)222.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)23 要計(jì)算GF(28)上的乘法，必須先確定一個(gè)GF(2)上的8次不可約多項(xiàng)式；GF(28)上兩個(gè)元素的乘積就是這兩個(gè)多項(xiàng)式的模乘（以這個(gè)8次不可約多項(xiàng)式為模）。 在Rijndael密碼中，這個(gè)8次不可約多項(xiàng)式確定為 m(x)= x8+x4+x3+x+1它的十六進(jìn)制表示為11B。2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)24n 例如，5783=C1可表示為以下的多項(xiàng)式乘法：n (x6+x4+x2+x+1)(x7+x+1)=x7

17、+x6+1(mod m(x)n 乘法運(yùn)算雖然不是標(biāo)準(zhǔn)的按字節(jié)的運(yùn)算，但也是比較簡(jiǎn)單的計(jì)算部件。2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)25 以上定義的乘法滿足交換律，且有單位元01。另外，對(duì)任何次數(shù)小于8的多項(xiàng)式b(x)，可用推廣的歐幾里得算法得 b(x)a(x)+m(x)c(x)=1即a(x)b(x)=1 mod m(x)，因此a(x)是b(x)的乘法逆元。 再者，乘法還滿足分配律：a(x)(b(x)+c(x)= a(x)b(x)+a(x)c(x) 所以，256個(gè)字節(jié)值構(gòu)成的集合，在以上定義的加法和乘法運(yùn)算下，有有限域GF(28)的結(jié)構(gòu)。2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)26（

18、3）乘）乘X運(yùn)算運(yùn)算在AES算法中，若一最高項(xiàng)指數(shù)不大于7的多項(xiàng)式b(x)乘上x(chóng)的乘法運(yùn)算，稱(chēng)為xtime運(yùn)算。例如：如果 ，求模結(jié)果不變，否則要對(duì)乘積結(jié)果對(duì)m(x)求模 。求模過(guò)程可以用乘積結(jié)果減去m(x).在具體運(yùn)算時(shí)可以用下面的方法：x乘b(x)可以先對(duì)b(x)在字節(jié)內(nèi)左移一位，若 ，則再與1b做逐比特的異或運(yùn)算來(lái)實(shí)現(xiàn)。該運(yùn)算記為b=xtime(a)。在專(zhuān)用的芯片中只需4個(gè)異或。07b17b注意：注意：X的冪乘運(yùn)算可以重復(fù)應(yīng)用xtime來(lái)實(shí)現(xiàn)。對(duì)任意常數(shù)的乘法可以通過(guò)對(duì)中間結(jié)果相加來(lái)實(shí)現(xiàn)。2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)27例如：例如：2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)

19、基礎(chǔ)28 GF(28)上還定義了一個(gè)運(yùn)算，稱(chēng)之為x乘法，其定義為xb(x)= b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0 x(mod m(x) 如果b7=0，求模結(jié)果不變，否則為乘積結(jié)果減去m(x)，即求乘積結(jié)果與m(x)的異或。2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)29n 由此得出x（十六進(jìn)制數(shù)02）乘b(x)可以先對(duì)b(x)在字節(jié)內(nèi)左移一位（最后一位補(bǔ)0），若b7=1，則再與1B（其二進(jìn)制為00011011）做逐比特異或來(lái)實(shí)現(xiàn)，該運(yùn)算記為b=xtime(a)。n 在專(zhuān)用芯片中，xtime只需4個(gè)異或。x的冪乘運(yùn)算可以重復(fù)應(yīng)用xtime來(lái)實(shí)現(xiàn)。而任意常數(shù)

20、乘法可以通過(guò)對(duì)中間結(jié)果相加實(shí)現(xiàn)。2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)30例如，5713可按如下方式實(shí)現(xiàn)： 5702=xtime(57)=AE；5704=xtime(AE)=47；5708=xtime(47)=8E；5710=xtime(8E)=07；5713=57(010210) =57AE07=FE。2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)312. 系數(shù)在系數(shù)在GF(28)上的多項(xiàng)式上的多項(xiàng)式 4個(gè)字節(jié)構(gòu)成的向量可以表示為系數(shù)在GF(28)上的次數(shù)小于4的多項(xiàng)式。 多項(xiàng)式的加法就是對(duì)應(yīng)系數(shù)相加；換句話說(shuō)，多項(xiàng)式的加法就是4字節(jié)向量的逐比特異或。2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的

21、數(shù)學(xué)基礎(chǔ)32 規(guī)定多項(xiàng)式的乘法運(yùn)算必須要取模M(x)=x4+1，這樣使得次數(shù)小于4的多項(xiàng)式的乘積仍然是一個(gè)次數(shù)小于4的多項(xiàng)式，將多項(xiàng)式的模乘運(yùn)算記為，設(shè) a(x)= a3x3+a2x2+a1x+a0， b(x)= b3x3+b2x2+b1x+b0， c(x)= a(x)b(x)=c3x3+c2x2+c1x+c0。2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)33n由于xj mod (x4+1)= x j mod 4，所以nc0=a0b0a3b1a2b2a1b3；nc1= a1b0a0b1a3b2a2b3；nc2= a2b0a1b1a0b2a3b3；nc3= a3b0a2b1a1b2a0b3。2.

22、1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)34可將上述計(jì)算表示為321001233012230112303210bbbbaaaaaaaaaaaaaaaacccc2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)35 注意到M(x)不是GF(28)上的不可約多項(xiàng)式（甚至也不是GF(2)上的不可約多項(xiàng)式），因此非0多項(xiàng)式的這種乘法不是群運(yùn)算。 不過(guò)在Rijndael密碼中，對(duì)多項(xiàng)式b(x)，這種乘法運(yùn)算只限于乘一個(gè)固定的有逆元的多項(xiàng)式a(x)= a3x3+a2x2+a1x+a0。2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)36定理定理1 系數(shù)在系數(shù)在GF(28)上的多項(xiàng)式上的多項(xiàng)式a3x3+a2x2+a1

23、x+a0是模是模x4+1可逆的，當(dāng)可逆的，當(dāng)且僅當(dāng)矩陣且僅當(dāng)矩陣在在GF(28)上可逆。上可逆。0321103221033210aaaaaaaaaaaaaaaa2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)37證明： a3x3+a2x2+a1x+a0是模x4+1可逆的，當(dāng)且僅當(dāng)存在多項(xiàng)式h3x3+h2x2+h1x+h0，(a3x3+a2x2+a1x+a0)(h3x3+h2x2+h1x+h0)=1 mod(x4+1)因此有(a3x3+a2x2+a1x+a0)(h2x3+h1x2+h0 x+h3)=x mod (x4+1)(a3x3+a2x2+a1x+a0)(h1x3+h0 x2+h3x+h2)=x

24、2 mod (x4+1)(a3x3+a2x2+a1x+a0)(h0 x3+h3x2+h2x+h1)=x3 mod(x4+1)；2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)38將以上關(guān)系寫(xiě)成矩陣形式即得（證畢）032103211032103221032103321032101000010000100001aaaahhhhaaaahhhhaaaahhhhaaaahhhh 2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)39 c(x)=xb(x)定義為x與b(x)的模x4+1乘法，即c(x)= xb(x)= b2x3+b1x2+b0 x+b3。其矩陣表示中，除a1=01外，其他所有ai= 00，即 因此

25、，x（或x的冪）模乘多項(xiàng)式相當(dāng)于對(duì)字節(jié)構(gòu)成的向量進(jìn)行字節(jié)循環(huán)移位。0011223300000001010000000001000000000100cbcbcbcb2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)40Rijndael密碼的設(shè)計(jì)力求滿足以下3條標(biāo)準(zhǔn)： 抵抗所有已知的攻擊。 在多個(gè)平臺(tái)上速度快，編碼緊湊。 設(shè)計(jì)簡(jiǎn)單。2.2 Rijndael的設(shè)計(jì)思想的設(shè)計(jì)思想41 當(dāng)前的大多數(shù)分組密碼，其輪函數(shù)是Feistel結(jié)構(gòu)，即將中間狀態(tài)的部分比特不加改變地簡(jiǎn)單放置到其他位置。Rijndael沒(méi)有這種結(jié)構(gòu)，其輪函數(shù)是由3個(gè)不同的可逆均勻變換組成的，稱(chēng)它們?yōu)?個(gè)“層”。所謂“均勻變換”是指狀態(tài)的每個(gè)

26、比特都是用類(lèi)似的方法進(jìn)行處理的。不同層的特定選擇大部分是建立在“寬軌跡策略”的應(yīng)用基礎(chǔ)上的。簡(jiǎn)單地說(shuō)，“寬軌跡策略”就是提供抗線性密碼分析和差分密碼分析能力的一種設(shè)計(jì)。2.2 Rijndael的設(shè)計(jì)思想的設(shè)計(jì)思想42 為實(shí)現(xiàn)寬軌跡策略，輪函數(shù)3個(gè)層中的每一層都有它自己的功能： 線性混合層線性混合層 確保多輪之上的高度擴(kuò)散； 非線性層非線性層將具有最優(yōu)的“最壞情況非線性特性”的S盒并行使用； 密鑰加層密鑰加層單輪子密鑰簡(jiǎn)單地異或到中間狀態(tài)上，實(shí)現(xiàn)一次性掩蓋。2.2 Rijndael的設(shè)計(jì)思想的設(shè)計(jì)思想43 在第一輪之前，用了一個(gè)初始密鑰加層，其目的是在不知道密鑰的情況下，對(duì)最后一個(gè)密鑰加層以后的

27、任一層（或者是當(dāng)進(jìn)行已知明文攻擊時(shí)，對(duì)第一個(gè)密鑰加層以前的任一層）可簡(jiǎn)單地剝?nèi)ィ虼顺跏济荑€加層對(duì)密碼的安全性無(wú)任何意義。許多密碼的設(shè)計(jì)中都在輪變換之前和之后用了密鑰加層，如IDEA、SAFER和Blowfish。2.2 Rijndael的設(shè)計(jì)思想的設(shè)計(jì)思想44 為了使加密算法和解密算法在結(jié)構(gòu)上更加接近，最后一輪的線性混合層與前面各輪的線性混合層不同，這類(lèi)似于DES的最后一輪不做左右交換?？梢宰C明這種設(shè)計(jì)不以任何方式提高或降低該密碼的安全性。2.2 Rijndael的設(shè)計(jì)思想的設(shè)計(jì)思想45 Rijndael是一個(gè)迭代型分組密碼，其分組長(zhǎng)度和密鑰長(zhǎng)度都可變，各自可以獨(dú)立地指定為128比特、192

28、比特、256比特。3. Rijndael的算法說(shuō)明的算法說(shuō)明46 類(lèi)似于明文分組和密文分組，算法的中間結(jié)果也須分組，稱(chēng)算法中間結(jié)果的分組為狀態(tài)，所有的操作都在狀態(tài)上進(jìn)行。狀態(tài)可以用以字節(jié)為元素的矩陣陣列表示，該陣列有4行，列數(shù)記為Nb，Nb等于分組長(zhǎng)度除以32。 例如用128比特密鑰加密192比特的明文，則明文和密鑰被表示成下面的狀態(tài)：3.1 狀態(tài)、種子密鑰和輪數(shù)狀態(tài)、種子密鑰和輪數(shù)47明文狀態(tài)密鑰狀態(tài)48 種子密鑰類(lèi)似地用一個(gè)以字節(jié)為元素的矩陣陣列表示，該陣列有4行，列數(shù)記為Nk，Nk等于分組長(zhǎng)度除以32。表3.8是Nb=6的狀態(tài)和Nk=4的種子密鑰的矩陣陣列表示。（見(jiàn)65頁(yè)表3.8） 有時(shí)

29、可將這些分組當(dāng)作一維數(shù)組，其每一元素是上述陣列表示中的4字節(jié)元素構(gòu)成的列向量，數(shù)組長(zhǎng)度可為4、6、8，數(shù)組元素下標(biāo)的范圍分別是03、05和07。4字節(jié)元素構(gòu)成的列向量有時(shí)也稱(chēng)為字。3.1 狀態(tài)、種子密鑰和輪數(shù)狀態(tài)、種子密鑰和輪數(shù)49 算法的輸入和輸出被看成是由8比特字節(jié)構(gòu)成的一維數(shù)組，其元素下標(biāo)的范圍是0(4Nb 1)，因此輸入和輸出以字節(jié)為單位的分組長(zhǎng)度分別是16、24和32，其元素下標(biāo)的范圍分別是015、023和031。輸入的種子密鑰也看成是由8比特字節(jié)構(gòu)成的一維數(shù)組，其元素下標(biāo)的范圍是0(4Nk 1)，因此種子密鑰以字節(jié)為單位的分組長(zhǎng)度也分別是16、24和32，其元素下標(biāo)的范圍分別是01

30、5、023和031。3.1 狀態(tài)、種子密鑰和輪數(shù)狀態(tài)、種子密鑰和輪數(shù)50 算法的輸入（包括最初的明文輸入和中間過(guò)程的輪輸入）以字節(jié)為單位按a00a10a20a30a01a11a21a31的順序放置到狀態(tài)陣列中。 同理，種子密鑰以字節(jié)為單位按k00k10k20k30k01k11k21k31的順序放置到種子密鑰陣列中。 而輸出（包括中間過(guò)程的輪輸出和最后的密文輸出）也是以字節(jié)為單位按相同的順序從狀態(tài)陣列中取出。3.1 狀態(tài)、種子密鑰和輪數(shù)狀態(tài)、種子密鑰和輪數(shù)51n 若輸入（或輸出）分組中第n個(gè)元素對(duì)應(yīng)于狀態(tài)陣列的第(i, j)位置上的元素，則n和(i, j)有以下關(guān)系：i=n mod 4; j=

31、;n=i+4jn 迭代的輪數(shù)記為Nr，Nr與Nb和Nk有關(guān)，表給出了Nr與Nb和Nk的關(guān)系。4n3.1 狀態(tài)、種子密鑰和輪數(shù)狀態(tài)、種子密鑰和輪數(shù) 14 14 14 14 12 12 14 12 10rN4bN6bN8bN4kN6kN8kN52 Rijndael的輪函數(shù)由4個(gè)不同的計(jì)算部件組成，分別是：字節(jié)代換（ByteSub）、行移位（ShiftRow）、列混合（MixColumn）、密鑰加（AddRoundKey）。3.2 輪函數(shù)輪函數(shù)53(1) 字節(jié)代換（ByteSub） 字節(jié)代換是非線形變換，獨(dú)立地對(duì)狀態(tài)的每個(gè)字節(jié)進(jìn)行。代換表（即S-盒）是可逆的，由以下兩個(gè)變換的合成得到： 首先，將字節(jié)

32、看作GF(28)上的元素，映射到自己的乘法逆元，00映射到自己。 其次，對(duì)字節(jié)做如下的（GF(2)上的，可逆的）仿射變換：3.2 輪函數(shù)輪函數(shù)540011223344556677100011111110001111111000110111100010111110000011111001001111101000111110yxyxyxyxyxyxyxyx 3.2 輪函數(shù)輪函數(shù)55 上述S-盒對(duì)狀態(tài)的所有字節(jié)所做的變換記為ByteSub (State)圖3.19是字節(jié)代換示意圖。圖3.19 字節(jié)代換示意圖3.2 輪函數(shù)輪函數(shù)56 ByteSub的逆變換由代換表的逆表做字節(jié)代換，可通過(guò)如下兩步實(shí)現(xiàn):

33、 首先進(jìn)行仿射變換的逆變換，再求每一字節(jié)在GF(28)上逆元。3.2 輪函數(shù)輪函數(shù)5758S盒對(duì)狀態(tài)的所有字節(jié)所做的變換記為：盒對(duì)狀態(tài)的所有字節(jié)所做的變換記為： ByteSub(State)59(2) 行移位（ShiftRow） 行移位是將狀態(tài)陣列的各行進(jìn)行循環(huán)移位，不同狀態(tài)行的位移量不同。第0行不移動(dòng)，第1行循環(huán)左移C1個(gè)字節(jié)，第2行循環(huán)左移C2個(gè)字節(jié)，第3行循環(huán)左移C3個(gè)字節(jié)。位移量C1、C2、C3的取值與Nb有關(guān)，由表3.10給出。（見(jiàn)66頁(yè)表3.10） 按指定的位移量對(duì)狀態(tài)的行進(jìn)行的行移位運(yùn)算記為ShiftRow (State)圖3.20是行移位示意圖。3.2 輪函數(shù)輪函數(shù)60圖3.2

34、0 行移位示意圖3.2 輪函數(shù)輪函數(shù)61例如當(dāng)Nb=4時(shí)，具體的操作如下： 按指定的位移量對(duì)狀態(tài)的行進(jìn)行的行移位運(yùn)算記為： ShiftRow(state)行移位（行移位（ShiftRow）62 ShiftRow的逆變換是對(duì)狀態(tài)陣列的后3列分別以位移量Nb-C1、Nb-C2、Nb-C3進(jìn)行循環(huán)移位，使得第i行第j列的字節(jié)移位到(j+Nb-Ci) mod Nb。3.2 輪函數(shù)輪函數(shù)63（3） 列混合（MixColumn） 在列混合變換中，將狀態(tài)陣列的每個(gè)列視為GF(28)上的多項(xiàng)式，再與一個(gè)固定的多項(xiàng)式c(x)進(jìn)行模x4+1乘法。當(dāng)然要求c(x)是模x4+1可逆的多項(xiàng)式，否則列混合變換就是不可逆的

35、，因而會(huì)使不同的輸入分組對(duì)應(yīng)的輸出分組可能相同。Rijndael的設(shè)計(jì)者給出的c(x)為（系數(shù)用十六進(jìn)制數(shù)表示）： c(x)=03x3+01x2+01x+023.2 輪函數(shù)輪函數(shù)64 c(x)是與x4+1互素的，因此是模x4+1可逆的。列混合運(yùn)算也可寫(xiě)為矩陣乘法。設(shè)b(x)= c(x)a(x)，則3210321002010103030201010103020101010302aaaabbbb3.2 輪函數(shù)輪函數(shù)65 這個(gè)運(yùn)算需要做GF(28)上的乘法，但由于所乘的因子是3個(gè)固定的元素02、03、01，所以這些乘法運(yùn)算仍然是比較簡(jiǎn)單的。 對(duì)狀態(tài)State的所有列所做的列混合運(yùn)算記為MixColu

36、mn（State） 圖3.21是列混合運(yùn)算示意圖。3.2 輪函數(shù)輪函數(shù)66圖3.21 列混合運(yùn)算示意圖3.2 輪函數(shù)輪函數(shù) 67列混合運(yùn)算列混合運(yùn)算68列混合運(yùn)算列混合運(yùn)算69列混合運(yùn)算列混合運(yùn)算70 列混合運(yùn)算的逆運(yùn)算是類(lèi)似的，即每列都用一個(gè)特定的多項(xiàng)式d(x)相乘。d(x)滿足(03x3+01x2+01x+02)d(x)=01由此可得d(x)=0Bx3+0Dx2+09x+0E3.2 輪函數(shù)輪函數(shù)71(4) 密鑰加（AddRoundKey） 密鑰加是將輪密鑰簡(jiǎn)單地與狀態(tài)進(jìn)行逐比特異或。輪密鑰由種子密鑰通過(guò)密鑰編排算法得到，輪密鑰長(zhǎng)度等于分組長(zhǎng)度Nb。狀態(tài)State與輪密鑰RoundKey的密

37、鑰加運(yùn)算表示為 AddRoundKey (State, RoundKey)圖3.22是密鑰加運(yùn)算示意圖。3.2 輪函數(shù)輪函數(shù)72圖3.22 密鑰加運(yùn)算示意圖3.2 輪函數(shù)輪函數(shù)73 密鑰加運(yùn)算的逆運(yùn)算是其自身。 綜上所述，組成Rijndael輪函數(shù)的計(jì)算部件簡(jiǎn)捷快速，功能互補(bǔ)。輪函數(shù)的偽C代碼如下：Round (State, RoundKey) ByteSub (State); ShiftRow (State); MixColumn (State); AddRoundKey (State, RoundKey)3.2 輪函數(shù)輪函數(shù)74 結(jié)尾輪的輪函數(shù)與前面各輪不同，將MixColumn這一步去掉

38、。其偽C代碼如下： FinalRound (State, RoundKey) ByteSub (State); ShiftRow (State); AddRoundKey (State, RoundKey)3.2 輪函數(shù)輪函數(shù)75 在以上偽C代碼記法中，State、RoundKey 可用指針類(lèi)型，函數(shù)Round、FinalRound、ByteSub、ShiftRow、MixColumn、AddRoundKey都在指針State、RoundKey所指向的陣列上進(jìn)行運(yùn)算。3.2 輪函數(shù)輪函數(shù)76 密鑰編排指從種子密鑰得到輪密鑰的過(guò)程，它由密鑰擴(kuò)展和輪密鑰選取兩部分組成。其基本原則如下： （1）輪密

39、鑰的比特?cái)?shù)等于分組長(zhǎng)度乘以輪數(shù)加1；例如要將128比特的明文經(jīng)過(guò)10輪的加密，則總共需要（10+1）*128=1408比特的密鑰。 （2）種子密鑰被擴(kuò)展成為擴(kuò)展密鑰； （3）輪密鑰從擴(kuò)展密鑰中取，其中第1輪輪密鑰取擴(kuò)展密鑰的前Nb個(gè)字，第2輪輪密鑰取接下來(lái)的Nb個(gè)字，如此下去。3.3 3.3 密鑰編排密鑰編排77(1) 密鑰擴(kuò)展 擴(kuò)展密鑰是以4字節(jié)字為元素的一維陣列，表示為WNb* (Nr+1)，其中前Nk個(gè)字取為種子密鑰，以后每個(gè)字按遞歸方式定義。擴(kuò)展算法根據(jù)Nk6和Nk6有所不同。3.3 3.3 密鑰編排密鑰編排78KeyExpansion (byteKey4*Nk , WNb*(Nr+1

40、) for (i =0; i Nk; i +)Wi=(Key4* i,Key4* i +1,Key4* i +2,Key4* i +3 ); for (i =Nk; i Nb*(Nr+1); i +) temp=Wi-1;if (i % Nk= =0)temp=SubByte (RotByte (temp)Rconi /Nk;Wi=Wi-Nk temp; 當(dāng)當(dāng)Nk6時(shí)，擴(kuò)展算法如下時(shí)，擴(kuò)展算法如下 79 其中Key4*Nk為種子密鑰，看作以字節(jié)為元素的一維陣列。函數(shù)SubByte ( )返回4字節(jié)字，其中每一個(gè)字節(jié)都是用Rijndael的S盒作用到輸入字對(duì)應(yīng)的字節(jié)得到。函數(shù)RotByte (

41、) 也返回4字節(jié)字，該字由輸入的字循環(huán)移位得到，即當(dāng)輸入字為(a, b, c, d)時(shí)，輸出字為 (b, c, d, a)。 當(dāng)當(dāng)Nk6時(shí)，擴(kuò)展算法如下時(shí)，擴(kuò)展算法如下 80 可以看出，擴(kuò)展密鑰的前Nk個(gè)字即為種子密鑰，之后的每個(gè)字Wi等于前一個(gè)字Wi-1與Nk個(gè)位置之前的字Wi- Nk的異或；不過(guò)當(dāng)i/Nk為整數(shù)時(shí)，須先將前一個(gè)字Wi-1經(jīng)過(guò)以下一系列的變換： 1字節(jié)的循環(huán)移位RotByte用S盒進(jìn)行變換SubByte異或輪常數(shù)Rconi/Nk。 當(dāng)當(dāng)Nk6時(shí)，擴(kuò)展算法如下時(shí)，擴(kuò)展算法如下 81KeyExpansion (byte Key4*Nk , WNb*(Nr+1) for (i=0;

42、 i Nk; i +)Wi=(Key4* i, Key4* i +1, Key4* i +2, Key4* i +3 );for (i =Nk; i 6時(shí)，擴(kuò)展算法如下：時(shí)，擴(kuò)展算法如下：82Nk6與Nk6的密鑰擴(kuò)展算法的區(qū)別在于：當(dāng)i為Nk的4的倍數(shù)時(shí)，須先將前一個(gè)字Wi-1經(jīng)過(guò)SubByte變換。3.3 3.3 密鑰編排密鑰編排83 以上兩個(gè)算法中，Rconi/Nk 為輪常數(shù)，其值與Nk無(wú)關(guān)，定義為（字節(jié)用十六進(jìn)制表示，同時(shí)理解為GF(28)上的元素）： Rcon i=(RCi, 00, 00, 00) 其中RCi 是GF(28) 中值為xi-1的元素，因此RC1 =1(即01)RCi =

43、 x(即02)RCi-1= xi-13.3 3.3 密鑰編排密鑰編排84(2) 輪密鑰選取 輪密鑰i（即第i 個(gè)輪密鑰）由輪密鑰緩沖字WNb* i到WNb*(i+1)給出，如圖3.23所示。圖3.23 Nb=6且Nk=4時(shí)的密鑰擴(kuò)展與輪密鑰選取3.3 3.3 密鑰編排密鑰編排85 加密算法為順序完成以下操作：初始的密鑰加；(Nr-1)輪迭代；一個(gè)結(jié)尾輪。即Rijndael (State, CipherKey)KeyExpansion (CipherKey, ExpandedKey);AddRoundKey (State, ExpandedKey);for (i=1; i Nr; i +) Ro

44、und (State, ExpandedKey+Nb* i);FinalRound (State, ExpandedKey+Nb*Nr)3.4 3.4 加密算法加密算法86 其中CipherKey是種子密鑰，ExpandedKey是擴(kuò)展密鑰。密鑰擴(kuò)展可以事先進(jìn)行（預(yù)計(jì)算），且Rijndael密碼的加密算法可以用這一擴(kuò)展密鑰來(lái)描述，即Rijndael (State, ExpandedKey)AddRoundKey (State, ExpandedKey);for (i=1; i Nr; i +)Round (State, ExpandedKey+Nb* i);FinalRound (State,

45、 ExpandedKey+Nb*Nr)3.4 3.4 加密算法加密算法87首先給出幾個(gè)引理。 引理3.1 設(shè)字節(jié)代換（ByteSub）、行移位（ShiftRow）的逆變換分別為InvByteSub、InvShiftRow。則組合部件“ByteSubShiftRow”的逆變換為“InvByteSubInvShiftRow”。3.5 加解密的相近程度及解密算法加解密的相近程度及解密算法88n 證明：組合部件“ByteSubShiftRow”的逆變換原本為“InvShiftRowInvByteSub”。由于字節(jié)代換（ByteSub）是對(duì)每個(gè)字節(jié)進(jìn)行相同的變換，故“InvShiftRow”與“InvB

46、yteSub”兩個(gè)計(jì)算部件可以交換順序。（證畢）3.5 加解密的相近程度及解密算法加解密的相近程度及解密算法89 引理3.2 設(shè)列混合（MixColumn）的逆變換為InvMixColumn。則列混合部件與密鑰加部件（AddRoundKey）的組合部件“MixColumnAddRoundKey (, Key)”的逆變換為“InvMixColumnAddRoundKey (, InvKey)”。 其中密鑰InvKey與Key的關(guān)系為： InvKey=InvMixColumn (Key)。3.5 加解密的相近程度及解密算法加解密的相近程度及解密算法90證明：組合部件“MixColumnAddRou

47、ndKey (, Key)” 的逆變換原本為“AddRoundKey (, Key)InvMixColumn”，由于列混合（MixColumn）實(shí)際上是線性空間GF(28)4上的可逆線性變換，因此“AddRoundKey (, Key)InvMixColumn”=“InvMixColumnAddRoundKey (, InvMixColumn (Key)”（證畢）3.5 加解密的相近程度及解密算法加解密的相近程度及解密算法91引理3.3 將某一輪的后兩個(gè)計(jì)算部件和下一輪的前兩個(gè)計(jì)算部件組成組合部件，該組合部件的程序?yàn)镸ixColumn (State)； AddRoundKey (State, Key(i); ByteSub (State); ShiftRow (State)則該組合部件的逆變換程序?yàn)镮nvByteSub (State); InvShiftRow (State); InvMixColumn (State); AddRoundKey (State, InvMixColumn (Key(i)3.5 加解密的相近程度及解密算法加解密的相近程度及解密算法92 證明：這是引理3.1和引理3.2的直接推論。 注意到在引理3.3所描述的逆變換中，第2步到第4步在形狀上很像加密算法的輪函數(shù)，這將是解密算法的輪函數(shù)。