密碼學課件：六、分組密碼-AES

1、分組密碼主要內(nèi)容AES算法的數(shù)學基礎AES介紹分組密碼的工作模式國際數(shù)據(jù)加密標準-IDEAAES算法的數(shù)學基礎有限域及其運算群和交換群的定義一個非空集合G上定義一個二元運算“”，如果滿足下列條件（1）封閉性： a,bG，有abG；（2）結合律： 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；如果群滿足交換律，則稱為交換群。如果一個群的元素是有限的，則為有限群，否則為無限群。定義：有

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

3、=1，矛盾），根據(jù)元素的階的定義， 有ap=1且a,a2,a3,a(p-1),ap彼此不同。根據(jù)群中運算的封閉性有a,a2,a3,a(p-1),apG，又因為G的階為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為素數(shù)，a是m的本原根，在集合Zm*=1,2,m-1定義二元運算”如下：xy=(ax mod m)(ay mod m)=a(x+y) mod m, x,yZm*則(Zm*

4、,)為循環(huán)群。其中，單位元為1。任意元素的階都為m-1，任何元素都可以作為群的生成元。m為素數(shù)，a是m的本原根，集合Zm*=a mod m, a2 mod m, a3 mod m,am-1 mod m上定義的數(shù)乘”運算構成群，且為循環(huán)群。即群(Zm*,)為循環(huán)群。其中，單位元為1。環(huán)的定義環(huán)是一個代數(shù)系統(tǒng)，它由一個至少包含兩個元素的集合R構成，在集合R上定義有兩個二元運算：加法“+”和乘法“”，并滿足下列條件。（1）R關于加法“+”是一個交換群，其單位元為“0”，稱為環(huán)的零元，元素a的逆元為-a；與加法對應的逆運算（減法）定義為：a-b=a+(-b)。（2）乘法滿足結合律： 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ù)集關于整數(shù)的加法和乘法構成整數(shù)環(huán)。類似地，有理數(shù)集關于有理數(shù)的加法和乘法構成有理數(shù)環(huán)；實數(shù)集關于有理數(shù)的加法和乘法構成實數(shù)環(huán)；復數(shù)集關于有理數(shù)的加法和乘法構成復數(shù)環(huán)。此外，若令 表示全體偶數(shù)構成的集合，則 關于偶數(shù)的加法和乘法構成一個環(huán)，稱為偶數(shù)環(huán)。一般地，凡是數(shù)（無論是實數(shù)還是復數(shù)）集關于數(shù)的加法和乘法構成的環(huán)都稱為數(shù)環(huán)。顯而易見，凡是數(shù)環(huán)都以數(shù)0為其零元。例如例3 設n是一個正整數(shù)，設集合 Zn=0n, 1n, , n-1

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

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

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

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

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

11、。多項式的帶余除法定理設a(x)和b(x)為F上的多項式，且b(x)0，則存在唯一的一對元素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)為可約多項式，否則稱a(x)為不可約多項式。Fx上域的構造對Fx中的每個不可約多項式p(x)，可以如下構造一個域

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

13、(x)即為pn階域。有限域元素的多項式表示由定理，對每個素數(shù)p，都可以構造一個p階有限域。這樣，可以得出如下結論：任何有限域必與某一多項式域同構，因此，可以用多項式域來表示其他有限域。有限域元素還有其他許多表示方法，而不同的表示方法可能在計算的效率有一些差別。例：16階域GF(24)的構造16階域GF(24)可在2階域上構造。設集合F=0,1，F(xiàn)上定義運算+和如下：1+1=0,0+0=0,1+0=0+1=1；11=1,00=0,10=01=0。則以上F和運算構成的代數(shù)系統(tǒng)為2階域。設p(x)為以上2階域上的一個4次不可約多項式，則Fxp(x)中的所有16個元素為：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，且多項式域為16階域。其中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)的構造下面確定p(x)。因F上的4次不可約多項式有x4+x3+x2+x+1，x4+x3+1和x4+x2+1，而同階的有限域是同構的，故可從上述不可約多項式中任選一個作為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因此以上構造的多項式域為16階域。例：16階域GF(24)的構造分析：針對多項式域，群為循環(huán)群，對除0外的所有15個元素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的階進行計算，階為15的元素即為該群的生成元，也就是域的本原元，共有(16-1)=8個，分別是：x+1, x2+1, x2+x, x2+x+1, x3+1, x3+x, x3+x+1, x3+x2+x因此循環(huán)群可以表示成這些生成元的冪的形式。如：設生成元=x+1，則a(x)=x2+x+1=7 mod p(x)和b(x)=x3+x2+x+1=3 mod p(x)，進一步有a(x)b(x)=73 mod p(x)=10 mod p(x)=x3+x216階域的結構同階有限域都同構

17、，故下表包含了所有16階域運算的全部信息。域中的元素關于乘法的階=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個。表中給出了關于這兩個本原元、 的運算結果，顯然是同構的，因為i=7i。例，構造域GF(28)同理，可構造256階域GF(

18、28)例如可取不可約多項式為p(x)=x8+x4+x3+x+1，則Fxp(x)中的所有256個元素為：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。定義運算：a(x)b(x)=(a(x)+b(x) mod p(x)a(x)b(x)=(a(x)b(x) mod p(x)則多項式域為256階域。256階有限域GF(28)256階有限域的特征為2，根據(jù)前面

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

20、二進制為：01010111，對應的多項式為：x6+x4+x2+x+1GF(28)中元素的多項式表示AES算法對字節(jié)進行運算，把一個字節(jié)（8bit: b7b6b5b4b3b2b1b0 ）對應成多項式域Fxp(x)上的一個元素。這樣， AES中對字節(jié)的運算可以轉換為256階域GF(28)上的多項式的運算。下面介紹多項式的運算特點。GF(28)中元素的多項式表示GF(28)上的加法說明：根據(jù)域運算的封閉性，域GF(28)中任意兩個元素的和仍在域中，運算結果的系數(shù)等于兩個元素對應多項式的系數(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ù)域運算的封閉性，多項式域GF(28)中任意兩個元素的乘積仍在域中，乘積采用模乘，結果也是一個次數(shù)不超過7的多項式。多項式域GF(28) 上的模常使用的一個不可約多項式為m(x)=x8+x4+x3+x+1，它的二進制表示為：100011011，十六進制表示為“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) （多項式的分解）對應二進制11000001GF(28)上的x乘法GF(28)上還定義了一個運算，稱為x乘法，定義為：xb(x)=(b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0 x) mod m(x)如果b7=0，求模結果不變，若b7=1，則結果加上m(x)。由此得出x乘法的高效運算方法：因多項式x對應于元素00000010，則要求xb(x)，可以先對b(x)在字節(jié)內(nèi)左移一位（最后一位補0），若b7=1，則再與“1B”（其二進制為00011011）進行逐位異或來實現(xiàn)。因此：x乘法實現(xiàn)的效率非常高。該運算記

23、為xtime(b) x乘法實現(xiàn)的效率非常高，可利用x乘法來加快GF(28)中任意兩個元素的乘法運算。例如：5713的實現(xiàn)：13=01+02+10（將13分解）5702=xtime(57)=AE （01010111,左移1位, 010101110,b7=0,結果不變?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、運算字運算也是定義在域上的運算。AES中的一個字由4個字節(jié)構成，每個字節(jié)看成是GF(28)中的一個元素。4個字節(jié)構成的字可以表示成一個次數(shù)小于4的多項式，其系數(shù)取自GF(28)。例如，對于字： 57 83 4A D1對應的多項式為：57x3+83x2+4Ax+D157、83、4A、D1分別對應GF(28)中的一個多項式。字的加法兩個字相加：對應的多項式的系數(shù)相加，對應系數(shù)簡單按位異或。例如：57 83 4A D1+26 ED 41 22對應的系數(shù)相加就是GF(28)中多項式的相加：57+26：83+ED：4A+41：D1+22：字的乘法多項式的乘法：設a(x)=a3x3+a2x2+a1x+a0

25、，b(x)=b3x3+b2x2+b1x+b0，c(x)=a(x)b(x)，又設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次的多項式，不能表示成4字節(jié)，通過模一個4次多項式M(x)進行化簡，使得結果變?yōu)榇螖?shù)小于4次的多項式。字（多項式）的乘法取4次多項式M(x)=x4+1，設(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以上運算中aibj即是GF(28)上多項式乘法。字（多項式）的乘法說明：因為M(x)=x4+1=(x+1)(x3+x2+x+1)，故M(x)不是不可約多項式。這樣，字的乘法運算中，與一個多項式的模x4+1乘法將不一定可逆（因與M(x)不一定互素）。AES中，特意選擇一個具有逆元的固定多

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

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

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

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

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

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

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

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

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

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

37、+3)三、當4i43且i0 mod 4時，wi=wi-4wi-1四、當4i43且i=0 mod 4時wi=wi-4(SubWord(RotWord(wi-1) RConi/4)其中，RotWord(B0,B1,B2,B3)對四個字節(jié)(B0,B1,B2,B3)進行循環(huán)移位操作：RotWord(B0,B1,B2,B3)=(B1,B2,B3,B0)SubWord進行置換操作：SubWord(B0,B1,B2,B3)=(B0,B1,B2,B3)其中，Bi=SubBytes(Bi)，i=0,1,2,3解密算法AES的解密與加密算法相似但不對稱，偽代碼描述如下：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進行變換完成。另外，AES的解密過程使用的子密鑰相同，但使用的順序相反。解密算法1.InvSubBytes變換InvSubBytes變換是字節(jié)替換SubBytes逆變換，即先用到仿射變換的逆變換，再計算GF(28)中的乘法逆。逆S-盒對狀態(tài)矩陣中的每一個字節(jié)進行逆變換。通過如下逆S-盒實現(xiàn)：解密算法1.InvSubBytes變換也就是根據(jù) b7b6

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

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

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

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

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

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

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

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