第3章-分組密碼體制(new)

1、第第3章章 分組密碼體制分組密碼體制3.1 分組密碼概述分組密碼概述3.2 數(shù)據加密標準數(shù)據加密標準3.3 差分密碼分析與線性密碼分析差分密碼分析與線性密碼分析3.4 分組密碼的運行模式分組密碼的運行模式3.5 IDEA3.6 AES算法算法Rijndael習題習題x=(x0,x1,xn-1)，密鑰密鑰k=(k0,k1,kt-1) 加密函數(shù)加密函數(shù)E：VnKVm，K為密鑰空間為密鑰空間輸出數(shù)字序列輸出數(shù)字序列y=(y0,y1,ym-1)（長為長為m的矢量）的矢量）如圖如圖3.1所示。所示。3.1分組密碼概述分組密碼概述圖圖3.1 分組密碼框圖分組密碼框圖分組密碼實質上是字長為分組密碼實質上是字

2、長為n的數(shù)字序列的的數(shù)字序列的代換密碼代換密碼。與流密碼比較：與流密碼比較： 與一組長為與一組長為n的明文數(shù)字有關。的明文數(shù)字有關。 在相同密鑰下，對長為在相同密鑰下，對長為n的輸入明文組所實施的變換是的輸入明文組所實施的變換是等同的，所以只需研究對任一組明文數(shù)字的變換規(guī)則。等同的，所以只需研究對任一組明文數(shù)字的變換規(guī)則。用途：用途： 易于構造易于構造偽隨機數(shù)生成器、流密碼、消息認證碼偽隨機數(shù)生成器、流密碼、消息認證碼（MAC）和雜湊函數(shù)和雜湊函數(shù)等，等， 消息認證技術、數(shù)據完整性機制、實體認證協(xié)議消息認證技術、數(shù)據完整性機制、實體認證協(xié)議以及以及單鑰數(shù)字簽字體制單鑰數(shù)字簽字體制的核心組成部分

3、。的核心組成部分。對分組密碼的要求：對分組密碼的要求： 安全性安全性、運行速度、存儲量（程序的長度、數(shù)據分組運行速度、存儲量（程序的長度、數(shù)據分組長度、高速緩存大?。崿F(xiàn)平臺（硬件、軟件、芯片）、長度、高速緩存大?。?、實現(xiàn)平臺（硬件、軟件、芯片）、運行模式運行模式等。等。 需要與安全性要求之間進行適當?shù)恼壑羞x擇。需要與安全性要求之間進行適當?shù)恼壑羞x擇。通常取通常取m=n。若若mn，則為有數(shù)據擴展的分組密碼；則為有數(shù)據擴展的分組密碼；若若mn，則為有數(shù)據壓縮的分組密碼。則為有數(shù)據壓縮的分組密碼。在二元情況下，在二元情況下，x和和y均為二元數(shù)字序列，它們的每個分量均為二元數(shù)字序列，它們的每個分量

4、xi，yiGF(2)。設計的算法應滿足下述要求：設計的算法應滿足下述要求： 分組長度分組長度n要足夠大。要足夠大。 使分組代換字母表中的元素個數(shù)使分組代換字母表中的元素個數(shù)2n足夠大，防止明文足夠大，防止明文窮舉攻擊法奏效。窮舉攻擊法奏效。 DES、IDEA、FEAL和和LOKI等等: n=64 密鑰量要足夠大。密鑰量要足夠大。 盡可能消除弱密鑰并使所有密鑰同等地好，以防止密盡可能消除弱密鑰并使所有密鑰同等地好，以防止密鑰窮舉攻擊奏效。但密鑰又不能過長，以便于密鑰的管理。鑰窮舉攻擊奏效。但密鑰又不能過長，以便于密鑰的管理。 DES采用采用56比特密鑰，看來太短了比特密鑰，看來太短了IDEA采用

5、采用128比特密鑰比特密鑰 置換的算法要足夠復雜。置換的算法要足夠復雜。 充分實現(xiàn)明文與密鑰的擴散和混淆，沒有簡單的關系充分實現(xiàn)明文與密鑰的擴散和混淆，沒有簡單的關系可循，能抗擊各種已知的攻擊，如可循，能抗擊各種已知的攻擊，如差分攻擊差分攻擊和和線性攻擊線性攻擊； 有高的非線性階數(shù)，實現(xiàn)復雜的密碼變換；有高的非線性階數(shù)，實現(xiàn)復雜的密碼變換； 使對手破譯時除了用窮舉法外，無其它捷徑可循。使對手破譯時除了用窮舉法外，無其它捷徑可循。 加密和解密運算簡單，易于軟件和硬件高速實現(xiàn)。加密和解密運算簡單，易于軟件和硬件高速實現(xiàn)。 設計的算法采用規(guī)則的模塊結構，如多輪迭代等，以設計的算法采用規(guī)則的模塊結構，

6、如多輪迭代等，以便于軟件和便于軟件和VLSI快速實現(xiàn)；快速實現(xiàn)；差錯傳播和數(shù)據擴展要盡可能地小。差錯傳播和數(shù)據擴展要盡可能地小。 數(shù)據擴展。數(shù)據擴展。一般無數(shù)據擴展，在采用同態(tài)置換和隨機化加密技術一般無數(shù)據擴展，在采用同態(tài)置換和隨機化加密技術時可引入數(shù)據擴展。時可引入數(shù)據擴展。 差錯傳播盡可能地小。差錯傳播盡可能地小。設計分組密碼時的一些常用方法。設計分組密碼時的一些常用方法。代換代換、擴散和混淆擴散和混淆、Feistel密碼結構密碼結構變換是可逆的，稱明文分組到密文分組的可逆變換為代換。變換是可逆的，稱明文分組到密文分組的可逆變換為代換。不同可逆變換的個數(shù)有不同可逆變換的個數(shù)有2n!個。個。

7、圖圖3.2 n=4的代換密碼的一般結構的代換密碼的一般結構3.1.1 代換代換問題：問題：1) 分組長度太小，通過對明文的統(tǒng)計分析被攻破。分組長度太小，通過對明文的統(tǒng)計分析被攻破。2) 分組長度很大的可逆代換結構是不實際的。分組長度很大的可逆代換結構是不實際的。對對n比特的代換結構，密鑰的大小是比特的代換結構，密鑰的大小是n2n比特。如比特。如n=64，密鑰大小，密鑰大小: 64264=2701021比特，難以處理。比特，難以處理。將將n分成較小的段分成較小的段，例如可選，例如可選n=rn0，其中其中r和和n0都是正都是正整數(shù)，將設計整數(shù)，將設計n個變量的代換變?yōu)樵O計個變量的代換變?yōu)樵O計r個較

8、小的子代換，個較小的子代換，而每個子代換只有而每個子代換只有n0個輸入變量。個輸入變量。一般一般n0都不太大，稱每個子代換為代換盒，簡稱為都不太大，稱每個子代換為代換盒，簡稱為S盒。盒。Shannon提出的設計密碼系統(tǒng)的兩個基本方法提出的設計密碼系統(tǒng)的兩個基本方法目的目的:抗擊敵手對密碼系統(tǒng)的統(tǒng)計分析?？箵魯呈謱γ艽a系統(tǒng)的統(tǒng)計分析。在在Shannon稱之為理想密碼的密碼系統(tǒng)中，密文的所有稱之為理想密碼的密碼系統(tǒng)中，密文的所有統(tǒng)計特性都與所使用的密鑰獨立。統(tǒng)計特性都與所使用的密鑰獨立。圖圖3.2討論的代換密碼就是這樣的一個密碼系統(tǒng)，然而討論的代換密碼就是這樣的一個密碼系統(tǒng)，然而它是不實用的。它是

9、不實用的。3.1.2 擴散和混淆擴散和混淆擴散。擴散。將明文的統(tǒng)計特性散布到密文中去，密文中每一位將明文的統(tǒng)計特性散布到密文中去，密文中每一位均受明文中多位影響。均受明文中多位影響。目的：使明文和密文之間的統(tǒng)計關系變得盡可能復雜，以目的：使明文和密文之間的統(tǒng)計關系變得盡可能復雜，以使敵手無法得到密鑰。使敵手無法得到密鑰。如如明文的統(tǒng)計特性將被散布到密文中，每一字母在密文明文的統(tǒng)計特性將被散布到密文中，每一字母在密文中出現(xiàn)的頻率比在明文中出現(xiàn)的頻率更接近于相等，雙字中出現(xiàn)的頻率比在明文中出現(xiàn)的頻率更接近于相等，雙字母及多字母出現(xiàn)的頻率也更接近于相等。母及多字母出現(xiàn)的頻率也更接近于相等?？蓪?shù)據重

10、復執(zhí)行某個置換，再對這一置換作用于一可對數(shù)據重復執(zhí)行某個置換，再對這一置換作用于一函數(shù)，可獲得擴散。函數(shù)，可獲得擴散。1mod26knn iiychrord m混淆?；煜?。使密文和密鑰之間的統(tǒng)計關系變得盡可能復雜，以使密文和密鑰之間的統(tǒng)計關系變得盡可能復雜，以使敵手無法得到密鑰。使敵手無法得到密鑰。 使用復雜的代換算法可以得到預期的混淆效果，而簡使用復雜的代換算法可以得到預期的混淆效果，而簡單的線性代換函數(shù)得到的混淆效果則不夠理想。單的線性代換函數(shù)得到的混淆效果則不夠理想。擴散和混淆成功地實現(xiàn)了分組密碼的本質屬性，因而擴散和混淆成功地實現(xiàn)了分組密碼的本質屬性，因而成為設計現(xiàn)代分組密碼的基礎。成

11、為設計現(xiàn)代分組密碼的基礎。發(fā)明者發(fā)明者 Horst Feistel ，物理學家兼密碼學家，在他為，物理學家兼密碼學家，在他為 IBM 工作的時候，為工作的時候，為Feistel 密碼結構的研究奠定了基礎。密碼結構的研究奠定了基礎。 1973年首次踏上歷史舞臺。當時美國聯(lián)邦政府正試圖年首次踏上歷史舞臺。當時美國聯(lián)邦政府正試圖采用采用DES，于是便使用于是便使用Feistel 網絡作為網絡作為DES 的要素之一。的要素之一。思想：思想：利用乘積密碼可獲得簡單的代換密碼，乘積密利用乘積密碼可獲得簡單的代換密碼，乘積密碼指順序地執(zhí)行兩個或多個基本密碼系統(tǒng)，使得最后結果碼指順序地執(zhí)行兩個或多個基本密碼系

12、統(tǒng)，使得最后結果的密碼強度高于每個基本密碼系統(tǒng)。的密碼強度高于每個基本密碼系統(tǒng)。Shannon提出的利用乘積密碼實現(xiàn)混淆和擴散思想的提出的利用乘積密碼實現(xiàn)混淆和擴散思想的具體應用具體應用3.1.3 Feistel密碼結構密碼結構1.Feistel加密結構加密結構輸入：長為輸入：長為2w的明文，分成左右的明文，分成左右兩半兩半L0和和R0，一個密鑰一個密鑰K。在進行完在進行完n輪迭代后，左右兩半輪迭代后，左右兩半再合并到一起以產生密文分組。再合并到一起以產生密文分組。 第第i輪迭代的輸入為前一輪輸出的輪迭代的輸入為前一輪輸出的函數(shù)：函數(shù)：Ki：第：第i輪用的子密鑰，由加密密輪用的子密鑰，由加密密

13、鑰鑰K得到。得到。111,iiiiiiLRRLF RK圖圖3.3是是Feistel網絡示意圖網絡示意圖Feistel網絡中每輪結構都相同，每輪中右半數(shù)據被作用網絡中每輪結構都相同，每輪中右半數(shù)據被作用于輪函數(shù)于輪函數(shù)F后，再與左半數(shù)據進行異或運算，這一過程就是后，再與左半數(shù)據進行異或運算，這一過程就是上面介紹的代換。上面介紹的代換。每輪的輪函數(shù)的結構都相同，但以不同的子密鑰每輪的輪函數(shù)的結構都相同，但以不同的子密鑰Ki作作為參數(shù)。代換過程完成后，再交換左、右兩半數(shù)據，這一為參數(shù)。代換過程完成后，再交換左、右兩半數(shù)據，這一過程稱為置換。過程稱為置換。這種結構是這種結構是Shannon提出的代換提

14、出的代換置換網絡置換網絡（substitution -permutation network, SPN）的特有形式。的特有形式。Feistel網絡的實現(xiàn)與以下參數(shù)和特性有關：網絡的實現(xiàn)與以下參數(shù)和特性有關： 分組大小。分組大小。分組越大則安全性越高，但加密速度就越慢。分組越大則安全性越高，但加密速度就越慢。 最為普遍使用的分組大小是最為普遍使用的分組大小是64比特。比特。 密鑰大小。密鑰大小。密鑰越長則安全性越高，但加密速度就越慢。密鑰越長則安全性越高，但加密速度就越慢。現(xiàn)在普遍認為現(xiàn)在普遍認為64比特或更短的密鑰長度是不安全的，通常使比特或更短的密鑰長度是不安全的，通常使用用128比特的密鑰

15、長度。比特的密鑰長度。 輪數(shù)。輪數(shù)。單輪結構遠不足以保證安全性，但多輪結構可提供單輪結構遠不足以保證安全性，但多輪結構可提供足夠的安全性。典型地，輪數(shù)取為足夠的安全性。典型地，輪數(shù)取為16。 子密鑰產生算法。子密鑰產生算法。復雜性越大，密碼分析的困難性就越大。復雜性越大，密碼分析的困難性就越大。輪函數(shù)。輪函數(shù)。復雜性越大，密碼分析的困難性也越大。復雜性越大，密碼分析的困難性也越大。在設計在設計Feistel網絡時，還有以下兩個方面需要考慮：網絡時，還有以下兩個方面需要考慮： 快速的軟件實現(xiàn)?？焖俚能浖崿F(xiàn)。在很多情況中，算法是被鑲嵌在應用程序中，因而無在很多情況中，算法是被鑲嵌在應用程序中，因

16、而無法用硬件實現(xiàn)。此時算法的執(zhí)行速度是考慮的關鍵。法用硬件實現(xiàn)。此時算法的執(zhí)行速度是考慮的關鍵。 算法容易分析。算法容易分析。如果算法能被無疑義地解釋清楚，就可容易地分析算如果算法能被無疑義地解釋清楚，就可容易地分析算法抵抗攻擊的能力，有助于設計高強度的算法。法抵抗攻擊的能力，有助于設計高強度的算法。2. Feistel解密結構解密結構Feistel解密過程本質上和加密過程是一樣的，算法使用解密過程本質上和加密過程是一樣的，算法使用密文作為輸入，但使用子密鑰密文作為輸入，但使用子密鑰Ki的次序與加密過程相反，的次序與加密過程相反，即第即第1輪使用輪使用Kn，第第2輪使用輪使用Kn-1，最后一輪

17、使用最后一輪使用K1。這一特性保證了解密和加密可采用同一算法。這一特性保證了解密和加密可采用同一算法。 圖圖3.4 Feistel加解密過程加解密過程加密過程由上而下加密過程由上而下解密過程由下而上。解密過程由下而上。加密：加密：LEi和和Rei解密：解密：LDi和和RDi加密過程第加密過程第i輪的輸輪的輸出是出是LEiREi解密過程第解密過程第16-i輪相輪相應的輸入是應的輸入是RDiLDi加密過程的最后一輪執(zhí)行完后，兩半輸出再經交換，加密過程的最后一輪執(zhí)行完后，兩半輸出再經交換，因此密文是因此密文是RE16LE16。解密過程取以上密文作為同一算法的輸入，即第解密過程取以上密文作為同一算法的

18、輸入，即第1輪輸輪輸入是入是RE16LE16，等于加密過程第等于加密過程第16輪兩半輸出交換后的結輪兩半輸出交換后的結果。果。下面證明解密過程第下面證明解密過程第1輪的輸出等于加密過程第輪的輸出等于加密過程第16輪輸輪輸入左右兩半的交換值。入左右兩半的交換值。在加密過程中：在加密過程中：在解密過程中在解密過程中161516151516,LERERELEF REK10161510016161516151516151615,LDRDLERERDLDF RDKREF REKLEF REKF REKLE所以解密過程第所以解密過程第1輪的輸出為輪的輸出為LE15RE15，等于加密過程第等于加密過程第16

19、輪輸入左右兩半交換后的結果。輪輸入左右兩半交換后的結果。容易證明這種對應關系在容易證明這種對應關系在16輪中每輪都成立。輪中每輪都成立。一般地，加密過程的第一般地，加密過程的第i輪有輪有因此因此111,iiiiiiLERERELEF REK111,iiiiiiiiiRELELEREF REKREF LEK以上兩式描述了加密過程中第以上兩式描述了加密過程中第i輪的輸入與第輪的輸入與第i輪輸出的輪輸出的函數(shù)關系，由此關系可得圖函數(shù)關系，由此關系可得圖3.4右邊顯示的右邊顯示的LDi和和RDi的取值的取值關系。關系。最后可以看到，解密過程第最后可以看到，解密過程第16輪的輸出是輪的輸出是RE0LE0

20、，左右兩半再經一次交換后即得最初的明文。左右兩半再經一次交換后即得最初的明文。數(shù)據加密標準（數(shù)據加密標準（data encryption standard, DES）美國美國IBM公司研制，是早期公司研制，是早期Lucifer密碼的一種發(fā)展和修改密碼的一種發(fā)展和修改迄今為止世界上最為廣泛使用和流行的一種分組密碼算法分迄今為止世界上最為廣泛使用和流行的一種分組密碼算法分組長度為組長度為64比特，密鑰長度為比特，密鑰長度為56比特比特在在1975年年3月月17日首次被公布在聯(lián)邦記錄中，經過大量的公開日首次被公布在聯(lián)邦記錄中，經過大量的公開討論后，討論后，DES于于1977年年1月月15日被正式批準

21、并作為美國聯(lián)邦信息日被正式批準并作為美國聯(lián)邦信息處理標準，即處理標準，即FIPS-46，同年同年7月月15日開始生效。日開始生效。規(guī)定每隔規(guī)定每隔5年由美國國家保密局（年由美國國家保密局（national security agency, NSA）作出評估，并重新批準它是否繼續(xù)作為聯(lián)邦加密標準。作出評估，并重新批準它是否繼續(xù)作為聯(lián)邦加密標準。3.2 數(shù)據加密標準數(shù)據加密標準最近的一次評估是在最近的一次評估是在1994年年1月，美國已決定月，美國已決定1998年年12月以后將不再月以后將不再使用使用DES。1997年年DESCHALL小組經過近小組經過近4個月的努力，通過個月的努力，通過Inte

22、rnet搜索了搜索了31016個密鑰，找出了個密鑰，找出了DES的密鑰，恢復出了明文。的密鑰，恢復出了明文。1998年年5月美國月美國EFF(electronics frontier foundation)宣布，他們以一臺宣布，他們以一臺價值價值20萬美元的計算機改裝成的專用解密機，用萬美元的計算機改裝成的專用解密機，用56小時破譯了小時破譯了56 比特密鑰比特密鑰的的DES。美國國家標準和技術協(xié)會美國國家標準和技術協(xié)會(NIST)已征集并進行了幾輪評估、篩選，產已征集并進行了幾輪評估、篩選，產生了稱之為生了稱之為AES(advanced encryption standard) 的新加密標準

23、。的新加密標準。盡管如此，盡管如此，DES對于推動密碼理論的發(fā)展和應用畢竟起了重大作用，對于推動密碼理論的發(fā)展和應用畢竟起了重大作用，對于掌握分組密碼的基本理論、設計思想和實際應用仍然有著重要的參考對于掌握分組密碼的基本理論、設計思想和實際應用仍然有著重要的參考價值。價值。下面首先來描述這一算法。下面首先來描述這一算法。明文分組長為明文分組長為64比特，比特，密鑰長為密鑰長為56比特。比特。3個階段：個階段：初始置換初始置換IP，具有相同功能的具有相同功能的16輪變換，輪變換，逆初始置換逆初始置換IP-1DES的結構和的結構和Feistel密碼密碼結構完全相同。結構完全相同。3.2.1 DES

24、描述描述圖圖3.5 DES加密算法框圖加密算法框圖圖圖3.5的右邊是使用的右邊是使用56比特密鑰的方法。比特密鑰的方法。密鑰首先通過一個置換函數(shù)，然后，對加密過程的每密鑰首先通過一個置換函數(shù)，然后，對加密過程的每一輪，通過一個左循環(huán)移位和一個置換產生一個子密鑰。一輪，通過一個左循環(huán)移位和一個置換產生一個子密鑰。其中每輪的置換都相同，但由于密鑰被重復迭代，所其中每輪的置換都相同，但由于密鑰被重復迭代，所以產生的每輪子密鑰不相同。以產生的每輪子密鑰不相同。1. 初始置換初始置換DES的置換表見表的置換表見表3.2。表。表3.2(a)和表和表3.2(b)分別給出了初始置分別給出了初始置換和逆初始置換

25、的定義：換和逆初始置換的定義：M1 M2 M3 M4 M5 M6 M7 M8M9 M10 M11 M12 M13 M14 M15 M16 M17 M18 M19 M20 M21 M22 M23 M24M25 M26 M27 M28 M29 M30 M31 M32M33 M34 M35 M36 M37 M38 M39 M40M41 M42 M43 M44 M45 M46 M47 M48M49 M50 M51 M52 M53 M54 M55 M56M57 M58 M59 M60 M61 M62 M63 M64為了顯示這兩個置換的確是彼此互逆的，考慮下面為了顯示這兩個置換的確是彼此互逆的，考慮下面6

26、4比比特的輸入特的輸入M ：其中其中Mi是二元數(shù)字。由表是二元數(shù)字。由表3.2(a)得得X=IP(M)為：為：M58 M50 M42 M34 M26 M18 M10 M2M60 M52 M44 M36 M28 M20 M12 M4M62 M54 M46 M38 M30 M22 M14 M6M64 M56 M48 M40 M32 M24 M16 M8M57 M49 M41 M33 M25 M17 M9 M1M59 M51 M43 M35 M27 M19 M11 M3M61 M53 M45 M37 M29 M21 M13 M5M63 M55 M47 M39 M31 M23 M15 M7如果再取逆初

27、始置換如果再取逆初始置換Y=IP-1(X)=IP-1(IP(M)，可以看出，可以看出，M各位的初始順序將被恢復。各位的初始順序將被恢復。2. 輪結構輪結構圖圖3.6 DES加密算法的輪結構。加密算法的輪結構。首先看圖的左半部分。首先看圖的左半部分。將將64比特的輪輸入分成各為比特的輪輸入分成各為32比特的左、右兩半，分別記比特的左、右兩半，分別記為為L和和R。和和Feistel網絡一樣，每輪變換可由以下公式表示：網絡一樣，每輪變換可由以下公式表示：111(,)iiiiiiLRRLF RK輪密鑰輪密鑰Ki為為48比特，函數(shù)比特，函數(shù)F(R,K)的計算過程如圖的計算過程如圖3.7所示。所示。輪輸入

28、的右半部分輪輸入的右半部分R為為32比特，比特，R首先被擴展成首先被擴展成48比特，比特，擴展過程由表擴展過程由表3.2(c)定義，其中將定義，其中將R的的16個比特各重復一次。個比特各重復一次。擴展后的擴展后的48比特再與子密鑰比特再與子密鑰Ki異或，然后再通過一個異或，然后再通過一個S盒，盒，產生產生32比特的輸出。比特的輸出。該輸出再經過一個由表該輸出再經過一個由表3.2(d)定義的置換，產生的結果即為函定義的置換，產生的結果即為函數(shù)數(shù)F(R,K)的輸出。的輸出。圖圖3.7 函數(shù)函數(shù)F(R,K)的計算過程的計算過程F中的代換由中的代換由8個個S盒組成，每個盒組成，每個S盒的輸入長為盒的輸

29、入長為6比特、輸出比特、輸出長為長為4比特，其變換關系由表比特，其變換關系由表3.3定義，每個定義，每個S盒給出了盒給出了4個代個代換（由一個表的換（由一個表的4行給出）。行給出）。行行 列列0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15S1012314 4 13 1 2 15 11 8 3 10 6 12 5 9 0 70 15 7 4 14 2 13 1 10 6 12 11 9 5 3 84 1 14 8 13 6 2 11 15 12 9 7 3 10 5 015 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13S2S8對每個盒對每個盒S

30、i，其其6比特輸入中，第比特輸入中，第1個和第個和第6個比特形成個比特形成一個一個2位二進制數(shù)，用來選擇位二進制數(shù)，用來選擇Si的的4個代換中的一個。個代換中的一個。6比特比特輸入中，中間輸入中，中間4位用來選擇列。行和列選定后，得到其交叉位用來選擇列。行和列選定后，得到其交叉位置的十進制數(shù)，將這個數(shù)表示為位置的十進制數(shù)，將這個數(shù)表示為4位二進制數(shù)即得這一位二進制數(shù)即得這一S盒的輸出。盒的輸出。例如，例如，S1 的輸入為的輸入為011001，行選為，行選為01（即第（即第1行），列行），列選為選為1100（即第（即第12列），行列交叉位置的數(shù)為列），行列交叉位置的數(shù)為9，其，其4位二位二進制表

31、示為進制表示為1001，所以，所以S1的輸出為的輸出為1001。S盒的每一行定義了一個可逆代換，圖盒的每一行定義了一個可逆代換，圖3.2（在（在3.1.1節(jié)）節(jié)）表示表示S1第第0行所定義的代換。行所定義的代換。3. 密鑰的產生密鑰的產生再看圖再看圖3.5和圖和圖3.6，輸入算法的，輸入算法的56比特密鑰首先經過一比特密鑰首先經過一個置換運算，該置換由表個置換運算，該置換由表3.4(a)給出，然后將置換后的給出，然后將置換后的56比比特分為各為特分為各為28比特的左、右兩半，分別記為比特的左、右兩半，分別記為C0和和D0。在第在第i 輪分別對輪分別對Ci-1和和Di-1進行左循環(huán)移位，所移位數(shù)

32、由進行左循環(huán)移位，所移位數(shù)由表表3.4(c)給出。移位后的結果作為求下一輪子密鑰的輸入，給出。移位后的結果作為求下一輪子密鑰的輸入，同時也作為置換選擇同時也作為置換選擇2的輸入。的輸入。通過置換選擇通過置換選擇2產生的產生的48比特的比特的Ki，即為本輪的子密鑰，即為本輪的子密鑰，作為函數(shù)作為函數(shù)F(Ri-1,Ki)的輸入。的輸入。其中置換選擇其中置換選擇2由表由表3.4(b)定義。定義。 DES密鑰編排中使用的表（表密鑰編排中使用的表（表3-4） (a) 置換選擇置換選擇1 (b) 置換選擇置換選擇2 (c) 左循環(huán)移位位數(shù)左循環(huán)移位位數(shù) 注注. 對對i=1,2,16， Ci、Di分別是由分

33、別是由C0、D0左旋若干比特而得到，至左旋若干比特而得到，至i=16，剛好左旋了剛好左旋了28比特位而回復當初比特位而回復當初，即，即:C16=C0，D16=D0。 PC1PC2574941332517914171124151585042342618328156211010259514335272319124268191136052443616727201326355473931231541523137475576254463812223040514533481466153453729444939563453211352820304464250362932輪數(shù)1 2 3 4 5 6 7 8 9

34、 10 11 12 13 14 15 16位數(shù)1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 4解密解密 和和Feistel密碼一樣，密碼一樣，DES的解密和加密算法使用同一算法，但的解密和加密算法使用同一算法，但子密鑰使用的順序相反子密鑰使用的順序相反 解密時子密鑰的產生有兩種方式：解密時子密鑰的產生有兩種方式： 1）是先由）是先由K產生產生16個子密鑰，再逆續(xù)使用個子密鑰，再逆續(xù)使用 2）反序產生。）反序產生。(在前面講過的密鑰擴展過程中若改在前面講過的密鑰擴展過程中若改LSi為為 則也就可以依次產生這逆序的子密鑰。則也就可以依次產生這逆序的子密鑰。其它, 216, 9 ,

35、 2, 11, 0iiRSi40/149 DES加密實例加密實例 取取16進制明文進制明文X：0123456789ABCDEF 密鑰密鑰K為：為： 133457799BBCDFF1 去掉奇偶校驗位以二進制形式表示的密鑰是去掉奇偶校驗位以二進制形式表示的密鑰是 00010010011010010101101111001001101101111011011111111000 應用初始置換應用初始置換IP，我們得到：，我們得到：L0=11001100000000001100110011111111R0=11110000101010101111000010101010然后進行然后進行16輪加密。最后對

36、輪加密。最后對L16, R16 使用使用IP-1得到密文：得到密文：85E813540F0AB40541/149 DES的設計特色：的設計特色： 在在DES算法中，函數(shù)是最基本的關鍵環(huán)節(jié)，算法中，函數(shù)是最基本的關鍵環(huán)節(jié)， 其中其中 用用S-盒實現(xiàn)小塊盒實現(xiàn)小塊的非線性變換，達到混亂目的；的非線性變換，達到混亂目的； 用用置換置換P實現(xiàn)大塊實現(xiàn)大塊的非線性變換，達到擴散目的。的非線性變換，達到擴散目的。 置換置換P的設計的設計使每層使每層S-盒的盒的4bit輸出進入到下一層的輸出進入到下一層的4個不同個不同S-盒盒 每個每個S-盒的輸入由分屬上一層中盒的輸入由分屬上一層中4個不同個不同S-盒的輸

37、出構成。盒的輸出構成。 DES的核心是的核心是S盒，除此之外的計算是屬線性的。盒，除此之外的計算是屬線性的。 S盒作為該密碼體制的非線性組件對安全性至關重要。盒作為該密碼體制的非線性組件對安全性至關重要。 S-盒的設計準則還沒有完全公開。一些密碼學家懷疑美國盒的設計準則還沒有完全公開。一些密碼學家懷疑美國NSA(the National Security Agency)設計設計S-盒時隱藏了盒時隱藏了“陷門陷門”，使得只有，使得只有他們才知道破譯算法，但沒有證據能表明這一點。他們才知道破譯算法，但沒有證據能表明這一點。42/1491976年，美國年，美國NSA披露了披露了S-盒的下述幾條設計原

38、則：盒的下述幾條設計原則： 每個每個S-盒的每一行是整數(shù)盒的每一行是整數(shù)015的一個全排列；的一個全排列； 每個每個S-盒的輸出都不是其輸入的線性或仿射函數(shù)；盒的輸出都不是其輸入的線性或仿射函數(shù)； 改變任一改變任一S-盒任意盒任意1bit的輸入，其輸出至少有的輸入，其輸出至少有2bit發(fā)生變化；發(fā)生變化； 對任一對任一S-盒的任意盒的任意6bit輸入輸入x，S(x)與與S(x 001100)至少有至少有2bit不同；不同； 對任一對任一S-盒的任意盒的任意6bit輸入輸入x，及，及 , 0,1，都有，都有S(x)S(x 1100)； 對任一對任一S-盒，當它的任一位輸入保持不變，其它盒，當它的

39、任一位輸入保持不變，其它5位輸入盡情變化位輸入盡情變化時，所有諸時，所有諸4bit輸出中，輸出中，0與與1的總數(shù)接近相等。的總數(shù)接近相等。S盒的爭論：盒的爭論： 公眾仍然不知道公眾仍然不知道S盒的構造中是否還使用了進一步的設計準則（有盒的構造中是否還使用了進一步的設計準則（有陷門？）陷門？） 密鑰長度是否足夠？（已經證明密鑰長度不夠）密鑰長度是否足夠？（已經證明密鑰長度不夠） 迭代的長度？（迭代的長度？（8、16、32？）？）43/149DES的安全性問題的安全性問題 完全依賴于所用的密鑰，即算法是公開的。完全依賴于所用的密鑰，即算法是公開的。1）取反特性：）取反特性： 對于明文組對于明文組M

40、，密文組，密文組C和主密鑰和主密鑰K，若，若C=DESK(M)， 則則 ，其中，其中 、 和和 ,分別為分別為M，C和和K的逐位取反。的逐位取反。證明：證明： 置換本身的取反特性可以保持置換本身的取反特性可以保持 (1)若以若以K為主密鑰擴展的為主密鑰擴展的16個加密子密鑰記為個加密子密鑰記為K1,K2,K16，則以，則以 為主密鑰擴展的為主密鑰擴展的16個加密子密鑰為個加密子密鑰為 (2)由由 (1 a) (1 b)=a b，可得，可得 =F(Ri-1,Ki) (3)由由 b1 a b= ，可得，可得 ，由此得證。，由此得證。 由此由此DES在選擇明文攻擊時工作量會減少一半。攻擊者破譯所使用

41、在選擇明文攻擊時工作量會減少一半。攻擊者破譯所使用的密鑰，選取兩個明密文對的密鑰，選取兩個明密文對(M,C1)和和( ,C2)，并對于可能密鑰，并對于可能密鑰K計計算出，算出，DESK(M)=C，若，若C=C1或或 C2，則說明密鑰為，則說明密鑰為K或或 。 其中其中C2=)(MDESCKba 1621,.,KKK),(1iiKRFaba ),(),(1111iiiiiiKRFLKRFLiRMCKKMCK)(MDESCK44/149 2）弱密鑰與半弱密鑰）弱密鑰與半弱密鑰. 大多數(shù)密碼體制都有某些明顯的大多數(shù)密碼體制都有某些明顯的“壞密鑰壞密鑰” 對于對于K和和K，若由，若由K擴展出來的加密子

42、密鑰為：擴展出來的加密子密鑰為：K1,K2,K15,K16，而由，而由K擴展出來的加密子密鑰卻是：擴展出來的加密子密鑰卻是：K16,K15,K2,K1，即有，即有DESK-1=DESK，則稱，則稱K與與K互為互為對合對合。 在在F256中的中的對合對對合對：在：在DES的主密鑰擴展中，的主密鑰擴展中，C0與與D0各自獨立地循環(huán)移位來產生加各自獨立地循環(huán)移位來產生加(解解)密子密鑰。密子密鑰。 若若C0與與D0分別是分別是00,11,10,01中任意一個的中任意一個的14次重復次重復，則因這樣的則因這樣的C0與與D0都對環(huán)移都對環(huán)移(無論左或右無論左或右)偶數(shù)位具有自偶數(shù)位具有自封閉性，故封閉性

43、，故45/149 若若PC-1-1(C0D0)=K,則由則由K擴展出來的加密子密鑰為：擴展出來的加密子密鑰為： K1,K2,K2,K2,K2,K2,K2,K2, K1, K1, K1, K1, K1, K1, K1, K2 把把C0與與D0各自左環(huán)移一位得各自左環(huán)移一位得C1與與D1，設，設PC-1-1 (C1D1)=K，則由，則由K擴展出來的加密子密鑰為：擴展出來的加密子密鑰為： K2, K1, K1, K1, K1, K1, K1, K1, K2,K2,K2,K2,K2,K2,K2, K1 因此，由上述因此，由上述C0與與D0導致的導致的K與與K互為對合；互為對合；K中中只有這些對合對只有

44、這些對合對 對于對于K，若，若K是自己的對合，則稱是自己的對合，則稱K為為DES的一個弱密鑰的一個弱密鑰 若若K存在異于自己的對合，則稱存在異于自己的對合，則稱K為為DES的一個半弱密鑰的一個半弱密鑰46/149 顯然，顯然，C0與與D0分別是分別是00,11,10,01中任意一個的中任意一個的14次次重復的情況共有重復的情況共有42=16種，其中種，其中C0與與D0分別是分別是00,11中任意一個的中任意一個的14次重復的情況次重復的情況(計計22=4種種)對應弱密鑰；對應弱密鑰；剩下的剩下的(16-4=12種種)對應半弱密鑰對應半弱密鑰。 弱密鑰與半弱密鑰直接引起的弱密鑰與半弱密鑰直接引起

45、的“危險危險”是在多重使用是在多重使用DES加密中加密中，第二次加密有可能使第一次加密復原；另外，第二次加密有可能使第一次加密復原；另外，弱弱密鑰與半弱密鑰使得擴展出來的諸加密子密鑰至多有兩種密鑰與半弱密鑰使得擴展出來的諸加密子密鑰至多有兩種差異差異，如此導致原本多輪迭代的復雜結構簡化和容易分析。，如此導致原本多輪迭代的復雜結構簡化和容易分析。 所幸在總數(shù)所幸在總數(shù)256個可選密鑰中，弱密鑰與半弱密鑰所個可選密鑰中，弱密鑰與半弱密鑰所占的比例極小，如果是隨機選擇，占的比例極小，如果是隨機選擇，(半半)弱密鑰出現(xiàn)弱密鑰出現(xiàn)的概率很小，因而其存在性并不會危及的概率很小，因而其存在性并不會危及DES

46、的安全。的安全。47/149 顯然，顯然，C0與與D0分別是分別是00,11,10,01中任意一個的中任意一個的14次次重復的情況共有重復的情況共有42=16種，其中種，其中C0與與D0分別是分別是00,11中任意一個的中任意一個的14次重復的情況次重復的情況(計計22=4種種)對應弱密鑰；對應弱密鑰；剩下的剩下的(16-4=12種種)對應半弱密鑰對應半弱密鑰。 弱密鑰與半弱密鑰直接引起的弱密鑰與半弱密鑰直接引起的“危險危險”是在多重使用是在多重使用DES加密中加密中，第二次加密有可能使第一次加密復原；另外，第二次加密有可能使第一次加密復原；另外，弱弱密鑰與半弱密鑰使得擴展出來的諸加密子密鑰至

47、多有兩種密鑰與半弱密鑰使得擴展出來的諸加密子密鑰至多有兩種差異差異，如此導致原本多輪迭代的復雜結構簡化和容易分析。，如此導致原本多輪迭代的復雜結構簡化和容易分析。 所幸在總數(shù)所幸在總數(shù)256個可選密鑰中，弱密鑰與半弱密鑰所個可選密鑰中，弱密鑰與半弱密鑰所占的比例極小，如果是隨機選擇，占的比例極小，如果是隨機選擇，(半半)弱密鑰出現(xiàn)弱密鑰出現(xiàn)的概率很小，因而其存在性并不會危及的概率很小，因而其存在性并不會危及DES的安全。的安全。48/149 3)密文與明文、密文與密鑰的相關性密文與明文、密文與密鑰的相關性. 人們的研究結果表明：人們的研究結果表明：DES的編碼過程可使的編碼過程可使每個密文比特

48、每個密文比特都是都是所所有明文比特有明文比特和和所有密鑰比特所有密鑰比特的的復雜混合函數(shù)復雜混合函數(shù)，而要達到這一要求，而要達到這一要求至少需要至少需要DES的迭代：的迭代：5輪輪。人們也用。人們也用 2-檢驗證明：檢驗證明：DES迭代迭代8輪輪以后，就可認為輸出和輸入不相關了。以后，就可認為輸出和輸入不相關了。 4）密鑰搜索機）密鑰搜索機. 在對在對DES安全性的批評意見中，較一致的看法是安全性的批評意見中，較一致的看法是DES的密鑰太短！的密鑰太短！其長度其長度56bit，致使密鑰量僅為，致使密鑰量僅為2561017，不能抵抗窮搜攻擊，事實，不能抵抗窮搜攻擊，事實證明的確如此。證明的確如此

49、。 1997年年1月月28日，美國日，美國RSA數(shù)據安全公司在數(shù)據安全公司在RSA安全年會上發(fā)布了安全年會上發(fā)布了一項一項“秘密密鑰挑戰(zhàn)秘密密鑰挑戰(zhàn)”競賽，分別懸賞競賽，分別懸賞1000美金、美金、5000美金和美金和10000美金用于攻破不同長度的美金用于攻破不同長度的RC5密碼算法，同時還密碼算法，同時還懸賞懸賞10000美金破譯密鑰長度為美金破譯密鑰長度為56bit的的DES。RSA公司發(fā)起這場挑戰(zhàn)賽是為公司發(fā)起這場挑戰(zhàn)賽是為了調查在了調查在Internet上分布式計算的能力，并測試不同密鑰長度的上分布式計算的能力，并測試不同密鑰長度的RC5算法和密鑰長度為算法和密鑰長度為56bit的的

50、DES算法的相對強度。算法的相對強度。49/149 結果是：密鑰長度為結果是：密鑰長度為40bit和和48bit的的RC5算法被攻破；美國算法被攻破；美國克羅拉多州的程序員克羅拉多州的程序員Verser從從1997年年3月月13日日起用了起用了96天的天的時間，在時間，在Internet上數(shù)萬名志愿者的協(xié)同工作下上數(shù)萬名志愿者的協(xié)同工作下，于，于1997年年6月月17日成功地日成功地找到了找到了DES的密鑰的密鑰，獲得了，獲得了RSA公司頒發(fā)的公司頒發(fā)的10000美金的獎勵。這一事件表明，依靠美金的獎勵。這一事件表明，依靠Internet的分布式的分布式計算能力，用窮搜方法破譯計算能力，用窮搜

51、方法破譯DES已成為可能。因此，隨著已成為可能。因此，隨著計算機能力的增強與計算技術的提高，必須相應地增加密計算機能力的增強與計算技術的提高，必須相應地增加密碼算法的密鑰長度。碼算法的密鑰長度。 5）DES的攻擊方法的攻擊方法 目前攻擊目前攻擊DES的主要方法有時間的主要方法有時間-空間權衡攻擊、差分攻擊、空間權衡攻擊、差分攻擊、線性攻擊和相關密鑰攻擊等方法，在這些攻擊方法中，線線性攻擊和相關密鑰攻擊等方法，在這些攻擊方法中，線性攻擊方法是最有效的一種方法。本章將對差分和線性分性攻擊方法是最有效的一種方法。本章將對差分和線性分析方法進行介紹析方法進行介紹50/149DES的評估的評估 規(guī)定規(guī)定

52、每隔每隔5年年由美國國家保密局（由美國國家保密局（national security agency, NSA）作）作出評估，并重新批準它是否繼續(xù)作為聯(lián)邦加密標準。最近的一次評估出評估，并重新批準它是否繼續(xù)作為聯(lián)邦加密標準。最近的一次評估是在是在1994年年1月，美國已決定月，美國已決定1998年年12月以后將不再使用月以后將不再使用DES。 一些強力攻擊的案例：一些強力攻擊的案例： 1997年年DESCHALL小組經過近小組經過近4個月的努力，通過個月的努力，通過Internet搜索了搜索了31016個密鑰，找出了個密鑰，找出了DES的密鑰，恢復出了明文。的密鑰，恢復出了明文。 1998年年5

53、月美國月美國EFF(electronics frontier foundation)宣布，他們以宣布，他們以一臺價值一臺價值20萬美元的計算機改裝成的專用解密機，用萬美元的計算機改裝成的專用解密機，用56小時破譯小時破譯了了56 比特密鑰的比特密鑰的DES。 美國國家標準和技術協(xié)會已征集并進行了幾輪評估、篩選，產生了稱美國國家標準和技術協(xié)會已征集并進行了幾輪評估、篩選，產生了稱之為之為AES(advanced encryption standard) 的新加密標準。的新加密標準。 盡管如此，盡管如此，DES對于推動密碼理論的發(fā)展和應用畢竟起了重大作用，對于推動密碼理論的發(fā)展和應用畢竟起了重大作

54、用，對于對于掌握分組密碼的基本理論、設計思想和實際應用掌握分組密碼的基本理論、設計思想和實際應用仍然有著重要的仍然有著重要的參考價值。參考價值。為了提高為了提高DES的安全性，并利用實現(xiàn)的安全性，并利用實現(xiàn)DES的現(xiàn)有軟硬件，的現(xiàn)有軟硬件，可將可將DES算法在多密鑰下多重使用。算法在多密鑰下多重使用。二重二重DES是多重使用是多重使用DES時最簡單的形式，如圖時最簡單的形式，如圖3.8所示。所示。其中明文為其中明文為P，兩個加密密鑰為兩個加密密鑰為K1和和K2，密文為：密文為：解密時，以相反順序使用兩個密鑰：解密時，以相反順序使用兩個密鑰：3.2.2 二重二重DES21 KKCEEP12 KK

55、PDDC圖圖3.8 二重二重DES因此，二重因此，二重DES所用密鑰長度為所用密鑰長度為112比特，強度極大地比特，強度極大地增加。增加。然而，假設對任意兩個密鑰然而，假設對任意兩個密鑰K1和和K2，能夠找出另一密能夠找出另一密鑰鑰K3，使得使得213 KKKEEPEP那么，二重那么，二重DES以及多重以及多重DES都沒有意義，因為它們都沒有意義，因為它們與與56比特密鑰的單重比特密鑰的單重DES等價，好在這種假設對等價，好在這種假設對DES并不并不成立。成立。將將DES加密過程加密過程64比特分組到比特分組到64比特分組的映射看作比特分組的映射看作一個置換，如果考慮一個置換，如果考慮264個

56、所有可能的輸入分組，則密鑰給個所有可能的輸入分組，則密鑰給定后，定后，DES的加密將把每個輸入分組映射到一個惟一的輸?shù)募用軐衙總€輸入分組映射到一個惟一的輸出分組。否則，如果有兩個輸入分組被映射到同一分組，出分組。否則，如果有兩個輸入分組被映射到同一分組，則解密過程就無法實施。對則解密過程就無法實施。對264個輸入分組，總映射個數(shù)個輸入分組，總映射個數(shù)為為 。2064102!10另一方面，對每個不同的密鑰，另一方面，對每個不同的密鑰，DES都定義了一個映都定義了一個映射，總映射數(shù)為射，總映射數(shù)為256N/2，則令則令如果如果T6有所不同。有所不同。 當當Nk6時，擴展算法如下時，擴展算法如下

57、KeyExpansion (byteKey4*Nk , WNb*(Nr+1) for (i =0; i Nk; i +)Wi=(Key4* i,Key4* i +1,Key4* i +2,Key4* i +3 ); for (i =Nk; i 6時，擴展算法如下：時，擴展算法如下： KeyExpansion (byte Key4*Nk , WNb*(Nr+1) for (i=0; i Nk; i +)Wi=(Key4* i, Key4* i +1, Key4* i +2, Key4* i +3 );for (i =Nk; i 6與與Nk6的密鑰擴展算法的區(qū)別在于：當?shù)拿荑€擴展算法的區(qū)別在于：當

58、i為為Nk的的4的倍數(shù)時，須先將前一個字的倍數(shù)時，須先將前一個字Wi-1經過經過SubByte變換。變換。以上兩個算法中，以上兩個算法中，Rconi/Nk 為輪常數(shù)，其值與為輪常數(shù)，其值與Nk無關，定義為（字節(jié)用十六進制表示，同時理無關，定義為（字節(jié)用十六進制表示，同時理解為解為GF(28)上的元素）：上的元素）：Rcon i=(RCi, 00, 00, 00)其中其中RCi 是是GF(28) 中值為中值為xi-1的元素，因此的元素，因此RC1 =1(即即01)RCi = x(即即02)RCi-1= xi-1(2) 輪密鑰選取輪密鑰選取輪密鑰輪密鑰i（即第即第i 個輪密鑰）由輪密鑰緩沖字個輪密

59、鑰）由輪密鑰緩沖字WNb* i到到WNb*(i+1)給出，如圖給出，如圖3.23所示。所示。圖圖3.23 Nb=6且且Nk=4時的密鑰擴展與輪密鑰選取時的密鑰擴展與輪密鑰選取4. 加密算法加密算法加密算法為順序完成以下操作：初始的密鑰加；加密算法為順序完成以下操作：初始的密鑰加；(Nr-1)輪迭代；一個結尾輪。即輪迭代；一個結尾輪。即Rijndael (State, CipherKey)KeyExpansion (CipherKey, ExpandedKey);AddRoundKey (State, ExpandedKey);for (i=1; i Nr; i +) Round (State,

60、 ExpandedKey+Nb* i);FinalRound (State, ExpandedKey+Nb*Nr)其中其中CipherKey是種子密鑰，是種子密鑰，ExpandedKey是擴展是擴展密鑰。密鑰擴展可以事先進行（預計算），且密鑰。密鑰擴展可以事先進行（預計算），且Rijndael密碼的加密算法可以用這一擴展密鑰來描密碼的加密算法可以用這一擴展密鑰來描述，即述，即Rijndael (State, ExpandedKey)AddRoundKey (State, ExpandedKey);for (i=1; i Nr; i +)Round (State, ExpandedKey+Nb*