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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、長(zhǎng)度。比特的密鑰長(zhǎng)度。 輪數(shù)。輪數(shù)。單輪結(jié)構(gòu)遠(yuǎn)不足以保證安全性，但多輪結(jié)構(gòu)可提供單輪結(jié)構(gòu)遠(yuǎn)不足以保證安全性，但多輪結(jié)構(gòu)可提供足夠的安全性。典型地，輪數(shù)取為足夠的安全性。典型地，輪數(shù)取為16。 子密鑰產(chǎn)生算法。子密鑰產(chǎn)生算法。復(fù)雜性越大，密碼分析的困難性就越大。復(fù)雜性越大，密碼分析的困難性就越大。輪函數(shù)。輪函數(shù)。復(fù)雜性越大，密碼分析的困難性也越大。復(fù)雜性越大，密碼分析的困難性也越大。在設(shè)計(jì)在設(shè)計(jì)Feistel網(wǎng)絡(luò)時(shí)，還有以下兩個(gè)方面需要考慮：網(wǎng)絡(luò)時(shí)，還有以下兩個(gè)方面需要考慮： 快速的軟件實(shí)現(xiàn)。快速的軟件實(shí)現(xiàn)。在很多情況中，算法是被鑲嵌在應(yīng)用程序中，因而無(wú)在很多情況中，算法是被鑲嵌在應(yīng)用程序中，因

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

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

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

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

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

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

22、rnet搜索了搜索了31016個(gè)密鑰，找出了個(gè)密鑰，找出了DES的密鑰，恢復(fù)出了明文。的密鑰，恢復(fù)出了明文。1998年年5月美國(guó)月美國(guó)EFF(electronics frontier foundation)宣布，他們以一臺(tái)宣布，他們以一臺(tái)價(jià)值價(jià)值20萬(wàn)美元的計(jì)算機(jī)改裝成的專用解密機(jī)，用萬(wàn)美元的計(jì)算機(jī)改裝成的專用解密機(jī)，用56小時(shí)破譯了小時(shí)破譯了56 比特密鑰比特密鑰的的DES。美國(guó)國(guó)家標(biāo)準(zhǔn)和技術(shù)協(xié)會(huì)美國(guó)國(guó)家標(biāo)準(zhǔn)和技術(shù)協(xié)會(huì)(NIST)已征集并進(jìn)行了幾輪評(píng)估、篩選，產(chǎn)已征集并進(jìn)行了幾輪評(píng)估、篩選，產(chǎn)生了稱之為生了稱之為AES(advanced encryption standard) 的新加密標(biāo)準(zhǔn)

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

24、描述描述圖圖3.5 DES加密算法框圖加密算法框圖圖圖3.5的右邊是使用的右邊是使用56比特密鑰的方法。比特密鑰的方法。密鑰首先通過(guò)一個(gè)置換函數(shù)，然后，對(duì)加密過(guò)程的每密鑰首先通過(guò)一個(gè)置換函數(shù)，然后，對(duì)加密過(guò)程的每一輪，通過(guò)一個(gè)左循環(huán)移位和一個(gè)置換產(chǎn)生一個(gè)子密鑰。一輪，通過(guò)一個(gè)左循環(huán)移位和一個(gè)置換產(chǎn)生一個(gè)子密鑰。其中每輪的置換都相同，但由于密鑰被重復(fù)迭代，所其中每輪的置換都相同，但由于密鑰被重復(fù)迭代，所以產(chǎn)生的每輪子密鑰不相同。以產(chǎn)生的每輪子密鑰不相同。1. 初始置換初始置換DES的置換表見(jiàn)表的置換表見(jiàn)表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為了顯示這兩個(gè)置換的確是彼此互逆的，考慮下面為了顯示這兩個(gè)置換的確是彼此互逆的，考慮下面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各位的初始順序?qū)⒈换謴?fù)。各位的初始順序?qū)⒈换謴?fù)。2. 輪結(jié)構(gòu)輪結(jié)構(gòu)圖圖3.6 DES加密算法的輪結(jié)構(gòu)。加密算法的輪結(jié)構(gòu)。首先看圖的左半部分。首先看圖的左半部分。將將64比特的輪輸入分成各為比特的輪輸入分成各為32比特的左、右兩半，分別記比特的左、右兩半，分別記為為L(zhǎng)和和R。和和Feistel網(wǎng)絡(luò)一樣，每輪變換可由以下公式表示：網(wǎng)絡(luò)一樣，每輪變換可由以下公式表示：111(,)iiiiiiLRRLF RK輪密鑰輪密鑰Ki為為48比特，函數(shù)比特，函數(shù)F(R,K)的計(jì)算過(guò)程如圖的計(jì)算過(guò)程如圖3.7所示。所示。輪輸入

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

29、入長(zhǎng)為6比特、輸出比特、輸出長(zhǎng)為長(zhǎng)為4比特，其變換關(guān)系由表比特，其變換關(guān)系由表3.3定義，每個(gè)定義，每個(gè)S盒給出了盒給出了4個(gè)代個(gè)代換（由一個(gè)表的換（由一個(gè)表的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對(duì)每個(gè)盒對(duì)每個(gè)盒S

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

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

32、由進(jìn)行左循環(huán)移位，所移位數(shù)由表表3.4(c)給出。移位后的結(jié)果作為求下一輪子密鑰的輸入，給出。移位后的結(jié)果作為求下一輪子密鑰的輸入，同時(shí)也作為置換選擇同時(shí)也作為置換選擇2的輸入。的輸入。通過(guò)置換選擇通過(guò)置換選擇2產(chǎn)生的產(chǎn)生的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ù) 注注. 對(duì)對(duì)i=1,2,16， Ci、Di分別是由分

33、別是由C0、D0左旋若干比特而得到，至左旋若干比特而得到，至i=16，剛好左旋了剛好左旋了28比特位而回復(fù)當(dāng)初比特位而回復(fù)當(dāng)初，即，即: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的解密和加密算法使用同一算法，但的解密和加密算法使用同一算法，但子密鑰使用的順序相反子密鑰使用的順序相反 解密時(shí)子密鑰的產(chǎn)生有兩種方式：解密時(shí)子密鑰的產(chǎn)生有兩種方式： 1）是先由）是先由K產(chǎn)生產(chǎn)生16個(gè)子密鑰，再逆續(xù)使用個(gè)子密鑰，再逆續(xù)使用 2）反序產(chǎn)生。）反序產(chǎn)生。(在前面講過(guò)的密鑰擴(kuò)展過(guò)程中若改在前面講過(guò)的密鑰擴(kuò)展過(guò)程中若改LSi為為 則也就可以依次產(chǎn)生這逆序的子密鑰。則也就可以依次產(chǎn)生這逆序的子密鑰。其它, 216, 9 ,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

53、月美國(guó)月美國(guó)EFF(electronics frontier foundation)宣布，他們以宣布，他們以一臺(tái)價(jià)值一臺(tái)價(jià)值20萬(wàn)美元的計(jì)算機(jī)改裝成的專用解密機(jī)，用萬(wàn)美元的計(jì)算機(jī)改裝成的專用解密機(jī)，用56小時(shí)破譯小時(shí)破譯了了56 比特密鑰的比特密鑰的DES。 美國(guó)國(guó)家標(biāo)準(zhǔn)和技術(shù)協(xié)會(huì)已征集并進(jìn)行了幾輪評(píng)估、篩選，產(chǎn)生了稱美國(guó)國(guó)家標(biāo)準(zhǔn)和技術(shù)協(xié)會(huì)已征集并進(jìn)行了幾輪評(píng)估、篩選，產(chǎn)生了稱之為之為AES(advanced encryption standard) 的新加密標(biāo)準(zhǔn)。的新加密標(biāo)準(zhǔn)。 盡管如此，盡管如此，DES對(duì)于推動(dòng)密碼理論的發(fā)展和應(yīng)用畢竟起了重大作用，對(duì)于推動(dòng)密碼理論的發(fā)展和應(yīng)用畢竟起了重大作

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

55、PDDC圖圖3.8 二重二重DES因此，二重因此，二重DES所用密鑰長(zhǎng)度為所用密鑰長(zhǎng)度為112比特，強(qiáng)度極大地比特，強(qiáng)度極大地增加。增加。然而，假設(shè)對(duì)任意兩個(gè)密鑰然而，假設(shè)對(duì)任意兩個(gè)密鑰K1和和K2，能夠找出另一密能夠找出另一密鑰鑰K3，使得使得213 KKKEEPEP那么，二重那么，二重DES以及多重以及多重DES都沒(méi)有意義，因?yàn)樗鼈兌紱](méi)有意義，因?yàn)樗鼈兣c與56比特密鑰的單重比特密鑰的單重DES等價(jià)，好在這種假設(shè)對(duì)等價(jià)，好在這種假設(shè)對(duì)DES并不并不成立。成立。將將DES加密過(guò)程加密過(guò)程64比特分組到比特分組到64比特分組的映射看作比特分組的映射看作一個(gè)置換，如果考慮一個(gè)置換，如果考慮264個(gè)

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

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時(shí)，擴(kuò)展算法如下：時(shí)，擴(kuò)展算法如下： 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的密鑰擴(kuò)展算法的區(qū)別在于：當(dāng)?shù)拿荑€擴(kuò)展算法的區(qū)別在于：當(dāng)

58、i為為Nk的的4的倍數(shù)時(shí)，須先將前一個(gè)字的倍數(shù)時(shí)，須先將前一個(gè)字Wi-1經(jīng)過(guò)經(jīng)過(guò)SubByte變換。變換。以上兩個(gè)算法中，以上兩個(gè)算法中，Rconi/Nk 為輪常數(shù)，其值與為輪常數(shù)，其值與Nk無(wú)關(guān)，定義為（字節(jié)用十六進(jìn)制表示，同時(shí)理無(wú)關(guān)，定義為（字節(jié)用十六進(jìn)制表示，同時(shí)理解為解為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 個(gè)輪密鑰）由輪密鑰緩沖字個(gè)輪密

59、鑰）由輪密鑰緩沖字WNb* i到到WNb*(i+1)給出，如圖給出，如圖3.23所示。所示。圖圖3.23 Nb=6且且Nk=4時(shí)的密鑰擴(kuò)展與輪密鑰選取時(shí)的密鑰擴(kuò)展與輪密鑰選取4. 加密算法加密算法加密算法為順序完成以下操作：初始的密鑰加；加密算法為順序完成以下操作：初始的密鑰加；(Nr-1)輪迭代；一個(gè)結(jié)尾輪。即輪迭代；一個(gè)結(jié)尾輪。即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是擴(kuò)展是擴(kuò)展密鑰。密鑰擴(kuò)展可以事先進(jìn)行（預(yù)計(jì)算），且密鑰。密鑰擴(kuò)展可以事先進(jìn)行（預(yù)計(jì)算），且Rijndael密碼的加密算法可以用這一擴(kuò)展密鑰來(lái)描密碼的加密算法可以用這一擴(kuò)展密鑰來(lái)描述，即述，即Rijndael (State, ExpandedKey)AddRoundKey (State, ExpandedKey);for (i=1; i Nr; i +)Round (State, ExpandedKey+Nb*