密碼學(xué)課件：六、分組密碼-AES

1、分組密碼主要內(nèi)容AES算法的數(shù)學(xué)基礎(chǔ)AES介紹分組密碼的工作模式國際數(shù)據(jù)加密標(biāo)準(zhǔn)-IDEAAES算法的數(shù)學(xué)基礎(chǔ)有限域及其運(yùn)算群和交換群的定義一個(gè)非空集合G上定義一個(gè)二元運(yùn)算“”，如果滿足下列條件（1）封閉性： a,bG，有abG；（2）結(jié)合律： a,b,cG，有abc=(ab)c=a(bc)；（3）單位元： eG, aG，有ae=ea=a，e稱為單位元；（4）逆元： aG, a-1G，使得aa-1=a-1a=e, a-1稱為逆元；則稱該代數(shù)系統(tǒng)為群，記為(G,)。（5）交換律： a,bG，有ab=ba；如果群滿足交換律，則稱為交換群。如果一個(gè)群的元素是有限的，則為有限群，否則為無限群。定義：有

2、限群中元素的個(gè)數(shù)為群的階。元素的階的定義定義：an=aaa（n個(gè)a進(jìn)行運(yùn)算），a0=1，a-n=(a-1)n對(duì)于群(G,)中的一個(gè)元素a，滿足an=e（e為單位元）的最小正整數(shù)n稱為元素a的階。若這樣的n不存在，則稱元素a是無限階的。Lagrange（拉格朗日）定理有限群G的元素的階能夠整除G的階。循環(huán)群的定義定義：群G被稱作循環(huán)群，如果aG，使得bG，存在某個(gè)整數(shù)i使得b=ai。將這樣的元素a稱為循環(huán)群的生成元，記G=。定理階為素?cái)?shù)的群必是循環(huán)群。證明：設(shè)群G的階為素?cái)?shù)p，由于G的任一元素的階能夠整除p，故任取aG，a的階要么是1要么是p。設(shè)單位元為1，若a1，則a的階為p（若階為1，有a1

3、=1，矛盾），根據(jù)元素的階的定義， 有ap=1且a,a2,a3,a(p-1),ap彼此不同。根據(jù)群中運(yùn)算的封閉性有a,a2,a3,a(p-1),apG，又因?yàn)镚的階為p，故G=1, a,a2,a3,a(p-1)，這就證明了G是循環(huán)群。群的性質(zhì)除了定義中的性質(zhì)，群還有以下性質(zhì)。（1）群中的單位元具有唯一性；（2）群中的逆元具有唯一性；（3）（消去律） a,b,cG，如果ab=ac，則b=c；同樣，如果ba=ca，則b=c。例如m為素?cái)?shù)，a是m的本原根，在集合Zm*=1,2,m-1定義二元運(yùn)算”如下：xy=(ax mod m)(ay mod m)=a(x+y) mod m, x,yZm*則(Zm*

4、,)為循環(huán)群。其中，單位元為1。任意元素的階都為m-1，任何元素都可以作為群的生成元。m為素?cái)?shù)，a是m的本原根，集合Zm*=a mod m, a2 mod m, a3 mod m,am-1 mod m上定義的數(shù)乘”運(yùn)算構(gòu)成群，且為循環(huán)群。即群(Zm*,)為循環(huán)群。其中，單位元為1。環(huán)的定義環(huán)是一個(gè)代數(shù)系統(tǒng)，它由一個(gè)至少包含兩個(gè)元素的集合R構(gòu)成，在集合R上定義有兩個(gè)二元運(yùn)算：加法“+”和乘法“”，并滿足下列條件。（1）R關(guān)于加法“+”是一個(gè)交換群，其單位元為“0”，稱為環(huán)的零元，元素a的逆元為-a；與加法對(duì)應(yīng)的逆運(yùn)算（減法）定義為：a-b=a+(-b)。（2）乘法滿足結(jié)合律： a,b,cR，有a

5、bc=(ab)c=a(bc) 。（3）乘法在加法上滿足分配律： a,b,cR，有a(b+c)=(b+c)a= ab+ac將滿足上面性質(zhì)的代數(shù)系統(tǒng)稱為環(huán)R，即為 。例如整數(shù)集關(guān)于整數(shù)的加法和乘法構(gòu)成整數(shù)環(huán)。類似地，有理數(shù)集關(guān)于有理數(shù)的加法和乘法構(gòu)成有理數(shù)環(huán)；實(shí)數(shù)集關(guān)于有理數(shù)的加法和乘法構(gòu)成實(shí)數(shù)環(huán)；復(fù)數(shù)集關(guān)于有理數(shù)的加法和乘法構(gòu)成復(fù)數(shù)環(huán)。此外，若令 表示全體偶數(shù)構(gòu)成的集合，則 關(guān)于偶數(shù)的加法和乘法構(gòu)成一個(gè)環(huán)，稱為偶數(shù)環(huán)。一般地，凡是數(shù)（無論是實(shí)數(shù)還是復(fù)數(shù)）集關(guān)于數(shù)的加法和乘法構(gòu)成的環(huán)都稱為數(shù)環(huán)。顯而易見，凡是數(shù)環(huán)都以數(shù)0為其零元。例如例3 設(shè)n是一個(gè)正整數(shù)，設(shè)集合 Zn=0n, 1n, , n-1

6、n是模n的剩余類構(gòu)成的集合，在Zn上定義”+”運(yùn)算：an+bn=a+bn 則(Zn,+)是加法交換群。在Zn上定義”運(yùn)算：anbn=abn則(Zn,+,)構(gòu)成一個(gè)環(huán)，稱為模n的剩余類環(huán)。當(dāng)n為素?cái)?shù)，a與n互素，根據(jù)費(fèi)爾馬小定理有an-11 mod n，對(duì)任意整數(shù)a有ana mod n。因此在模n的剩余類環(huán)中，對(duì)每個(gè)整數(shù)a有an=a。域的定義域是一個(gè)代數(shù)系統(tǒng)，它由一個(gè)至少包含兩個(gè)元素的集合F構(gòu)成，在集合F上定義有兩個(gè)二元運(yùn)算：加法“+”和乘法“”，并滿足下列條件。（1）F關(guān)于加法“+”是一個(gè)交換群，其單位元為“0”，稱為域的零元，元素a的逆元為-a；與加法對(duì)應(yīng)的逆運(yùn)算（減法）定義為：a-b=a+

7、(-b)。（2）F0關(guān)于乘法“”是一個(gè)交換群，其單位元為“1”，仍稱為域的單位元或么元，元素的a的逆元為a-1；與乘法對(duì)應(yīng)的逆運(yùn)算除法定義為：a/b=ab-1。（3）乘法在加法上滿足分配律： a,b,cF，有a(b+c)=(b+c)a= ab+ac將滿足上面性質(zhì)的代數(shù)系統(tǒng)稱為域F，即為 。有限域的定義如果域F只包含有限個(gè)元素，則稱域F為有限域，也稱為伽羅華域或Galois域。有限域中元素的個(gè)數(shù)稱為有限域的階。同構(gòu)的定義設(shè)代數(shù)系統(tǒng)和都是域，如果一一映射h，對(duì)于任意的a,bF，有h(a+b)=h(a)h(b)h(ab)=h(a)h(b)則稱一一映射h是從到的同構(gòu)，稱與是同構(gòu)的。定理1每個(gè)有限域的階

8、必為素?cái)?shù)的冪，該素?cái)?shù)稱為有限域的特征。定理2對(duì)任意的素?cái)?shù)p與正整數(shù)n，存在pn階有限域，記為GF(pn)。當(dāng)n=1時(shí)，有限域GF(p)也稱為素域。 定理3同階的有限域必同構(gòu)。以上三個(gè)定理說明：pn階有限域存在，且彼此同構(gòu)，也就是說在同構(gòu)意義下，含有pn個(gè)元素的有限域只有一個(gè)。密碼學(xué)中常用的域?yàn)樗赜騁F(p)（p為素?cái)?shù)）或GF(2n)域。有限域的幾個(gè)性質(zhì)（1）F為q階有限域，則aF，有aq=a。（2）有限域F中非零元組成的集合F*（即F0）關(guān)于有限域F乘法“”構(gòu)成的群是一個(gè)循環(huán)群。F*稱為有限域的乘法群。定義：有限域F的乘法群F*的生成元稱為有限域F的本原元。說明：F*的生成元不唯一，但不是F*

9、中所有的元素都是生成元。根據(jù)循環(huán)群的生成元的定義，只有階等于F的階的元素才是生成元。本原元的性質(zhì)設(shè)F為q階有限域，則F中共有(q-1)個(gè)本原元。有限域的構(gòu)造舉例：對(duì)任意素?cái)?shù)p可以按照如下所述構(gòu)造一個(gè)p階有限域。代數(shù)系統(tǒng)，Np=0,1,2,p-1。 a,bNp，定義a+pb=(a+b) mod p, apb=(ab)mod p?？梢宰C明，如上構(gòu)造的代數(shù)系統(tǒng)是一個(gè)有限域。設(shè)p=5，則GF(5)的加法和乘法代數(shù)運(yùn)算如下：+501234001234112340223401334012440123501234000000101234202413303142404321域上多項(xiàng)式的定義域上x的多項(xiàng)式定義為

10、形如anxn+an-1xn-1+a1x+a0的多項(xiàng)式，其中nN，an,an-1,a1,a0F。若an0，稱n為多項(xiàng)式的次數(shù)，并稱an為首項(xiàng)系數(shù)。首項(xiàng)系數(shù)為1的多項(xiàng)式稱為首1多項(xiàng)式。稱0為-次多項(xiàng)式。其中0和1分別為域F的零元和單位元。F上的多項(xiàng)式anxn+an-1xn-1+a1x+a0簡(jiǎn)記為 。F上x的多項(xiàng)式的全體記為Fx。多項(xiàng)式a(x)的次數(shù)記為deg(a(x)。多項(xiàng)式的運(yùn)算的定義設(shè)上的兩個(gè)多項(xiàng)式 與 ，定義F上的多項(xiàng)式的加法”+”與乘法”如下：（1）加法”+”其中，M=max(m,n)，當(dāng)in時(shí)，取ai=0；當(dāng)im時(shí)，取bi=0。（2）乘法”其中，當(dāng)in時(shí)，取ai=0；當(dāng)im時(shí)，取bi=0

11、。多項(xiàng)式的帶余除法定理設(shè)a(x)和b(x)為F上的多項(xiàng)式，且b(x)0，則存在唯一的一對(duì)元素q(x),r(x)F(x)，使：a(x)=q(x)b(x)+r(x)其中，deg(r(x)deg(b(x)，q(x)稱為商式，r(x)稱為余式。即r(x)=a(x) mod b(x)。例：a(x)=2x3+9x2+5，b(x)=x2+4x-3，則q(x)=2x+1，r(x)=2x+8。定義若存在q(x)和b(x)使a(x)=q(x)b(x)，且deg(q(x)1，deg(b(x)1，則a(x)為可約多項(xiàng)式，否則稱a(x)為不可約多項(xiàng)式。Fx上域的構(gòu)造對(duì)Fx中的每個(gè)不可約多項(xiàng)式p(x)，可以如下構(gòu)造一個(gè)域

12、Fxp(x)。設(shè)p(x)是Fx中的n次不可約多項(xiàng)式，令Fxp(x)為Fx中所有次數(shù)小于n的多項(xiàng)式的集合，即：Fxp(x)=an-1xn-1+an-2xn-2+a1x+a0|an-1,an-2,a1,a0F任取a(x),b(x)Fxp(x)，定義Fxp(x)上的二元運(yùn)算和如下：a(x)b(x)=(a(x)+b(x) mod p(x)a(x)b(x)=(a(x)b(x) mod p(x)域Fxp(x)中的單位元和零元分別是F中的單位元與零元。多項(xiàng)式域的定理是域，當(dāng)且僅當(dāng)p(x)是F上的不可約多項(xiàng)式，其中F是有限域?？梢宰C明，對(duì)于任意素?cái)?shù)p和正整數(shù)n，存在p階域F上的n次不可約多項(xiàng)式f(x)，F(xiàn)xf

13、(x)即為pn階域。有限域元素的多項(xiàng)式表示由定理，對(duì)每個(gè)素?cái)?shù)p，都可以構(gòu)造一個(gè)p階有限域。這樣，可以得出如下結(jié)論：任何有限域必與某一多項(xiàng)式域同構(gòu)，因此，可以用多項(xiàng)式域來表示其他有限域。有限域元素還有其他許多表示方法，而不同的表示方法可能在計(jì)算的效率有一些差別。例：16階域GF(24)的構(gòu)造16階域GF(24)可在2階域上構(gòu)造。設(shè)集合F=0,1，F(xiàn)上定義運(yùn)算+和如下：1+1=0,0+0=0,1+0=0+1=1；11=1,00=0,10=01=0。則以上F和運(yùn)算構(gòu)成的代數(shù)系統(tǒng)為2階域。設(shè)p(x)為以上2階域上的一個(gè)4次不可約多項(xiàng)式，則Fxp(x)中的所有16個(gè)元素為：0, 1, x, x+1, x

14、2, x2+1, x2+x, x2+x+1, x3, x3+1, x3+x, x3+x+1, x3+x2, x3+x2+1, x3+x2+x, x3+x2+x+1，且多項(xiàng)式域?yàn)?6階域。其中a(x)b(x)=(a(x)+b(x) mod p(x)a(x)b(x)=(a(x)b(x) mod p(x)例：16階域GF(24)的構(gòu)造下面確定p(x)。因F上的4次不可約多項(xiàng)式有x4+x3+x2+x+1，x4+x3+1和x4+x2+1，而同階的有限域是同構(gòu)的，故可從上述不可約多項(xiàng)式中任選一個(gè)作為p(x)。例如，取p(x)=x4+x3+x2+x+1。例如，任取a(x)=x2+x+1，b(x)=x3+x2

15、+x+1，求a(x)b(x)以及a(x)b(x)。根據(jù)定義：a(x)b(x)=(a(x)+b(x) mod p(x)=(x2+x+1)+(x3+x2+x+1) mod p(x) =x3 mod (x4+x3+x2+x+1)=x3a(x)b(x)=(a(x)b(x) mod p(x)=(x2+x+1)(x3+x2+x+1) mod p(x) = x5+x3+x2+1 mod (x4+x3+x2+x+1)=x3+x2因此以上構(gòu)造的多項(xiàng)式域?yàn)?6階域。例：16階域GF(24)的構(gòu)造分析：針對(duì)多項(xiàng)式域，群為循環(huán)群，對(duì)除0外的所有15個(gè)元素1, x, x+1, x2, x2+1, x2+x, x2+x+

16、1, x3, x3+1, x3+x, x3+x+1, x3+x2, x3+x2+1, x3+x2+x, x3+x2+x+1的階進(jìn)行計(jì)算，階為15的元素即為該群的生成元，也就是域的本原元，共有(16-1)=8個(gè)，分別是：x+1, x2+1, x2+x, x2+x+1, x3+1, x3+x, x3+x+1, x3+x2+x因此循環(huán)群可以表示成這些生成元的冪的形式。如：設(shè)生成元=x+1，則a(x)=x2+x+1=7 mod p(x)和b(x)=x3+x2+x+1=3 mod p(x)，進(jìn)一步有a(x)b(x)=73 mod p(x)=10 mod p(x)=x3+x216階域的結(jié)構(gòu)同階有限域都同構(gòu)

17、，故下表包含了所有16階域運(yùn)算的全部信息。域中的元素關(guān)于乘法的階=x+1的冪=x2+x+1的冪0111515x5126x+11513x25912x2+115211x2+x15134x2+x+1157x3563x3+115814x3+x15142x3+x+115118x3+x231010 x3+x2+1355x3+x2+x1547x3+x2+x+1539階為15的元素即為該域乘法群的生成元，即該域的本原元，如=x+1、 =x2+x+1等都是該域的本原元，共有(16-1)=8個(gè)。表中給出了關(guān)于這兩個(gè)本原元、 的運(yùn)算結(jié)果，顯然是同構(gòu)的，因?yàn)閕=7i。例，構(gòu)造域GF(28)同理，可構(gòu)造256階域GF(

18、28)例如可取不可約多項(xiàng)式為p(x)=x8+x4+x3+x+1，則Fxp(x)中的所有256個(gè)元素為：0, 1, x, x+1, x2, x2+1, x2+x, x2+x+1, x3, x3+1, x3+x, x3+x+1, x3+x2, x3+x2+1, x3+x2+x, x3+x2+x+1, , x7, x7+1, x7+x, x7+x+1, ,x7+x6+x5+x4+x3+x2+x+1。定義運(yùn)算：a(x)b(x)=(a(x)+b(x) mod p(x)a(x)b(x)=(a(x)b(x) mod p(x)則多項(xiàng)式域?yàn)?56階域。256階有限域GF(28)256階有限域的特征為2，根據(jù)前面

19、的介紹，用2階域F上的8次不可約多項(xiàng)式p(x)構(gòu)造的多項(xiàng)式域Fxp(x)即為GF(28)。有限域GF(28)256階有限域GF(28)以下說明256階數(shù)域的元素255,254,0與256階多項(xiàng)式域Fxp(x)的元素如何對(duì)應(yīng)。首先將數(shù)域的元素表示成二進(jìn)制形式為：11111111,b7b6b5b4b3b2b1b0,00000000。有限域GF(28)可將256階數(shù)域的元素b7b6b5b4b3b2b1b0與256階多項(xiàng)式域Fxp(x)的元素對(duì)應(yīng)關(guān)系如下：b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0這樣任意8位二進(jìn)制數(shù)就和一個(gè)多項(xiàng)式建立了一一對(duì)應(yīng)的關(guān)系。例：十六進(jìn)制數(shù)57，

20、二進(jìn)制為：01010111，對(duì)應(yīng)的多項(xiàng)式為：x6+x4+x2+x+1GF(28)中元素的多項(xiàng)式表示AES算法對(duì)字節(jié)進(jìn)行運(yùn)算，把一個(gè)字節(jié)（8bit: b7b6b5b4b3b2b1b0 ）對(duì)應(yīng)成多項(xiàng)式域Fxp(x)上的一個(gè)元素。這樣， AES中對(duì)字節(jié)的運(yùn)算可以轉(zhuǎn)換為256階域GF(28)上的多項(xiàng)式的運(yùn)算。下面介紹多項(xiàng)式的運(yùn)算特點(diǎn)。GF(28)中元素的多項(xiàng)式表示GF(28)上的加法說明：根據(jù)域運(yùn)算的封閉性，域GF(28)中任意兩個(gè)元素的和仍在域中，運(yùn)算結(jié)果的系數(shù)等于兩個(gè)元素對(duì)應(yīng)多項(xiàng)式的系數(shù)的異或。例：57+83=？57: 01010111，83:10000011(x6+x4+x2+x+1)+(x7+

21、x+1)=x7+x6+x4+x2即：11010100（D4）， 57+83=D4GF(28)上的乘法說明：根據(jù)域運(yùn)算的封閉性，多項(xiàng)式域GF(28)中任意兩個(gè)元素的乘積仍在域中，乘積采用模乘，結(jié)果也是一個(gè)次數(shù)不超過7的多項(xiàng)式。多項(xiàng)式域GF(28) 上的模常使用的一個(gè)不可約多項(xiàng)式為m(x)=x8+x4+x3+x+1，它的二進(jìn)制表示為：100011011，十六進(jìn)制表示為“11B”GF(28)上的乘法例： 5783=C1(x6+x4+x2+x+1)(x7+x+1)=x13+x11+x9+x8+x7+x7+x5+x3+x2+x+x6+x4+x2+x+1=(x13+x11+x9+x8+x6+x5+x4+x

22、3+1)x7+x6+1 mod (x8+x4+x3+x+1) （多項(xiàng)式的分解）對(duì)應(yīng)二進(jìn)制11000001GF(28)上的x乘法GF(28)上還定義了一個(gè)運(yùn)算，稱為x乘法，定義為：xb(x)=(b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0 x) mod m(x)如果b7=0，求模結(jié)果不變，若b7=1，則結(jié)果加上m(x)。由此得出x乘法的高效運(yùn)算方法：因多項(xiàng)式x對(duì)應(yīng)于元素00000010，則要求xb(x)，可以先對(duì)b(x)在字節(jié)內(nèi)左移一位（最后一位補(bǔ)0），若b7=1，則再與“1B”（其二進(jìn)制為00011011）進(jìn)行逐位異或來實(shí)現(xiàn)。因此：x乘法實(shí)現(xiàn)的效率非常高。該運(yùn)算記

23、為xtime(b) x乘法實(shí)現(xiàn)的效率非常高，可利用x乘法來加快GF(28)中任意兩個(gè)元素的乘法運(yùn)算。例如：5713的實(shí)現(xiàn)：13=01+02+10（將13分解）5702=xtime(57)=AE （01010111,左移1位, 010101110,b7=0,結(jié)果不變?yōu)?10101110,即AE）5704=570202=xtime(AE)=47AE: 10101110,左移1位, 101011100,b7=1,與1B異或得1000111，即475708=570402=xtime(47)=8E5710=570802=xtime(8E)=075713=57(01+02+10)=57+AE+07=FE字

24、運(yùn)算字運(yùn)算也是定義在域上的運(yùn)算。AES中的一個(gè)字由4個(gè)字節(jié)構(gòu)成，每個(gè)字節(jié)看成是GF(28)中的一個(gè)元素。4個(gè)字節(jié)構(gòu)成的字可以表示成一個(gè)次數(shù)小于4的多項(xiàng)式，其系數(shù)取自GF(28)。例如，對(duì)于字： 57 83 4A D1對(duì)應(yīng)的多項(xiàng)式為：57x3+83x2+4Ax+D157、83、4A、D1分別對(duì)應(yīng)GF(28)中的一個(gè)多項(xiàng)式。字的加法兩個(gè)字相加：對(duì)應(yīng)的多項(xiàng)式的系數(shù)相加，對(duì)應(yīng)系數(shù)簡(jiǎn)單按位異或。例如：57 83 4A D1+26 ED 41 22對(duì)應(yīng)的系數(shù)相加就是GF(28)中多項(xiàng)式的相加：57+26：83+ED：4A+41：D1+22：字的乘法多項(xiàng)式的乘法：設(shè)a(x)=a3x3+a2x2+a1x+a0

25、，b(x)=b3x3+b2x2+b1x+b0，c(x)=a(x)b(x)，又設(shè)c(x)= c6x6+c5x5+c4x4+c3x3+c2x2+c1x+c0，則有c0=a0b0，c1=a1b0a0b1，c2=a2b0a1b1a0b2c3=a3b0a1b2a2b1a0b3，c4=a3b1a2b2a1b3c5=a3b2a2b3，c6=a3b3上式中c(x)不是次數(shù)小于4次的多項(xiàng)式，不能表示成4字節(jié)，通過模一個(gè)4次多項(xiàng)式M(x)進(jìn)行化簡(jiǎn)，使得結(jié)果變?yōu)榇螖?shù)小于4次的多項(xiàng)式。字（多項(xiàng)式）的乘法取4次多項(xiàng)式M(x)=x4+1，設(shè)(a3x3+a2x2+a1x+a0)(b3x3+b2x2+b1x+b0) mod

26、x4+1= d3x3+d2x2+d1x+d0=d(x) 可證： 表示成矩陣形式為：（利用性質(zhì)xj mod (x4+1)=xj mod 4）d0=a0b0+a3b1+a2b2+a1b3d1=a1b0+a0b1+a3b2+a2b3d2=a2b0+a1b1+a0b2+a3b3d3=a3b0+a2b1+a1b2+a0b3以上運(yùn)算中aibj即是GF(28)上多項(xiàng)式乘法。字（多項(xiàng)式）的乘法說明：因?yàn)镸(x)=x4+1=(x+1)(x3+x2+x+1)，故M(x)不是不可約多項(xiàng)式。這樣，字的乘法運(yùn)算中，與一個(gè)多項(xiàng)式的模x4+1乘法將不一定可逆（因與M(x)不一定互素）。AES中，特意選擇一個(gè)具有逆元的固定多

27、項(xiàng)式a(x)=03x3+01x2+01x+02進(jìn)行模x4+1乘法，從而保證了模x4+1乘法的可逆，使得解密的逆運(yùn)算可行。a(x)模x4+1的乘法逆為a-1(x)=0bx3+0dx2+09x+0e，即a(x)a-1(x)= 1 mod x4+1高級(jí)數(shù)據(jù)加密標(biāo)準(zhǔn)Advanced Encryption Standard: AES歷史1997年1月2日，美國國家標(biāo)準(zhǔn)與技術(shù)研究所（NIST）開始征集DES的替代工作，稱為高級(jí)加密標(biāo)準(zhǔn)，即AES。要求：安全性可達(dá)100年，在三重DES之上。 1997年9月12日，NIST發(fā)布正式的征集公告，要求AES具有128位分組長度，并支持128位、192位、256位

28、密鑰長度。 1998年6月15日，收到提交的21個(gè)算法 1998年8月20日，第一次AES候選大會(huì)，宣布其中15個(gè)候選算法 1999年3月，第二次AES候選大會(huì) 1999年8月，5個(gè)候選算法進(jìn)入決賽：MARS,RC6,Rijndael,Serpert和Twofish歷史 2000年4月，第三次AES候選大會(huì) 2000年10月2日，Rijndael被選擇為高級(jí)加密標(biāo)準(zhǔn)。 2001年2月28日，NIST宣布AES的草案供公眾討論 2001年11月26日，AES被采納成為標(biāo)準(zhǔn) 2001年12月4日，聯(lián)辦紀(jì)事中作為FIPS197公布。15個(gè)候選算法作者的國家：澳大利亞、比利時(shí)、加拿大、哥斯達(dá)黎加、法國

29、、德國、以色列、日本、韓國、挪威、英國及美國。Rijndael算法是由兩位比利時(shí)的研究者J. Daemen 和V. Ri jmen提出。AES的總體描述分組長度為128位，三種可選的密鑰長度：128位、192位和256位。加密輪數(shù)Nr與密鑰長度有關(guān)。AES中的操作都是以字節(jié)為基礎(chǔ)，所有變量都由適當(dāng)數(shù)量的字節(jié)組成。中間變量state用44字節(jié)矩陣表示：128位的輸入：16個(gè)字節(jié) x0,.,x15標(biāo)準(zhǔn)密鑰長度加解密輪數(shù)AES-12812810AES-19219212AES-25625614x0 x1x2x3x4x5x6x7x8x9x10 x11x12x13x14x15SS00SS01SS02SS0

30、3SS10SS11SS12SS13SS20SS21SS22SS23SS30SS31SS32SS33AES的總體描述AES的總體結(jié)構(gòu)AES的總體描述AES的加密、解密流程AES的總體描述加密算法的執(zhí)行過程描述如下：（1）給定一個(gè)明文M，將M賦值狀態(tài)矩陣State，即將State初始化為M，并將輪密鑰Roundkey與State異或，稱為：AddRoundkey(State,Roundkey)（2）在加密算法的前Nr-1輪中，每一輪加密操作如下：用S-盒進(jìn)行替換操作：SubBytes(State) ；對(duì)替換的結(jié)果State做行移位操作：ShiftRows(State)；再對(duì)State 做列混合變換

31、：MixColumns(State)；最后進(jìn)行密鑰異或運(yùn)算：AddRoundkey(State,Roundkey) 。AES的總體描述（3）在最后一輪中，對(duì)前Nr-1輪的結(jié)果State再依次進(jìn)行SubBytes(State)ShiftRows(State)AddRoundkey(State,Roundkey)操作。（4）將輸出的State定義為密文C。AES的總體描述AES的總體執(zhí)行過程算法的基本變換字節(jié)替換變換（SubBytes(State)）例如： 設(shè)State中的一個(gè)字節(jié)為53，SubBytes(53)=？使用一個(gè)S-盒對(duì)每個(gè)字節(jié)進(jìn)行替換。下面介紹S-盒的構(gòu)造方法。算法的基本變換字節(jié)替換

32、變換（SubBytes(State)）S-盒按如下方法構(gòu)造：（1）一個(gè)字節(jié)表示成十六進(jìn)制的xy，x,y分別為行和列輸入（2）求該字節(jié)在GF(28)中的乘法逆（模m(x)=x8+x4+x3+x+1），設(shè)乘法逆為（ b7b6b5b4b3b2b1b0） （3）然后進(jìn)行如下計(jì)算，求得（ b7b6b5b4b3b2b1b0） ，即為結(jié)果。算法的基本變換字節(jié)替換變換（SubBytes(State)）例：十六進(jìn)制的53，二進(jìn)制為01010011，GF(28)中的元素為x6+x4+x+1在GF(28)中的乘法逆(模m(x)=x8+x4+x3+x+1下的乘法逆)元素為x7+x6+x3+x（即對(duì)應(yīng)11001010）

33、因此，在二進(jìn)制下，有b7b6b5b4b3b2b1b0=11001010下面計(jì)算b0=b0+b4+b5+b6+b7+1 mod 2 =0+0+0+1+1+1 mod 2=1同理可得： b7b6b5b4b3b2b1b0=11101101，十六進(jìn)制為ED，故S-盒中的5行3列的元素為ED ，即SubBytes(53)=ED算法的基本變換字節(jié)替換變換（SubBytes(State)）按以上方法計(jì)算出所有元素的結(jié)果，形成S-盒如下表：算法的基本變換字節(jié)替換變換（SubBytes(State)）與DES的S-盒相比，AES的S-盒能進(jìn)行代數(shù)上的定義，而不像DES的S-盒看起來像是“隨機(jī)”的代換。算法的基本

34、變換行移位變換（ShiftRows(State) ）State的第一行保持不動(dòng)，第二行循環(huán)左移一個(gè)字節(jié)，第三行循環(huán)左移兩個(gè)字節(jié)，第四行循環(huán)左移三個(gè)字節(jié)SS00SS01SS02SS03SS11SS12SS13SS10SS22SS23SS20SS21SS33SS30SS31SS32SS00SS01SS02SS03SS10SS11SS12SS13SS20SS21SS22SS23SS30SS31SS32SS33不移動(dòng)左移一個(gè)字節(jié)左移兩個(gè)字節(jié)左移三個(gè)字節(jié)算法的基本變換列混合變換（MixColumns(State)）對(duì)State中每列進(jìn)行獨(dú)立操作，把每列看成一個(gè)3次多項(xiàng)式s(x)，再與固定多項(xiàng)式a(x)=

35、03x3+01x2+01x+02進(jìn)行模x4+1的乘法運(yùn)算。3次多項(xiàng)式系數(shù)的運(yùn)算即是有限GF(28)中多項(xiàng)式的運(yùn)算。如對(duì)第c列（0c3），其對(duì)應(yīng)的3次多項(xiàng)式為sc(x)=s0,c+s1,cx+s2,cx2 +s3,cx3，則列混合變換后的值為sc(x)=sc(x)a(x)。矩陣表示如下：輪密鑰生成算法Roundkey的產(chǎn)生： 對(duì)于需要進(jìn)行N輪加密的AES算法，共需要N+1個(gè)子密鑰。 輪密鑰生成算法以字為基礎(chǔ)，每個(gè)字包含32位（4個(gè)字節(jié)）。 下面以128位的種子密鑰為例，說明產(chǎn)生11個(gè)輪密鑰的方法。 首先將128位的種子密鑰分成16個(gè)字節(jié)，分別為key0, key1, key2, . , key1

36、5，每個(gè)keyi（0i15）8位，共128位。每一輪的輪密鑰由4個(gè)字（128位）組成，11個(gè)輪密鑰共包含44個(gè)字，表示為w0,w43.具體算法步驟如下：輪密鑰生成算法一、初始化10個(gè)字RCon（ 32位，4個(gè)字節(jié)）：RCon1=01000000 RCon9=1B000000RCon2=02000000 RCon10=36000000RCon3=04000000RCon4=08000000RCon5=10000000RCon6=20000000RCon7=40000000RCon8=80000000輪密鑰生成算法二、當(dāng)0i3時(shí)，wi=(key4i, key4i+1, key4i+2, key4i

37、+3)三、當(dāng)4i43且i0 mod 4時(shí)，wi=wi-4wi-1四、當(dāng)4i43且i=0 mod 4時(shí)wi=wi-4(SubWord(RotWord(wi-1) RConi/4)其中，RotWord(B0,B1,B2,B3)對(duì)四個(gè)字節(jié)(B0,B1,B2,B3)進(jìn)行循環(huán)移位操作：RotWord(B0,B1,B2,B3)=(B1,B2,B3,B0)SubWord進(jìn)行置換操作：SubWord(B0,B1,B2,B3)=(B0,B1,B2,B3)其中，Bi=SubBytes(Bi)，i=0,1,2,3解密算法AES的解密與加密算法相似但不對(duì)稱，偽代碼描述如下：AESDecipher(byte in16,

38、 byte out16,word w4*(Nr+1) byte state4,4; state=in;AddRoundKey(state, w4*Nr, 4*Nr+3);/前Nr-1輪解密 for(int round=Nr-1; round0;round-) InvShiftRows(state); InvSubBytes(state); AddRoundKey(state, w4*Nr, 4*Nr+3); InvMixColumns(state);/最后一輪解密 InvShiftRows(state); InvSubBytes(state); AddRoundKey(state, w0,3)

39、; 解密算法AES的解密使用了四種逆變換： InvSubBytes() InvShiftRows() InvMixColumns() AddRoundKey()（ AddRoundKey() 的逆變換是它自身）以相反的順序?qū)τ擅芪挠成涞玫降膕tate進(jìn)行變換完成。另外，AES的解密過程使用的子密鑰相同，但使用的順序相反。解密算法1.InvSubBytes變換InvSubBytes變換是字節(jié)替換SubBytes逆變換，即先用到仿射變換的逆變換，再計(jì)算GF(28)中的乘法逆。逆S-盒對(duì)狀態(tài)矩陣中的每一個(gè)字節(jié)進(jìn)行逆變換。通過如下逆S-盒實(shí)現(xiàn)：解密算法1.InvSubBytes變換也就是根據(jù) b7b6

40、b5b4b3b2b1b0反過來求得 b7b6b5b4b3b2b1b0 ，再求b7b6b5b4b3b2b1b0在GF(28)中的乘法逆，乘法逆即為逆S-盒的結(jié)果。解密算法2.InvShiftRows變換InvShiftRows變換是行移位變換ShiftRows的逆變換，對(duì)狀態(tài)矩陣的各行按照相反的方向進(jìn)行循環(huán)移位操作。第一行保持不變；第二行循環(huán)右移一個(gè)字節(jié)；第三行循環(huán)右移二個(gè)字節(jié)；第四行循環(huán)右移三個(gè)字節(jié)；解密算法3.InvMixColumns變換InvMixColumns變換是列混合變換MixColumns的逆變換，對(duì)狀態(tài)矩陣的各列進(jìn)行處理，把每一列當(dāng)作系數(shù)在GF(28)有限域上的四項(xiàng)多項(xiàng)式。與M

41、ixColumns對(duì)應(yīng)， InvMixColumns變換把列多項(xiàng)式與多項(xiàng)式a(x)相對(duì)于模多項(xiàng)式x4+1的逆a-1(x)相乘a-1(x)=0bx3+0dx2+09x+0e設(shè)列多項(xiàng)式為sc(x)=s0,c+s1,cx+s2,cx2 +s3,cx3，0c3， InvMixColumns變換寫成矩陣形式如下：AES的分析（1）在AES算法中，輪密鑰生成算法的非線性性質(zhì)消除了產(chǎn)生相同輪密鑰的可能性。加/解密過程中使用不同的變換可以避免出現(xiàn)弱密鑰、半弱密鑰、半半弱密鑰等。（2）經(jīng)過驗(yàn)證，AES能夠抵抗所有針對(duì)DES的攻擊方法的攻擊，如部分差分攻擊、相關(guān)密鑰攻擊等。（3）到目前為止，最有效的攻擊方法是窮舉

42、搜索攻擊，因此AES是安全的。AES的主要特點(diǎn) 不屬于Feistel結(jié)構(gòu) 加密、解密相似但不對(duì)稱 支持128數(shù)據(jù)塊大小 支持128/192/256密鑰長度 有較好的數(shù)學(xué)理論作為基礎(chǔ) 結(jié)構(gòu)簡(jiǎn)單、速度快AES的設(shè)計(jì)原則簡(jiǎn)單性簡(jiǎn)單性便于分析理解是如何抵抗所有類型的攻擊。對(duì)稱性（1）各輪之間的對(duì)稱性各輪之間具有對(duì)稱性，好處是在密鑰的控制下對(duì)同一輪交換進(jìn)行循環(huán)迭代，優(yōu)點(diǎn)是只要描述一輪變換即可將整個(gè)規(guī)范描述清楚，另外，在軟件實(shí)現(xiàn)中可僅對(duì)一輪進(jìn)行編輯。AES的設(shè)計(jì)原則對(duì)稱性（2）輪變換內(nèi)部的對(duì)稱性（3）D-盒的對(duì)稱性（4）S-盒的對(duì)稱性（5）加密和解密過程的對(duì)稱性AES的設(shè)計(jì)原則對(duì)抗攻擊方面（1）選擇差分均

43、勻性比較小和非線性度比較高的S-盒（2）適當(dāng)選擇線性變換，使得固定輪數(shù)中的活動(dòng)S-盒的個(gè)數(shù)盡可能多。優(yōu)點(diǎn)是可以估計(jì)算法的最大差分特征概率和最大線性逼近概率，這樣可以評(píng)估抵抗差分密碼分析和線性密碼分析的能力。AES的硬件實(shí)現(xiàn)在硬件實(shí)現(xiàn)方面，算法依靠有限域GF(28)的有關(guān)定義給加密和解密提供了良好的理論基礎(chǔ)，并且算法的結(jié)構(gòu)緊湊、規(guī)整，加密和解密過程相似，非常適合硬件實(shí)現(xiàn)，但有不利因素：（1）在輪變換過程中，變換函數(shù)的作用順序不同，解密過程與加密過程無法完全實(shí)現(xiàn)資源共享（2）算法的列變換過程和逆列變換過程中變換系數(shù)較大，矩陣乘法運(yùn)算耗時(shí)較多，影響加解密的速度（3）在每一輪變換的過程中，4個(gè)函數(shù)先后

44、執(zhí)行，增大了時(shí)延，因此應(yīng)對(duì)其優(yōu)化，使變換可以并行執(zhí)行，以減小時(shí)延，同時(shí)增加吞吐量。分組密碼的工作模式概述分組密碼以固定的分組長度作為基本的處理單元，要加密的消息長度通常比分組長度長很多。為了將算法應(yīng)用于實(shí)際，定義了幾種工作模式：NIST（美國國家標(biāo)準(zhǔn)技術(shù)研究所）定義了7種，其中5種比較常用。在之后的介紹中設(shè)分組的長度為b，分組的個(gè)數(shù)為n。電子本模式（ECB）電子密碼本ECB模式（Electronic Codebook Mode）是最簡(jiǎn)單的模式。對(duì)每個(gè)分組Pi使用相同的密鑰加密。Ci=Ek(Pi)，Mi=Dk(Ci) ，i=1,2,n加密前將整個(gè)明文分成長為b的分組，必要的話對(duì)最后一個(gè)進(jìn)行填充。

45、因k唯一，對(duì)每個(gè)分組只有唯一的密文。電子本模式（ECB）電子本模式（ECB）優(yōu)點(diǎn)：簡(jiǎn)單、易行加密后的輸出直接作為密文，不進(jìn)行任何形式的反饋，每個(gè)分組的處理相互獨(dú)立，是分組密碼的標(biāo)準(zhǔn)工作模式。電子本模式（ECB）缺點(diǎn)：（1）不能隱藏明文的模式信息在處理具有固定數(shù)據(jù)結(jié)構(gòu)的明文時(shí)，容易暴露明文數(shù)據(jù)的固有格式。例如，某些報(bào)文具有標(biāo)準(zhǔn)化的形式，如作業(yè)號(hào)、通信地址、發(fā)表時(shí)間、密級(jí)等數(shù)據(jù)，這些數(shù)據(jù)除了有固定的位置，明文數(shù)據(jù)也非常有規(guī)律。這些信息在加密后將出現(xiàn)在同一位置，為破譯帶來線索。電子本模式（ECB）缺點(diǎn)：（2）對(duì)明文的主動(dòng)攻擊是可能的：因分組相互獨(dú)立，信息塊可被替換、重排、刪除、重放。（3）無法糾正傳

46、輸中的同步錯(cuò)誤如果密文在傳輸中增加或丟失一個(gè)bit，將引起密文分組的對(duì)齊錯(cuò)誤，整個(gè)密文序列將不能正確解密。密碼分組鏈接模式（CBC）Cipher Block Chaining Mode加密算法的輸入是當(dāng)前明文分組Mi和上一次產(chǎn)生的密文分組Ci的異或，即：C0=IVCi=Ek(MiCi-1)，1in解密：C0=IVMi=Dk(Ci)Ci-1，1inIV（初始化向量）在加解密中都用到，通信雙方必須都知道，一般無需保密，隨消息進(jìn)行更換。CBC加解密示意圖：密碼分組鏈接模式（CBC）特點(diǎn)：（1）能夠隱藏明文的數(shù)據(jù)模式，相同的明文可對(duì)應(yīng)不同的密文。（2）在一定程度上抵抗主動(dòng)攻擊：信息塊不容易被替換、重排

47、、刪除、重放（3）誤差有限傳遞：密文中一個(gè)位的錯(cuò)誤只影響當(dāng)前分組和下一個(gè)分組的解密。密碼反饋模式（CFB）Cipher Feedback Mode模式中，引入一個(gè)整數(shù)參數(shù)s，1sb，明文按s進(jìn)行分組，且明文的長度必須是s的整數(shù)倍。CFB的加解密過程密碼反饋模式（CFB）令函數(shù)LSBi()表示輸入的前i個(gè)最低有效位，MSBi()表示輸入的前i個(gè)最高有效位。例如，LSB3(111011011)=011， MSB4(111011011)=1110。加解密規(guī)則如下：密碼反饋模式（CFB）特點(diǎn)：CFB模式由于有密文反饋，若密文分組中有一位或多位出錯(cuò)，將引起當(dāng)前分組和后續(xù)部分分組的解密錯(cuò)誤。只有當(dāng)錯(cuò)誤的密文比特從寄存器中移出后，解密才會(huì)恢復(fù)正常。故一個(gè)密文分組的錯(cuò)誤，影響后面最多 個(gè)分組的解密。 表示大于等于x的最小正整數(shù)。輸出反饋模式（OFB）Output Feedback Mode通過反復(fù)加密一個(gè)初始向量IV來得到密鑰流，這種機(jī)制獨(dú)立于明文和密文。定義Z0=IV，然后計(jì)算：Zi=Ek(Zi-1)，1in加密： Ci=MiZi解密： Mi=CiZiOFB的加解密過程輸出反饋模式（OF