密碼學(xué)5.3對(duì)稱密碼體制.ppt

1、第五章 對(duì)稱密碼體制之三,信息安全技術(shù),5.3 高級(jí)加密標(biāo)準(zhǔn)AES 5.3.0 AES概述 1997.4.15美國(guó)家標(biāo)準(zhǔn)和技術(shù)研究所NIST(National Institure of Standard Technology)發(fā)起AES征集 1997.9.12在美聯(lián)邦登記處公布征集公告 1998.8.20第一次AES候選會(huì)議公布15個(gè)算法 1999.3.22第二次AES候選會(huì)議公布分析測(cè)試結(jié)果 1999.8 NIST選出5個(gè)候選算法 2000.4.13第三次AES候選會(huì)議討論分析測(cè)試結(jié)果 2000.10.2 NIST正式宣布獲勝者為Rijndael算法（讀作“Rain Doll”） 2001

2、NIST正式發(fā)布基于Rijndael算法的AES,設(shè)計(jì)者比利時(shí)Katholieke大學(xué)電機(jī)系COSIC實(shí)驗(yàn)室博士后研究員Vincent Rijman、比利時(shí)Proton國(guó)際公司博士設(shè)計(jì)員Joan Daemen 設(shè)計(jì)準(zhǔn)則 能抵抗所有已知的攻擊 多平臺(tái)運(yùn)行時(shí)速度快、編碼簡(jiǎn)單 設(shè)計(jì)簡(jiǎn)單 安全性時(shí)限至少可維持20年,AES與Rijndael算法在概念上的區(qū)別 AES是NIST所制定的數(shù)據(jù)加密標(biāo)準(zhǔn)，采用128位分組，128、192或256位密鑰的Rijndael算法,Rijndael算法本身是一種可變分組長(zhǎng)度和可變密鑰長(zhǎng)度的分組密碼算法，分組長(zhǎng)度和密鑰長(zhǎng)度可獨(dú)立地設(shè)定為128256的32整數(shù)倍,密鑰安全

3、強(qiáng)度 128位密鑰空間3.41038，用攻擊DES的機(jī)器約需149 1012年才能窮舉攻陷（宇宙誕生至今約小于7 1010年） 192位密鑰空間 6.21057 256位密鑰空間 1.1 1077,5.3.1 算法描述 Rijndael屬于對(duì)稱密碼體制 Rijndael采用S-P網(wǎng)絡(luò)結(jié)構(gòu) NIST對(duì)Rijndael 的評(píng)估標(biāo)準(zhǔn)及結(jié)論 一般安全性沒(méi)有已知的能攻破Rijndael 的攻擊方法 軟件執(zhí)行 具有良好的軟件執(zhí)行性能 受限空間環(huán)境非常適合在受限空間環(huán)境中執(zhí)行操作 硬件執(zhí)行在反饋模式下速度最快 對(duì)執(zhí)行的攻擊有利于抵抗能量攻擊和計(jì)時(shí)攻擊 加密與解密加密與解密算法不同，但速度相當(dāng),密鑰靈活性支持

4、加密中的快速子密鑰計(jì)算 其他的多功能性和靈活性原則上分組與密鑰長(zhǎng)度為32的任意倍數(shù) 指令級(jí)并行執(zhí)行的潛力對(duì)于單個(gè)分組加密有很好的并行執(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 、

5、 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é)矩陣上，每列對(duì)應(yīng)一個(gè)雙字（4字節(jié)、32位） 狀態(tài)列數(shù)記作Nb， Nb=分組長(zhǎng)度/32 密鑰列數(shù)記作Nk， Nk =種子密鑰長(zhǎng)度/32 可能的列數(shù)Nb、 Nk有48（對(duì)應(yīng)的分組或密鑰長(zhǎng)度為128、160、192、224、256） 實(shí)際應(yīng)用時(shí)Nb、 Nk常取4、6、8之一

6、,輪數(shù)r取決于分組長(zhǎng)度和密鑰長(zhǎng)度：,迭代輪數(shù),GF(28)上的字節(jié)運(yùn)算 伽羅瓦(Galois)域GF(28)中的元素a是一個(gè)字節(jié)矢量 (a7,a1,a0) =xxH，可表作系數(shù)是0或1的次數(shù)小于8的多項(xiàng)式： 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為模的多項(xiàng)式乘法，即相乘后再用m約簡(jiǎn)，記作“ ” 例如：57H 83H = ( x6+ x4+ x2+ x + 1)

7、 ( 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（對(duì)應(yīng)02H）相當(dāng)于字節(jié)(a7,a1,a0)左移1位，但當(dāng)有溢出時(shí)必須用模m=11BH=(100011011)= x8+x4+x3+x+1來(lái)約簡(jiǎn)，這相當(dāng)于異

8、或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; 這就意味著對(duì)任意字節(jié)a的乘法均可分解為 若干x乘運(yùn)算，以便于算法的程序?qū)崿F(xiàn)。,在GF(28)中的乘法幺元是01H=(00000001)=1 對(duì)于GF(28)中的非零a，必存在

9、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個(gè)字節(jié)組成的列向量（a0j，a1j，a2j，a3j )被表示為伽羅瓦環(huán)GF(28)x/(x4+1)中的元素a 系數(shù)為兩位十六進(jìn)制數(shù)、次方不超過(guò)4的多項(xiàng)式a0j x3 + a1j x2 + a2j x +

10、a3j 環(huán)中兩個(gè)元素相加定義為相應(yīng)的字節(jié)在GF(28)中的相加（按位異或） 環(huán)中兩個(gè)元素相乘定義為對(duì)模m=x4+1=01H x4+01H 的普通多項(xiàng)式相乘，但系數(shù)運(yùn)算遵從GF(28)中的運(yùn)算,5.3.4 基本變換 字節(jié)代換BS S盒變換 分別對(duì)狀態(tài)的所有字節(jié)a進(jìn)行如下仿射變換：, a-1 +,b=BS(a)=,其中： a-1是a的乘法逆元,注：計(jì)算上定義了一個(gè)S盒由16*16個(gè)字節(jié)組成的矩陣（見(jiàn)下頁(yè)），包含了256種可能的變換。以輸入字節(jié)的高4位為行值、低4位作為列值，然后取出S盒中的對(duì)應(yīng)字節(jié)作為輸出。,用于字節(jié)運(yùn)算的S盒,例：對(duì)輸入“95H”，在第9行第5列找到輸出為“2aH”,行移變換SR

11、 將狀態(tài)的第i行循環(huán)左移Ci 個(gè)字節(jié) （i=1,2,3;第0行不動(dòng)） Ci=1,2,3或4,Ci取決于明文長(zhǎng)度 (i=1,2,3)：,列混合變換MC 對(duì)狀態(tài)的各個(gè)字節(jié)列Aj進(jìn)行變換(j=0,1,Nb-1) ：,把狀態(tài)列當(dāng)作伽羅瓦環(huán)GF(28)x/(x4+1)中的多項(xiàng)式a= a0j x3 + a1j x2 + a2j x + a3j ，對(duì)一個(gè)固定的多項(xiàng)式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)

12、* 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 對(duì)狀態(tài)的各個(gè)字節(jié)列與密鑰字wj進(jìn)行按位異或,密鑰擴(kuò)展,種子密鑰K=(k0,k1, ,kNk-1),擴(kuò)展密鑰W=(w0,w1, ,wN

13、b*(r+1)-1),共Nk個(gè)雙字，32* Nk位,因需(r+1)個(gè)含Nb個(gè)雙字的輪密鑰，故共需Nb*(r+1) 個(gè)雙字的擴(kuò)展密鑰,每個(gè)雙字4字節(jié)32位,5.3.5 密鑰擴(kuò)展與調(diào)度,對(duì)于Nk6,wi=,ki ;當(dāng)iNk,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表示對(duì)雙字的每個(gè)字節(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=

14、04H， c0,4=08H， c0,5=10H， c0,6=20H， c0,7=40H， c0,8=80H， c0,9=1BH， c0,10=36H（后兩個(gè)均左移后異或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】,對(duì)于Nk6,wi=,ki ;當(dāng)

15、iNk,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

16、= 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) 個(gè)雙字,初始輪密鑰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個(gè)雙字,即4*Nb個(gè)字節(jié)或32*Nb位,例如：設(shè)Nb=4、Nk=4，則r=10

17、、擴(kuò)展密鑰雙字共4(10+1)=44個(gè)。故輪密鑰： 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個(gè)。故輪密鑰： 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,w11

18、8,w119),5.3.6 AES的解密 逆字節(jié)變換BS-1,用于逆字節(jié)運(yùn)算的逆S盒,例：對(duì)輸入“2aH”，在第2行第a列找到輸出為“95H”,逆行移位變換SR-1 將狀態(tài)的第i行循環(huán)右移Ci 個(gè)字節(jié)（Ci的意義同前） 例子：第1、2、3行循環(huán)右移1、2、3個(gè)字節(jié),逆列混淆變換MC-1,逆列混淆的實(shí)例：,驗(yàn)證：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位，因