第3章 密碼學(xué)基礎(chǔ) 分組密碼體制

第3章分組密碼體制3.1分組密碼概述（▲Feistel密碼結(jié)構(gòu)，擴散和混淆）3.2數(shù)據(jù)加密標(biāo)準(zhǔn)▲3.3差分密碼分析與線性密碼分析* （中途相遇攻擊原理）3.4分組密碼的運行模式▲3.5IDEA3.6AES算法——Rijndael▲習(xí)題在許多密碼系統(tǒng)中，單鑰分組密碼是系統(tǒng)安全的一個重要組成部分，用分組密碼易于構(gòu)造偽隨機數(shù)生成器、流密碼、消息認證碼（MAC）和雜湊函數(shù)等，還可進而成為消息認證技術(shù)、數(shù)據(jù)完整性機制、實體認證協(xié)議以及單鑰數(shù)字簽字體制的核心組成部分。實際應(yīng)用中對于分組密碼可能提出多方面的要求，除了安全性外，還有運行速度、存儲量（程序的長度、數(shù)據(jù)分組長度、高速緩存大小）、實現(xiàn)平臺（硬件、軟件、芯片）、運行模式等限制條件。這些都需要與安全性要求之間進行適當(dāng)?shù)恼壑羞x擇。3.1分組密碼概述明文x0,x1,…,xi,…明文分組x=(x0,x1,…,xn-1)，密鑰k=(k0,k1,…,kt-1)密文分組

y=(y0,y1,…,ym-1加密函數(shù)E：Vn×K→Vm圖3.1分組密碼框圖通常取m=n。若m>n，則為有數(shù)據(jù)擴展的分組密碼；若m<n，則為有數(shù)據(jù)壓縮的分組密碼。設(shè)計的算法應(yīng)滿足下述要求：①分組長度n要足夠大，使分組代換字母表中的元素個數(shù)2n足夠大，防止明文窮舉攻擊法奏效。DES、IDEA、FEAL和LOKI等分組密碼都采用n=64，在生日攻擊下用232組密文成功概率為1/2，同時要求232×64b=215MB存貯，故采用窮舉攻擊是不現(xiàn)實的。②密鑰量要足夠大（即置換子集中的元素足夠多），盡可能消除弱密鑰并使所有密鑰同等地好，以防止密鑰窮舉攻擊奏效。但密鑰又不能過長，以便于密鑰的管理。 DES采用56比特密鑰，太短了，IDEA采用128比特密鑰，據(jù)估計，在今后30～40年內(nèi)采用80比特密鑰是足夠安全的。③由密鑰確定置換的算法要足夠復(fù)雜，充分實現(xiàn)明文與密鑰的擴散和混淆，沒有簡單的關(guān)系可循，能抗擊各種已知的攻擊，如差分攻擊和線性攻擊；有高的非線性階數(shù)，實現(xiàn)復(fù)雜的密碼變換；使對手破譯時除了用窮舉法外，無其它捷徑可循。④加密和解密運算簡單，易于軟件和硬件高速實現(xiàn)。如將分組n化分為子段，每段長為8、16或者32。在以軟件實現(xiàn)時，應(yīng)選用簡單的運算，使作用于子段上的密碼運算易于以標(biāo)準(zhǔn)處理器的基本運算，如加、乘、移位等實現(xiàn)，避免用以軟件難于實現(xiàn)的逐比特置換。為了便于硬件實現(xiàn)，加密和解密過程之間的差別應(yīng)僅在于由秘密密鑰所生成的密鑰表不同而已。這樣，加密和解密就可用同一器件實現(xiàn)。設(shè)計的算法采用規(guī)則的模塊結(jié)構(gòu)，如多輪迭代等，以便于軟件和VLSI快速實現(xiàn)。此外，差錯傳播和數(shù)據(jù)擴展要盡可能地小。⑤數(shù)據(jù)擴展盡可能地小。一般無數(shù)據(jù)擴展，在采用同態(tài)置換和隨機化加密技術(shù)時可引入數(shù)據(jù)擴展。⑥差錯傳播盡可能地小。 如果明文和密文的分組長都為n比特，則明文的每一個分組都有2n個可能的取值。為使加密運算可逆（使解密運算可行），明文的每一個分組都應(yīng)產(chǎn)生惟一的一個密文分組，這樣的變換是可逆的，稱明文分組到密文分組的可逆變換為代換。明文到密文，或密文到明文，可由代換表完成表示，代換表是可逆的、一對一的映射表。見教材P36，表3-1。不同可逆變換的個數(shù)有2n!個。3.1.1代換圖3.2表示n=4的代換密碼的一般結(jié)構(gòu)，4比特輸入產(chǎn)生16個可能輸入狀態(tài)中的一個，由代換結(jié)構(gòu)將這一狀態(tài)映射為16個可能輸出狀態(tài)中的一個，每一輸出狀態(tài)由4個密文比特表示。加密映射和解密映射可由代換表來定義，如表3.1所示。這種定義法是分組密碼最常用的形式，能用于定義明文和密文之間的任何可逆映射。（見33頁表3.1）圖3.2代換結(jié)構(gòu)如果分組長度太小，系統(tǒng)則等價于古典的代換密碼，容易通過對明文的統(tǒng)計分析而被攻破。從實現(xiàn)的角度來看，分組長度很大的可逆代換結(jié)構(gòu)是不實際的。仍以表3.1為例，該表定義了n=4時從明文到密文的一個可逆映射，其中第2列是每個明文分組對應(yīng)的密文分組的值，可用來定義這個可逆映射。因此從本質(zhì)上來說，第2列是從所有可能映射中決定某一特定映射的密鑰。這個例子中，密鑰需要64比特。一般地，對n比特的代換結(jié)構(gòu)，密鑰的大小是n×2n比特。如對64比特的分組，密鑰大小應(yīng)是64×264=270≈1021比特，因此難以處理。 實際中常將n分成較小的段，例如可選n=r·n0，其中r和n0都是正整數(shù)，將設(shè)計n個變量的代換變?yōu)樵O(shè)計r個較小的子代換，而每個子代換只有n0個輸入變量。一般n0都不太大，

稱每個子代換為代換盒，簡稱為S盒。

例如DES中將輸入為48比特、輸出為32比特的代換用8個S盒來實現(xiàn)，每個S盒的輸入端數(shù)僅為6比特，輸出端數(shù)僅為4比特。

擴散和混淆是由Shannon提出的設(shè)計密碼系統(tǒng)的兩個基本方法，目的是抗擊敵手對密碼系統(tǒng)的統(tǒng)計分析。 如果敵手知道明文的某些統(tǒng)計特性，如消息中不同字母出現(xiàn)的頻率、可能出現(xiàn)的特定單詞或短語，而且這些統(tǒng)計特性以某種方式在密文中反映出來，那么敵手就有可能得出加密密鑰或其一部分，或者得出包含加密密鑰的一個可能的密鑰集合。3.1.2擴散和混淆

所謂擴散，就是將明文的統(tǒng)計特性散布到密文中去，實現(xiàn)方式是使得密文中每一位由明文中多位產(chǎn)生。 例如對英文消息M=m1m2m3…的加密操作其中ord(mi)是求字母mi對應(yīng)的序號，chr(i)是求序號i對應(yīng)的字母。這時明文的統(tǒng)計特性將被散布到密文中，因而每一字母在密文中出現(xiàn)的頻率比在明文中出現(xiàn)的頻率更接近于相等，雙字母及多字母出現(xiàn)的頻率也更接近于相等。在二元分組密碼中，可對數(shù)據(jù)重復(fù)執(zhí)行某個置換，再對這一置換作用于一函數(shù)，可獲得擴散。 混淆是使密文和密鑰之間的統(tǒng)計關(guān)系變得盡可能復(fù)雜，以使敵手無法得到密鑰。 因此即使敵手能得到密文的一些統(tǒng)計關(guān)系，由于密鑰和密文之間的統(tǒng)計關(guān)系復(fù)雜化，敵手也無法得到密鑰。使用復(fù)雜的代換算法可以得到預(yù)期的混淆效果，而簡單的線性代換函數(shù)得到的混淆效果則不夠理想。 擴散和混淆成功地實現(xiàn)了分組密碼的本質(zhì)屬性，因而成為設(shè)計現(xiàn)代分組密碼的基礎(chǔ)。 乘積密碼指順序地執(zhí)行兩個或多個基本密碼系統(tǒng)，使得最后結(jié)果的密碼強度高于每個基本密碼系統(tǒng)產(chǎn)生的結(jié)果. Feistel還提出了實現(xiàn)代換和置換的方法。其思想實際上是Shannon提出的利用乘積密碼實現(xiàn)混淆和擴散思想的具體應(yīng)用。3.1.3Feistel密碼結(jié)構(gòu)圖3.3Feistel網(wǎng)絡(luò)示意圖1.Feistel加密結(jié)構(gòu) 輸入是分組長為2w的明文和一個密鑰K。將每組明文分成左右兩半L0和R0，在進行完n輪迭代后，左右兩半再合并到一起以產(chǎn)生密文分組。其第i輪迭代的輸入為前一輪輸出的函數(shù)：其中Ki是第i輪用的子密鑰，由加密密鑰K得到。一般地，各輪子密鑰彼此不同而且與K也不同。Feistel網(wǎng)絡(luò)的實現(xiàn)與以下參數(shù)和特性有關(guān)：①分組大小:分組越大則安全性越高，但加密速度就越慢。分組密碼設(shè)計中最為普遍使用的分組大小是64比特。②密鑰大?。好荑€越長則安全性越高，但加密速度就越慢?，F(xiàn)在普遍認為64比特或更短的密鑰長度是不安全的，通常使用128比特的密鑰長度。③輪數(shù)：單輪結(jié)構(gòu)遠不足以保證安全性，但多輪結(jié)構(gòu)可提供足夠的安全性。典型地，輪數(shù)取為16。④子密鑰產(chǎn)生算法：該算法的復(fù)雜性越大，則密碼分析的困難性就越大。⑤輪函數(shù)：輪函數(shù)的復(fù)雜性越大，密碼分析的困難性也越大。在設(shè)計Feistel網(wǎng)絡(luò)時，還有以下兩個方面需要考慮：①快速的軟件實現(xiàn)：在很多情況中，算法是被鑲嵌在應(yīng)用程序中，因而無法用硬件實現(xiàn)。此時算法的執(zhí)行速度是考慮的關(guān)鍵。②算法容易分析：如果算法能被無疑義地解釋清楚，就可容易地分析算法抵抗攻擊的能力，有助于設(shè)計高強度的算法。2.Feistel解密結(jié)構(gòu)

Feistel解密過程本質(zhì)上和加密過程是一樣的，算法使用密文作為輸入，但使用子密鑰Ki的次序與加密過程相反，即第1輪使用Kn，第2輪使用Kn-1，……，最后一輪使用K1。這一特性保證了解密和加密可采用同一算法。圖3.4Feistel加解密過程在加密過程中：在解密過程中所以解密過程第1輪的輸出為LE15‖RE15，等于加密過程第16輪輸入左右兩半交換后的結(jié)果。容易證明這種對應(yīng)關(guān)系在16輪中每輪都成立。一般地，加密過程的第i輪有因此數(shù)據(jù)加密標(biāo)準(zhǔn)（dataencryptionstandard,DES）是迄今為止世界上最為廣泛使用和流行的一種分組密碼算法，它的分組長度為64比特，密鑰長度為56比特，它是由美國IBM公司研制的，是早期的稱作Lucifer密碼的一種發(fā)展和修改。DES在1975年3月17日首次被公布在聯(lián)邦記錄中，經(jīng)過大量的公開討論后，DES于1977年1月15日被正式批準(zhǔn)并作為美國聯(lián)邦信息處理標(biāo)準(zhǔn)，即FIPS-46，同年7月15日開始生效。規(guī)定每隔5年由美國國家保密局（nationalsecurityagency,NSA）作出評估，并重新批準(zhǔn)它是否繼續(xù)作為聯(lián)邦加密標(biāo)準(zhǔn)。3.2數(shù)據(jù)加密標(biāo)準(zhǔn)最近的一次評估是在1994年1月，美國已決定1998年12月以后將不再使用DES。1997年DESCHALL小組經(jīng)過近4個月的努力，通過Internet搜索了3×1016個密鑰，找出了DES的密鑰，恢復(fù)出了明文。1998年5月美國EFF(electronicsfrontierfoundation)宣布，他們以一臺價值20萬美元的計算機改裝成的專用解密機，用56小時破譯了56比特密鑰的DES。美國國家標(biāo)準(zhǔn)和技術(shù)協(xié)會已征集并進行了幾輪評估、篩選，產(chǎn)生了稱之為AES(advancedencryptionstandard)的新加密標(biāo)準(zhǔn)。盡管如此，DES對于推動密碼理論的發(fā)展和應(yīng)用畢竟起了重大作用，對于掌握分組密碼的基本理論、設(shè)計思想和實際應(yīng)用仍然有著重要的參考價值，下面首先來描述這一算法。圖3.5DES加密算法框圖

1.初始置換

1.初始置換 M1M2M3M4M5M6M7M8

M9M10M11M12M13M14M15M16 M17M18M19M20M21M22M23M24

M25M26M27M28M29M30M31M32

M33M34M35M36M37M38M39M40

M41M42M43M44M45M46M47M48

M49M50M51M52M53M54M55M56

M57M58M59M60M61M62M63M64其中Mi是二元數(shù)字。由表3.2(a)得X=IP(M)為：

M58M50M42M34M26M18M10M2 M60M52M44M36M28M20M12M4 M62M54M46M38M30M22M14M6 M64M56M48M40M32M24M16M8 M57M49M41M33M25M17M9M1 M59M51M43M35M27M19M11M3 M61M53M45M37M29M21M13M5 M63M55M47M39M31M23M15M7如果再取逆初始置換Y=IP-1(X)=IP-1(IP(M))，可以看出，M各位的初始順序?qū)⒈换謴?fù)。圖3.6DES加密算法的輪結(jié)構(gòu) 每輪變換可由以下公式表示：圖3.7函數(shù)F(R,K)的計算過程 對每個盒Si，其6比特輸入中，第1個和第6個比特形成一個2位二進制數(shù)，用來選擇Si的4個代換中的一個。6比特輸入中，中間4位用來選擇列。行和列選定后，得到其交叉位置的十進制數(shù)，將這個數(shù)表示為4位二進制數(shù)即得這一S盒的輸出。 例如，S1

的輸入為011001，行選為01（即第1行），列選為1100（即第12列），行列交叉位置的數(shù)為9，其4位二進制表示為1001，所以S1的輸出為1001。 S盒的每一行定義了一個可逆代換。P-盒置換P-盒置換為： 16720212912281711523265183110 282414322739191330622114253.密鑰的產(chǎn)生子密鑰產(chǎn)生PC-1(置換選擇1)：（1）舍掉種子密鑰K中的8個校驗位；（2）按照PC-1表作置換，即：C0=k57k49k41…k44k36

前28位D0=k63k55k47…k12k4

后28位循環(huán)移位LS：C0C1，D0D1PC-2(置換選擇2)（1）刪除移位后C1中的第9，18，22，25位和D1中的第7，10，15，26位（即刪除移位后C1||D1重新編號后的第9，18，22，25，35，38，43，54位）（2）按照PC-2表作置換，即得子密鑰k1置換運算說明 置換結(jié)果：始終以輸入位串的重新編號作為置換表的輸出而得到的結(jié)果。4.解密 和Feistel密碼一樣，DES的解密和加密使用同一算法，但子密鑰使用的順序相反。DES加密計算舉例DES舉例DES舉例（續(xù)）為了提高DES的安全性，并利用實現(xiàn)DES的現(xiàn)有軟硬件，可將DES算法在多密鑰下多重使用。二重DES是多重使用DES時最簡單的形式，如圖3.8所示。其中明文為P，兩個加密密鑰為K1和K2，密文為：解密時，以相反順序使用兩個密鑰：3.2.2二重DES圖3.8二重DES 因此，二重DES所用密鑰長度為112比特，強度極大地增加。 然而，假設(shè)對任意兩個密鑰K1和K2，能夠找出另一密鑰K3，使得 那么，二重DES以及多重DES都沒有意義，因為它們與56比特密鑰的單重DES等價，好在這種假設(shè)對DES并不成立。 將DES加密過程64比特分組到64比特分組的映射看作一個置換，如果考慮264個所有可能的輸入分組，則密鑰給定后，DES的加密將把每個輸入分組映射到一個惟一的輸出分組。否則，如果有兩個輸入分組被映射到同一分組，則解密過程就無法實施。對264個輸入分組，總映射個數(shù)為另一方面，對每個不同的密鑰，DES都定義了一個映射，總映射數(shù)為256<1017。因此，可假定用兩個不同的密鑰兩次使用DES，可得一個新映射，而且這一新映射不出現(xiàn)在單重DES定義的映射中。這一假定已于1992年被證明。所以使用二重DES產(chǎn)生的映射不會等價于單重DES加密。但對二重DES有以下一種稱為中途相遇攻擊的攻擊方案，這種攻擊不依賴于DES的任何特性，因而可用于攻擊任何分組密碼。其基本思想如下：如果有那么（見圖3.8）如果已知一個明文密文對(P,C)，攻擊的實施可如下進行：首先，用256個所有可能的K1對P加密，將加密結(jié)果存入一表并對表按X排序，然后用256個所有可能的K2對C解密，在上述表中查找與C解密結(jié)果相匹配的項，如果找到，則記下相應(yīng)的K1和K2。最后再用一新的明文密文對(P′,C′)檢驗上面找到的K1和K2，用K1和K2對P′兩次加密，若結(jié)果等于C′，就可確定K1和K2是所要找的密鑰。對已知的明文P，二重DES能產(chǎn)生264個可能的密文,而可能的密鑰個數(shù)為2112，所以平均來說，對一個已知的明文，有2112/264=248個密鑰可產(chǎn)生已知的密文。而再經(jīng)過另外一對明文密文的檢驗，誤報率將下降到248-64=2-16。所以在實施中途相遇攻擊時，如果已知兩個明文密文對，則找到正確密鑰的概率為1-2-16。抵抗中途相遇攻擊的一種方法是使用3個不同的密鑰做3次加密，從而可使已知明文攻擊的代價增加到2112。然而，這樣又會使密鑰長度增加到56×3=168比特，因而過于笨重。 一種實用的方法是僅使用兩個密鑰做3次加密，實現(xiàn)方式為加密\解密\加密，簡記為EDE(encryptdecryptencrypt)，即：3.2.3兩個密鑰的三重DES圖3.9兩個密鑰的三重DES三個密鑰的三重DES密鑰長度為168比特，加密方式為令K3=K2或K1=K2，則變?yōu)橐恢谼ES。三個密鑰的三重DES已在因特網(wǎng)的許多應(yīng)用（如PGP和S/MIME）中被采用。3.2.4三個密鑰的三重DES差分密碼分析是迄今已知的攻擊迭代密碼最有效的方法之一，其基本思想是：通過分析明文對的差值對密文對的差值的影響來恢復(fù)某些密鑰比特。*3.3差分密碼分析與線性密碼分析

3.3.1差分密碼分析對分組長度為n的r輪迭代密碼，兩個n比特串Yi和Y*i的差分定義為其中表示n比特串集上的一個特定群運算，表示在此群中的逆元。由加密對可得差分序列ΔY0,ΔY1,…,ΔYr其中Y0和Y*0是明文對，Yi和Y*i(1≤i≤r)是第i輪的輸出，它們同時也是第i+1輪的輸入。第i輪的子密鑰記為Ki，F(xiàn)是輪函數(shù)，且Yi=F(Yi-1,Ki)。對r-輪迭代密碼的差分密碼分析過程可綜述為如下的步驟：①找出一個(r-1)-輪特征Ω(r-1)=α0,α1,…,αr-1，使得它的概率達到最大或幾乎最大。②均勻隨機地選擇明文Y0并計算Y*0，使得Y0和Y*0的差分為α0，找出Y0和Y*0在實際密鑰加密下所得的密文Yr和Y*r。若最后一輪的子密鑰Kr（或Kr的部分比特）有2m個可能值Kjr(1≤j≤2m)，設(shè)置相應(yīng)的2m個計數(shù)器Λj(1≤j≤2m)；用每個Kjr解密密文Yr和Y*r，得到Y(jié)r-1和Y*r-1，如果Yr-1和Y*r-1的差分是αr-1，則給相應(yīng)的計數(shù)器Λj加1。③重復(fù)步驟②，直到一個或幾個計數(shù)器的值明顯高于其他計數(shù)器的值，輸出它們所對應(yīng)的子密鑰（或部分比特）。一種攻擊的復(fù)雜度可以分為兩部分：數(shù)據(jù)復(fù)雜度和處理復(fù)雜度。數(shù)據(jù)復(fù)雜度是實施該攻擊所需輸入的數(shù)據(jù)量；而處理復(fù)雜度是處理這些數(shù)據(jù)所需的計算量。這兩部分的主要部分通常被用來刻畫該攻擊的復(fù)雜度。 一種攻擊的復(fù)雜度可以分為兩部分：數(shù)據(jù)復(fù)雜度和處理復(fù)雜度。數(shù)據(jù)復(fù)雜度是實施該攻擊所需輸入的數(shù)據(jù)量；而處理復(fù)雜度是處理這些數(shù)據(jù)所需的計算量。這兩部分的主要部分通常被用來刻畫該攻擊的復(fù)雜度。 差分密碼分析的數(shù)據(jù)復(fù)雜度是成對加密所需的選擇明文對(Y0,Y*0)個數(shù)的兩倍。處理復(fù)雜度是從(ΔYr-1,Yr,Y*r)找出子密鑰Kr（或Kr的部分比特）的計算量，它實際上與r無關(guān)，而且由于輪函數(shù)是弱的，所以此計算量在大多數(shù)情況下相對較小。因此，差分密碼分析的復(fù)雜度取決于它的數(shù)據(jù)復(fù)雜度。 線性密碼分析是對迭代密碼的一種已知明文攻擊，它利用的是密碼算法中的“不平衡（有效）的線性逼近”。 設(shè)明文分組長度和密文分組長度都為n比特，密鑰分組長度為m比特。記明文分組：P[1]，P[2]，…,P[n]，密文分組：C[1]，C[2]，…，C[n]，密鑰分組：K[1]，K[2]，…，K[m]。定義：3.3.2線性密碼分析 線性密碼分析的目標(biāo)就是找出以下形式的有效線性方程：其中1≤a≤n,1≤b≤n,1≤c≤m。 如果方程成立的概率p≠1/2，則稱該方程是有效的線性逼近。如果是最大的，則稱該方程是最有效的線性逼近。 設(shè)N表示明文數(shù)，T是使方程左邊為0的明文數(shù)。如果T>N/2，則令如果T<N/2，則令從而可得關(guān)于密鑰比特的一個線性方程。對不同的明文密文對重復(fù)以上過程，可得關(guān)于密鑰的一組線性方程，從而確定出密鑰比特。研究表明，當(dāng)充分小時，攻擊成功的概率是這一概率只依賴于，并隨著N或的增加而增加。 如何對差分密碼分析和線性密碼分析進行改進，降低它們的復(fù)雜度仍是現(xiàn)在理論研究的熱點，目前已推出了很多改進方法，例如,高階差分密碼分析、截段差分密碼分析（truncateddifferentialcryptanalysis）、不可能差分密碼分析、多重線性密碼分析、非線性密碼分析、劃分密碼分析和差分-線性密碼分析，再如針對密鑰編排算法的相關(guān)密鑰攻擊、基于Lagrange插值公式的插值攻擊及基于密碼器件的能量分析（poweranalysis），另外還有錯誤攻擊、時間攻擊、Square攻擊和Davies攻擊等。參考文獻“DifferentialCryptanalysisoftheDataEncryptionStandard”(差分密碼分析)“LinearcryptanalysisMethodforDESCipher”(線性密碼分析)分組密碼在加密時,明文分組的長度是固定的，而實際應(yīng)用中待加密消息的數(shù)據(jù)量是不定的，數(shù)據(jù)格式可能是多種多樣的。為了能在各種應(yīng)用場合使用DES，美國在FIPSPUS74和81中定義了DES的4種運行模式，如表3-5所示。這些模式也可用于其他分組密碼，下面以DES為例來介紹這4種模式。3.4分組密碼的運行模式ECB(electroniccodebook)模式是最簡單的運行模式，它一次對一個64比特長的明文分組加密，而且每次的加密密鑰都相同，如圖3.10所示。當(dāng)密鑰取定時，對明文的每一個分組，都有一個惟一的密文與之對應(yīng)。因此形象地說，可以認為有一個非常大的電碼本，對任意一個可能的明文分組，電碼本中都有一項對應(yīng)于它的密文。3.4.1電碼本（ECB）模式圖3.10ECB模式示意圖 如果消息長于64比特，則將其分為長為64比特的分組，最后一個分組如果不夠64比特，則需要填充。解密過程也是一次對一個分組解密，而且每次解密都使用同一密鑰。圖3.10中，明文是由分組長為64比特的分組序列P1，P2，…，PN構(gòu)成，相應(yīng)的密文分組序列是C1，C2，…，CN。 ECB在用于短數(shù)據(jù)（如加密密鑰）時非常理想，因此如果需要安全地傳遞DES密鑰，ECB是最合適的模式。 ECB的最大特性是同一明文分組在消息中重復(fù)出現(xiàn)的話，產(chǎn)生的密文分組也相同。 ECB用于長消息時可能不夠安全，如果消息有固定結(jié)構(gòu)，密碼分析者有可能找出這種關(guān)系。例如，如果已知消息總是以某個預(yù)定義字段開始，那么分析者就可能得到很多明文-密文對。如果消息有重復(fù)的元素而重復(fù)的周期是64的倍數(shù)，那么密碼分析者就能夠識別這些元素。以上這些特性都有助于密碼分析者，有可能為其提供對分組的代換或重排的機會。ECB優(yōu)缺點小結(jié)優(yōu)點：加密短數(shù)據(jù)，如對密鑰的加密，效率較高。缺點：（1）難抗已知明文攻擊，特別是有固定格式的長消息不適合；（2）信息有周期規(guī)律出現(xiàn)，易破譯。例如每隔一頁為64位（倍數(shù)），每隔一頁的頁眉都相同：“科大畢業(yè)設(shè)計”，易破譯出此局部明文，從而找到密鑰k；（3）明文分組在消息中重復(fù)，則也有重復(fù)的密文分組。為了解決ECB的安全缺陷，可以讓重復(fù)的明文分組產(chǎn)生不同的密文分組，CBC（cipherblockchaining）模式就可滿足這一要求。 加密算法的輸入是當(dāng)前明文分組和前一次密文分組的異或， 因此加密算法的輸入不會顯示出與這次的明文分組之間的固定關(guān)系，所以重復(fù)的明文分組不會在密文中暴露出這種重復(fù)關(guān)系。3.4.2密碼分組鏈接（CBC）模式圖3.11CBC模式示意圖 解密時，每一個密文分組被解密后，再與前一個密文分組異或，即（設(shè)）因而產(chǎn)生出明文分組。 在產(chǎn)生第1個密文分組時，需要有一個初始向量IV與第1個明文分組異或。解密時，IV和解密算法對第1個密文分組的輸出進行異或以恢復(fù)第1個明文分組。 IV對于收發(fā)雙方都應(yīng)是已知的，為使安全性最高，IV應(yīng)像密鑰一樣被保護，可使用ECB加密模式來發(fā)送IV。保護IV的原因如下：如果敵手能欺騙接收方使用不同的IV值，敵手就能夠在明文的第1個分組中插入自己選擇的比特值，這是因為： 用X(i)表示64比特分組X的第i個比特，那么，由異或的性質(zhì)得 其中撇號表示比特補。上式意味著如果敵手篡改IV中的某些比特，則接收方收到的P1中相應(yīng)的比特也發(fā)生了變化，從而使接收方不能得到真實的P1分組。CBC優(yōu)缺點小結(jié)優(yōu)點：克服了ECB的第（3）個缺點，即CBC中重復(fù)的明文分組不會在密文中暴露重復(fù)關(guān)系。缺點：（1）如何保護IV不被篡改；學(xué)生？？？（2）存在“比特錯誤傳播”特性，例如Ci中有1位錯，則會影響Pi+1（？？？），錯誤傳播有限。 如上所述，DES是分組長為64比特的分組密碼，但利用CFB（cipherfeedback）模式或OFB模式可將DES轉(zhuǎn)換為流密碼。流密碼不需要對消息填充，而且運行是實時的。因此如果傳送字母流，可使用流密碼對每個字母直接加密并傳送。 流密碼具有密文和明文一樣長這一性質(zhì)，因此，如果需要發(fā)送的每個字符長為8比特，就應(yīng)使用8比特密鑰來加密每個字符。3.4.3密碼反饋（CFB）模式圖3.12CFB模式示意圖(密文反饋)

解密時，將收到的密文單元與加密函數(shù)的輸出進行異或。注意這時仍然使用加密算法而不是解密算法，原因如下：設(shè)Sj(X)是X的j個最高有效位，那么因此可證明以后各步也有類似的這種關(guān)系。CFB模式除能獲得保密性外，還能用于認證。CFB優(yōu)缺點小結(jié)優(yōu)點：形成流密碼方式傳送，可對傳送的位數(shù)靈活控制，或1位，或8位（1個字母）等；缺點：有“比特錯誤傳播”特性，同CBC。Ci中有1位出錯，則會影響Pi和Pi+1，對于傳播來講，就只有Pi+1，故錯誤傳播有限。OFB（outputfeedback）模式的結(jié)構(gòu)類似于CFB，見圖3.13。不同之處如下：OFB模式是將加密算法的輸出反饋到移位寄存器，而CFB模式中是將密文單元反饋到移位寄存器。3.4.4輸出反饋(OFB)模式圖3.13OFB模式示意圖（輸出反饋）

OFB模式的優(yōu)點是傳輸過程中的比特錯誤不會被傳播（因為OFB中各個密文分組的形成是“獨立”的，不依賴于前面的密文分組）。

OFB的缺點是它比CFB模式更易受到對消息流的篡改攻擊，比如在密文中取1比特的補，那么在恢復(fù)的明文中相應(yīng)位置的比特也為原比特的補（異或運算的特性）。 因此使得敵手有可能通過對消息校驗部分的篡改和對數(shù)據(jù)部分的篡改，而以糾錯碼不能檢測的方式篡改密文，即使完整性檢查失效。OFB模式缺點：完整性檢查失效 來學(xué)嘉（X.J.Lai）和J.L.Massey提出的第1版IDEA（internationaldataencryptionalgorithm，國際數(shù)據(jù)加密算法）于1990年公布，當(dāng)時稱為PES（proposedencryptionstandard，建議加密標(biāo)準(zhǔn)）。1991年，在Biham和Shamir提出差分密碼分析之后，設(shè)計者推出了改進算法IPES，即改進型建議加密標(biāo)準(zhǔn)。1992年，設(shè)計者又將IPES改名為IDEA。這是近年來提出的各種分組密碼中一個很成功的方案，已在PGP中采用。3.5IDEA 算法中明文和密文分組長度都是64比特，密鑰長128比特。其設(shè)計原理可從強度和實現(xiàn)兩方面考慮。1.密碼強度算法的強度主要是通過有效的混淆和擴散特性而得以保證。3.5.1設(shè)計原理IDEA三種運算(X+Y)mod2(X+Y)mod2n(X.Y)mod(2n+1) 對于“整數(shù)乘法”運算，若X或Y為0，則視X或Y為2n；若X.Y為2n，則視乘積結(jié)果為0.

算法中擴散是由稱為乘加（multiplication/addition,MA）結(jié)構(gòu)的基本單元實現(xiàn)的。該結(jié)構(gòu)的輸入是兩個16比特的子段和兩個16比特的子密鑰，輸出也為兩個16比特的子段。這一結(jié)構(gòu)在算法中重復(fù)使用了8次，獲得了非常有效的擴散效果。每一輪兩個子段交換，起混淆作用，以抗差分密碼分析。圖3.14MA結(jié)構(gòu)2.實現(xiàn)IDEA可方便地通過軟件和硬件實現(xiàn)。①軟件軟件實現(xiàn)采用16比特子段處理，可通過使用容易編程的加法、移位等運算實現(xiàn)算法的3種運算。②硬件由于加、解密相似，差別僅為使用密鑰的方式，因此可用同一器件實現(xiàn)。再者，算法中規(guī)則的模塊結(jié)構(gòu)，可方便VLSI的實現(xiàn)。圖3.15IDEA的加密框圖圖3.16IDEA第1輪的輪結(jié)構(gòu)1.輪結(jié)構(gòu)圖3.17IDEA的輸出變換2.子密鑰的產(chǎn)生

加密過程中52個16比特的子密鑰是由128比特的加密密鑰按如下方式產(chǎn)生的：前8個子密鑰Z1，Z2，…，Z8直接從加密密鑰中取，即Z1取前16比特（最高有效位），Z2取下面的16比特，依次類推。然后加密密鑰循環(huán)左移25位，再取下面8個子密鑰Z9，Z10，…，Z16，取法與Z1，Z2，…，Z8的取法相同。這一過程重復(fù)下去，直到52子密鑰都被產(chǎn)生為止。（畫圖描述）3.解密過程 解密過程和加密過程基本相同，但子密鑰的選取不同。解密子密鑰U1，U2，…，U52是由加密子密鑰按如下方式得到（將加密過程最后一步的輸出變換當(dāng)作第9輪）：①第i(i=1,…,9)輪解密的前4個子密鑰由加密過程第(10-i)輪的前4個子密鑰得出： 其中第1和第4個解密子密鑰取為相應(yīng)的第1和第4個加密子密鑰的模216+1乘法逆元，第2和第3個子密鑰的取法為：當(dāng)輪數(shù)i=2,…,8時，取為相應(yīng)的第3個和第2個加密子密鑰的模216加法逆元。i=1和9時，取為相應(yīng)的第2個和第3個加密子密鑰的模216加法逆元。②第i(i=1,…,8)輪解密的后兩個子密鑰等于加密過程第(9-i)輪的后兩個子密鑰。 下面驗證解密過程的確可以得到正確的結(jié)果。圖3.18中左邊為加密過程，由上至下，右邊為解密過程，由下至上。將每一輪進一步分為兩步，第1步是變換，其余部分作為第2步，稱為子加密。圖3.18IDEA加密和解密框圖（加密）子加密：W81=I81MAR(I81I83，I82I84)W82=I83MAR(I81I83，I82I84)W83=I82MAL(I81I83，I82I84)W84=I84MAL(I81I83，I82I84)（加密）變換：Y1=W81⊙Z49Y2=W83+Z50Y3=W82+Z51Y4=W84⊙Z52解密過程中第1輪的第1步產(chǎn)生以下關(guān)系：J11=Y1⊙U1J12=Y2+U2J13=Y3+U3J14=Y4⊙U4（解密）變換：J11=Y1⊙Z-149=W81⊙Z49⊙Z-149=W81J12=Y2+

-Z50=W83+

Z50+

-Z50=W83J13=Y3+

-Z51=W82+

Z51+

-Z51=W82J14=Y4⊙Z-152=W84⊙Z52⊙Z-152=W84(解密)子加密：其中MAR(X,Y)是MA結(jié)構(gòu)輸入為X和Y時的右邊輸出，MAL(X,Y)是左邊輸出。則V11=J11MAR(J11J13,J12J14)=W81MAR(W81W82,W83W84)=I81MAR(I81I83,I82I84)MAR[I81MAR(I81I83,I82I84)I83

MAR(I81I83,I82I84),I82

MAL(I81I83,I82I84)I84

MAL(I81I83,I82I84)]=I81MAR(I81I83,I82I84)MAR(I81I83,I82I84)=I81類似地，可有V12=I83V13=I82V14=I84所以解密過程第1輪第2步的輸出等于加密過程倒數(shù)第2步輸入中第2個子段和第3個子段交換后的值。同理可證圖3.18中每步都有上述類似關(guān)系，這種關(guān)系一直到V81=I11V82=I13V83=I12V84=I14即除第2個子段和第3個子段交換位置外，解密過程的輸出變換與加密過程第1輪第1步的變換完全相同。即除第2個子段和第3個子段交換位置外，解密過程的輸出變換與加密過程第1輪第1步的變換完全相同。所以最后可得知，整個解密過程的輸出等于整個加密過程的輸入。IDEA安全性分析1.抗窮舉攻擊——密鑰長度較大2.抗差分密碼分析攻擊——不是嚴(yán)格的Feistel密碼結(jié)構(gòu)3.抗線性密碼分析攻擊——本身具有很強的非線性性 1997年4月15日，美國ANSI發(fā)起征集AES（advancedencryptionstandard）的活動，并為此成立了AES工作小組。此次活動的目的是確定一個非保密的、可以公開技術(shù)細節(jié)的、全球免費使用的分組密碼算法，以作為新的數(shù)據(jù)加密標(biāo)準(zhǔn)。1997年9月12日，美國聯(lián)邦登記處公布了正式征集AES候選算法的通告。對AES的基本要求是：比三重DES快、至少與三重DES一樣安全、數(shù)據(jù)分組長度為128比特、密鑰長度為128/192/256比特。3.6AES算法——Rijndael 1998年8月12日，在首屆AES候選會議（firstAEScandidateconference）上公布了AES的15個候選算法，任由全世界各機構(gòu)和個人攻擊和評論，這15個候選算法是CAST256、CRYPTON、E2、DEAL、FROG、SAFER+、RC6、MAGENTA、LOKI97、SERPENT、MARS、Rijndael、DFC、Twofish、HPC。1999年3月，在第2屆AES候選會議（secondAEScandidateconference）上經(jīng)過對全球各密碼機構(gòu)和個人對候選算法分析結(jié)果的討論，從15個候選算法中選出了5個。 這5個是RC6、Rijndael、SERPENT、Twofish和MARS。2000年4月13日至14日，召開了第3屆AES候選會議（thirdAEScandidateconference），繼續(xù)對最后5個候選算法進行討論。2000年10月2日，NIST宣布Rijndael作為新的AES。至此，經(jīng)過3年多的討論，Rijndael終于脫穎而出。 Rijndael由比利時的JoanDaemen和VincentRijmen設(shè)計，算法的原型是Square算法，它的設(shè)計策略是寬軌跡策略（widetrailstrategy）。寬軌跡策略是針對差分分析和線性分析提出的，它的最大優(yōu)點是可以給出算法的最佳差分特征的概率及最佳線性逼近的偏差的界；由此，可以分析算法抵抗差分密碼分析及線性密碼分析的能力。1.有限域GF(28) 有限域中的元素可以用多種不同的方式表示。對于任意素數(shù)的方冪，都有惟一的一個有限域，因此GF(28)的所有表示是同構(gòu)的，但不同的表示方法會影響到GF(28)上運算的復(fù)雜度，本算法采用傳統(tǒng)的多項式表示法。3.6.1Rijndael的數(shù)學(xué)基礎(chǔ)和設(shè)計思想有限域GF(28)

上的多項式的表示和計算表示：2——多項式系數(shù)的模；8——多項式項數(shù)（長度）f(x)=b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0(b7b6b5b4b3b2b1b0)實為多項式與二進制串在特定域上的一一對應(yīng)關(guān)系在GF(28)有限域上的多項式運算舉例：1.加法——異或

(x2+1)+(x2+x+1)=x101XOR111=01022.乘法——左移位&異或

(x+1).(x2+1)=x.(x2+1)+1.(x2+1) =x3+x+x2+1=x3+x2+x+1011.101=(101)<<1XOR(101)<<0= 1010XOR101=11112

3.模乘——左移位&異或 技巧1：xnmodp(x)=[p(x)-xn]，p(x)也是n次多項式(x3+x2+x+1)mod(x3+x+1)=(x3+x+1)-(x3+x2+x+1)=x21111mod1011=1111XOR1011=01002有限域GF(28)

上的多項式的表示和計算技巧2：x.f(x)modm(x)=b6b5b4b3b2b1b00,若b7=0

或=b6b5b4b3b2b1b00(00011011),若b7=1其中：f(x)=b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0

m(x)=x8+x4+x3+x+1計算都在GF(28)域上，m(x)為此域上的素多項式，位串(00011011)為m(x)除去x8項的二進制表示。有限域GF(28)

上的多項式的計算舉例設(shè)在GF(28),f(x)=x6+x4+x2+x+1,g(x)=x7+x+1,m(x)=x8+x4+x3+x+1求f(x).g(x)modm(x)

解見板書多項式模乘運算舉例例：f(x)=x2+x,g(x)=x2+1,模多項式m(x)=x3+x+1

求：f(x)×g(x)modm(x)=?解：①多項式除法求余方法；②二進制運算方法 ①…….

②f(x):(110)g(x):(101)m(x):1011 (110)×(101)=(110)×[(100)XOR(001)] =(110)×(100)XOR(110)×(001) =(110)×(010)×(010)XOR(110) =[(100)XOR(011)]×(010)XOR(110) =(111)×(010)XOR(110) =(110)XOR(011)XOR(110)=(011)即所求結(jié)果為：x+1歐幾里德算法——求最大公因式(a(x),b(x)) EUCLID[a(x),b(x)]

1.A(x)=a(x);B(x)=b(x) 2.ifB(x)=0returnA(x)=gcd[a(x),b(x)] 3.R(x)=A(x)modB(x) 4.A(x)=B(x) 5.B(x)=R(x) 6.goto2求最大公因式(a(x),b(x))舉例已知a(x)=x6+x5+x4+x3+x2+x+1,b(x)=x4+x2+x+1,求(a(x),b(x)).解：由歐幾里德算法得：x6+x5+x4+x3+x2+x+1=(x2+x)(x4+x2+x+1)+(x3+x2+1)

x4+x2+x+1=(x+1)(x3+x2+1)所以，(a(x),b(x))=(x3+x2+1,0)=x3+x2+1特別地,(a(x),0)=a(x)擴展的歐幾里德算法——求乘法逆元a-1(x)modm(x)1.[A1(X),A2(X),A3(X)][1,0,m(x)];[B1(X),B2(X),B3(X)][0,1,a(x)]2.若B3(x)=0,則返回A3(X)=(a(x),m(x)),無乘法逆元3.若B3(x)=1,則返回B3(X)=(a(x),m(x)),B2(X)=a-1(x)modm(x)4.Q(X)=A3(X)/B3(X)的商5.[T1(X),T2(X),T3(X)][A1(X)-Q(X)B1(X),A2(X)-Q(X)B2(X),A3(X)-Q(X)B3(X)]6.[A1(X),A2(X),A3(X)][B1(X),B2(X),B3(X)]7.[B1(X),B2(X),B3(X)][T1(X),T2(X),T3(X)]8.轉(zhuǎn)到2求乘法逆元a-1(x)modm(x)舉例求 GF(2)上(x7+x+1)-1mod(x8+x4+x3+x+1)解：由擴展的歐幾里德算法計算下表：

Q(x)A1(X)A2(X)A3(X)B1(X)B2(X)B3(X)-10x8+x4+x3+x+101x7+x+1x01x7+x+11xx4+x3+x2+1x3+x2+11xx4+x3+x+1x3+x2+1x2+1xx3+x2+1x3+x2+1x2+1xx6+x2+x+1x71所以：(x7+x+1，x8+x4+x3+x+1)=1

(x7+x+1)-1mod(x8+x4+x3+x+1)=x7 將b7b6b5b4b3b2b1b0構(gòu)成的字節(jié)b看成系數(shù)在{0,1}中的多項式b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0例如：十六進制數(shù)‘57’對應(yīng)的二進制為01010111，看成一個字節(jié)，對應(yīng)的多項式為x6+x4+x2+x+1。

兩個元素的和仍然是一個次數(shù)不超過7的多項式，其系數(shù)等于兩個元素對應(yīng)系數(shù)的模2加（比特異或）。例如：‘57’+‘83’=‘D4’，用多項式表示為(x6+x4+x2+x+1)+(x7+x+1)=x7+x6+x4+x2用二進制表示為01010111+10000011=11010100由于每個元素的加法逆元等于自己，所以減法和加法相同。乘法，必須先確定一個GF(2)上的8次不可約多項式；在Rijndael密碼中，這個8次不可約多項式確定為m(x)=x8+x4+x3+x+1它的十六進制表示為‘11B’。例如，‘57’·‘83’=‘C1’可表示為以下的多項式乘法：(x6+x4+x2+x+1)·(x7+x+1)=x7+x6+1(modm(x))乘法運算雖然不是標(biāo)準(zhǔn)的按字節(jié)的運算，但也是比較簡單的計算部件。以上定義的乘法滿足交換律，且有單位元‘01’。另外，對任何次數(shù)小于8的多項式b(x)，可用推廣的歐幾里得算法得b(x)a(x)+m(x)c(x)=1即a(x)·b(x)=1modm(x)，因此a(x)是b(x)的乘法逆元。再者，乘法還滿足分配律：a(x)·(b(x)+c(x))=a(x)·b(x)+a(x)·c(x) 256個字節(jié)值構(gòu)成的集合，在以上定義的加法和乘法運算下，有有限域GF(28)的結(jié)構(gòu)。 GF(28)上還定義了一個運算，稱之為x乘法，其定義為x·b(x)=b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0

x(modm(x))如果b7=0，求模結(jié)果不變，否則為乘積結(jié)果減去m(x)，即求乘積結(jié)果與m(x)的異或。 由此得出x（十六進制數(shù)‘02’）乘b(x)可以先對b(x)在字節(jié)內(nèi)左移一位（最后一位補0），若b7=1，則再與‘1B’（其二進制為00011011）做逐比特異或來實現(xiàn)，該運算記為b=xtime(a)。在專用芯片中，xtime只需4個異或。x的冪乘運算可以重復(fù)應(yīng)用xtime來實現(xiàn)。而任意常數(shù)乘法可以通過對中間結(jié)果相加實現(xiàn)。例如，‘57’·‘13’可按如下方式實現(xiàn)：‘57’·‘02’=xtime(57)=‘AE’；‘57’·‘04’=xtime(AE)=‘47’；‘57’·‘08’=xtime(47)=‘8E’；‘57’·‘10’=xtime(8E)=‘07’；‘57’·‘13’=‘57’·(‘01’‘02’‘10’)=‘57’‘AE’‘07’=‘FE’。2.系數(shù)在GF(28)上的多項式 4個字節(jié)構(gòu)成的向量可以表示為系數(shù)在GF(28)上的次數(shù)小于4的多項式。多項式的加法就是對應(yīng)系數(shù)相加；換句話說，多項式的加法就是4字節(jié)向量的逐比特異或。

多項式的乘法運算必須要取模M(x)=x4+1，這樣使得次數(shù)小于4的多項式的乘積仍然是一個次數(shù)小于4的多項式，將多項式的模乘運算記為，設(shè)a(x)=a3x3+a2x2+a1x+a0，b(x)=b3x3+b2x2+b1x+b0，c(x)=a(x)b(x)=c3x3+c2x2+c1x+c0。由于xjmod(x4+1)=x

j

mod4，所以c0=a0b0

a3b1

a2b2

a1b3；c1=a1b0

a0b1

a3b2

a2b3；c2=a2b0

a1b1

a0b2

a3b3；c3=a3b0

a2b1

a1b2

a0b3。可將上述計算表示為 注意到M(x)不是GF(28)上的不可約多項式（甚至也不是GF(2)上的不可約多項式），因此非0多項式的這種乘法不是群運算。不過在Rijndael密碼中，對多項式b(x)，這種乘法運算只限于乘一個固定的有逆元的多項式a(x)=a3x3+a2x2+a1x+a0。 定理3.1系數(shù)在GF(28)上的多項式a3x3+a2x2+a1x+a0是模x4+1可逆的，當(dāng)且僅當(dāng)矩陣在GF(28)上可逆。 證明：a3x3+a2x2+a1x+a0是模x4+1可逆的，當(dāng)且僅當(dāng)存在多項式h3x3+h2x2+h1x+h0(a3x3+a2x2+a1x+a0)(h3x3+h2x2+h1x+h0)=1mod(x4+1)

因此有(a3x3+a2x2+a1x+a0)(h2x3+h1x2+h0x+h3)=xmod(x4+1)(a3x3+a2x2+a1x+a0)(h1x3+h0x2+h3x+h2)=x2mod(x4+1)(a3x3+a2x2+a1x+a0)(h0x3+h3x2+h2x+h1)=x3mod(x4+1)將以上關(guān)系寫成矩陣形式即得（證畢）c(x)=xb(x)定義為x與b(x)的模x4+1乘法，即c(x)=xb(x)=b2x3+b1x2+b0x+b3。其矩陣表示中，除a1=‘01’外，其他所有ai=‘00’，即 因此，x（或x的冪）模乘多項式相當(dāng)于對字節(jié)構(gòu)成的向量進行字節(jié)循環(huán)移位。3.設(shè)計思想 Rijndael密碼的設(shè)計力求滿足以下3條標(biāo)準(zhǔn)：①抵抗所有已知的攻擊。②在多個平臺上速度快，編碼緊湊。③設(shè)計簡單。 當(dāng)前的大多數(shù)分組密碼，其輪函數(shù)是Feistel結(jié)構(gòu)，即將中間狀態(tài)的部分比特不加改變地簡單放置到其他位置。Rijndael沒有這種結(jié)構(gòu)，其輪函數(shù)是由3個不同的可逆均勻變換組成的，稱它們?yōu)?個“層”。所謂“均勻變換”是指狀態(tài)的每個比特都是用類似的方法進行處理的。不同層的特定選擇大部分是建立在“寬軌跡策略”的應(yīng)用基礎(chǔ)上的。簡單地說，“寬軌跡策略”就是提供抗線性密碼分析和差分密碼分析能力的一種設(shè)計。 為實現(xiàn)寬軌跡策略，輪函數(shù)3個層中的每一層都有它自己的功能：線性混合層 確保多輪之上的高度擴散；非線性層 將具有最優(yōu)的“最壞情況非線性特性”的S盒并行使用；密鑰加層 單輪子密鑰簡單地異或到中間狀態(tài)上，實現(xiàn)一次性掩蓋。 在第一輪之前，用了一個初始密鑰加層，其目的是在不知道密鑰的情況下，對最后一個密鑰加層以后的任一層（或者是當(dāng)進行已知明文攻擊時，對第一個密鑰加層以前的任一層）可簡單地剝?nèi)?，因此初始密鑰加層對密碼的安全性無任何意義。許多密碼的設(shè)計中都在輪變換之前和之后用了密鑰加層，如IDEA、SAFER和Blowfish。 為了使加密算法和解密算法在結(jié)構(gòu)上更加接近，最后一輪的線性混合層與前面各輪的線性混合層不同，這類似于DES的最后一輪不做左右交換?？梢宰C明這種設(shè)計不以任何方式提高或降低該密碼的安全性。 Rijndael是一個迭代型分組密碼，其分組長度和密鑰長度都可變，各自可以獨立地指定為128比特、192比特、256比特。3.6.2算法說明AES加密和解密1.狀態(tài)、種子密鑰和輪數(shù)

類似于明文分組和密文分組，算法的中間結(jié)果也須分組，稱算法中間結(jié)果的分組為狀態(tài)，所有的操作都在狀態(tài)上進行。狀態(tài)可以用以字節(jié)為元素的矩陣陣列表示，該陣列有4行，列數(shù)記為Nb，Nb等于分組長度除以32。

種子密鑰類似地用一個以字節(jié)為元素的矩陣陣列表示，該陣列有4行，列數(shù)記為Nk，Nk等于分組長度除以32。 有時可將這些分組當(dāng)作一維數(shù)組，其每一元素是上述陣列表示中的4字節(jié)元素構(gòu)成的列向量，數(shù)組長度可為4、6、8，數(shù)組元素下標(biāo)的范圍分別是0~3、0~5和0~7。4字節(jié)元素構(gòu)成的列向量有時也稱為字。 算法的輸入和輸出被看成是由8比特字節(jié)構(gòu)成的一維數(shù)組，其元素下標(biāo)的范圍是0~(4Nb

–1)，因此輸入和輸出以字節(jié)為單位的分組長度分別是16、24和32，其元素下標(biāo)的范圍分別是0~15、0~23和0~31。 輸入的種子密鑰也看成是由8比特字節(jié)構(gòu)成的一維數(shù)組，其元素下標(biāo)的范圍是0~(4Nk–1)，因此種子密鑰以字節(jié)為單位的分組長度也分別是16、24和32，其元素下標(biāo)的范圍分別是0~15、0~23和0~31。 算法的輸入（包括最初的明文輸入和中間過程的輪輸入）以字節(jié)為單位按a00a10a20a30a01a11a21a31…的順序放置到狀態(tài)陣列中。同理，種子密鑰以字節(jié)為單位按k00k10k20k30k01k11k21k31…的順序放置到種子密鑰陣列中。而輸出（包括中間過程的輪輸出和最后的密文輸出）也是以字節(jié)為單位按相同的順序從狀態(tài)陣列中取出。若輸入（或輸出）分組中第n個元素對應(yīng)于狀態(tài)陣列的第(i,j)位置上的元素，則n和(i,j)有以下關(guān)系：i=nmod4;j=;n=i+4j迭代的輪數(shù)記為Nr，Nr與Nb和Nk有關(guān)，表3.9給出了Nr與Nb和Nk的關(guān)系。2.輪函數(shù) Rijndael的輪函數(shù)由4個不同的計算部件組成，分別是：字節(jié)代換（ByteSub）行移位（ShiftRow）列混合（MixColumn）密鑰加（AddRoundKey）(1)字節(jié)代換（ByteSub） 字節(jié)代換是非線形變換，獨立地對狀態(tài)的每個字節(jié)進行。代換表（即S-盒）是可逆的，由以下兩個變換的合成得到：①首先，將字節(jié)看作GF(28)上的元素，映射到自己的乘法逆元，‘00’映射到自己。②其次，對字節(jié)做如下的（GF(2)上的，可逆的）仿射變換：上述S-盒對狀態(tài)的所有字節(jié)所做的變換記為ByteSub(State)圖3.19字節(jié)代換示意圖 ByteSub的逆變換由代換表的逆表做字節(jié)代換，可通過如下兩步實現(xiàn):首先進行仿射變換的逆變換，再求每一字節(jié)在GF(28)上逆元。(2)行移位（ShiftRow） 行移位是將狀態(tài)陣列的各行進行循環(huán)移位，不同狀態(tài)行的位移量不同。第0行不移動，第1行循環(huán)左移C1個字節(jié)，第2行循環(huán)左移C2個字節(jié)，第3行循環(huán)左移C3個字節(jié)。位移量C1、C2、C3的取值與Nb有關(guān)，由表3.10給出。圖3.20行移位示意圖

行移位運算記為ShiftRow(State) ShiftRow的逆變換是對狀態(tài)陣列的后3列分別以位移量Nb-C1、Nb-C2、Nb-C3進行循環(huán)移位，使得第i行第j列的字節(jié)移位到(j+Nb-Ci)modNb。（3）列混合（MixColumn）

在列混合變換中，將狀態(tài)陣列的每個列視為GF(28)上的多項式，再與一個固定的多項式c(x)進行模x4+1乘法。當(dāng)然要求c(x)是模x4+1可逆的多項式，否則列混合變換就是不可逆的，因而會使不同的輸入分組對應(yīng)的輸出分組可能相同。Rijndael的設(shè)計者給出的c(x)為（系數(shù)用十六進制數(shù)表示）：

c(x)=‘03’x3+‘01’x2+‘01’x+‘02’c(x)是與x4+1互素的，因此是模x4+1可逆的。列混合運算也可寫為矩陣乘法。設(shè)b(x)=c(x)a(x)，則這個運算需要做GF(28)上的乘法，但由于所乘的因子是3個固定的元素02、03、01，所以這些乘法運算仍然是比較簡單的。對狀態(tài)State的所有列所做的列混合運算記為MixColumn（State）圖3.21是列混合運算示意圖。列混合結(jié)構(gòu)示意圖圖3.21列混合運算示意圖 列混合運算的逆運算是類似的，即每列都用一個特定的多項式d(x)相乘。d(x)滿足(‘03’x3+‘01’x2+‘01’x+‘02’)d(x)=‘01’由此可得d(x)=‘0B’x3+‘0D’x2+‘09’x+‘0E’(4)密鑰加（AddRoundKey） 密鑰加是將輪密鑰簡單地與狀態(tài)進行逐比特異或。輪密鑰由種子密鑰通過密鑰編排算法得到，輪密鑰長度等于分組長度Nb。狀態(tài)State與輪密鑰RoundKey的密鑰加運算表示為

AddRoundKey(State,RoundKey)圖3.22是密鑰加運算示意圖。圖3.22密鑰加運算示意圖密鑰加運算的逆運算是其自身。綜上所述，組成Rijndael輪函數(shù)的計算部件簡捷快速，功能互補。輪函數(shù)的偽C代碼如下：Round(State,RoundKey){ByteSub(State);ShiftRow(State);MixColumn(State);AddRoundKey(State,RoundKey)}結(jié)尾輪的輪函數(shù)與前面各輪不同，將MixColumn這一步去掉，其偽C代碼如下：FinalRound(State,RoundKey){ByteSub(State);ShiftRow(State);AddRoundKey(State,RoundKey)}在以上偽C代碼記法中，State、RoundKey可用指針類型，函數(shù)Round、FinalRound、ByteSub、ShiftRow、MixColumn、AddRoundKey都在指針State、RoundKey所指向的陣列上進行運算。3.密鑰編排 密鑰編排指從種子密鑰得到輪密鑰的過程，它由密鑰擴展和輪密鑰選取兩部分組成。其基本原則如下：輪密鑰的比特數(shù)等于分組長度乘以輪數(shù)加1；種子密鑰被擴展成為擴展密鑰；輪密鑰從擴展密鑰中取，其中第1輪輪密鑰取擴展密鑰的前Nb個字，第2輪輪密鑰取接下來的Nb個字，如此下去。密鑰擴展圖(1)密鑰擴展 擴展密鑰是以4字節(jié)字為元素的一維陣列，表示為W[Nb*(Nr+1)]，其中前Nk個字取為種子密鑰，以后每個字按遞歸方式定義。擴展算法根據(jù)Nk≤