高級數(shù)據(jù)加密標(biāo)準(zhǔn)AES課件

高級數(shù)據(jù)加密標(biāo)準(zhǔn)AES背景AES的數(shù)學(xué)基礎(chǔ)AES加密算法描述AES解密算法算法評價結(jié)論背景現(xiàn)代計算機速度的迅速提高，使得只有56bit密鑰的DES算法的安全性面臨著極大的挑戰(zhàn)。1997年，NIST公開征求AES（AdvancedEncryptionStandard）作為2001年以后的數(shù)據(jù)加密標(biāo)準(zhǔn)。1998年8月，AES召開第一次候選會，確定15個算法入圍。1999年3月，AES召開第二次候選會，有5個算法入圍（MARS,RC6,Rijndael,Serpent和Twofish）。2000年10月，NIST選出由比利時的JoanDaemen和VincentRijmen提交的Rijndael算法作為AES。2001年夏天，NIST頒布新的信息處理標(biāo)準(zhǔn)（FIPS），將Rijndael算法作為AES。AES的數(shù)學(xué)基礎(chǔ)(1)有限域GF(28)上定義了4種運算：“+”、“·”、“·X”和帶系數(shù)的多項式乘運算“”。對字節(jié)b，用多項式表示為：

b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0“+”運算：兩個字節(jié)相加，相當(dāng)于字節(jié)的每一位簡單異或。例：’57’＋’83’＝‘d4’(57)16=(01010111)2→x6+x4+x2+x+1(83)16=(10000011)2→x7+x+1’57’＋’83’→(x6+x4+x2+x+1)+(x7+x+1)=x7+x6+x4+x2→(11010100)2＝(d4)16AES的數(shù)學(xué)基礎(chǔ)(2)“·”運算：選擇一個不可約多項式：m(x)=x8+x4+x3+x+1，“·”運算為兩多項式相乘后進行模m(x)的運算。例：’57’·’83’＝‘c1’(57)16=(01010111)2→x6+x4+x2+x+1(83)16=(10000011)2→x7+x+1’57’·’83’→(x6+x4+x2+x+1)·(x7+x+1)mod(x8+x4+x3+x+1)=x13+x11+x9+x8+x7+x7+x5+x3+x2+

x+x6+x4+x2+x+1)mod(x8+x4+x3+x+1)

=(x13+x11+x9+x8+x6+x5+x4+x3+1)mod(x8+x4+x3+x+1)

＝x7+x6+1→(11000001)2＝(c1)16(x13+x11+x9+x8+x6+x5+x4+x3+1)mod(x8+x4+x3+x+1)

:X5+x3x8+x4+x3+x+1x13+x11+x9+x8+x6+x5+x4+x3+1x13+x9+x8+x6+x5x7+x6+1x11+x4+x3+1x11+x7+x6+x4+x3AES的數(shù)學(xué)基礎(chǔ)(3)“·X”運算：

b·X=b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x求乘法逆元：因為m(x)是GF(28)上的不可約多項式，所以對于任意b(x)，都可以用擴展的Euclid算法求a(x)，使得

a(x)·b(x)+c(x)·m(x)=1

因而a(x)·b(x)modm(x)=1

即b－1(x)modm(x)=a(x)例：求(x7+x6+1)關(guān)于模m(x)＝x8+x4+x3+x+1的乘法逆元。輾轉(zhuǎn)相除：

x8+x4+x3+x+1＝(x7+x6+1)(x+1)+(x6+x4+x3)x7+x6+1=(x6+x4+x3)(x+1)+(x5+x3+1)x6+x4+x3=(x5+x3+1)x+(x3+x)x5+x3+1=(x3+x)x2+1擴展的Euclid算法：

1=(x5+x3+1)＋(x3+x)x2

＝(x5+x3+1)＋((x6+x4+x3)+(x5+x+1)x)x2

=(x5+x3+1)(1+x3)+(x6+x4+x3)x2

=[(x7+x6+1)+(x6+x4+x3)(x+1)](1+x3)+(x6+x4+x3)x2

=(x7+x6+1)(1+x3)+(x6+x4+x3)(x4+x3+x2+x+1

)=(x7+x6+1)(1+x3)+[(x8+x4+x3+x+1)+(x7+x6+1)(x+1)](x4+x3+x2+x+1

)=(x7+x6+1)(x5+x3)+(x8+x4+x3+x+1)(x4+x3+x2+x+1

)

因此，(x7+x6+1)－1mod(x8+x4+x3+x+1)＝x5+x3

AES的數(shù)學(xué)基礎(chǔ)(4)帶系數(shù)的多項式乘運算“”：令a(x)=a3x3+a2x2+a1x+a0,b(x)=b3x3+b2x2+b1x+b0,其乘積

c(x)=a(x)·b(x)=c6x6+c5x5+c4x4+c3x3+c2x2+c1x+c0其中，c0=a0

·b0c1=a1·b0

a0

·b1c2=a2·b0

a1

·b1

a0

·b2c3=a3·b0

a2

·b1

a1

·b2

a0

·b3c4=a3·b1

a2

·b2

a1

·b3c5=a3·b2

a2

·b3c6=a3

·b3對（x4+1）取模得d(x):d(x)=a(x)b(x)=d3x3+d2x2+d1x+d0其中，d0=a0

·b0

a3·b1

a2

·b2

a1

·b3

d1=a1·b0

a0

·b1

a3·b2

a2

·b3d2=a2·b0

a1

·b1

a0

·b2

a3

·b3d3=a3·b0

a2

·b1

a1

·b2

a0

·b3注意：ximod(x4+1)=ximod4AES加密算法描述加密算法概述一圈變換密鑰擴展加密算法描述加密算法概述（1）AES算法與以往的基于Feistel網(wǎng)的密碼（如DES）不同，算法的每一步都是可逆的。算法的明文塊長可以為128bit，192bit或256bit，密鑰也可以分別為128bit，192bit或256bit。算法有多圈相同的運算，每一圈包括4個步驟：非線性代替（S-盒）行循環(huán)左移（ShiftRow）列混合變換（MixColum）與擴展密鑰相異或每一圈的子密鑰從擴展密鑰中取出密鑰擴展過程同時應(yīng)用了非線性變換和循環(huán)左移算法定義的所有運算都是在有限域GF(28)上進行的加密算法概述（2）算法中進行運算的單位包括：1個字節(jié)1列1行用字節(jié)數(shù)組表示的整個加密塊加密塊數(shù)組中，n可以是3，5，7，所代表的加密塊分別表示128bit，192bit和256bit。ai,ja0,ja1,ja2,ja3,jai,0ai,1…ai,3a0,2a0,3a1,2a1,3a2,2a2,3a0,0a0,1a1,0a1,1a2,0a2,1a3,0a3,1a3,2a3,3…a0,n…a1,n…a2,n…a3,n加密算法概述（3）令Nr代表算法的圈數(shù)，Nk代表密鑰長度/32，Nb代表塊長度/32，則算法的圈數(shù)Nr的取值與Nk和Nb的關(guān)系為：除最后一圈不做列混合變換外，每一圈都經(jīng)過4步相同的操作：NrNb＝4Nb＝6Nb＝8Nk＝4101214Nk＝6121214Nk＝8141414Round(State,RoundKey){

ByteSub(State);//S-盒

ShiftRow(State);//行循環(huán)左移

MixColumn(State);//列混合變換

AddRoundKey(State,RoundKey);//與擴展密鑰相異或}一圈變換（1）非線性代替（S-盒）：包括2步在GF(28)上求每個字節(jié)關(guān)于模m(x)的乘法逆元素，‘00’的逆元定義為‘00’；應(yīng)用GF(2)上的一個仿射變換：一圈變換（2）每個字節(jié)aij經(jīng)過以上2步變換后，記為bij?？梢詫⒚總€可能的aij值對應(yīng)的bij值制成表格，通過查表的方式來實現(xiàn)S-盒代替，見下表。其中‘xy’代表1個字節(jié)的16進制表示。一圈變換（3）行循環(huán)左移（ShiftRow）：每一行以字節(jié)為單位循環(huán)左移，左移的字節(jié)數(shù)見右表。因此，第1行不移位，第2行左移1個字節(jié)…列混合變換（Mixcolumn）：對每一列中每個字節(jié)a(x)，令b(x)=c(x)a(x)，其中c(x)為：c(x)=’03’x3+’01’x2+’01’x+’02’與擴展密鑰相異或：aijkij＝bijNbC1C2C3412361238134一圈變換（4）一圈結(jié)構(gòu)圖：Step1.ByteSub(State)Step2.ShiftRow(State)Step3.MixColumn(State)Step4.AddRoundKey(State,RoundKey)StateS-盒行循環(huán)左移c(x)AARoundKeyRound(State,RoundKey)密鑰擴展（1）擴展密鑰是一個以4字節(jié)大小為單位(用Word表示)的線性數(shù)組。當(dāng)Nk大于6的時候有一點不同。開始Nk個Word是加密用的密鑰，以后每個Word通過對K實行變換得到。當(dāng)Nk≤6時，若Nk

?i，則Word[i]=Word[i-1]Word[i-Nk];若Nk|i，則先循環(huán)左移，然后查非線性變換表（S-盒），之后再與常量Rcon[i/Nk]異或，其中：Rcon[i]=(RC[i],’00’,’00’,’00’)，RC[1]=1，RC[i]=x·(RC[i-1])=x(i-1)。最后，與Word[i-Nk]異或。當(dāng)Nk＝8時，若imodNk=4，則先查非線性變換表，再與Word[i-Nk]異或。密鑰擴展的偽代碼：

KeyExpansion(bytekey[4*Nk],wordw[Nb*(Nr+1)],Nk){ for(i=0;i<Nk;i++) w[i]=word[key[4*i],key[4*i+1],key[4*i+2],key[4*i+3]]; for(i=Nk;i<Nb*(Nr+1);i++){ wordtemp=w[i-1]; if(i%Nk==0) temp=SubWord(RotWord(temp))^Rcon[i/Nk]; elseif(Nk==8andi%Nk==4) temp=SubWord(temp); w[i]=w[i-Nk]^temp; }}密鑰擴展（2）可以從擴展密鑰中選擇Roundkey，例如：當(dāng)Nb＝6,Nk＝4時，擴展密鑰和各圈子密鑰的選擇如下：加密算法描述整個算法可以用

下面的代碼表示：

Rijndael(State,CipherKey) {

KeyExpansion(CipherKey,ExpandedKey);

AddRoundKey(State,ExpandedKey); for(i=1;i<Nr;i++) Round(State,ExpandedKey+Nb*i);

FinalRound(State,ExpandedKey+Nb*Nr); }AES解密算法（1）由于Rijndael算法的每一步都是可逆的，因此一圈的逆過程如下：

InvRound(State,RoundKey) {

AddRoundKey(State,RoundKey);

InvMixColumn(State);

InvShiftRow(State);

InvByteSub(State); }AES解密算法（2）列混合變換的逆變換InvMixColumn：

s’(x)=c-1(x)s(x)

對于0≤j＜Nb，有循環(huán)左移的逆變換為循環(huán)右移相應(yīng)的字節(jié)數(shù)AES解密算法（3）逆S-盒：先做逆仿射變換，然后求GF(28)上模m(x)的乘法逆元，也可以做成一個查找表（逆S-盒）。算法評價(1)所有的運算定義在有限域GF(28)上，算法執(zhí)行時除了一個查表操作外，其它的運算都是簡單的異或和移位，運行速度很快。在每一圈運算和密鑰擴展中都應(yīng)用了非線性操作，大大增強了抗差分和線性密碼分析能力。輪運算：（1）所有操作都是可逆的；（2）每一步對一定攻擊都有很強的抵抗能力，S-盒能抵抗差分和線性密碼分析，行循環(huán)左移能抵抗截斷差分密碼分析及Square攻擊，列混合達到了擴散的目的；（3）能在廣泛的硬件平臺上高效快速地執(zhí)行；（4）每一步操作都易于描述。算法評價(2)密鑰擴展：（1）非線性操作防止了僅僅由密鑰的差分而導(dǎo)致每一圈子密鑰的差分；（2）密鑰擴展產(chǎn)生的效果使每一圈子密鑰都不同；（3）有效地抵抗密鑰相關(guān)分析及已知部分密鑰的分析；（4）消除了每圈中以及圈與圈之間的對稱性；（5）運行速度快，易于描述。抵抗常見攻擊：研究表明，AES算法能夠抵抗差分和線性密碼分析、截斷差分分析、Square攻擊和相關(guān)密鑰分析等攻擊方法；沒有弱密鑰，因此對密鑰的選擇沒有