第五章 對稱密碼體制之三,信息安全技術(shù),5.3 高級加密標(biāo)準(zhǔn)AES 5.3.0 AES概述 1997.4.15美國家標(biāo)準(zhǔn)和技術(shù)研究所NIST(National Institure of Standard Technology)發(fā)起AES征集 1997.9.12在美聯(lián)邦登記處公布征集公告 1998.8.20第一次AES候選會議公布15個算法 1999.3.22第二次AES候選會議公布分析測試結(jié)果 1999.8 NIST選出5個候選算法 2000.4.13第三次AES候選會議討論分析測試結(jié)果 2000.10.2 NIST正式宣布獲勝者為Rijndael算法（讀作“Rain Doll”） 2001 NIST正式發(fā)布基于Rijndael算法的AES,設(shè)計者比利時Katholieke大學(xué)電機(jī)系COSIC實(shí)驗室博士后研究員Vincent Rijman、比利時Proton國際公司博士設(shè)計員Joan Daemen 設(shè)計準(zhǔn)則 能抵抗所有已知的攻擊 多平臺運(yùn)行時速度快、編碼簡單 設(shè)計簡單 安全性時限至少可維持20年,AES與Rijndael算法在概念上的區(qū)別 AES是NIST所制定的數(shù)據(jù)加密標(biāo)準(zhǔn)，采用128位分組，128、192或256位密鑰的Rijndael算法,Rijndael算法本身是一種可變分組長度和可變密鑰長度的分組密碼算法，分組長度和密鑰長度可獨(dú)立地設(shè)定為128256的32整數(shù)倍,密鑰安全強(qiáng)度 128位密鑰空間3.41038，用攻擊DES的機(jī)器約需149 1012年才能窮舉攻陷（宇宙誕生至今約小于7 1010年） 192位密鑰空間 6.21057 256位密鑰空間 1.1 1077,5.3.1 算法描述 Rijndael屬于對稱密碼體制 Rijndael采用S-P網(wǎng)絡(luò)結(jié)構(gòu) NIST對Rijndael 的評估標(biāo)準(zhǔn)及結(jié)論 一般安全性沒有已知的能攻破Rijndael 的攻擊方法 軟件執(zhí)行 具有良好的軟件執(zhí)行性能 受限空間環(huán)境非常適合在受限空間環(huán)境中執(zhí)行操作 硬件執(zhí)行在反饋模式下速度最快 對執(zhí)行的攻擊有利于抵抗能量攻擊和計時攻擊 加密與解密加密與解密算法不同，但速度相當(dāng),密鑰靈活性支持加密中的快速子密鑰計算 其他的多功能性和靈活性原則上分組與密鑰長度為32的任意倍數(shù) 指令級并行執(zhí)行的潛力對于單個分組加密有很好的并行執(zhí)行能力,5.3.2 Square結(jié)構(gòu)（略）,5.3.3 基本運(yùn)算 4種變換 AK輪密鑰加(AddRoundKey)，即異或運(yùn)算“” BS字節(jié)代換(ByteSub) SR行移變換(ShiftRow) MC列混合變換(MixColumn) 2種基本運(yùn)算 字節(jié)運(yùn)算（8位） 雙字運(yùn)算（4字節(jié)）,算法總流程,BS、SR和MC,明文X,輪密鑰K0,輪密鑰K1,BS、SR和MC,輪密鑰Kr-1,BS、SR,輪密鑰Kr,密文Y,SR-1、BS-1,明文X,MC-1,SR-1 、 BS-1,密文Y,MC-1,SR-1、BS-1,AK,AK,AK,AK,AK,AK,AK,AK,第1輪,第r-1輪,第r輪,第1輪,第r-1輪,第r輪,加密,解密,其中： SR-1 、 BS-1 、MC-1 分別是SR 、 BS 、MC的逆變換,狀態(tài)列,明文、密文、中間結(jié)果（稱為“狀態(tài)”）和密鑰均以先列后行的順序映射到4行的字節(jié)矩陣上，每列對應(yīng)一個雙字（4字節(jié)、32位） 狀態(tài)列數(shù)記作Nb， Nb=分組長度/32 密鑰列數(shù)記作Nk， Nk =種子密鑰長度/32 可能的列數(shù)Nb、 Nk有48（對應(yīng)的分組或密鑰長度為128、160、192、224、256） 實(shí)際應(yīng)用時Nb、 Nk常取4、6、8之一,輪數(shù)r取決于分組長度和密鑰長度：,迭代輪數(shù),GF(28)上的字節(jié)運(yùn)算 伽羅瓦(Galois)域GF(28)中的元素a是一個字節(jié)矢量 (a7,a1,a0) =xxH，可表作系數(shù)是0或1的次數(shù)小于8的多項式： a = a7x7 + a1x + a0 如：3BH=(00111011)在GF(28)中可以表作x5+x4+ x3+x+1 在GF(28)中的加法是按位異或 在Rijndael中取模m=11BH=(100011011)= x8+x4+x3+x+1,在GF(28)中的乘法是以m為模的多項式乘法，即相乘后再用m約簡，記作“ ” 例如：57H 83H = ( 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+ x3+ 1)+ x5 (x8+ x4+ x3+ x + 1)（可任意加上模的倍數(shù)） = (x11+ x4 + x3 + 1) + x3 (x8+ x4+ x3+ x + 1) =x7+ x6 + 1=C1H,GF(28)中的元素a乘以x（對應(yīng)02H）相當(dāng)于字節(jié)(a7,a1,a0)左移1位，但當(dāng)有溢出時必須用模m=11BH=(100011011)= x8+x4+x3+x+1來約簡，這相當(dāng)于異或11BH。 稱這種特殊的一元運(yùn)算為“x乘”。,例如： x 57H=x 01010111=10101110=AEH x AEH=x 10101110=101011100（有溢出） =101011100 100011011=01000111=47H； 顯然：57H 04H= (57H 02H) 02H = x (x 57H)=x AEH =47H； 而57H 03H = (57H 02H)+57H =x 57H +57H; 這就意味著對任意字節(jié)a的乘法均可分解為 若干x乘運(yùn)算，以便于算法的程序?qū)崿F(xiàn)。,在GF(28)中的乘法幺元是01H=(00000001)=1 對于GF(28)中的非零a，必存在b，使得b a=1，也即存在c，使得b a +m c=1，或a b=1 (mod m)，稱b為a的乘法逆元，記作“a-1” a = (a7,a1,a0)的乘法逆元a-1可由下述方法算出： 設(shè)a-1 = (x7,x1,x0)，則由a a-1 =1 (mod m)可得關(guān)于x7,x1,x0的聯(lián)立方程組，于是可算出x7,x1,x0 ，從而得到a-1,4字節(jié)列向量的表示與運(yùn)算 在Rijndael中，由4個字節(jié)組成的列向量（a0j，a1j，a2j，a3j )被表示為伽羅瓦環(huán)GF(28)x/(x4+1)中的元素a 系數(shù)為兩位十六進(jìn)制數(shù)、次方不超過4的多項式a0j x3 + a1j x2 + a2j x + a3j 環(huán)中兩個元素相加定義為相應(yīng)的字節(jié)在GF(28)中的相加（按位異或） 環(huán)中兩個元素相乘定義為對模m=x4+1=01H x4+01H 的普通多項式相乘，但系數(shù)運(yùn)算遵從GF(28)中的運(yùn)算,5.3.4 基本變換 字節(jié)代換BS S盒變換 分別對狀態(tài)的所有字節(jié)a進(jìn)行如下仿射變換：, a-1 +,b=BS(a)=,其中： a-1是a的乘法逆元,注：計算上定義了一個S盒由16*16個字節(jié)組成的矩陣（見下頁），包含了256種可能的變換。以輸入字節(jié)的高4位為行值、低4位作為列值，然后取出S盒中的對應(yīng)字節(jié)作為輸出。,用于字節(jié)運(yùn)算的S盒,例：對輸入“95H”，在第9行第5列找到輸出為“2aH”,行移變換SR 將狀態(tài)的第i行循環(huán)左移Ci 個字節(jié) （i=1,2,3;第0行不動） Ci=1,2,3或4,Ci取決于明文長度 (i=1,2,3)：,列混合變換MC 對狀態(tài)的各個字節(jié)列Aj進(jìn)行變換(j=0,1,Nb-1) ：,把狀態(tài)列當(dāng)作伽羅瓦環(huán)GF(28)x/(x4+1)中的多項式a= a0j x3 + a1j x2 + a2j x + a3j ，對一個固定的多項式c= 03H x3 + 01H x2 + 01H x + 02H作模m=01H x4+01H的乘法a * c 。,設(shè)某狀態(tài)列為 a(x) = a0j x3 + a1j x2 + a2j x + a3j ， 轉(zhuǎn)換后狀態(tài)列為 b(x) = c(x) * a(x) = b0j x3 + b1j x2 + b2j x + b3j， 則可推出： b0j= 02H a0j + 03H a1j + 01H a2j +01H a3j b1j= 01H a0j + 02H a1j + 03H a2j +01H a3j b2j= 01H a0j + 01H a1j + 02H a2j +03H a3j b3j= 03H a0j + 01H a1j + 01H a2j +02H a3j,用矩陣乘法表示即為：,輪密鑰加變換AK 對狀態(tài)的各個字節(jié)列與密鑰字wj進(jìn)行按位異或,密鑰擴(kuò)展,種子密鑰K=(k0,k1, ,kNk-1),擴(kuò)展密鑰W=(w0,w1, ,wNb*(r+1)-1),共Nk個雙字，32* Nk位,因需(r+1)個含Nb個雙字的輪密鑰，故共需Nb*(r+1) 個雙字的擴(kuò)展密鑰,每個雙字4字節(jié)32位,5.3.5 密鑰擴(kuò)展與調(diào)度,對于Nk6,wi=,ki ;當(dāng)i<Nk,wi-Nk BS(R(wi-1 ) Ci/Nk ;當(dāng)i是Nk的倍數(shù),wi-Nk wi-1 ;其余情況,其中： i=0,1,Nb(r+1)-1 BS表示對雙字的每個字節(jié)分別進(jìn)行如前字節(jié)代換 R表示將雙字循環(huán)左移1字節(jié) 輪常數(shù)cj= (c0,j 00H 00H 00H)，c0,1=01H，c0,j=x c0,j-1，即左移1位，若溢出則再異或11BH,c0,2=02H， c0,3=04H， c0,4=08H， c0,5=10H， c0,6=20H， c0,7=40H， c0,8=80H， c0,9=1BH， c0,10=36H（后兩個均左移后異或11BH） 例如：設(shè)Nk=4，128位種子密鑰K=(k0,k1,k2,k3)，則 (w0,w1,w2,w3)=(k0,k1,k2,k3)， w4 = w0 BS(R(w3 ) (01H 00H 00H 00H) w5 = w1 w4；w6 = w2 w5 ；w7 = w3 w6 w8 = w4 BS(R(w7 ) (02H 00H 00H 00H) w9 = w5 w8 實(shí)例：P104【例5-5】,對于Nk6,wi=,ki ;當(dāng)i<Nk,wi-Nk BS(R(wi-1 ) ci/Nk ;當(dāng)i是Nk的倍數(shù),wi-Nk wi-1 ;其余情況,wi-Nk BS(wi-1) ;當(dāng)i-4是Nk的倍數(shù),例如：設(shè)Nk=8，256位種子密鑰K=(k0,k1,k2,k3 ,k4 ,k5,k6 ,k7 )， 則 (w0,w1,w2,w3 ,w4,w5,w6 ,w7)=(k0,k1,k2,k3 ,k4 ,k5,k6 ,k7 )， w8 = w0 BS(R(w7 ) (01H 00H 00H 00H) w9 = w1 w8；w10 = w2 w9 ；w11 = w3 w10 w12 = w4 BS(w11) w13 = w5 w12；w14 = w6 w13 ；w15 = w7 w14 w16 = w8 BS(R(w15 ) (02H 00H 00H 00H) w17 = w9 w16 ,密鑰調(diào)度,擴(kuò)展密鑰W=(w0,w1, ,wNb*(r+1)-1),共Nb*(r+1) 個雙字,初始輪密鑰K0 =(w0,w1, ,wNb-1),第1輪輪密鑰K1 =(wNb,wNb+1, ,w2Nb-1),第2輪輪密鑰K2 =(w2Nb,w2Nb+1, ,w3Nb-1), ,第r輪輪密鑰Kr =(wr*Nb,wr*Nb+1, ,w(r+1)*Nb-1),各輪密鑰均為Nb個雙字,即4*Nb個字節(jié)或32*Nb位,例如：設(shè)Nb=4、Nk=4，則r=10、擴(kuò)展密鑰雙字共4(10+1)=44個。故輪密鑰： K0=( w0,w1,w2,w3)、K1=( w4,w5,w6,w7)、K2=( w8,w9,w10,w11)、 、 K10=(w40,w41,w42,w43),又如：設(shè)Nb=8、Nk=6，則r=14 、擴(kuò)展密鑰雙字共8(14+1)=120個。故輪密鑰： K0=( w0,w1,w2,w3,w4,w5,w6,w7)、K1=( w8,w9,w10,w11,w12,w13,w14,w15)、 K2=( w16,w17,w18,w19,w20,w21,w22,w23)、 、 K14=(w112,w113,w114,w115,w116,w117,w118,w119),5.3.6 AES的解密 逆字節(jié)變換BS-1,用于逆字節(jié)運(yùn)算的逆S盒,例：對輸入“2aH”，在第2行第a列找到輸出為“95H”,逆行移位變換SR-1 將狀態(tài)的第i行循環(huán)右移Ci 個字節(jié)（Ci的意義同前） 例子：第1、2、3行循環(huán)右移1、2、3個字節(jié),逆列混淆變換MC-1,逆列混淆的實(shí)例：,驗證：0E 47+0B 37+0D 94+09 ED=87,0E 47=（00001110）（01000111）(00000010）+(00000100) +(00001000) （01000111） =(00000010) （01000111）+(00000100) （01000111）+(00001000) （01000111） =(10001110) （左移1位）+(00011100) +(00011011) （左移2位，因有溢出加1BH）+(00001000) （01000111) （左移3位，移2位后再移1位） =(10001110) +(00000111) +(00001110) =(10000111) 0B 37=(00001011) (00110111)=(00000001) +(00000010) +(00001000) (00110111) =(00110111)+(01101110) +(10111000) +(00011011) =(11111010),0D 94=(00001101) (10010100)=(0000001) +(00000100) +(00001000) (10010100) =(10010100) +(01100110) +(11001100) =(00111110) 09 ED=(00001001) (11101101)=(00000001) +(00001000) (11101101) =(11101101) +(00101001) =(11000100) 0E 47+0B 37+0D 94+09 ED=(10000111)+(11111010)+ (00111110)+ (11000100) =(10000111) =87 AES實(shí)例（P105）,AES的加密解密演示 AESRijndaelComeTrue.exe 文本加解密,作業(yè) P107頁：11、12、13、14,