現(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)生過程候選算法產(chǎn)生過程n2 2、Rijndael的數(shù)學(xué)基礎(chǔ)和設(shè)計思想的數(shù)學(xué)基礎(chǔ)和設(shè)計思想n3 3、Rijndael的算法說明的算法說明n4 4、習(xí)題、習(xí)題3n背景背景 從各方面來看，從各方面來看，DESDES已走到了它生命的盡頭。已走到了它生命的盡頭。其其56比特密鑰實在太小，比特密鑰實在太小，雖然三重雖然三重DESDES可以解決密鑰長度的可以解決密鑰長度的問題，但是問題，但是DESDES的設(shè)計主要針對硬件實現(xiàn)，而今在許多的設(shè)計主要針對硬件實現(xiàn)，而今在許多領(lǐng)

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

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

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

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

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

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

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

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

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

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

12、ey Length(Nk words)Block Size(Nb words)Number of Rounds (Nr)AES-1284410AES-1926412AES-2568414AES參數(shù)參數(shù)16域的概念：一個域的概念：一個field 是一個是一個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）沒有0的除法：如果a,b屬于G,并且ab=0,

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

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

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

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

17、+x6+1(mod m(x)n 乘法運算雖然不是標(biāo)準(zhǔn)的按字節(jié)的運算，但也是比較簡單的計算部件。2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)25 以上定義的乘法滿足交換律，且有單位元01。另外，對任何次數(shù)小于8的多項式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個字節(jié)值構(gòu)成的集合，在以上定義的加法和乘法運算下，有有限域GF(28)的結(jié)構(gòu)。2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)26（

18、3）乘）乘X運算運算在AES算法中，若一最高項指數(shù)不大于7的多項式b(x)乘上x的乘法運算，稱為xtime運算。例如：如果 ，求模結(jié)果不變，否則要對乘積結(jié)果對m(x)求模 。求模過程可以用乘積結(jié)果減去m(x).在具體運算時可以用下面的方法：x乘b(x)可以先對b(x)在字節(jié)內(nèi)左移一位，若 ，則再與1b做逐比特的異或運算來實現(xiàn)。該運算記為b=xtime(a)。在專用的芯片中只需4個異或。07b17b注意：注意：X的冪乘運算可以重復(fù)應(yīng)用xtime來實現(xiàn)。對任意常數(shù)的乘法可以通過對中間結(jié)果相加來實現(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)上還定義了一個運算，稱之為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)可以先對b(x)在字節(jié)內(nèi)左移一位（最后一位補(bǔ)0），若b7=1，則再與1B（其二進(jìn)制為00011011）做逐比特異或來實現(xiàn)，該運算記為b=xtime(a)。n 在專用芯片中，xtime只需4個異或。x的冪乘運算可以重復(fù)應(yīng)用xtime來實現(xiàn)。而任意常數(shù)

20、乘法可以通過對中間結(jié)果相加實現(xiàn)。2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)30例如，5713可按如下方式實現(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)上的多項式上的多項式 4個字節(jié)構(gòu)成的向量可以表示為系數(shù)在GF(28)上的次數(shù)小于4的多項式。 多項式的加法就是對應(yīng)系數(shù)相加；換句話說，多項式的加法就是4字節(jié)向量的逐比特異或。2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的

21、數(shù)學(xué)基礎(chǔ)32 規(guī)定多項式的乘法運算必須要取模M(x)=x4+1，這樣使得次數(shù)小于4的多項式的乘積仍然是一個次數(shù)小于4的多項式，將多項式的模乘運算記為，設(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可將上述計算表示為321001233012230112303210bbbbaaaaaaaaaaaaaaaacccc2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)35 注意到M(x)不是GF(28)上的不可約多項式（甚至也不是GF(2)上的不可約多項式），因此非0多項式的這種乘法不是群運算。 不過在Rijndael密碼中，對多項式b(x)，這種乘法運算只限于乘一個固定的有逆元的多項式a(x)= a3x3+a2x2+a1x+a0。2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)36定理定理1 系數(shù)在系數(shù)在GF(28)上的多項式上的多項式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)存在多項式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)系寫成矩陣形式即得（證畢）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的冪）模乘多項式相當(dāng)于對字節(jié)構(gòu)成的向量進(jìn)行字節(jié)循環(huán)移位。0011223300000001010000000001000000000100cbcbcbcb2.1 Rijndael的數(shù)學(xué)基礎(chǔ)的數(shù)學(xué)基礎(chǔ)40Rijndael密碼的設(shè)計力求滿足以下3條標(biāo)準(zhǔn)： 抵抗所有已知的攻擊。 在多個平臺上速度快，編碼緊湊。 設(shè)計簡單。2.2 Rijndael的設(shè)計思想的設(shè)計思想41 當(dāng)前的大多數(shù)分組密碼，其輪函數(shù)是Feistel結(jié)構(gòu)，即將中間狀態(tài)的部分比特不加改變地簡單放置到其他位置。Rijndael沒有這種結(jié)構(gòu)，其輪函數(shù)是由3個不同的可逆均勻變換組成的，稱它們?yōu)?個“層”。所謂“均勻變換”是指狀態(tài)的每個

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

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

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

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

30、5、023和031。3.1 狀態(tài)、種子密鑰和輪數(shù)狀態(tài)、種子密鑰和輪數(shù)50 算法的輸入（包括最初的明文輸入和中間過程的輪輸入）以字節(jié)為單位按a00a10a20a30a01a11a21a31的順序放置到狀態(tài)陣列中。 同理，種子密鑰以字節(jié)為單位按k00k10k20k30k01k11k21k31的順序放置到種子密鑰陣列中。 而輸出（包括中間過程的輪輸出和最后的密文輸出）也是以字節(jié)為單位按相同的順序從狀態(tài)陣列中取出。3.1 狀態(tài)、種子密鑰和輪數(shù)狀態(tài)、種子密鑰和輪數(shù)51n 若輸入（或輸出）分組中第n個元素對應(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個不同的計算部件組成，分別是：字節(jié)代換（ByteSub）、行移位（ShiftRow）、列混合（MixColumn）、密鑰加（AddRoundKey）。3.2 輪函數(shù)輪函數(shù)53(1) 字節(jié)代換（ByteSub） 字節(jié)代換是非線形變換，獨立地對狀態(tài)的每個字節(jié)進(jìn)行。代換表（即S-盒）是可逆的，由以下兩個變換的合成得到： 首先，將字節(jié)

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

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

34、0 行移位示意圖3.2 輪函數(shù)輪函數(shù)61例如當(dāng)Nb=4時，具體的操作如下： 按指定的位移量對狀態(tài)的行進(jìn)行的行移位運算記為： ShiftRow(state)行移位（行移位（ShiftRow）62 ShiftRow的逆變換是對狀態(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)陣列的每個列視為GF(28)上的多項式，再與一個固定的多項式c(x)進(jìn)行模x4+1乘法。當(dāng)然要求c(x)是模x4+1可逆的多項式，否則列混合變換就是不可逆的

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

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

37、鑰加運算表示為 AddRoundKey (State, RoundKey)圖3.22是密鑰加運算示意圖。3.2 輪函數(shù)輪函數(shù)72圖3.22 密鑰加運算示意圖3.2 輪函數(shù)輪函數(shù)73 密鑰加運算的逆運算是其自身。 綜上所述，組成Rijndael輪函數(shù)的計算部件簡捷快速，功能互補(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 可用指針類型，函數(shù)Round、FinalRound、ByteSub、ShiftRow、MixColumn、AddRoundKey都在指針State、RoundKey所指向的陣列上進(jìn)行運算。3.2 輪函數(shù)輪函數(shù)76 密鑰編排指從種子密鑰得到輪密鑰的過程，它由密鑰擴(kuò)展和輪密鑰選取兩部分組成。其基本原則如下： （1）輪密

39、鑰的比特數(shù)等于分組長度乘以輪數(shù)加1；例如要將128比特的明文經(jīng)過10輪的加密，則總共需要（10+1）*128=1408比特的密鑰。 （2）種子密鑰被擴(kuò)展成為擴(kuò)展密鑰； （3）輪密鑰從擴(kuò)展密鑰中取，其中第1輪輪密鑰取擴(kuò)展密鑰的前Nb個字，第2輪輪密鑰取接下來的Nb個字，如此下去。3.3 3.3 密鑰編排密鑰編排77(1) 密鑰擴(kuò)展 擴(kuò)展密鑰是以4字節(jié)字為元素的一維陣列，表示為WNb* (Nr+1)，其中前Nk個字取為種子密鑰，以后每個字按遞歸方式定義。擴(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時，擴(kuò)展算法如下時，擴(kuò)展算法如下 79 其中Key4*Nk為種子密鑰，看作以字節(jié)為元素的一維陣列。函數(shù)SubByte ( )返回4字節(jié)字，其中每一個字節(jié)都是用Rijndael的S盒作用到輸入字對應(yīng)的字節(jié)得到。函數(shù)RotByte (

41、) 也返回4字節(jié)字，該字由輸入的字循環(huán)移位得到，即當(dāng)輸入字為(a, b, c, d)時，輸出字為 (b, c, d, a)。 當(dāng)當(dāng)Nk6時，擴(kuò)展算法如下時，擴(kuò)展算法如下 80 可以看出，擴(kuò)展密鑰的前Nk個字即為種子密鑰，之后的每個字Wi等于前一個字Wi-1與Nk個位置之前的字Wi- Nk的異或；不過當(dāng)i/Nk為整數(shù)時，須先將前一個字Wi-1經(jīng)過以下一系列的變換： 1字節(jié)的循環(huán)移位RotByte用S盒進(jìn)行變換SubByte異或輪常數(shù)Rconi/Nk。 當(dāng)當(dāng)Nk6時，擴(kuò)展算法如下時，擴(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時，擴(kuò)展算法如下：時，擴(kuò)展算法如下：82Nk6與Nk6的密鑰擴(kuò)展算法的區(qū)別在于：當(dāng)i為Nk的4的倍數(shù)時，須先將前一個字Wi-1經(jīng)過SubByte變換。3.3 3.3 密鑰編排密鑰編排83 以上兩個算法中，Rconi/Nk 為輪常數(shù)，其值與Nk無關(guān)，定義為（字節(jié)用十六進(jìn)制表示，同時理解為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 個輪密鑰）由輪密鑰緩沖字WNb* i到WNb*(i+1)給出，如圖3.23所示。圖3.23 Nb=6且Nk=4時的密鑰擴(kuò)展與輪密鑰選取3.3 3.3 密鑰編排密鑰編排85 加密算法為順序完成以下操作：初始的密鑰加；(Nr-1)輪迭代；一個結(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ù)計算），且Rijndael密碼的加密算法可以用這一擴(kuò)展密鑰來描述，即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首先給出幾個引理。 引理3.1 設(shè)字節(jié)代換（ByteSub）、行移位（ShiftRow）的逆變換分別為InvByteSub、InvShiftRow。則組合部件“ByteSubShiftRow”的逆變換為“InvByteSubInvShiftRow”。3.5 加解密的相近程度及解密算法加解密的相近程度及解密算法88n 證明：組合部件“ByteSubShiftRow”的逆變換原本為“InvShiftRowInvByteSub”。由于字節(jié)代換（ByteSub）是對每個字節(jié)進(jìn)行相同的變換，故“InvShiftRow”與“InvB

46、yteSub”兩個計算部件可以交換順序。（證畢）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）實際上是線性空間GF(28)4上的可逆線性變換，因此“AddRoundKey (, Key)InvMixColumn”=“InvMixColumnAddRoundKey (, InvMixColumn (Key)”（證畢）3.5 加解密的相近程度及解密算法加解密的相近程度及解密算法91引理3.3 將某一輪的后兩個計算部件和下一輪的前兩個計算部件組成組合部件，該組合部件的程序為MixColumn (State)； AddRoundKey (State, Key(i); ByteSub (State); ShiftRow (State)則該組合部件的逆變換程序為InvByteSub (State); InvShiftRow (State); InvMixColumn (State); AddRoundKey (State, InvMixColumn (Key(i)3.5 加解密的相近程度及解密算法加解密的相近程度及解密算法92 證明：這是引理3.1和引理3.2的直接推論。 注意到在引理3.3所描述的逆變換中，第2步到第4步在形狀上很像加密算法的輪函數(shù)，這將是解密算法的輪函數(shù)。