1、第3章 分組密碼體制,3.1 分組密碼概述 3.2 數(shù)據(jù)加密標準 3.3 差分密碼分析與線性密碼分析 3.4 分組密碼的運行模式 3.5 IDEA 3.6 AES算法Rijndael 習題,在許多密碼系統(tǒng)中，單鑰分組密碼是系統(tǒng)安全的一個重要組成部分，用分組密碼易于構造偽隨機數(shù)生成器、流密碼、消息認證碼（MAC）和雜湊函數(shù)等，還可進而成為消息認證技術、數(shù)據(jù)完整性機制、實體認證協(xié)議以及單鑰數(shù)字簽字體制的核心組成部分。實際應用中對于分組密碼可能提出多方面的要求，除了安全性外，還有運行速度、存儲量（程序的長度、數(shù)據(jù)分組長度、高速緩存大小）、實現(xiàn)平臺（硬件、軟件、芯片）、運行模式等限制條件。這些都需要與

2、安全性要求之間進行適當?shù)恼壑羞x擇。,3.1分組密碼概述,分組密碼是將明文消息編碼表示后的數(shù)字序列x0,x1,xi,劃分成長為n的組x=(x0,x1,xn-1)，各組（長為n的矢量）分別在密鑰k=(k0,k1,kt-1)控制下變換成等長的輸出數(shù)字序列y=(y0,y1,ym-1)（長為m的矢量），其加密函數(shù)E：VnKVm，Vn和Vm分別是n維和m維矢量空間，K為密鑰空間，如圖3.1所示。它與流密碼不同之處在于輸出的每一位數(shù)字不是只與相應時刻輸入的明文數(shù)字有關，而是與一組長為n的明文數(shù)字有關。在相同密鑰下，分組密碼對長為n的輸入明文組所實施的變換是等同的，所以只需研究對任一組明文數(shù)字的變換規(guī)則。這種

3、密碼實質上是字長為n的數(shù)字序列的代換密碼。,圖3.1 分組密碼框圖,通常取m=n。若mn，則為有數(shù)據(jù)擴展的分組密碼；若mn，則為有數(shù)據(jù)壓縮的分組密碼。在二元情況下，x和y均為二元數(shù)字序列，它們的每個分量xi，yiGF(2)。本節(jié)將主要討論二元情況。設計的算法應滿足下述要求：, 分組長度n要足夠大，使分組代換字母表中的元素個數(shù)2n足夠大，防止明文窮舉攻擊法奏效。DES、IDEA、FEAL和LOKI等分組密碼都采用n=64，在生日攻擊下用232組密文成功概率為1/2，同時要求23264b=215MB存貯，故采用窮舉攻擊是不現(xiàn)實的。, 密鑰量要足夠大（即置換子集中的元素足夠多），盡可能消除弱密鑰并使

4、所有密鑰同等地好，以防止密鑰窮舉攻擊奏效。但密鑰又不能過長，以便于密鑰的管理。DES采用56比特密鑰，看來太短了，IDEA采用128比特密鑰，據(jù)估計，在今后3040年內采用80 比特密鑰是足夠安全的。, 由密鑰確定置換的算法要足夠復雜，充分實現(xiàn)明文與密鑰的擴散和混淆，沒有簡單的關系可循，能抗擊各種已知的攻擊，如差分攻擊和線性攻擊；有高的非線性階數(shù)，實現(xiàn)復雜的密碼變換；使對手破譯時除了用窮舉法外，無其它捷徑可循。, 加密和解密運算簡單，易于軟件和硬件高速實現(xiàn)。如將分組n化分為子段，每段長為8、16或者32。在以軟件實現(xiàn)時，應選用簡單的運算，使作用于子段上的密碼運算易于以標準處理器的基本運算，如加

5、、乘、移位等實現(xiàn)，避免用以軟件難于實現(xiàn)的逐比特置換。為了便于硬件實現(xiàn)，加密和解密過程之間的差別應僅在于由秘密密鑰所生成的密鑰表不同而已。這樣，加密和解密就可用同一器件實現(xiàn)。設計的算法采用規(guī)則的模塊結構，如多輪迭代等，以便于軟件和VLSI快速實現(xiàn)。此外，差錯傳播和數(shù)據(jù)擴展要盡可能地小。, 數(shù)據(jù)擴展。一般無數(shù)據(jù)擴展，在采用同態(tài)置換和隨機化加密技術時可引入數(shù)據(jù)擴展。 差錯傳播盡可能地小。,要實現(xiàn)上述幾點要求并不容易。首先，要在理論上研究有效而可靠的設計方法，而后進行嚴格的安全性檢驗，并且要易于實現(xiàn)。 下面介紹設計分組密碼時的一些常用方法。,如果明文和密文的分組長都為n比特，則明文的每一個分組都有2n

6、個可能的取值。為使加密運算可逆（使解密運算可行），明文的每一個分組都應產(chǎn)生惟一的一個密文分組，這樣的變換是可逆的，稱明文分組到密文分組的可逆變換為代換。不同可逆變換的個數(shù)有2n!個。,3.1.1 代換,圖3.2表示n=4的代換密碼的一般結構，4比特輸入產(chǎn)生16個可能輸入狀態(tài)中的一個，由代換結構將這一狀態(tài)映射為16個可能輸出狀態(tài)中的一個，每一輸出狀態(tài)由4個密文比特表示。加密映射和解密映射可由代換表來定義，如表3.1所示。這種定義法是分組密碼最常用的形式，能用于定義明文和密文之間的任何可逆映射。（見33頁表3.1）,圖3.2 代換結構,但這種代換結構在實用中還有一些問題需考慮。如果分組長度太小，如

7、n=4，系統(tǒng)則等價于古典的代換密碼，容易通過對明文的統(tǒng)計分析而被攻破。這個弱點不是代換結構固有的，只是因為分組長度太小。如果分組長度n足夠大，而且從明文到密文可有任意可逆的代換，那么明文的統(tǒng)計特性將被隱藏而使以上的攻擊不能奏效。,然而，從實現(xiàn)的角度來看，分組長度很大的可逆代換結構是不實際的。仍以表3.1為例，該表定義了n=4時從明文到密文的一個可逆映射，其中第2列是每個明文分組對應的密文分組的值，可用來定義這個可逆映射。因此從本質上來說，第2列是從所有可能映射中決定某一特定映射的密鑰。這個例子中，密鑰需要64比特。一般地，對n比特的代換結構，密鑰的大小是n2n比特。如對64比特的分組，密鑰大小

8、應是64264=2701021比特，因此難以處理。,實際中常將n分成較小的段，例如可選n=rn0，其中r和n0都是正整數(shù)，將設計n個變量的代換變?yōu)樵O計r個較小的子代換，而每個子代換只有n0個輸入變量。一般n0都不太大，稱每個子代換為代換盒，簡稱為S盒。例如DES中將輸入為48比特、輸出為32比特的代換用8個S盒來實現(xiàn)，每個S盒的輸入端數(shù)僅為6比特，輸出端數(shù)僅為4比特。,擴散和混淆是由Shannon提出的設計密碼系統(tǒng)的兩個基本方法，目的是抗擊敵手對密碼系統(tǒng)的統(tǒng)計分析。如果敵手知道明文的某些統(tǒng)計特性，如消息中不同字母出現(xiàn)的頻率、可能出現(xiàn)的特定單詞或短語，而且這些統(tǒng)計特性以某種方式在密文中反映出來，

9、那么敵手就有可能得出加密密鑰或其一部分，或者得出包含加密密鑰的一個可能的密鑰集合。在Shannon稱之為理想密碼的密碼系統(tǒng)中，密文的所有統(tǒng)計特性都與所使用的密鑰獨立。圖3.2討論的代換密碼就是這樣的一個密碼系統(tǒng)，然而它是不實用的。,3.1.2 擴散和混淆,所謂擴散，就是將明文的統(tǒng)計特性散布到密文中去，實現(xiàn)方式是使得明文的每一位影響密文中多位的值，等價于說密文中每一位均受明文中多位影響。例如對英文消息M=m1m2m3的加密操作 其中ord(mi)是求字母mi對應的序號，chr(i)是求序號i對應的字母。這時明文的統(tǒng)計特性將被散布到密文中，因而每一字母在密文中出現(xiàn)的頻率比在明文中出現(xiàn)的頻率更接近于

10、相等，雙字母及多字母出現(xiàn)的頻率也更接近于相等。在二元分組密碼中，可對數(shù)據(jù)重復執(zhí)行某個置換，再對這一置換作用于一函數(shù)，可獲得擴散。,分組密碼在將明文分組依靠密鑰變換到密文分組時，擴散的目的是使明文和密文之間的統(tǒng)計關系變得盡可能復雜，以使敵手無法得到密鑰；混淆是使密文和密鑰之間的統(tǒng)計關系變得盡可能復雜，以使敵手無法得到密鑰。因此即使敵手能得到密文的一些統(tǒng)計關系，由于密鑰和密文之間的統(tǒng)計關系復雜化，敵手也無法得到密鑰。使用復雜的代換算法可以得到預期的混淆效果，而簡單的線性代換函數(shù)得到的混淆效果則不夠理想。 擴散和混淆成功地實現(xiàn)了分組密碼的本質屬性，因而成為設計現(xiàn)代分組密碼的基礎。,很多分組密碼的結構

11、從本質上說都是基于一個稱為Feistel網(wǎng)絡的結構。Feistel提出利用乘積密碼可獲得簡單的代換密碼，乘積密碼指順序地執(zhí)行兩個或多個基本密碼系統(tǒng)，使得最后結果的密碼強度高于每個基本密碼系統(tǒng)產(chǎn)生的結果，F(xiàn)eistel還提出了實現(xiàn)代換和置換的方法。其思想實際上是Shannon提出的利用乘積密碼實現(xiàn)混淆和擴散思想的具體應用。,3.1.3 Feistel密碼結構,1. Feistel加密結構 圖3.3是Feistel網(wǎng)絡示意圖，加密算法的輸入是分組長為2w的明文和一個密鑰K。將每組明文分成左右兩半L0和R0，在進行完n輪迭代后，左右兩半再合并到一起以產(chǎn)生密文分組。其第i輪迭代的輸入為前一輪輸出的函數(shù)

12、： 其中Ki是第i輪用的子密鑰，由加密密鑰K得到。一般地，各輪子密鑰彼此不同而且與K也不同。,圖3.3 Feistel網(wǎng)絡示意圖,Feistel網(wǎng)絡中每輪結構都相同，每輪中右半數(shù)據(jù)被作用于輪函數(shù)F后，再與左半數(shù)據(jù)進行異或運算，這一過程就是上面介紹的代換。每輪的輪函數(shù)的結構都相同，但以不同的子密鑰Ki作為參數(shù)。代換過程完成后，再交換左、右兩半數(shù)據(jù)，這一過程稱為置換。這種結構是Shannon提出的代換置換網(wǎng)絡（substitution-permutation network, SPN）的特有形式。,Feistel網(wǎng)絡的實現(xiàn)與以下參數(shù)和特性有關： 分組大小分組越大則安全性越高，但加密速度就越慢。分組

13、密碼設計中最為普遍使用的分組大小是64比特。 密鑰大小密鑰越長則安全性越高，但加密速度就越慢?，F(xiàn)在普遍認為64比特或更短的密鑰長度是不安全的，通常使用128比特的密鑰長度。 輪數(shù)單輪結構遠不足以保證安全性，但多輪結構可提供足夠的安全性。典型地，輪數(shù)取為16。 子密鑰產(chǎn)生算法該算法的復雜性越大，則密碼分析的困難性就越大。 輪函數(shù)輪函數(shù)的復雜性越大，密碼分析的困難性也越大。,在設計Feistel網(wǎng)絡時，還有以下兩個方面需要考慮： 快速的軟件實現(xiàn)在很多情況中，算法是被鑲嵌在應用程序中，因而無法用硬件實現(xiàn)。此時算法的執(zhí)行速度是考慮的關鍵。 算法容易分析如果算法能被無疑義地解釋清楚，就可容易地分析算法抵

14、抗攻擊的能力，有助于設計高強度的算法。,2. Feistel解密結構 Feistel解密過程本質上和加密過程是一樣的，算法使用密文作為輸入，但使用子密鑰Ki的次序與加密過程相反，即第1輪使用Kn，第2輪使用Kn-1，最后一輪使用K1。這一特性保證了解密和加密可采用同一算法。,圖3.4的左邊表示16輪Feistel網(wǎng)絡的加密過程，右邊表示解密過程，加密過程由上而下，解密過程由下而上。為清楚起見，加密算法每輪的左右兩半用LEi和REi表示，解密算法每輪的左右兩半用LDi和RDi表示。圖中右邊標出了解密過程中每一輪的中間值與左邊加密過程中間值的對應關系，即加密過程第i輪的輸出是LEiREi（表示鏈接

15、），解密過程第16-i輪相應的輸入是RDiLDi。,圖3.4 Feistel加解密過程,加密過程的最后一輪執(zhí)行完后，兩半輸出再經(jīng)交換，因此密文是RE16LE16。解密過程取以上密文作為同一算法的輸入，即第1輪輸入是RE16LE16，等于加密過程第16輪兩半輸出交換后的結果。下面證明解密過程第1輪的輸出等于加密過程第16輪輸入左右兩半的交換值。,在加密過程中： 在解密過程中,所以解密過程第1輪的輸出為LE15RE15，等于加密過程第16輪輸入左右兩半交換后的結果。容易證明這種對應關系在16輪中每輪都成立。一般地，加密過程的第i輪有 因此,以上兩式描述了加密過程中第i輪的輸入與第i輪輸出的函數(shù)關系

16、，由此關系可得圖3.4右邊顯示的LDi和RDi的取值關系。 最后可以看到，解密過程第16輪的輸出是RE0LE0，左右兩半再經(jīng)一次交換后即得最初的明文。,數(shù)據(jù)加密標準（data encryption standard, DES）是迄今為止世界上最為廣泛使用和流行的一種分組密碼算法，它的分組長度為64比特，密鑰長度為56比特，它是由美國IBM公司研制的，是早期的稱作Lucifer密碼的一種發(fā)展和修改。DES在1975年3月17日首次被公布在聯(lián)邦記錄中，經(jīng)過大量的公開討論后，DES于1977年1月15日被正式批準并作為美國聯(lián)邦信息處理標準，即FIPS-46，同年7月15日開始生效。規(guī)定每隔5年由美國

17、國家保密局（national security agency, NSA）作出評估，并重新批準它是否繼續(xù)作為聯(lián)邦加密標準。,3.2 數(shù)據(jù)加密標準,最近的一次評估是在1994年1月，美國已決定1998年12月以后將不再使用DES。1997年DESCHALL小組經(jīng)過近4個月的努力，通過Internet搜索了31016個密鑰，找出了DES的密鑰，恢復出了明文。1998年5月美國EFF(electronics frontier foundation)宣布，他們以一臺價值20萬美元的計算機改裝成的專用解密機，用56小時破譯了56 比特密鑰的DES。美國國家標準和技術協(xié)會已征集并進行了幾輪評估、篩選，產(chǎn)生了

18、稱之為AES(advanced encryption standard) 的新加密標準。盡管如此，DES對于推動密碼理論的發(fā)展和應用畢竟起了重大作用，對于掌握分組密碼的基本理論、設計思想和實際應用仍然有著重要的參考價值，下面首先來描述這一算法。,圖3.5是DES加密算法的框圖，其中明文分組長為64比特，密鑰長為56比特。圖的左邊是明文的處理過程，有3個階段，首先是一個初始置換IP，用于重排明文分組的64比特數(shù)據(jù)。然后是具有相同功能的16輪變換，每輪中都有置換和代換運算，第16輪變換的輸出分為左右兩半，并被交換次序。最后再經(jīng)過一個逆初始置換IP-1（為IP的逆）從而產(chǎn)生64比特的密文。除初始置換

19、和逆初始置換外，DES的結構和圖3.3所示的Feistel密碼結構完全相同。,3.2.1 DES描述,圖3.5 DES加密算法框圖,圖3.5的右邊是使用56比特密鑰的方法。密鑰首先通過一個置換函數(shù)，然后，對加密過程的每一輪，通過一個左循環(huán)移位和一個置換產(chǎn)生一個子密鑰。其中每輪的置換都相同，但由于密鑰被重復迭代，所以產(chǎn)生的每輪子密鑰不相同。,1. 初始置換 DES的置換表見表3.2。（見40頁表3.2） 表3.2(a)和表3.2(b)分別給出了初始置換和逆初始置換的定義，為了顯示這兩個置換的確是彼此互逆的，考慮下面64比特的輸入M ：,M1 M2 M3 M4 M5 M6 M7 M8 M9 M10

20、 M11 M12 M13 M14 M15 M16 M17 M18 M19 M20 M21 M22 M23 M24 M25 M26 M27 M28 M29 M30 M31 M32 M33 M34 M35 M36 M37 M38 M39 M40 M41 M42 M43 M44 M45 M46 M47 M48 M49 M50 M51 M52 M53 M54 M55 M56 M57 M58 M59 M60 M61 M62 M63 M64,其中Mi是二元數(shù)字。由表3.2(a)得X=IP(M)為： M58 M50 M42 M34 M26 M18 M10 M2 M60 M52 M44 M36 M28 M20

21、 M12 M4 M62 M54 M46 M38 M30 M22 M14 M6 M64 M56 M48 M40 M32 M24 M16 M8 M57 M49 M41 M33 M25 M17 M9 M1 M59 M51 M43 M35 M27 M19 M11 M3 M61 M53 M45 M37 M29 M21 M13 M5 M63 M55 M47 M39 M31 M23 M15 M7,如果再取逆初始置換Y=IP-1(X)=IP-1(IP(M)，可以看出，M各位的初始順序將被恢復。,2. 輪結構 圖3.6是DES加密算法的輪結構。,圖3.6 DES加密算法的輪結構,首先看圖的左半部分。將64比特的

22、輪輸入分成各為32比特的左、右兩半，分別記為L和R。和Feistel網(wǎng)絡一樣，每輪變換可由以下公式表示：,其中輪密鑰Ki為48比特，函數(shù)F(R,K)的計算過程如圖3.7所示。輪輸入的右半部分R為32比特，R首先被擴展成48比特，擴展過程由表3.2(c)定義，其中將R的16個比特各重復一次。擴展后的48比特再與子密鑰Ki異或，然后再通過一個S盒，產(chǎn)生32比特的輸出。該輸出再經(jīng)過一個由表3.2(d)定義的置換，產(chǎn)生的結果即為函數(shù)F(R,K)的輸出。,圖3.7 函數(shù)F(R,K)的計算過程,F中的代換由8個S盒組成，每個S盒的輸入長為6比特、輸出長為4比特，其變換關系由表3.3定義，每個S盒給出了4個

23、代換（由一個表的4行給出）。（見42頁表3.3）,對每個盒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盒的每一行定義了一個可逆代換，圖3.2（在3.1.1節(jié)）表示S1第0行所定義的代換。,3. 密鑰的產(chǎn)生 再看圖3.5和圖3.6，輸入算法的56比特密鑰首先經(jīng)過一

24、個置換運算，該置換由表3.4(a)給出，然后將置換后的56比特分為各為28比特的左、右兩半，分別記為C0和D0。在第i 輪分別對Ci-1和Di-1進行左循環(huán)移位，所移位數(shù)由表3.4(c)給出。移位后的結果作為求下一輪子密鑰的輸入，同時也作為置換選擇2的輸入。通過置換選擇2產(chǎn)生的48比特的Ki，即為本輪的子密鑰，作為函數(shù)F(Ri-1,Ki)的輸入。其中置換選擇2由表3.4(b)定義。（見44頁表3.4）,4. 解密 和Feistel密碼一樣，DES的解密和加密使用同一算法，但子密鑰使用的順序相反。,為了提高DES的安全性，并利用實現(xiàn)DES的現(xiàn)有軟硬件，可將DES算法在多密鑰下多重使用。 二重DE

25、S是多重使用DES時最簡單的形式，如圖3.8所示。其中明文為P，兩個加密密鑰為K1和K2，密文為： 解密時，以相反順序使用兩個密鑰：,3.2.2 二重DES,圖3.8 二重DES,因此，二重DES所用密鑰長度為112比特，強度極大地增加。然而，假設對任意兩個密鑰K1和K2，能夠找出另一密鑰K3，使得,那么，二重DES以及多重DES都沒有意義，因為它們與56比特密鑰的單重DES等價，好在這種假設對DES并不成立。將DES加密過程64比特分組到64比特分組的映射看作一個置換，如果考慮264個所有可能的輸入分組，則密鑰給定后，DES的加密將把每個輸入分組映射到一個惟一的輸出分組。否則，如果有兩個輸入

26、分組被映射到同一分組，則解密過程就無法實施。對264個輸入分組，總映射個數(shù)為 。,另一方面，對每個不同的密鑰，DES都定義了一個映射，總映射數(shù)為2561017。 因此，可假定用兩個不同的密鑰兩次使用DES，可得一個新映射，而且這一新映射不出現(xiàn)在單重DES定義的映射中。這一假定已于1992年被證明。所以使用二重DES產(chǎn)生的映射不會等價于單重DES加密。但對二重DES有以下一種稱為中途相遇攻擊的攻擊方案，這種攻擊不依賴于DES的任何特性，因而可用于攻擊任何分組密碼。其基本思想如下：,如果有 那么（見圖3.8）,如果已知一個明文密文對(P,C)，攻擊的實施可如下進行：首先，用256個所有可能的K1對

27、P加密，將加密結果存入一表并對表按X排序，然后用256個所有可能的K2對C解密，在上述表中查找與C解密結果相匹配的項，如果找到，則記下相應的K1和K2。最后再用一新的明文密文對(P,C)檢驗上面找到的K1和K2，用K1和K2對P兩次加密，若結果等于C，就可確定K1和K2是所要找的密鑰。,對已知的明文P，二重DES能產(chǎn)生264個可能的密文,而可能的密鑰個數(shù)為2112，所以平均來說，對一個已知的明文，有2112/264=248個密鑰可產(chǎn)生已知的密文。而再經(jīng)過另外一對明文密文的檢驗，誤報率將下降到248-64=2-16。所以在實施中途相遇攻擊時，如果已知兩個明文密文對，則找到正確密鑰的概率為1-2-

28、16。,抵抗中途相遇攻擊的一種方法是使用3個不同的密鑰做3次加密，從而可使已知明文攻擊的代價增加到2112。然而，這樣又會使密鑰長度增加到563=168比特，因而過于笨重。一種實用的方法是僅使用兩個密鑰做3次加密，實現(xiàn)方式為加密|解密|加密，簡記為EDE( encryptdecryptencrypt)，見圖3.9，即：,3.2.3 兩個密鑰的三重DES,圖3.9 兩個密鑰的三重DES,此方案已在密鑰管理標準ANS X.917和ISO 8732中被采用。,三個密鑰的三重DES密鑰長度為168比特，加密方式為 令K3=K2或K1=K2，則變?yōu)橐恢谼ES。 三個密鑰的三重DES已在因特網(wǎng)的許多應用（

29、如PGP和S/MIME）中被采用。,3.2.4 三個密鑰的三重DES,差分密碼分析是迄今已知的攻擊迭代密碼最有效的方法之一，其基本思想是： 通過分析明文對的差值對密文對的差值的影響來恢復某些密鑰比特。,3.3 差分密碼分析與線性密碼分析 3.3.1 差分密碼分析,對分組長度為n的r輪迭代密碼，兩個n比特串Yi和Y*i的差分定義為 其中表示n比特串集上的一個特定群運算， 表示 在此群中的逆元。 由加密對可得差分序列 Y0,Y1,Yr 其中Y0和Y*0是明文對，Yi和Y*i(1ir)是第i輪的輸出，它們同時也是第i+1輪的輸入。第i輪的子密鑰記為Ki，F(xiàn)是輪函數(shù)，且Yi=F(Yi-1,Ki)。,定

30、義3.1 r-輪特征(r-round characteristic) 是一個差分序列： 0,1,r 其中0是明文對Y0和Y*0的差分，i(1ir)是第i輪輸出Yi和Y*i的差分。r-輪特征=0,1,r的概率是指在明文Y0和子密鑰K1,Kr獨立、均勻隨機時，明文對Y0和Y*0的差分為0的條件下，第i(1ir)輪輸出Yi和Y*i的差分為i的概率。,定義3.2 在r-輪特征=0,1,r中，定義 =P(F(Y)=i|Y=i-1) 即 表示在輸入差分為i-1的條件下，輪函數(shù)F的輸出差分為i的概率。 r-輪特征=0,1,r的概率近似看作 。,對r-輪迭代密碼的差分密碼分析過程可綜述為如下的步驟： 找出一個

31、(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(1j2m)，設置相應的2m個計數(shù)器j(1j2m)；用每個Kjr解密密文Yr和Y*r，得到Yr-1和Y*r-1，如果Yr-1和Y*r-1的差分是r-1，則給相應的計數(shù)器j加1。, 重復步驟，直到一個或幾個計數(shù)器的值明顯高于其他計數(shù)器的值，輸出它們所對應的子密鑰（或部分比特）。,一種攻擊的復雜度可以分為兩部分： 數(shù)據(jù)復雜度和處理復雜度。數(shù)

32、據(jù)復雜度是實施該攻擊所需輸入的數(shù)據(jù)量；而處理復雜度是處理這些數(shù)據(jù)所需的計算量。這兩部分的主要部分通常被用來刻畫該攻擊的復雜度。,差分密碼分析的數(shù)據(jù)復雜度是成對加密所需的選擇明文對(Y0,Y*0)個數(shù)的兩倍。差分密碼分析的處理復雜度是從(Yr-1,Yr,Y*r)找出子密鑰Kr（或Kr的部分比特）的計算量，它實際上與r無關，而且由于輪函數(shù)是弱的，所以此計算量在大多數(shù)情況下相對較小。因此，差分密碼分析的復雜度取決于它的數(shù)據(jù)復雜度。,線性密碼分析是對迭代密碼的一種已知明文攻擊，它利用的是密碼算法中的“不平衡（有效）的線性逼近”。 設明文分組長度和密文分組長度都為n比特，密鑰分組長度為m比特。記明文分組

33、為P1，P2，,Pn，密文分組為C1，C2，Cn，密鑰分組為K1，K2，Km。定義 。,3.3.2 線性密碼分析,線性密碼分析的目標就是找出以下形式的有效線性方程： 其中1an,1bn,1cm。 如果方程成立的概率p1/2，則稱該方程是有效的線性逼近。如果 是最大的，則稱該方程是最有效的線性逼近。,設N表示明文數(shù)，T是使方程左邊為0的明文數(shù)。如果TN/2，則令 如果TN/2，則令 從而可得關于密鑰比特的一個線性方程。對不同的明文密文對重復以上過程，可得關于密鑰的一組線性方程，從而確定出密鑰比特。,研究表明，當 充分小時，攻擊成功的概率是 這一概率只依賴于 ，并隨著N或 的增加而增加。,如何對差

34、分密碼分析和線性密碼分析進行改進，降低它們的復雜度仍是現(xiàn)在理論研究的熱點，目前已推出了很多改進方法，例如,高階差分密碼分析、截段差分密碼分析（truncated differential cryptanalysis）、不可能差分密碼分析、多重線性密碼分析、非線性密碼分析、劃分密碼分析和差分-線性密碼分析，再如針對密鑰編排算法的相關密鑰攻擊、基于Lagrange插值公式的插值攻擊及基于密碼器件的能量分析（power analysis），另外還有錯誤攻擊、時間攻擊、Square攻擊和Davies攻擊等。,分組密碼在加密時,明文分組的長度是固定的，而實際應用中待加密消息的數(shù)據(jù)量是不定的，數(shù)據(jù)格式可能

35、是多種多樣的。為了能在各種應用場合使用DES，美國在FIPS PUS 74和81中定義了DES的4種運行模式，如表3.5所示。這些模式也可用于其他分組密碼，下面以DES為例來介紹這4種模式。（見49頁表3.5）,3.4 分組密碼的運行模式,ECB(electronic codebook)模式是最簡單的運行模式，它一次對一個64比特長的明文分組加密，而且每次的加密密鑰都相同，如圖3.10所示。當密鑰取定時，對明文的每一個分組，都有一個惟一的密文與之對應。因此形象地說，可以認為有一個非常大的電碼本，對任意一個可能的明文分組，電碼本中都有一項對應于它的密文。,3.4.1 電碼本（ECB）模式,圖3.

36、10 ECB模式示意圖,如果消息長于64比特，則將其分為長為64比特的分組，最后一個分組如果不夠64比特，則需要填充。解密過程也是一次對一個分組解密，而且每次解密都使用同一密鑰。圖3.10中，明文是由分組長為64比特的分組序列P1，P2，PN構成，相應的密文分組序列是C1，C2，CN。,ECB在用于短數(shù)據(jù)（如加密密鑰）時非常理想，因此如果需要安全地傳遞DES密鑰，ECB是最合適的模式。 ECB的最大特性是同一明文分組在消息中重復出現(xiàn)的話，產(chǎn)生的密文分組也相同。 ECB用于長消息時可能不夠安全，如果消息有固定結構，密碼分析者有可能找出這種關系。例如，如果已知消息總是以某個預定義字段開始，那么分析

37、者就可能得到很多明文密文對。如果消息有重復的元素而重復的周期是64的倍數(shù)，那么密碼分析者就能夠識別這些元素。以上這些特性都有助于密碼分析者，有可能為其提供對分組的代換或重排的機會。,為了解決ECB的安全缺陷，可以讓重復的明文分組產(chǎn)生不同的密文分組，CBC（cipher block chaining）模式就可滿足這一要求。 圖3.11是CBC模式示意圖，它一次對一個明文分組加密，每次加密使用同一密鑰,加密算法的輸入是當前明文分組和前一次密文分組的異或，因此加密算法的輸入不會顯示出與這次的明文分組之間的固定關系，所以重復的明文分組不會在密文中暴露出這種重復關系。,3.4.2 密碼分組鏈接（CBC）

38、模式,圖3.11 CBC模式示意圖,解密時，每一個密文分組被解密后，再與前一個密文分組異或，即 （設 ） 因而產(chǎn)生出明文分組。,在產(chǎn)生第1個密文分組時，需要有一個初始向量IV與第1個明文分組異或。解密時，IV和解密算法對第1個密文分組的輸出進行異或以恢復第1個明文分組。 IV對于收發(fā)雙方都應是已知的，為使安全性最高，IV應像密鑰一樣被保護，可使用ECB加密模式來發(fā)送IV。保護IV的原因如下： 如果敵手能欺騙接收方使用不同的IV值，敵手就能夠在明文的第1個分組中插入自己選擇的比特值，這是因為：,用X(i)表示64比特分組X的第i個比特，那么 ，由異或的性質得 其中撇號表示比特補。上式意味著如果敵

39、手篡改IV中的某些比特，則接收方收到的P1中相應的比特也發(fā)生了變化。,由于CBC 模式的鏈接機制，CBC模式對加密長于64比特的消息非常合適。 CBC模式除能夠獲得保密性外，還能用于認證。,如上所述，DES是分組長為64比特的分組密碼，但利用CFB（cipher feedback）模式或OFB模式可將DES轉換為流密碼。流密碼不需要對消息填充，而且運行是實時的。因此如果傳送字母流，可使用流密碼對每個字母直接加密并傳送。 流密碼具有密文和明文一樣長這一性質，因此，如果需要發(fā)送的每個字符長為8比特，就應使用8比特密鑰來加密每個字符。如果密鑰長超過8比特，則造成浪費。,3.4.3 密碼反饋（CFB）

40、模式,圖3.12是CFB模式示意圖，設傳送的每個單元（如一個字符）是j比特長，通常取j=8，與CBC模式一樣，明文單元被鏈接在一起，使得密文是前面所有明文的函數(shù)。,圖3.12 CFB模式示意圖,加密時，加密算法的輸入是64比特移位寄存器，其初值為某個初始向量IV。加密算法輸出的最左（最高有效位）j比特與明文的第一個單元P1進行異或，產(chǎn)生出密文的第1個單元C1，并傳送該單元。然后將移位寄存器的內容左移j位并將C1送入移位寄存器最右邊（最低有效位）j位。這一過程繼續(xù)到明文的所有單元都被加密為止。,解密時，將收到的密文單元與加密函數(shù)的輸出進行異或。注意這時仍然使用加密算法而不是解密算法，原因如下：

41、設Sj(X)是X的j個最高有效位，那么 因此 可證明以后各步也有類似的這種關系。 CFB模式除能獲得保密性外，還能用于認證。,OFB（output feedback）模式的結構類似于CFB，見圖3.13。不同之處如下：OFB模式是將加密算法的輸出反饋到移位寄存器，而CFB模式中是將密文單元反饋到移位寄存器。,3.4.4 輸出反饋(OFB)模式,圖3.13 OFB模式示意圖,OFB（output feedback）模式的結構類似于CFB，見圖3.13。不同之處如下：OFB模式是將加密算法的輸出反饋到移位寄存器，而CFB模式中是將密文單元反饋到移位寄存器。,OFB模式的優(yōu)點是傳輸過程中的比特錯誤不

42、會被傳播。例如C1中出現(xiàn)1比特錯誤，在解密結果中只有P1受到影響，以后各明文單元則不受影響。而在CFB中，C1也作為移位寄存器的輸入，因此它的1比特錯誤會影響解密結果中各明文單元的值。,OFB的缺點是它比CFB模式更易受到對消息流的篡改攻擊，比如在密文中取1比特的補，那么在恢復的明文中相應位置的比特也為原比特的補。因此使得敵手有可能通過對消息校驗部分的篡改和對數(shù)據(jù)部分的篡改，而以糾錯碼不能檢測的方式篡改密文。,瑞士聯(lián)邦技術學院來學嘉（X. J. Lai）和J. L. Massey提出的第1版IDEA（international data encryption algorithm，國際數(shù)據(jù)加密算

43、法）于1990年公布，當時稱為PES（proposed encryption standard，建議加密標準）。1991年，在Biham和Shamir提出差分密碼分析之后，設計者推出了改進算法IPES，即改進型建議加密標準。1992年，設計者又將IPES改名為IDEA。這是近年來提出的各種分組密碼中一個很成功的方案，已在PGP中采用。,3.5 IDEA,算法中明文和密文分組長度都是64比特，密鑰長128比特。其設計原理可從強度和實現(xiàn)兩方面考慮。 1. 密碼強度 算法的強度主要是通過有效的混淆和擴散特性而得以保證。,3.5.1 設計原理,混淆是通過使用以下3種運算而獲得，3種運算都有兩個16比特

44、的輸入和一個16比特的輸出： 逐比特異或，表示為。 模216（即65536）整數(shù)加法，表示為，其輸入和輸出作為16位無符號整數(shù)處理。 模216+1（即65537）整數(shù)乘法，表示為，其輸入、輸出中除16位全為0作為216處理外，其余都作為16位無符號整數(shù)處理。例如 00000000000000001000000000000000=1000000000000001 這是因為216215 mod (216+1)=215+1。,表3.6給出了操作數(shù)為2比特長時3種運算的運算表。在以下意義下，3種運算是不兼容的：（見55頁表3.6） 3種運算中任意兩種都不滿足分配律，例如 a + （b c）(a + b

45、 ) (a + c ) 3種運算中任意兩種都不滿足結合律，例如 a +（b c）(a + b ) c,+,3種運算結合起來使用可對算法的輸入提供復雜的變換，從而使得對IDEA的密碼分析比對僅使用異或運算的DES更為困難。 算法中擴散是由稱為乘加（multiplication/addition, MA）結構（見圖3.14）的基本單元實現(xiàn)的。該結構的輸入是兩個16比特的子段和兩個16比特的子密鑰，輸出也為兩個16比特的子段。這一結構在算法中重復使用了8次，獲得了非常有效的擴散效果。,圖3.14 MA結構,2. 實現(xiàn) IDEA可方便地通過軟件和硬件實現(xiàn)。 軟件軟件實現(xiàn)采用16比特子段處理，可通過使用

46、容易編程的加法、移位等運算實現(xiàn)算法的3種運算。 硬件由于加、解密相似，差別僅為使用密鑰的方式，因此可用同一器件實現(xiàn)。再者，算法中規(guī)則的模塊結構，可方便VLSI的實現(xiàn)。,加密過程（如圖3.15所示）由連續(xù)的8輪迭代和一個輸出變換組成，算法將64比特的明文分組分成4個16比特的子段，每輪迭代以4個16比特的子段作為輸入，輸出也為4個16比特的子段。最后的輸出變換也產(chǎn)生4個16比特的子段，鏈接起來后形成64比特的密文分組。每輪迭代還需使用6個16比特的子密鑰，最后的輸出變換需使用4個16比特的子密鑰，所以子密鑰總數(shù)為52。圖3.15的右半部分表示由初始的128比特密鑰產(chǎn)生52個子密鑰的子密鑰產(chǎn)生器。

47、,3.5.2 加密過程,圖3.15 IDEA的加密框圖,1. 輪結構 圖3.16是IDEA第1輪的結構示意圖，以后各輪也都是這種結構，但所用的子密鑰和輪輸入不同。從結構圖可見，IDEA不是傳統(tǒng)的Feistel密碼結構。每輪開始時有一個變換，該變換的輸入是4個子段和4個子密鑰，變換中的運算是兩個乘法和兩個加法，輸出的4個子段經(jīng)過異或運算形成了兩個16比特的子段作為MA結構的輸入。MA結構也有兩個輸入的子密鑰，輸出是兩個16比特的子段。,圖3.16 IDEA第1輪的輪結構,最后，變換的4個輸出子段和MA結構的兩個輸出子段經(jīng)過異或運算產(chǎn)生這一輪的4個輸出子段。注意，由X2產(chǎn)生的輸出子段和由X3產(chǎn)生的

48、輸出子段交換位置后形成W12和W13，目的在于進一步增加混淆效果，使得算法更易抵抗差分密碼分析。,算法的第9步是一個輸出變換，如圖3.17所示。它的結構和每一輪開始的變換結構一樣，不同之處在于輸出變換的第2個和第3個輸入首先交換了位置，目的在于撤銷第8輪輸出中兩個子段的交換。還需注意，第9步僅需4個子密鑰，而前面8輪中每輪需要6個子密鑰。,圖3.17 IDEA的輸出變換,2. 子密鑰的產(chǎn)生 加密過程中52個16比特的子密鑰是由128比特的加密密鑰按如下方式產(chǎn)生的： 前8個子密鑰Z1，Z2，Z8直接從加密密鑰中取，即Z1取前16比特（最高有效位），Z2取下面的16比特，依次類推。然后加密密鑰循環(huán)

49、左移25位，再取下面8個子密鑰Z9，Z10，Z16，取法與Z1，Z2，Z8的取法相同。這一過程重復下去，直到52子密鑰都被產(chǎn)生為止。,3. 解密過程 解密過程和加密過程基本相同，但子密鑰的選取不同。解密子密鑰U1，U2，U52是由加密子密鑰按如下方式得到（將加密過程最后一步的輸出變換當作第9輪）：, 第i(i=1,9)輪解密的前4個子密鑰由加密過程第(10-i)輪的前4個子密鑰得出：其中第1和第4個解密子密鑰取為相應的第1和第4個加密子密鑰的模216+1乘法逆元，第2和第3個子密鑰的取法為： 當輪數(shù)i=2,8時，取為相應的第3個和第2個加密子密鑰的模216加法逆元。i=1和9時，取為相應的第2

50、個和第3個加密子密鑰的模216加法逆元。 第i(i=1,8)輪解密的后兩個子密鑰等于加密過程第(9-i)輪的后兩個子密鑰。,表3.7是對以上關系的總結。其中Zj的模216+1乘法逆元為Z-1j，滿足（見58頁表3.7） ZjZ-1j=1mod(216+1) 因216+1是一素數(shù)，所以每一個不大于216的非0整數(shù)都有一個惟一的模216+1乘法逆元。Zj的模216加法逆元為-Zj，滿足： -Zj + Zj=0 mod (216),下面驗證解密過程的確可以得到正確的結果。圖3.18中左邊為加密過程，由上至下，右邊為解密過程，由下至上。將每一輪進一步分為兩步，第1步是變換，其余部分作為第2步，稱為子加

51、密。,圖3.18 IDEA加密和解密框圖,現(xiàn)在從下往上考慮。對加密過程的最后一個輸出變換，以下關系成立： Y1=W81 Z49 Y2=W83 + Z50 Y3=W82 + Z51 Y4=W84Z52 解密過程中第1輪的第1步產(chǎn)生以下關系： J11=Y1U1 J12=Y2 + U2 J13=Y3 + U3 J14=Y4U4,將解密子密鑰由加密子密鑰表達并將Y1，Y2，Y3,，Y4代入以下關系，有 J11=Y1Z-149= W81Z49Z-149= W81 J12=Y2 + -Z50=W83 + Z50 + -Z50=W83 J13=Y3 + -Z51=W82 + Z51 + -Z51=W82 J

52、14=Y4Z-152= W84Z52Z-152= W84,可見解密過程第1輪第1步的輸出等于加密過程最后一步輸入中第2個子段和第3個子段交換后的值。從圖3.16，可得以下關系： W81=I81MAR(I81I83，I82I84) W82=I83MAR(I81I83，I82I84) W83=I82MAL(I81I83，I82I84) W84=I84MAL(I81I83，I82I84),其中MAR(X,Y)是MA結構輸入為X和Y時的右邊輸出，MAL(X,Y)是左邊輸出。則 V11=J11MAR(J11J13,J12J14) =W81MAR(W81W82,W83W84) =I81MAR(I81I83

53、,I82I84) MAR I81MAR(I81I83,I82I84)I83 MAR(I81 I83,I82I84), I82 MAL(I81I83,I82I84) I84 MAL(I81I83,I82I84) =I81MAR(I81I83,I82I84) MAR(I81I83,I82I84) =I81,類似地，可有 V12=I83 V13=I82 V14=I84 所以解密過程第1輪第2步的輸出等于加密過程倒數(shù)第2步輸入中第2個子段和第3個子段交換后的值。 同理可證圖3.18中每步都有上述類似關系，這種關系一直到 V81=I11 V82=I13 V83=I12 V84=I14 即除第2個子段和第

54、3個子段交換位置外，解密過程的輸出變換與加密過程第1輪第1步的變換完全相同。,即除第2個子段和第3個子段交換位置外，解密過程的輸出變換與加密過程第1輪第1步的變換完全相同。 所以最后可得知，整個解密過程的輸出等于整個加密過程的輸入。,1997年4月15日，美國ANSI發(fā)起征集AES（advanced encryption standard）的活動，并為此成立了AES工作小組。此次活動的目的是確定一個非保密的、可以公開技術細節(jié)的、全球免費使用的分組密碼算法，以作為新的數(shù)據(jù)加密標準。1997年9月12日，美國聯(lián)邦登記處公布了正式征集AES候選算法的通告。對AES的基本要求是： 比三重DES快、至少

55、與三重DES一樣安全、數(shù)據(jù)分組長度為128比特、密鑰長度為128/192/256比特。,3.6 AES算法Rijndael,1998年8月12日，在首屆AES候選會議（first AES candidate conference）上公布了AES的15個候選算法，任由全世界各機構和個人攻擊和評論，這15個候選算法是CAST256、CRYPTON、E2、DEAL、FROG、SAFER+、RC6、MAGENTA、LOKI97、SERPENT、MARS、Rijndael、DFC、Twofish、HPC。1999年3月，在第2屆AES候選會議（second AES candidate conferenc

56、e）上經(jīng)過對全球各密碼機構和個人對候選算法分析結果的討論，從15個候選算法中選出了5個。,這5個是RC6、Rijndael、SERPENT、Twofish和MARS。2000年4月13日至14日，召開了第3屆AES候選會議（third AES candidate conference），繼續(xù)對最后5個候選算法進行討論。2000年10月2日，NIST宣布Rijndael作為新的AES。至此，經(jīng)過3年多的討論，Rijndael終于脫穎而出。,Rijndael 由比利時的Joan Daemen和Vincent Rijmen設計，算法的原型是Square算法，它的設計策略是寬軌跡策略（wide tra

57、il strategy）。寬軌跡策略是針對差分分析和線性分析提出的，它的最大優(yōu)點是可以給出算法的最佳差分特征的概率及最佳線性逼近的偏差的界；由此，可以分析算法抵抗差分密碼分析及線性密碼分析的能力。,1. 有限域GF(28) 有限域中的元素可以用多種不同的方式表示。對于任意素數(shù)的方冪，都有惟一的一個有限域，因此GF(28)的所有表示是同構的，但不同的表示方法會影響到GF(28)上運算的復雜度，本算法采用傳統(tǒng)的多項式表示法。,3.6.1 Rijndael的數(shù)學基礎和設計思想,將b7b6b5b4b3b2b1b0構成的字節(jié)b看成系數(shù)在0,1中的多項式 b7x7+b6x6+b5x5+b4x4+b3x3+

58、b2x2+b1x+b0 例如： 十六進制數(shù)57對應的二進制為01010111，看成一個字節(jié)，對應的多項式為x6+x4+x2+x+1。,在多項式表示中，GF(28)上兩個元素的和仍然是一個次數(shù)不超過7的多項式，其系數(shù)等于兩個元素對應系數(shù)的模2加（比特異或）。 例如： 57+83=D4，用多項式表示為 (x6+x4+x2+x+1)+(x7+x+1)=x7+x6+ x4+ x2 (mod m(x) 用二進制表示為 01010111+10000011=11010100 由于每個元素的加法逆元等于自己，所以減法和加法相同。,要計算GF(28)上的乘法，必須先確定一個GF(2)上的8次不可約多項式；GF(

59、28)上兩個元素的乘積就是這兩個多項式的模乘（以這個8次不可約多項式為模）。在Rijndael密碼中，這個8次不可約多項式確定為 m(x)= x8+x4+x3+x+1 它的十六進制表示為11B。 例如，5783=C1可表示為以下的多項式乘法： (x6+x4+x2+x+1)(x7+x+1)=x7+x6+1(mod m(x) 乘法運算雖然不是標準的按字節(jié)的運算，但也是比較簡單的計算部件。,以上定義的乘法滿足交換律，且有單位元01。另外，對任何次數(shù)小于8的多項式b(x)，可用推廣的歐幾里得算法得 b(x)a(x)+m(x)c(x)=1 即a(x)b(x)=1 mod m(x)，因此a(x)是b(x)的乘法逆元。再者，乘法還滿足分配律： a(x)(b(x)+c(x)= a(x)b(x)+a(x)c(x) 所以，256個字節(jié)值構成的集合，在以上定義的加法和乘法運算下，有有限域GF(28)的結構。,GF(28)上還定義了一個運算，稱之為x乘法，其定義為 xb(x)= b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0 x(mod m(x) 如果b7=0，求模結果