密碼學(xué)0－分組密碼體制

1、本科生學(xué)位課：現(xiàn)代密碼學(xué)本科生學(xué)位課：現(xiàn)代密碼學(xué)第三章第三章 分組密碼體制分組密碼體制主講教師主講教師：董慶寬：董慶寬研究方向研究方向：密碼學(xué)與信息安全：密碼學(xué)與信息安全email email ：個人主頁：個人主頁：http:/ 分組密碼概述分組密碼概述3.2 數(shù)據(jù)加密標(biāo)準(zhǔn)數(shù)據(jù)加密標(biāo)準(zhǔn)des3.3 差分密碼分析和線性密碼分析差分密碼分析和線性密碼分析3.4 分組密碼的運(yùn)行模式分組密碼的運(yùn)行模式3.5 idea 3.6 aesrijndael本章提要本章提要3/1553.1 分組密碼概述分組密碼概述分組密碼分組密碼(block cipher) ：l將明文消息分組，逐組加密；對稱密碼算法，屬于代換

2、密碼將明文消息分組，逐組加密；對稱密碼算法，屬于代換密碼l將明文消息編碼表示后的數(shù)字序列將明文消息編碼表示后的數(shù)字序列x0,x1,xi,劃分成長為劃分成長為n的組的組x=(x0,x1,xn-1)l各組（長為各組（長為n的矢量）分別在密鑰的矢量）分別在密鑰k=(k0,k1,kt-1)控制下變換成輸出控制下變換成輸出序列序列y=(y0,y1,ym-1)（長為（長為m的矢量）的矢量）l其加密函數(shù)其加密函數(shù)e：vnkvm，vn和和vm分別是分別是n維和維和m維矢量空間，維矢量空間，k為密鑰空間，如圖所示。為密鑰空間，如圖所示。4/155與流密碼不同之處：與流密碼不同之處：l(1)分組加密。在于輸出的每

3、一位數(shù)字不是只與相應(yīng)時刻輸入的明分組加密。在于輸出的每一位數(shù)字不是只與相應(yīng)時刻輸入的明文數(shù)字有關(guān)，而是與一組長為文數(shù)字有關(guān)，而是與一組長為n的明文數(shù)字有關(guān)。的明文數(shù)字有關(guān)。l(2)無記憶性。在相同密鑰下，分組密碼對長為無記憶性。在相同密鑰下，分組密碼對長為n的輸入明文組所實(shí)的輸入明文組所實(shí)施的變換是等同的，所以施的變換是等同的，所以只需研究對任一組明文數(shù)字的變換規(guī)則只需研究對任一組明文數(shù)字的變換規(guī)則。這種密碼實(shí)質(zhì)上是字長為這種密碼實(shí)質(zhì)上是字長為m的數(shù)字序列的代換密碼的數(shù)字序列的代換密碼。算法的輸入長度和輸出長度算法的輸入長度和輸出長度l通常取通常取m=n (用于加密用于加密)l若若mn，則為有

4、數(shù)據(jù)擴(kuò)展的分組密碼，則為有數(shù)據(jù)擴(kuò)展的分組密碼(用于認(rèn)證用于認(rèn)證)l若若m 。l另一方面，對每個不同的密鑰，另一方面，對每個不同的密鑰，des都定義了一個映射，總映射數(shù)為都定義了一個映射，總映射數(shù)為2561017n/2，則令，則令lkk1,k2,kc如果如果t|tminn/2 |,將將tmax對應(yīng)的候選者對應(yīng)的候選者kn(i)作為作為kn，并猜，并猜定定kk1,k2,kc0(p1/2)或或1 (p6有所不同。有所不同。當(dāng)當(dāng)nk 6時，擴(kuò)展算法如下時，擴(kuò)展算法如下lkeyexpansion (byte key4*nk , word wnb*(nr+1)ll for (i =0; i nk; i +

5、)lwi=(key4* i,key4* i +1,key4* i +2,key4* i +3 );l for (i =nk; i 6時，擴(kuò)展算法如下時，擴(kuò)展算法如下lkeyexpansion (byte key4*nk , word wnb*(nr+1)ll for (i=0; i nk; i +)lwi=(key4* i, key4* i +1, key4* i +2, key4* i +3 );lfor (i =nk; i 6與與nk6的密鑰擴(kuò)展算法的區(qū)別在于：當(dāng)?shù)拿荑€擴(kuò)展算法的區(qū)別在于：當(dāng)i為為nk的的4的的倍數(shù)時，須先將前一個字倍數(shù)時，須先將前一個字wi-1經(jīng)過經(jīng)過subbyte變換。

6、變換。以上兩個算法中，以上兩個算法中，rconi/nk 為輪常數(shù)，其值與為輪常數(shù)，其值與nk無關(guān)，定義為（字節(jié)用十六進(jìn)制表示，同時理無關(guān)，定義為（字節(jié)用十六進(jìn)制表示，同時理解為解為gf(28)上的元素）：上的元素）：l rcon i=(rci, 00, 00, 00)l 其中其中rci 是是gf(28) 中值為中值為xi-1的元素，因此的元素，因此lrc1 =1(即即01)lrci = x(即即02)rci-1= xi-1147/155(2) 輪密鑰選取輪密鑰選取l輪密鑰輪密鑰i（即第（即第i 個輪密鑰）由輪密鑰緩沖字個輪密鑰）由輪密鑰緩沖字wnb* i到到wnb*(i+1)給出，如圖給出，如

7、圖3.23所示。所示。lnb=6且且nk=4時的密鑰擴(kuò)展與輪密鑰選取時的密鑰擴(kuò)展與輪密鑰選取w0w1w2w3w4w5w6w7w8w9w10w11w12w13w14輪密鑰輪密鑰0輪密鑰輪密鑰1148/1554加密算法加密算法加密算法為順序完成以下操作：初始的密鑰加；加密算法為順序完成以下操作：初始的密鑰加；(nr-1)輪迭代；一個結(jié)尾輪。即輪迭代；一個結(jié)尾輪。即lrijndael (state, cipherkey)llkeyexpansion (cipherkey, expandedkey);laddroundkey (state, expandedkey);lfor (i=1; i nr;

8、i +) lround (state, expandedkey+nb* i);lfinalround (state, expandedkey+nb*nr)l149/155其中其中cipherkey是種子密鑰，是種子密鑰，expandedkey是擴(kuò)展是擴(kuò)展密鑰。密鑰。密鑰擴(kuò)展可以事先進(jìn)行（預(yù)計(jì)算），且密鑰擴(kuò)展可以事先進(jìn)行（預(yù)計(jì)算），且rijndael密密碼的加密算法可以用這一擴(kuò)展密鑰來描述，即碼的加密算法可以用這一擴(kuò)展密鑰來描述，即lrijndael (state, expandedkey)lladdroundkey (state, expandedkey);lfor (i=1; i nr; i

9、 +)lround (state, expandedkey+nb* i);lfinalround (state, expandedkey+nb*nr)l150/1555.加解密的相近程度及解密算法加解密的相近程度及解密算法首先給出幾個引理。首先給出幾個引理。引理引理3.1 設(shè)字節(jié)代換（設(shè)字節(jié)代換（bytesub）、行移位）、行移位（shiftrow）的逆變換分別為）的逆變換分別為invbytesub、invshiftrow。l則組合部件則組合部件“bytesubshiftrow”的逆變換為的逆變換為“invbytesubinvshiftrow”l證明：組合部件證明：組合部件“bytesubsh

10、iftrow”的逆變換原本的逆變換原本為為“invshiftrowinvbytesub”。由于字節(jié)代換。由于字節(jié)代換（bytesub）是對每個字節(jié)進(jìn)行相同的變換，故）是對每個字節(jié)進(jìn)行相同的變換，故“invshiftrow”與與“invbytesub”兩個計(jì)算部件可以兩個計(jì)算部件可以交換順序。（證畢）交換順序。（證畢）151/155引理引理3.2 設(shè)列混合（設(shè)列混合（mixcolumn）的逆變換為）的逆變換為invmixcolumn 則列混合部件與密鑰加部件則列混合部件與密鑰加部件（addroundkey）的組合部件）的組合部件“mixcolumnaddroundkey (, key)”的逆的逆

11、變換為變換為“invmixcolumnaddroundkey (, invkey)”l其中密鑰其中密鑰invkey與與key的關(guān)系為：的關(guān)系為：invkey=invmixcolumn (key)152/155證明：證明：l組合部件組合部件“mixcolumnaddroundkey (, key)” 的逆的逆變換原本為變換原本為“addroundkey (, key)invmixcolumn”，l由于列混合（由于列混合（mixcolumn）實(shí)際上是線性空間）實(shí)際上是線性空間gf(28)4上上的可逆線性變換，因此的可逆線性變換，因此“addroundkey (,key)invmixcolumn”l

12、=“invmixcolumnaddroundkey (, invmixcolumn (key)”（證畢）（證畢）l由由t(x)=a(x)*c(x)+key(x),知逆向列混淆后知逆向列混淆后 t(x)*c-1(x)= a(x)+key(x)*c-1(x),從而從而a(x) = t(x)*c-1(x) + key(x)*c-1(x),所所以逆的列混淆后應(yīng)該加上輪密鑰列混淆后的結(jié)果以逆的列混淆后應(yīng)該加上輪密鑰列混淆后的結(jié)果153/155引理3.3 將某一輪的后兩個計(jì)算部件和下一輪的前兩個計(jì)算部件組成將某一輪的后兩個計(jì)算部件和下一輪的前兩個計(jì)算部件組成組合部件，該組合部件的程序?yàn)榻M合部件，該組合部件

13、的程序?yàn)閘mixcolumn (state)；l addroundkey (state, key(i);l bytesub (state);l shiftrow (state)則該組合部件的逆變換程序?yàn)閯t該組合部件的逆變換程序?yàn)閘invbytesub (state);l invshiftrow (state);l invmixcolumn (state);l addroundkey (state, invmixcolumn (key(i)證明：這是引理證明：這是引理3.1和引理和引理3.2的直接推論。的直接推論。l注意到在引理注意到在引理3.3所描述的逆變換中，第所描述的逆變換中，第2步到第步

14、到第4步在形狀上很像加密算步在形狀上很像加密算法的輪函數(shù)，這將是解密算法的輪函數(shù)。注意到結(jié)尾輪只有法的輪函數(shù)，這將是解密算法的輪函數(shù)。注意到結(jié)尾輪只有3個計(jì)算部件，個計(jì)算部件，因此可以得到如下定理。因此可以得到如下定理。154/155定理定理3-2 rijndael密碼的解密算法為順序完成以下操作：初始的密鑰加；密碼的解密算法為順序完成以下操作：初始的密鑰加；(nr-1)輪迭代；一個結(jié)尾輪。其中解密算法的輪函數(shù)為輪迭代；一個結(jié)尾輪。其中解密算法的輪函數(shù)為linvround (state, roundkey)ll invbytesub (state);l invshiftrow (state);

15、l invmixcolumn (state);l addroundkey (state, roundkey)l解密算法的結(jié)尾輪為解密算法的結(jié)尾輪為linvfinalround (state, roundkey)ll invbytesub (state);l invshiftrow (state);l addroundkey (state, roundkey)l155/155設(shè)加密算法的初始密鑰加、第設(shè)加密算法的初始密鑰加、第1輪、第輪、第2輪、輪、第、第nr輪的子密鑰依次為輪的子密鑰依次為lk(0), k(1), k(2), , k(nr-1), k(nr)則解密算法的初始密鑰加、第則解密算法的初始密鑰加、第1輪、第輪、第2輪、輪、第、第nr輪的子密鑰依次為輪的子密鑰依次為lk(nr), invmixcolumn (k(nr-1), invmixcolumn (k(nr-2), ,invmixcolumn (k(1), k(0)。證明：這是上述證明：這是上述3個引理的直接推論。個引理的直接推論。l綜上所述，綜上所述，rijndael密碼的解密算法與加密算法的計(jì)算網(wǎng)密碼的解密算法與加密算法的計(jì)算網(wǎng)絡(luò)相同絡(luò)相同，只是將各計(jì)算部件換為對應(yīng)的逆部件。，只是將各計(jì)算部件換為對應(yīng)的逆部件。156/15