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

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

稱每個(gè)子代換為代換盒，簡(jiǎn)稱為S盒。

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

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

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

Feistel解密過程本質(zhì)上和加密過程是一樣的，算法使用密文作為輸入，但使用子密鑰Ki的次序與加密過程相反，即第1輪使用Kn，第2輪使用Kn-1，……，最后一輪使用K1。這一特性保證了解密和加密可采用同一算法。圖3.4Feistel加解密過程在加密過程中：在解密過程中所以解密過程第1輪的輸出為LE15‖RE15，等于加密過程第16輪輸入左右兩半交換后的結(jié)果。容易證明這種對(duì)應(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）作出評(píng)估，并重新批準(zhǔn)它是否繼續(xù)作為聯(lián)邦加密標(biāo)準(zhǔn)。3.2數(shù)據(jù)加密標(biāo)準(zhǔn)最近的一次評(píng)估是在1994年1月，美國已決定1998年12月以后將不再使用DES。1997年DESCHALL小組經(jīng)過近4個(gè)月的努力，通過Internet搜索了3×1016個(gè)密鑰，找出了DES的密鑰，恢復(fù)出了明文。1998年5月美國EFF(electronicsfrontierfoundation)宣布，他們以一臺(tái)價(jià)值20萬美元的計(jì)算機(jī)改裝成的專用解密機(jī)，用56小時(shí)破譯了56比特密鑰的DES。美國國家標(biāo)準(zhǔn)和技術(shù)協(xié)會(huì)已征集并進(jìn)行了幾輪評(píng)估、篩選，產(chǎn)生了稱之為AES(advancedencryptionstandard)的新加密標(biāo)準(zhǔn)。盡管如此，DES對(duì)于推動(dòng)密碼理論的發(fā)展和應(yīng)用畢竟起了重大作用，對(duì)于掌握分組密碼的基本理論、設(shè)計(jì)思想和實(shí)際應(yīng)用仍然有著重要的參考價(jià)值，下面首先來描述這一算法。圖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)的計(jì)算過程 對(duì)每個(gè)盒Si，其6比特輸入中，第1個(gè)和第6個(gè)比特形成一個(gè)2位二進(jìn)制數(shù)，用來選擇Si的4個(gè)代換中的一個(gè)。6比特輸入中，中間4位用來選擇列。行和列選定后，得到其交叉位置的十進(jìn)制數(shù)，將這個(gè)數(shù)表示為4位二進(jìn)制數(shù)即得這一S盒的輸出。 例如，S1

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

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

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

OFB模式的優(yōu)點(diǎn)是傳輸過程中的比特錯(cuò)誤不會(huì)被傳播（因?yàn)镺FB中各個(gè)密文分組的形成是“獨(dú)立”的，不依賴于前面的密文分組）。

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

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

加密過程中52個(gè)16比特的子密鑰是由128比特的加密密鑰按如下方式產(chǎn)生的：前8個(gè)子密鑰Z1，Z2，…，Z8直接從加密密鑰中取，即Z1取前16比特（最高有效位），Z2取下面的16比特，依次類推。然后加密密鑰循環(huán)左移25位，再取下面8個(gè)子密鑰Z9，Z10，…，Z16，取法與Z1，Z2，…，Z8的取法相同。這一過程重復(fù)下去，直到52子密鑰都被產(chǎn)生為止。（畫圖描述）3.解密過程 解密過程和加密過程基本相同，但子密鑰的選取不同。解密子密鑰U1，U2，…，U52是由加密子密鑰按如下方式得到（將加密過程最后一步的輸出變換當(dāng)作第9輪）：①第i(i=1,…,9)輪解密的前4個(gè)子密鑰由加密過程第(10-i)輪的前4個(gè)子密鑰得出： 其中第1和第4個(gè)解密子密鑰取為相應(yīng)的第1和第4個(gè)加密子密鑰的模216+1乘法逆元，第2和第3個(gè)子密鑰的取法為：當(dāng)輪數(shù)i=2,…,8時(shí)，取為相應(yīng)的第3個(gè)和第2個(gè)加密子密鑰的模216加法逆元。i=1和9時(shí)，取為相應(yīng)的第2個(gè)和第3個(gè)加密子密鑰的模216加法逆元。②第i(i=1,…,8)輪解密的后兩個(gè)子密鑰等于加密過程第(9-i)輪的后兩個(gè)子密鑰。 下面驗(yàn)證解密過程的確可以得到正確的結(jié)果。圖3.18中左邊為加密過程，由上至下，右邊為解密過程，由下至上。將每一輪進(jìn)一步分為兩步，第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時(shí)的右邊輸出，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個(gè)子段和第3個(gè)子段交換后的值。同理可證圖3.18中每步都有上述類似關(guān)系，這種關(guān)系一直到V81=I11V82=I13V83=I12V84=I14即除第2個(gè)子段和第3個(gè)子段交換位置外，解密過程的輸出變換與加密過程第1輪第1步的變換完全相同。即除第2個(gè)子段和第3個(gè)子段交換位置外，解密過程的輸出變換與加密過程第1輪第1步的變換完全相同。所以最后可得知，整個(gè)解密過程的輸出等于整個(gè)加密過程的輸入。IDEA安全性分析1.抗窮舉攻擊——密鑰長度較大2.抗差分密碼分析攻擊——不是嚴(yán)格的Feistel密碼結(jié)構(gòu)3.抗線性密碼分析攻擊——本身具有很強(qiáng)的非線性性 1997年4月15日，美國ANSI發(fā)起征集AES（advancedencryptionstandard）的活動(dòng)，并為此成立了AES工作小組。此次活動(dòng)的目的是確定一個(gè)非保密的、可以公開技術(shù)細(xì)節(jié)的、全球免費(fèi)使用的分組密碼算法，以作為新的數(shù)據(jù)加密標(biāo)準(zhǔn)。1997年9月12日，美國聯(lián)邦登記處公布了正式征集AES候選算法的通告。對(duì)AES的基本要求是：比三重DES快、至少與三重DES一樣安全、數(shù)據(jù)分組長度為128比特、密鑰長度為128/192/256比特。3.6AES算法——Rijndael 1998年8月12日，在首屆AES候選會(huì)議（firstAEScandidateconference）上公布了AES的15個(gè)候選算法，任由全世界各機(jī)構(gòu)和個(gè)人攻擊和評(píng)論，這15個(gè)候選算法是CAST256、CRYPTON、E2、DEAL、FROG、SAFER+、RC6、MAGENTA、LOKI97、SERPENT、MARS、Rijndael、DFC、Twofish、HPC。1999年3月，在第2屆AES候選會(huì)議（secondAEScandidateconference）上經(jīng)過對(duì)全球各密碼機(jī)構(gòu)和個(gè)人對(duì)候選算法分析結(jié)果的討論，從15個(gè)候選算法中選出了5個(gè)。 這5個(gè)是RC6、Rijndael、SERPENT、Twofish和MARS。2000年4月13日至14日，召開了第3屆AES候選會(huì)議（thirdAEScandidateconference），繼續(xù)對(duì)最后5個(gè)候選算法進(jìn)行討論。2000年10月2日，NIST宣布Rijndael作為新的AES。至此，經(jīng)過3年多的討論，Rijndael終于脫穎而出。 Rijndael由比利時(shí)的JoanDaemen和VincentRijmen設(shè)計(jì)，算法的原型是Square算法，它的設(shè)計(jì)策略是寬軌跡策略（widetrailstrategy）。寬軌跡策略是針對(duì)差分分析和線性分析提出的，它的最大優(yōu)點(diǎn)是可以給出算法的最佳差分特征的概率及最佳線性逼近的偏差的界；由此，可以分析算法抵抗差分密碼分析及線性密碼分析的能力。1.有限域GF(28) 有限域中的元素可以用多種不同的方式表示。對(duì)于任意素?cái)?shù)的方冪，都有惟一的一個(gè)有限域，因此GF(28)的所有表示是同構(gòu)的，但不同的表示方法會(huì)影響到GF(28)上運(yùn)算的復(fù)雜度，本算法采用傳統(tǒng)的多項(xiàng)式表示法。3.6.1Rijndael的數(shù)學(xué)基礎(chǔ)和設(shè)計(jì)思想有限域GF(28)

上的多項(xiàng)式的表示和計(jì)算表示：2——多項(xiàng)式系數(shù)的模；8——多項(xiàng)式項(xiàng)數(shù)（長度）f(x)=b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0(b7b6b5b4b3b2b1b0)實(shí)為多項(xiàng)式與二進(jìn)制串在特定域上的一一對(duì)應(yīng)關(guān)系在GF(28)有限域上的多項(xiàng)式運(yùn)算舉例：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次多項(xiàng)式(x3+x2+x+1)mod(x3+x+1)=(x3+x+1)-(x3+x2+x+1)=x21111mod1011=1111XOR1011=01002有限域GF(28)

上的多項(xiàng)式的表示和計(jì)算技巧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計(jì)算都在GF(28)域上，m(x)為此域上的素多項(xiàng)式，位串(00011011)為m(x)除去x8項(xiàng)的二進(jìn)制表示。有限域GF(28)

上的多項(xiàng)式的計(jì)算舉例設(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)

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

求：f(x)×g(x)modm(x)=?解：①多項(xiàng)式除法求余方法；②二進(jìn)制運(yùn)算方法 ①…….

②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)擴(kuò)展的歐幾里德算法——求乘法逆元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)解：由擴(kuò)展的歐幾里德算法計(jì)算下表：

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}中的多項(xiàng)式b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0例如：十六進(jìn)制數(shù)‘57’對(duì)應(yīng)的二進(jìn)制為01010111，看成一個(gè)字節(jié)，對(duì)應(yīng)的多項(xiàng)式為x6+x4+x2+x+1。

兩個(gè)元素的和仍然是一個(gè)次數(shù)不超過7的多項(xiàng)式，其系數(shù)等于兩個(gè)元素對(duì)應(yīng)系數(shù)的模2加（比特異或）。例如：‘57’+‘83’=‘D4’，用多項(xiàng)式表示為(x6+x4+x2+x+1)+(x7+x+1)=x7+x6+x4+x2用二進(jìn)制表示為01010111+10000011=11010100由于每個(gè)元素的加法逆元等于自己，所以減法和加法相同。乘法，必須先確定一個(gè)GF(2)上的8次不可約多項(xiàng)式；在Rijndael密碼中，這個(gè)8次不可約多項(xiàng)式確定為m(x)=x8+x4+x3+x+1它的十六進(jìn)制表示為‘11B’。例如，‘57’·‘83’=‘C1’可表示為以下的多項(xiàng)式乘法：(x6+x4+x2+x+1)·(x7+x+1)=x7+x6+1(modm(x))乘法運(yùn)算雖然不是標(biāo)準(zhǔn)的按字節(jié)的運(yùn)算，但也是比較簡(jiǎn)單的計(jì)算部件。以上定義的乘法滿足交換律，且有單位元‘01’。另外，對(duì)任何次數(shù)小于8的多項(xiàng)式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個(gè)字節(jié)值構(gòu)成的集合，在以上定義的加法和乘法運(yùn)算下，有有限域GF(28)的結(jié)構(gòu)。 GF(28)上還定義了一個(gè)運(yùn)算，稱之為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（十六進(jìn)制數(shù)‘02’）乘b(x)可以先對(duì)b(x)在字節(jié)內(nèi)左移一位（最后一位補(bǔ)0），若b7=1，則再與‘1B’（其二進(jìn)制為00011011）做逐比特異或來實(shí)現(xiàn)，該運(yùn)算記為b=xtime(a)。在專用芯片中，xtime只需4個(gè)異或。x的冪乘運(yùn)算可以重復(fù)應(yīng)用xtime來實(shí)現(xiàn)。而任意常數(shù)乘法可以通過對(duì)中間結(jié)果相加實(shí)現(xiàn)。例如，‘57’·‘13’可按如下方式實(shí)現(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)上的多項(xiàng)式 4個(gè)字節(jié)構(gòu)成的向量可以表示為系數(shù)在GF(28)上的次數(shù)小于4的多項(xiàng)式。多項(xiàng)式的加法就是對(duì)應(yīng)系數(shù)相加；換句話說，多項(xiàng)式的加法就是4字節(jié)向量的逐比特異或。

多項(xiàng)式的乘法運(yùn)算必須要取模M(x)=x4+1，這樣使得次數(shù)小于4的多項(xiàng)式的乘積仍然是一個(gè)次數(shù)小于4的多項(xiàng)式，將多項(xiàng)式的模乘運(yùn)算記為，設(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?？蓪⑸鲜鲇?jì)算表示為 注意到M(x)不是GF(28)上的不可約多項(xiàng)式（甚至也不是GF(2)上的不可約多項(xiàng)式），因此非0多項(xiàng)式的這種乘法不是群運(yùn)算。不過在Rijndael密碼中，對(duì)多項(xiàng)式b(x)，這種乘法運(yùn)算只限于乘一個(gè)固定的有逆元的多項(xiàng)式a(x)=a3x3+a2x2+a1x+a0。 定理3.1系數(shù)在GF(28)上的多項(xiàng)式a3x3+a2x2+a1x+a0是模x4+1可逆的，當(dāng)且僅當(dāng)矩陣在GF(28)上可逆。 證明：a3x3+a2x2+a1x+a0是模x4+1可逆的，當(dāng)且僅當(dāng)存在多項(xià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的冪）模乘多項(xiàng)式相當(dāng)于對(duì)字節(jié)構(gòu)成的向量進(jìn)行字節(jié)循環(huán)移位。3.設(shè)計(jì)思想 Rijndael密碼的設(shè)計(jì)力求滿足以下3條標(biāo)準(zhǔn)：①抵抗所有已知的攻擊。②在多個(gè)平臺(tái)上速度快，編碼緊湊。③設(shè)計(jì)簡(jiǎn)單。 當(dāng)前的大多數(shù)分組密碼，其輪函數(shù)是Feistel結(jié)構(gòu)，即將中間狀態(tài)的部分比特不加改變地簡(jiǎn)單放置到其他位置。Rijndael沒有這種結(jié)構(gòu)，其輪函數(shù)是由3個(gè)不同的可逆均勻變換組成的，稱它們?yōu)?個(gè)“層”。所謂“均勻變換”是指狀態(tài)的每個(gè)比特都是用類似的方法進(jìn)行處理的。不同層的特定選擇大部分是建立在“寬軌跡策略”的應(yīng)用基礎(chǔ)上的。簡(jiǎn)單地說，“寬軌跡策略”就是提供抗線性密碼分析和差分密碼分析能力的一種設(shè)計(jì)。 為實(shí)現(xiàn)寬軌跡策略，輪函數(shù)3個(gè)層中的每一層都有它自己的功能：線性混合層 確保多輪之上的高度擴(kuò)散；非線性層 將具有最優(yōu)的“最壞情況非線性特性”的S盒并行使用；密鑰加層 單輪子密鑰簡(jiǎn)單地異或到中間狀態(tài)上，實(shí)現(xiàn)一次性掩蓋。 在第一輪之前，用了一個(gè)初始密鑰加層，其目的是在不知道密鑰的情況下，對(duì)最后一個(gè)密鑰加層以后的任一層（或者是當(dāng)進(jìn)行已知明文攻擊時(shí)，對(duì)第一個(gè)密鑰加層以前的任一層）可簡(jiǎn)單地剝?nèi)ィ虼顺跏济荑€加層對(duì)密碼的安全性無任何意義。許多密碼的設(shè)計(jì)中都在輪變換之前和之后用了密鑰加層，如IDEA、SAFER和Blowfish。 為了使加密算法和解密算法在結(jié)構(gòu)上更加接近，最后一輪的線性混合層與前面各輪的線性混合層不同，這類似于DES的最后一輪不做左右交換?？梢宰C明這種設(shè)計(jì)不以任何方式提高或降低該密碼的安全性。 Rijndael是一個(gè)迭代型分組密碼，其分組長度和密鑰長度都可變，各自可以獨(dú)立地指定為128比特、192比特、256比特。3.6.2算法說明AES加密和解密1.狀態(tài)、種子密鑰和輪數(shù)

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

種子密鑰類似地用一個(gè)以字節(jié)為元素的矩陣陣列表示，該陣列有4行，列數(shù)記為Nk，Nk等于分組長度除以32。 有時(shí)可將這些分組當(dāng)作一維數(shù)組，其每一元素是上述陣列表示中的4字節(jié)元素構(gòu)成的列向量，數(shù)組長度可為4、6、8，數(shù)組元素下標(biāo)的范圍分別是0~3、0~5和0~7。4字節(jié)元素構(gòu)成的列向量有時(shí)也稱為字。 算法的輸入和輸出被看成是由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個(gè)元素對(duì)應(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個(gè)不同的計(jì)算部件組成，分別是：字節(jié)代換（ByteSub）行移位（ShiftRow）列混合（MixColumn）密鑰加（AddRoundKey）(1)字節(jié)代換（ByteSub） 字節(jié)代換是非線形變換，獨(dú)立地對(duì)狀態(tài)的每個(gè)字節(jié)進(jìn)行。代換表（即S-盒）是可逆的，由以下兩個(gè)變換的合成得到：①首先，將字節(jié)看作GF(28)上的元素，映射到自己的乘法逆元，‘00’映射到自己。②其次，對(duì)字節(jié)做如下的（GF(2)上的，可逆的）仿射變換：上述S-盒對(duì)狀態(tài)的所有字節(jié)所做的變換記為ByteSub(State)圖3.19字節(jié)代換示意圖 ByteSub的逆變換由代換表的逆表做字節(jié)代換，可通過如下兩步實(shí)現(xiàn):首先進(jìn)行仿射變換的逆變換，再求每一字節(jié)在GF(28)上逆元。(2)行移位（ShiftRow） 行移位是將狀態(tài)陣列的各行進(jìn)行循環(huán)移位，不同狀態(tài)行的位移量不同。第0行不移動(dòng)，第1行循環(huán)左移C1個(gè)字節(jié)，第2行循環(huán)左移C2個(gè)字節(jié)，第3行循環(huán)左移C3個(gè)字節(jié)。位移量C1、C2、C3的取值與Nb有關(guān)，由表3.10給出。圖3.20行移位示意圖

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

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

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

AddRoundKey(State,RoundKey)圖3.22是密鑰加運(yùn)算示意圖。圖3.22密鑰加運(yùn)算示意圖密鑰加運(yùn)算的逆運(yùn)算是其自身。綜上所述，組成Rijndael輪函數(shù)的計(jì)算部件簡(jiǎn)捷快速，功能互補(bǔ)。輪函數(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所指向的陣列上進(jìn)行運(yùn)算。3.密鑰編排 密鑰編排指從種子密鑰得到輪密鑰的過程，它由密鑰擴(kuò)展和輪密鑰選取兩部分組成。其基本原則如下：輪密鑰的比特?cái)?shù)等于分組長度乘以輪數(shù)加1；種子密鑰被擴(kuò)展成為擴(kuò)展密鑰；輪密鑰從擴(kuò)展密鑰中取，其中第1輪輪密鑰取擴(kuò)展密鑰的前Nb個(gè)字，第2輪輪密鑰取接下來的Nb個(gè)字，如此下去。密鑰擴(kuò)展圖(1)密鑰擴(kuò)展 擴(kuò)展密鑰是以4字節(jié)字為元素的一維陣列，表示為W[Nb*(Nr+1)]，其中前Nk個(gè)字取為種子密鑰，以后每個(gè)字按遞歸方式定義。擴(kuò)展算法根據(jù)Nk≤