現(xiàn)代密碼學(xué)第4章2：DES

1、1分組密碼：分組密碼：數(shù)據(jù)加密標(biāo)準(zhǔn)數(shù)據(jù)加密標(biāo)準(zhǔn)DESDES算法算法現(xiàn)代密碼學(xué)現(xiàn)代密碼學(xué)第第4章章(2)2本節(jié)主要內(nèi)容本節(jié)主要內(nèi)容n1 1、數(shù)據(jù)加密標(biāo)準(zhǔn)、數(shù)據(jù)加密標(biāo)準(zhǔn)DESDES的產(chǎn)生的產(chǎn)生n2 2、S-DESS-DES算法算法n3 3、DESDES加密與解密過(guò)程加密與解密過(guò)程n4 4、DESDES的安全性分析的安全性分析n5 5、DESDES的改進(jìn)與實(shí)現(xiàn)的改進(jìn)與實(shí)現(xiàn)n6 6、作業(yè)、作業(yè)31.數(shù)據(jù)加密標(biāo)準(zhǔn)數(shù)據(jù)加密標(biāo)準(zhǔn)DES的產(chǎn)生的產(chǎn)生 美國(guó)國(guó)家標(biāo)準(zhǔn)局1973年開(kāi)始研究除國(guó)防部外的其它部門(mén)的計(jì)算機(jī)系統(tǒng)的數(shù)據(jù)加密標(biāo)準(zhǔn)，于1973年5月15日和1974年8月27日先后兩次向公眾發(fā)出了征求加密算法的公告

2、。加密算法要達(dá)到的目的（通常稱為DES 密碼算法要求）主要為以下四點(diǎn)： （1）提供高質(zhì)量的數(shù)據(jù)保護(hù)，防止數(shù)據(jù)未經(jīng)授權(quán)的泄露和未被察覺(jué)的修改； （2）具有相當(dāng)高的復(fù)雜性，使得破譯的開(kāi)銷超過(guò)可能獲得的利益，同時(shí)又要便于理解和掌握； （3）DES密碼體制的安全性應(yīng)該不依賴于算法的保密，其安全性僅以加密密鑰的保密為基礎(chǔ)； （4）實(shí)現(xiàn)經(jīng)濟(jì)，運(yùn)行有效，并且適用于多種完全不同的應(yīng)用。 4n1977年1月，美國(guó)政府頒布：采納IBM公司設(shè)計(jì)的方案作為非機(jī)密數(shù)據(jù)的正式數(shù)據(jù)加密標(biāo)準(zhǔn)（DES Data Encryption Standard）。1.數(shù)據(jù)加密標(biāo)準(zhǔn)數(shù)據(jù)加密標(biāo)準(zhǔn)DES的產(chǎn)生的產(chǎn)生5 數(shù)據(jù)加密標(biāo)準(zhǔn)（data

3、encryption standard, DES）是迄今為止世界上最為廣泛使用和流行的一種分組密碼算法，它的分組長(zhǎng)度為64比特，密鑰長(zhǎng)度為56比特，它是由美國(guó)IBM公司研制的，是早期的稱作Lucifer密碼的一種發(fā)展和修改。 DES在1975年3月17日首次被公布在聯(lián)邦記錄中，經(jīng)過(guò)大量的公開(kāi)討論后，DES于1977年1月15日被正式批準(zhǔn)并作為美國(guó)聯(lián)邦信息處理標(biāo)準(zhǔn)，即FIPS-46，同年7月15日開(kāi)始生效。1.數(shù)據(jù)加密標(biāo)準(zhǔn)數(shù)據(jù)加密標(biāo)準(zhǔn)DES的產(chǎn)生的產(chǎn)生6 規(guī)定每隔5年由美國(guó)國(guó)家保密局（national security agency, NSA）作出評(píng)估，并重新批準(zhǔn)它是否繼續(xù)作為聯(lián)邦加密標(biāo)準(zhǔn)。最近

4、的一次評(píng)估是在1994年1月，美國(guó)已決定1998年12月以后將不再使用DES。 1997年DESCHALL小組經(jīng)過(guò)近4個(gè)月的努力，通過(guò)Internet搜索了31016個(gè)密鑰，找出了DES的密鑰，恢復(fù)出了明文。1.數(shù)據(jù)加密標(biāo)準(zhǔn)數(shù)據(jù)加密標(biāo)準(zhǔn)DES的產(chǎn)生的產(chǎn)生7n 1998年5月美國(guó)EFF(electronics frontier foundation)宣布，他們以一臺(tái)價(jià)值20萬(wàn)美元的計(jì)算機(jī)改裝成的專用解密機(jī)，用56小時(shí)破譯了56 比特密鑰的DES。美國(guó)國(guó)家標(biāo)準(zhǔn)和技術(shù)協(xié)會(huì)已征集并進(jìn)行了幾輪評(píng)估、篩選，產(chǎn)生了稱之為 AES(advanced encryption standard) 的新加密標(biāo)準(zhǔn)。盡管

5、如此，DES對(duì)于推動(dòng)密碼理論的發(fā)展和應(yīng)用畢竟起了重大作用，對(duì)于掌握分組密碼的基本理論、設(shè)計(jì)思想和實(shí)際應(yīng)用仍然有著重要的參考價(jià)值，下面首先來(lái)描述這一算法。1.數(shù)據(jù)加密標(biāo)準(zhǔn)數(shù)據(jù)加密標(biāo)準(zhǔn)DES的產(chǎn)生的產(chǎn)生8 Simplified DES方案，簡(jiǎn)稱方案，簡(jiǎn)稱S-DES方方案。它是一個(gè)供教學(xué)而非安全的加密算法，案。它是一個(gè)供教學(xué)而非安全的加密算法，它與它與DES的特性和結(jié)構(gòu)類似，但參數(shù)小。的特性和結(jié)構(gòu)類似，但參數(shù)小。注：注：1.* 加密算法涉及五個(gè)函數(shù)：加密算法涉及五個(gè)函數(shù)：(1)初始置換初始置換IP(initial permutation)(2)復(fù)合函數(shù)復(fù)合函數(shù)fk1，它是由密鑰，它是由密鑰K確定的，

6、具有置換確定的，具有置換和代換的運(yùn)算。和代換的運(yùn)算。 (3)置換函數(shù)置換函數(shù)SW(4)復(fù)合函數(shù)復(fù)合函數(shù)fk2(5)初始置換初始置換IP的逆置換的逆置換IP-12.2.簡(jiǎn)化的簡(jiǎn)化的DESDES9 加密加密S-DESS-DES方案示意圖方案示意圖10bit密鑰 解密解密8bit明文P108bit明文IP移位IP-1P8fkfkSWSW移位P8fkfkIPIP-18bit密文8bit密文K2K2K1K110nIP-1*fk2*SW*fk1*IP也可寫(xiě)為也可寫(xiě)為密文密文=IP-1（fk2(SW(fk1(IP(明文明文)其中其中 K1=P8(移位移位(P10(密鑰密鑰K)K2=P8(移位移位(移位移位(

7、P10(密鑰密鑰K)n解密算法的數(shù)學(xué)表示：解密算法的數(shù)學(xué)表示：明文明文=IP-1（fk1(SW(fk2(IP(密文密文)S-DES加密算法的數(shù)學(xué)表示加密算法的數(shù)學(xué)表示11對(duì)對(duì)S-DESS-DES的深入描述的深入描述（1） S-DES的密鑰生成：的密鑰生成：設(shè)設(shè)10bit的密鑰為（的密鑰為（ k1,k2,k10 )置換置換P10是這樣定義的是這樣定義的P10(k1,k2,k10)=(k3,k5,k2,k7,k4,k10,k1,k9,k8,k6) P8= (k1,k2,k10)=(k6,k3,k7,k4,k8,k5,k10,k9 ) LS-1為循環(huán)左移為循環(huán)左移1位，位， LS-2為循環(huán)左移為循環(huán)

8、左移2位位 按照上述條件按照上述條件,若若K選為選為(1010000010), 產(chǎn)生的產(chǎn)生的兩個(gè)子密鑰分別為兩個(gè)子密鑰分別為K1=(1 0 1 0 0 1 0 0),K2=(0 1 0 0 0 0 1 1)12(2) S-DES的加密運(yùn)算的加密運(yùn)算: 初始置換用初始置換用IP函數(shù)函數(shù): IP= 1 2 3 4 5 6 7 8 2 6 3 1 4 8 5 7 末端算法的置換為末端算法的置換為IP的逆置換的逆置換:IP-1= 1 2 3 4 5 6 7 8 4 1 3 5 7 2 8 6 易見(jiàn)易見(jiàn)IP-1(IP(X)=X 13S-DES加密圖加密圖8-bit 明文明文IP+P4+LR4K1844f

9、kF414S-DES加密圖加密圖(續(xù)續(xù))+8K2P4+IP-18-bit 密文密文4844fkF44228SW15 函數(shù)函數(shù)fk，是加密方案中的最重要部分，它可表示為：，是加密方案中的最重要部分，它可表示為：fk(L,R)=(L F(R,SK),R)，其中，其中L，R為為8位輸入位輸入, 左右左右各為各為4位位, F為從為從4位集到位集到4位集的一個(gè)映射位集的一個(gè)映射, 并不要求是并不要求是1-1的。的。SK為子密鑰。為子密鑰。 對(duì)映射對(duì)映射F來(lái)說(shuō)：來(lái)說(shuō)： 首先輸入是一個(gè)首先輸入是一個(gè)4-位數(shù)（位數(shù)（n1,n2,n3,n4），第一步），第一步運(yùn)算是擴(kuò)張運(yùn)算是擴(kuò)張/置換（置換（E/P）運(yùn)算：）運(yùn)

10、算： E/P 4 1 2 3 2 3 4 1 事實(shí)上，它的直觀表現(xiàn)形式為：事實(shí)上，它的直觀表現(xiàn)形式為： n4 n1 n2 n3 n2 n3 n4 n1168-bit子密鑰：子密鑰： K1=(k11,k12,k13,k14,k15,k16,k17,k18),然后與然后與E/P的結(jié)果作異或運(yùn)算得：的結(jié)果作異或運(yùn)算得：n4+k11 n1+k12 n2+k13n3+k14n2+k15 n3+k16n4+k17n1+k18 把它們重記為把它們重記為8位：位： P0,0 P0,1 P0,2 P0,3 P1,0 P1,1 P1,2 P1,3 上述第一行輸入進(jìn)上述第一行輸入進(jìn)S-盒盒S0，產(chǎn)生，產(chǎn)生2-位的輸

11、出；位的輸出；第二行的第二行的4位輸入進(jìn)位輸入進(jìn)S盒盒S1，產(chǎn)生，產(chǎn)生2-位的輸出。位的輸出。17兩個(gè)兩個(gè)S盒按如下定義：盒按如下定義：2313312001232301321032100S3012010331023210321032101S18S盒按下述規(guī)則運(yùn)算：盒按下述規(guī)則運(yùn)算： 將第將第1和第和第4的輸入比特做為的輸入比特做為2- bit數(shù)，指示為數(shù)，指示為S盒的一個(gè)行；將第盒的一個(gè)行；將第2和第和第3的輸入比特做為的輸入比特做為S盒的盒的一個(gè)列。如此確定為一個(gè)列。如此確定為S盒矩陣的（盒矩陣的（i,j）數(shù)。）數(shù)。 例 如 ： （例 如 ： （ P0 , 0 , P0 , 3） = ( 0

12、 0 ) , 并 且并 且(P0,1,P0,2)=(1 0)確定了確定了S0中的第中的第0行行2列（列（0，2）的系數(shù)為）的系數(shù)為3，記，記為（為（1 1）輸出。由）輸出。由S0, S1輸出輸出4-bit經(jīng)置換經(jīng)置換 P4 2 4 3 1它的輸出就是它的輸出就是F函數(shù)的輸出。函數(shù)的輸出。19S-DES的密鑰生成的密鑰生成10-bit密鑰密鑰P10LS-1LS-1LS-2LS-2K18K25555820S-DES的安全性分析的安全性分析對(duì)10 bit密鑰的強(qiáng)行攻擊是可行的密鑰空間：210=1024密碼分析：利用已知明文攻擊：已知: 明文（p1,p2,p8), 及對(duì)應(yīng)的密文（c1,c2,c8),未

13、知：(k1,k2, ，k10)Ci是pjs和kjs的函數(shù)這些加密算法可以表示成8個(gè)含10個(gè)變量的非線性方程非線性是由S盒作用的結(jié)果21 S0的非線性表示如下： 設(shè)a,b,c,d為輸入的4個(gè)比特，輸出的兩個(gè)比特分別為q,r. 則 q=abcd+ab+ac+b+d mod2 r=abcd+abd+ab+ac+ad+a+c+1 mod2 線性映射與非線性映射交替產(chǎn)生了復(fù)雜的密文比特輸出函數(shù)，使得密碼分析很困難。（可以試圖尋找8個(gè)密文比特的復(fù)雜度）S-DES的安全性分析的安全性分析22 圖4.5是DES加密算法的框圖，其中明文分組長(zhǎng)為64比特，密鑰長(zhǎng)為56比特。圖的左邊是明文的處理過(guò)程，有3個(gè)階段，首

14、先是一個(gè)初始置換IP，用于重排明文分組的64比特?cái)?shù)據(jù)。然后是具有相同功能的16輪變換，每輪中都有置換和代換運(yùn)算，第16輪變換的輸出分為左右兩半，并被交換次序。最后再經(jīng)過(guò)一個(gè)逆初始置換IP-1（為IP的逆）從而產(chǎn)生64比特的密文。除初始置換和逆初始置換外，DES的結(jié)構(gòu)和圖4.3所示的Feistel密碼結(jié)構(gòu)完全相同。3.DES描述描述23圖4.5 DES加密算法框圖DES加密算法框圖加密算法框圖24 圖4.5的右邊是使用56比特密鑰的方法。密鑰首先通過(guò)一個(gè)置換函數(shù)，然后，對(duì)加密過(guò)程的每一輪，通過(guò)一個(gè)左循環(huán)移位和一個(gè)置換產(chǎn)生一個(gè)子密鑰。其中每輪的置換都相同，但由于密鑰被重復(fù)迭代，所以產(chǎn)生的每輪子密鑰

15、不相同。25DES加密算法描述加密算法描述64比特明文初始置換第1輪第2輪第16輪左右交換初始逆置換64比特密文56比特密鑰置換選擇1左循環(huán)移位置換選擇11K左循環(huán)移位置換選擇12K左循環(huán)移位置換選擇116KDES加密算法框圖加密算法框圖26DES一輪加密的簡(jiǎn)圖一輪加密的簡(jiǎn)圖Li-1 Ri-1F+Li RiKi27 DES加加密過(guò)程密過(guò)程描述描述28DES加密算法描述加密算法描述第 i輪迭代PRi-1 (32bit)Ki(48bit)EE(Ri-1) (48bit)B1B2B3B4B5B6B7B8f(Ri-1 ,Ki)S1S2S3S4S5S6S7S8C1C2C3C4C5C6C7C8(重排：有重

16、復(fù))M(64bit)L0(32bit)R0(32bit)Li-1Ri-1IP-1C (64bit)LiRifKi(48bit)IP(置換)R16(32bit) L16(32bit)29IP初始置換初始置換(a)初始置換IP30(b)初始逆置換31DES的描述的描述在前面函數(shù)f的圖示中，擴(kuò)展置換（選擇運(yùn)算）E的定義為：3 212345456789891 0111 21 31 21 31 41 51 61 71 61 71 81 92 02 12 02 12 22 32 42 52 42 52 62 72 82 92 82 93 03 13 21置換運(yùn)算P的定義為：32輪結(jié)構(gòu)輪結(jié)構(gòu)Des加密算法的

17、輪結(jié)構(gòu)1iL32比特1iR32比特?cái)U(kuò)展/置換（E表）XOR代換/選擇（S盒）置換(p)XORiRiL484832321iC28比特1iD28比特左移位左移位置換選擇2iDiCiK33 首先看圖的左半部分。將64比特的輪輸入分成各為32比特的左、右兩半，分別記為L(zhǎng)和R。和Feistel網(wǎng)絡(luò)一樣，每輪變換可由以下公式表示：111(,)iiiiiiLRRLF RK34DES加密算法的輪結(jié)構(gòu)加密算法的輪結(jié)構(gòu)35R(32比特)ER(48比特)K(48比特)S1S1S1S1S1S1S1S1P32比特函數(shù)函數(shù)F(R，K)的計(jì)算過(guò)程的計(jì)算過(guò)程 36每個(gè)每個(gè)S盒的輸入為盒的輸入為6比特，輸出為比特，輸出為4 比

18、特，其變換關(guān)系如下：比特，其變換關(guān)系如下：S盒盒 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15列行0123S114 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 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 613S1盒的變換表盒的變換表37n（類比于（類比于S-DESS-DES）,F,F（R Ri-1i-1, K, Ki i）函數(shù)）函數(shù)F F以長(zhǎng)以長(zhǎng)度為度為3232的比特

19、串的比特串A=RA=R（32bits32bits）作第一個(gè)輸）作第一個(gè)輸入，以長(zhǎng)度為入，以長(zhǎng)度為4848的比特串變?cè)谋忍卮冊(cè)狫=K(48bits)J=K(48bits)作為第二個(gè)輸入。產(chǎn)生的輸出為長(zhǎng)度為作為第二個(gè)輸入。產(chǎn)生的輸出為長(zhǎng)度為3232的的位串。位串。(1)(1)對(duì)第一個(gè)變?cè)獙?duì)第一個(gè)變?cè)狝 A，由給定的擴(kuò)展函數(shù)，由給定的擴(kuò)展函數(shù)E E，將其擴(kuò)展成將其擴(kuò)展成4848位串，位串，E E（A A）(2)(2)計(jì)算計(jì)算E E（A A）+J+J，并把結(jié)果寫(xiě)成連續(xù)的，并把結(jié)果寫(xiě)成連續(xù)的8 8個(gè)個(gè)6 6位串位串,B=b,B=b1 1b b2 2b b3 3b b4 4b b5 5b b6 6b

20、b7 7b b8 8對(duì)對(duì)F函數(shù)的說(shuō)明函數(shù)的說(shuō)明38n(3)使用8個(gè)S盒，每個(gè)Sj是一個(gè)固定的416矩陣，它的元素取015的整數(shù)。給定長(zhǎng)度為6個(gè)比特串，如Bj=b1b2b3b4b5b6,計(jì)算Sj(Bj)如下：b1b6兩個(gè)比特確定了Sj的行數(shù), r(0=r=3); 而b2b3b4b5四個(gè)比特確定了Sj的列數(shù)c（0=c=15）。最后Sj(Bj)的值為S-盒矩陣Sj中r行c列的元素（r,c）, 得Cj=Sj(Bj)。(4) 最后，P為固定置換。對(duì)對(duì)F函數(shù)的說(shuō)明函數(shù)的說(shuō)明39n n DES 輪函數(shù)輪函數(shù)F()40 其中輪密鑰Ki為48比特，函數(shù)F(R,K)的計(jì)算過(guò)程如圖4.7所示。輪輸入的右半部分R為3

21、2比特，R首先被擴(kuò)展成48比特，擴(kuò)展過(guò)程由表3.2(c)定義，其中將R的16個(gè)比特各重復(fù)一次。擴(kuò)展后的48比特再與子密鑰Ki異或，然后再通過(guò)一個(gè)S盒，產(chǎn)生32比特的輸出。該輸出再經(jīng)過(guò)一個(gè)由表3.2(d)定義的置換，產(chǎn)生的結(jié)果即為函數(shù)F(R,K)的輸出。41圖4.7 函數(shù)F(R,K)的計(jì)算過(guò)程42 F中的代換由8個(gè)S盒組成，每個(gè)S盒的輸入長(zhǎng)為6比特、輸出長(zhǎng)為4比特，其變換關(guān)系由表3.3定義，每個(gè)S盒給出了4個(gè)代換（由一個(gè)表的4行給出）。（見(jiàn)42頁(yè)表3.3）43 對(duì)每個(gè)盒Si，其6比特輸入中，第1個(gè)和第6個(gè)比特形成一個(gè)2位二進(jìn)制數(shù)，用來(lái)選擇Si的4個(gè)代換中的一個(gè)。6比特輸入中，中間4位用來(lái)選擇列。

22、行和列選定后，得到其交叉位置的十進(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è)可逆代換，圖4.2（在3.1.1節(jié)）表示S1第0行所定義的代換。44n A=R(32 bits)J=K(48 bits)EE(A)為48 bits+B1 B2 B3 B4 B5 B6 B7 B8 S1S2S3S4S5S6S7S8C1 C2 C3 C4 C5 C6 C7 C8P32 bits F(A,J)B寫(xiě)成8個(gè)6比特串DES

23、 的的F函數(shù)函數(shù)45n初始置換初始置換IPIP：對(duì)明文輸入進(jìn)行次序的打亂。對(duì)明文輸入進(jìn)行次序的打亂。n逆置換逆置換IPIP-1-1：n擴(kuò)展函數(shù)擴(kuò)展函數(shù)E E；（3232到到4848）n置換函數(shù)置換函數(shù)P P。DESDES中使用的特定函數(shù)中使用的特定函數(shù)46n初始置換初始置換IP：從表：從表3.2中看出中看出X的第的第58個(gè)比個(gè)比特是特是IP（X）的第一個(gè)比特；）的第一個(gè)比特；X的第的第50個(gè)比個(gè)比特是特是IP（X）的第二個(gè)比特）的第二個(gè)比特n逆置換逆置換IP-1；擴(kuò)展函數(shù)；擴(kuò)展函數(shù)E；置換函數(shù)；置換函數(shù)P。DES中使用的其它特定函數(shù)中使用的其它特定函數(shù)47 再看圖4.5和圖4.6，輸入算法的5

24、6比特密鑰首先經(jīng)過(guò)一個(gè)置換運(yùn)算，該置換由表3.4(a)給出，然后將置換后的56比特分為各為28比特的左、右兩半，分別記為C0和D0。在第i 輪分別對(duì)Ci-1和Di-1進(jìn)行左循環(huán)移位，所移位數(shù)由表3.4(c)給出。移位后的結(jié)果作為求下一輪子密鑰的輸入，同時(shí)也作為置換選擇2的輸入。通過(guò)置換選擇2產(chǎn)生的48比特的Ki，即為本輪的子密鑰，作為函數(shù)F(Ri-1,Ki)的輸入。其中置換選擇2由表3.4(b)定義。（見(jiàn)44頁(yè)表3.4）密鑰的產(chǎn)生密鑰的產(chǎn)生48從密鑰從密鑰K計(jì)算子密鑰計(jì)算子密鑰n 實(shí)際上，實(shí)際上，K是長(zhǎng)度為是長(zhǎng)度為64的位串，其中的位串，其中56位是密鑰，位是密鑰，8位是奇偶校驗(yàn)位（為了檢錯(cuò)）

25、，位是奇偶校驗(yàn)位（為了檢錯(cuò)），在密鑰編排的計(jì)算中，這些校驗(yàn)位可略去。在密鑰編排的計(jì)算中，這些校驗(yàn)位可略去。(1). 給定給定64位的密鑰位的密鑰K，放棄奇偶校驗(yàn)位，放棄奇偶校驗(yàn)位（8，16，64）并根據(jù)固定置換）并根據(jù)固定置換PC-1（見(jiàn)（見(jiàn)144頁(yè)圖頁(yè)圖4-4-9）來(lái)排列）來(lái)排列K中剩下的位。中剩下的位。我們寫(xiě)我們寫(xiě) PC-1(K)=C0D0其中其中C0由由PC-1（K）的前）的前28位組成；位組成；D0由由后后28位組成。位組成。49n(2)對(duì)對(duì)1=i=16，計(jì)算，計(jì)算Ci=LSi(Ci-1);Di=LSi(Di-1)LSi表示循環(huán)左移表示循環(huán)左移2或或1個(gè)位置，取決于個(gè)位置，取決于i的的

26、值。的的值。i=1,2,9和和16 時(shí)移時(shí)移1個(gè)位置，否則移個(gè)位置，否則移2位置。位置。Ki=PC-2(CiDi), PC-2為固定置。為固定置。n注：注：一共一共16輪，每一輪使用輪，每一輪使用K中中48位組成一個(gè)位組成一個(gè)48比特比特密鑰?？伤愠雒荑€。可算出16個(gè)表，第個(gè)表，第i個(gè)表中的元素可對(duì)應(yīng)上第個(gè)表中的元素可對(duì)應(yīng)上第i輪密鑰使用輪密鑰使用K中第幾比特！如：中第幾比特！如：第第7輪的表輪的表7：K7取取K中的比特情況：中的比特情況：52 57 11 1 26 59 10 34 44 51 25 199 41 3 2 50 35 36 43 42 33 60 1828 7 14 29 4

27、7 46 22 5 15 63 61 394 31 13 38 53 62 55 20 23 37 30 650DES的密鑰擴(kuò)展的密鑰擴(kuò)展各輪迭代一共使用16個(gè)加密子密鑰K1,K2,K16，它們依據(jù)所給56bit主密鑰K按下述擴(kuò)展算法產(chǎn)生：K(56bit)C0(28bit)D0(28bit)PC-1(置換)LS1LS1C1D1C16D16LS16LS16PC-2PC-2K1(48bit)K16(48bit)(選?。河猩釛?其中，其它, 216, 9 , 2 , 1, 1 iLSi51密鑰的產(chǎn)生密鑰的產(chǎn)生KPC-1C0D0LS1LS1C1D1LS2LS2PC-2K1C2D2LS3LS3PC-2K

28、2 LSi表示循環(huán)左移一個(gè)或兩個(gè)位置其中i為1，2，9，16移一個(gè)位置其余移兩個(gè)位置5257494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124141711241328156212319124261672720134152313747304051453344493956344642503629PC-1置換PC-2置換在前面密鑰擴(kuò)展的圖示中，置換PC-1與選取PC-2分別為：53DES的描述的描述注. 對(duì)i=1,2,Ci、Di分別是由C0、D0左

29、旋若干比特而得到，至i=16，剛好左旋了28比特位而回復(fù)當(dāng)初，即:C16=C0，D16=D0。 人們往往把主密鑰K順序地每7bit歸為一組，共計(jì)8組，每一組都按應(yīng)含奇數(shù)個(gè)1而在后面補(bǔ)上一個(gè)校驗(yàn)bit：0或1。如此，K被擴(kuò)展為一個(gè)長(zhǎng)是64的比特串K+，可用16位十六進(jìn)制數(shù)表示。 K+由安全信道傳送，其帶上8個(gè)校驗(yàn)比特（分別在第8位、16位、64位）就是為了對(duì)傳輸過(guò)程中可能出錯(cuò)進(jìn)行檢測(cè)和校對(duì)。54n 取取16進(jìn)制明文進(jìn)制明文X：0123456789ABCDEF 密鑰密鑰K為：為： 133457799BBCDFF1 去掉奇偶校驗(yàn)位以二進(jìn)制形式表示的密鑰是去掉奇偶校驗(yàn)位以二進(jìn)制形式表示的密鑰是0001

30、0010011010010101101111001001101101111011011111111000應(yīng)用應(yīng)用IP，我們得到：，我們得到：L0=11001100000000001100110011111111L1=R0=11110000101010101111000010101010然后進(jìn)行然后進(jìn)行16輪加密。最后對(duì)輪加密。最后對(duì)L16, R16使用使用IP-1得到密文：得到密文：85E813540F0AB405DES加密的一個(gè)例加密的一個(gè)例子子55DES的解密過(guò)程的解密過(guò)程u脫密過(guò)程采用與加密過(guò)程一樣的算法，只不過(guò)須將加密過(guò)程中16輪迭代所用的子密鑰(亦稱為輪密鑰)K1,K2,K16反序進(jìn)

31、行使用。(在前面講過(guò)的密鑰擴(kuò)展過(guò)程中若改LSi為則也就可以依次產(chǎn)生這逆序的子密鑰。)其它, 216, 9 , 2, 11, 0iiRSi56DES解密解密DES解密與加密使用相同的算法，但子密鑰的使用順序相反。解密與加密使用相同的算法，但子密鑰的使用順序相反。EE1K2KPXC加密EE2K1KCXP解密二重二重DES57DES的設(shè)計(jì)特色的設(shè)計(jì)特色在DES算法中，函數(shù) 是最基本的關(guān)鍵環(huán)節(jié)，其中用S-盒實(shí)現(xiàn)小塊的非線性變換，達(dá)到混亂目的；用置換P實(shí)現(xiàn)大塊的非線性變換，達(dá)到擴(kuò)散目的。置換P的設(shè)計(jì)使每層S-盒的4bit輸出進(jìn)入到下一層的4個(gè)不同S-盒；每個(gè)S-盒的輸入由分屬上一層中4個(gè)不同S-盒的輸出

32、構(gòu)成。322482322:FFFf58DES的設(shè)計(jì)特色的設(shè)計(jì)特色S-盒的設(shè)計(jì)準(zhǔn)則還沒(méi)有完全公開(kāi)。一些密碼學(xué)家懷疑美國(guó)NSA(the National Se-curity Agency)設(shè)計(jì)S-盒時(shí)隱藏了“陷門(mén)”，使得只有他們才知道破譯算法，但沒(méi)有證據(jù)能表明這一點(diǎn)。591976年，美國(guó)NSA披露了S-盒的下述幾條設(shè)計(jì)原則：每個(gè)S-盒的每一行是整數(shù)015的一個(gè)全排列；每個(gè)S-盒的輸出都不是其輸入的線性或仿射函數(shù)；改變?nèi)我籗-盒任意1bit的輸入，其輸出至少有2bit發(fā)生變化；DES的設(shè)計(jì)特色的設(shè)計(jì)特色60對(duì)任一S-盒的任意6bit輸入x,S(x)與S(x001100)至少有2bit不同；對(duì)任一S-

33、盒的任意6bit輸入x，及,0,1，都有S(x)S(x1100)；對(duì)任一S-盒，當(dāng)它的任一位輸入保持不變，其它5位輸入盡情變化時(shí)，所有諸4bit輸出中，0與1的總數(shù)接近相等。DES的設(shè)計(jì)特色的設(shè)計(jì)特色61DESDES的爭(zhēng)論的爭(zhēng)論nDES的核心是的核心是S盒，除此之外的計(jì)算是屬盒，除此之外的計(jì)算是屬線性的。線性的。S盒作為該密碼體制的非線性組盒作為該密碼體制的非線性組件對(duì)安全性至關(guān)重要。件對(duì)安全性至關(guān)重要。nS盒的設(shè)計(jì)準(zhǔn)則：盒的設(shè)計(jì)準(zhǔn)則：1. S盒不是它輸入變量的線性函數(shù)盒不是它輸入變量的線性函數(shù)2.改變改變S盒的一個(gè)輸入位至少要引起兩位盒的一個(gè)輸入位至少要引起兩位的輸出改變的輸出改變3. 對(duì)任

34、何一個(gè)對(duì)任何一個(gè)S盒，如果固定一個(gè)輸入盒，如果固定一個(gè)輸入比特，其它輸入變化時(shí)，輸出數(shù)字中比特，其它輸入變化時(shí)，輸出數(shù)字中0和和1的總數(shù)近于相等。的總數(shù)近于相等。62n公眾仍然不知道公眾仍然不知道S盒的構(gòu)造中是否還使用盒的構(gòu)造中是否還使用了進(jìn)一步的設(shè)計(jì)準(zhǔn)則（有陷門(mén)？）。了進(jìn)一步的設(shè)計(jì)準(zhǔn)則（有陷門(mén)？）。n密鑰長(zhǎng)度是否足夠？密鑰長(zhǎng)度是否足夠？n迭代的長(zhǎng)度？（迭代的長(zhǎng)度？（8、16、32？）？）634.DES4.DES的安全問(wèn)題的安全問(wèn)題DES的安全性完全依賴于所用的密鑰。自從其算法作為標(biāo)準(zhǔn)公開(kāi)以來(lái)，人們對(duì)它的安全性就有激烈的爭(zhēng)論。下面簡(jiǎn)要介紹20年來(lái)人們就其安全方面的一些主要研究結(jié)果。取反特性.

35、對(duì)于明文組M，密文組C和主密鑰K，若C=DESK(M)則 ，其中 , 和 分別為M,C和K的逐位取反。)(MDESCKMCK64證明. 若以K為主密鑰擴(kuò)展的16個(gè)加密子密鑰記為K1,K2,K16，則以 為主密鑰擴(kuò)展的16個(gè)加密子密鑰為注意到 ，不難看出注意到 ，不難看出 K1621,KKKbababa)1 ()1 (16, 2 , 1),(),(11iKRfKRfiiiibabababa)(1)1 (16, 2 , 1,11 iRLRLRLiiiiJiiiKDES的安全問(wèn)題的安全問(wèn)題65上述取補(bǔ)特性會(huì)使DES在選擇明文攻擊下所需工作量減少一半：攻擊者為破譯所使用的密鑰，選取兩個(gè)明密文對(duì) 與 ，

36、并對(duì)于可能密鑰 ，計(jì)算出DESK(M)=C。若C=C1或 ，則分別說(shuō)明K或 為實(shí)際密鑰。),(1CM),(2CM562FK K2CC DES的安全問(wèn)題的安全問(wèn)題66弱密鑰與半弱密鑰. 大多數(shù)密碼體制都有某些明顯的“壞密鑰”，DES也不例外。對(duì)于 ，若由K擴(kuò)展出來(lái)的加密子密鑰為：K1,K2,K15,K16，而由K擴(kuò)展出來(lái)的加密子密鑰卻是：K16,K15,K2,K1，即有 ，則稱K與K互為對(duì)合。下面我們分析一下 中到底有些什么樣的對(duì)合對(duì)？KKDESDES1562FKK、562FDES的安全問(wèn)題的安全問(wèn)題67在DES的主密鑰擴(kuò)展中，C0與D0各自獨(dú)立地循環(huán)移位來(lái)產(chǎn)生加(解)密子密鑰。若C0與D0分別

37、是00,11,10,01中任意一個(gè)的14次重復(fù)，則因這樣的C0與D0都對(duì)環(huán)移(無(wú)論左或右)偶數(shù)位具有自封閉性，故若 ，則由K擴(kuò)展出來(lái)的加密子密鑰為：K1,K2,K2,K2,K2,K2,K2,K2,K1,K1,K1,K1,K1,K1,K1,K2；KDCPC)(1001DES的安全問(wèn)題的安全問(wèn)題68把C0與D0各自左環(huán)移一位得C1與D1，設(shè) ，則由K擴(kuò)展出來(lái)的加密子密鑰為：K2,K1,K1,K1,K1,K1,K1,K1,K2,K2,K2,K2,K2,K2,K2,K1。因此，由上述C0、D0導(dǎo)致的K與K互為對(duì)合；實(shí)際上，除了這些以外，在 中似乎不再有其它的對(duì)合對(duì)了。DES的安全問(wèn)題的安全問(wèn)題KDCP

38、C)(1111562F69對(duì)于 ，若K是自己的對(duì)合，則稱K為DES的一個(gè)弱密鑰；若K存在異于自己的對(duì)合，則稱K為DES的一個(gè)半弱密鑰。顯然，C0與D0分別是00,11,10,01中任意一個(gè)的14次重復(fù)的情況共有42=16種，其中C0與D0分別是00,11中任意一個(gè)的14次重復(fù)的情況(計(jì)22=4種)對(duì)應(yīng)弱密鑰；剩下的(16-4=12種)對(duì)應(yīng)半弱密鑰。562FKDES的安全問(wèn)題的安全問(wèn)題70弱密鑰與半弱密鑰直接引起的“危險(xiǎn)”是在多重使用DES加密中，第二次加密有可能使第一次加密復(fù)原；另外，弱密鑰與半弱密鑰使得擴(kuò)展出來(lái)的諸加密子密鑰至多有兩種差異，如此導(dǎo)致原本多輪迭代的復(fù)雜結(jié)構(gòu)簡(jiǎn)化和容易分析。所幸在

39、總數(shù)256個(gè)可選密鑰中，弱密鑰與半弱密鑰所占的比例極小，如果是隨機(jī)選擇，(半)弱密鑰出現(xiàn)的概率很小，因而其存在性并不會(huì)危及DES的安全。DES的安全問(wèn)題的安全問(wèn)題71密文與明文、密文與密鑰的相關(guān)性. 人們的研究結(jié)果表明：DES的編碼過(guò)程可使每個(gè)密文比特都是所有明文比特和所有密鑰比特的復(fù)雜混合函數(shù)，而要達(dá)到這一要求至少需要DES的迭代：5輪。人們也用2-檢驗(yàn)證明：DES迭代8輪以后，就可認(rèn)為輸出和輸入不相關(guān)了。DES的安全問(wèn)題的安全問(wèn)題72密鑰搜索機(jī). 在對(duì)DES安全性的批評(píng)意見(jiàn)中，較一致的看法是DES的密鑰太短！其長(zhǎng)度56bit，致使密鑰量?jī)H為2561017，不能抵抗窮搜攻擊，事實(shí)證明的確如此

40、。1997年1月28日，美國(guó)RSA數(shù)據(jù)安全公司在RSA安全年會(huì)上發(fā)布了一項(xiàng)“秘密密鑰挑戰(zhàn)”競(jìng)賽，分別懸賞1000美金、5000美金和10000美金用于攻破不同長(zhǎng)度的RC5密碼算法，同時(shí)還懸賞10000美金破譯密鑰長(zhǎng)度為56bit的DES。RSA公司發(fā)起這場(chǎng)挑戰(zhàn)賽是為了調(diào)查在Internet上分布式計(jì)算的能力，并測(cè)試不同密鑰長(zhǎng)度的RC5算法和密鑰長(zhǎng)度為56bit的DES算法的相對(duì)強(qiáng)度。DES的安全問(wèn)題的安全問(wèn)題73結(jié)果是：密鑰長(zhǎng)度為40bit和48bit的RC5算法被攻破；美國(guó)克羅拉多州的程序員Verser從1997年3月13日起用了96天的時(shí)間，在Internet上數(shù)萬(wàn)名志愿者的協(xié)同工作下，于

41、1997年6月17日成功地找到了DES的密鑰，獲得了RSA公司頒發(fā)的10000美金的獎(jiǎng)勵(lì)。這一事件表明，依靠Internet的分布式計(jì)算能力，用窮搜方法破譯DES已成為可能。因此，隨著計(jì)算機(jī)能力的增強(qiáng)與計(jì)算技術(shù)的提高，必須相應(yīng)地增加密碼算法的密鑰長(zhǎng)度。DES的安全問(wèn)題的安全問(wèn)題741977年，Diffe和Hellman曾建議制造每秒能測(cè)試106個(gè)密鑰的VLSI芯片，將這樣的100104個(gè)芯片并行操作搜索完整個(gè)密鑰空間大約需1天時(shí)間。他們估計(jì)制造這樣一臺(tái)機(jī)器需耗資大約2000萬(wàn)美金。1993年，Wiener給出了一個(gè)詳細(xì)的設(shè)計(jì)密鑰搜索機(jī)的方案。他建議制造每秒能測(cè)試5107個(gè)密鑰的芯片，基于這種芯

42、片的機(jī)器將流水作業(yè)，使得16次加密同時(shí)DES的安全問(wèn)題的安全問(wèn)題75發(fā)生。目前制造這種芯片每片需耗資10.5美金，耗資10萬(wàn)美金能建造一個(gè)由5760個(gè)芯片組成的框架，這使得搜索一個(gè)密鑰平均大約需要1.5天。使用十個(gè)這樣框架的機(jī)器將耗資100萬(wàn)美金，搜索一個(gè)密鑰平均大約3.5小時(shí)。據(jù)新華社1998年7月22日消息,電子邊境基金學(xué)會(huì)(EFF)使用一臺(tái)25萬(wàn)美金的電腦在56小時(shí)內(nèi)破譯了56位密鑰的DES。DES的安全問(wèn)題的安全問(wèn)題76DES的攻擊方法.目前攻擊DES的主要方法有時(shí)間-空間權(quán)衡攻擊、差分攻擊、線性攻擊和相關(guān)密鑰攻擊等方法，在這些攻擊方法中，線性攻擊方法是最有效的一種方法。除了上面介紹的

43、幾個(gè)方面外，20年來(lái)人們還發(fā)表了許多有關(guān)DES的其它方面的研究文章，這些研究不僅深入分析、檢驗(yàn)了DES的各個(gè)方面，而且也大大地推動(dòng)了密碼學(xué)的研究和發(fā)展。DES的安全問(wèn)題的安全問(wèn)題775.DES的強(qiáng)化變形的強(qiáng)化變形利用隨機(jī)因素對(duì)8個(gè)S-盒的排列順序進(jìn)行置換. 隨意選取一個(gè)正整數(shù)，比如今天的日期：1106。對(duì)于k=8,7,2，依次求出1106 (mod k)：(2,0,2,1,2,2,0) （注意到2,3,8的最小公倍數(shù)為357 8=840，進(jìn)行上述計(jì)算時(shí)可將1106用1106(mod 840)=266替代）。785.DES的強(qiáng)化變形的強(qiáng)化變形按照上面的數(shù)組求出18的一個(gè)全排列：1（其實(shí)，由已知全

44、排列34165827也可以求出對(duì)應(yīng)的數(shù)組：34165827( , , , , , , )）。按照上面求得的全排列，把8個(gè)S-盒重排成：S3,S4,S1,S6,S5,S8,S2,S7。12312341234152341652341652734165827202 1 2 20795.DES的強(qiáng)化變形的強(qiáng)化變形u三重DES(the Triple DES). 為了克服DES之56bit密鑰長(zhǎng)度較短的弱點(diǎn)，人們想到采用下述以DES作為基本環(huán)節(jié)的加密方式：稱之為三重DES。三重DES使進(jìn)行密鑰窮搜攻擊的復(fù)雜度從O(256)增至O(2112)，并且采用一定的技巧編程，三重DES的加密時(shí)間僅為DES的2倍、而

45、不是通常想象的3倍！)(211121KKCDESDESDESMKKK加密變換80 為了提高DES的安全性，并利用實(shí)現(xiàn)DES的現(xiàn)有軟硬件，可將DES算法在多密鑰下多重使用。 二重DES是多重使用DES時(shí)最簡(jiǎn)單的形式，如圖4.8所示。其中明文為P，兩個(gè)加密密鑰為K1和K2，密文為： 解密時(shí)，以相反順序使用兩個(gè)密鑰：21 KKCEEP12 KKPDDC二重二重DES81圖4.8 二重DES二重二重DES82 因此，二重DES所用密鑰長(zhǎng)度為112比特，強(qiáng)度極大地增加。然而，假設(shè)對(duì)任意兩個(gè)密鑰K1和K2，能夠找出另一密鑰K3，使得213 KKKEEPEP二重二重DES83 那么，二重DES以及多重DES

46、都沒(méi)有意義，因?yàn)樗鼈兣c56比特密鑰的單重DES等價(jià)，好在這種假設(shè)對(duì)DES并不成立。將DES加密過(guò)程64比特分組到64比特分組的映射看作一個(gè)置換，如果考慮264個(gè)所有可能的輸入分組，則密鑰給定后，DES的加密將把每個(gè)輸入分組映射到一個(gè)惟一的輸出分組。否則，如果有兩個(gè)輸入分組被映射到同一分組，則解密過(guò)程就無(wú)法實(shí)施。對(duì)264個(gè)輸入分組，總映射個(gè)數(shù)為 。2064102!10二重二重DES84 另一方面，對(duì)每個(gè)不同的密鑰，DES都定義了一個(gè)映射，總映射數(shù)為2561017。因此，可假定用兩個(gè)不同的密鑰兩次使用DES，可得一個(gè)新映射，而且這一新映射不出現(xiàn)在單重DES定義的映射中。 這一假定已于1992年被證

47、明。所以使用二重DES產(chǎn)生的映射不會(huì)等價(jià)于單重DES加密。但對(duì)二重DES有以下一種稱為中途相遇攻擊的攻擊方案，這種攻擊不依賴于DES的任何特性，因而可用于攻擊任何分組密碼。其基本思想如下：二重二重DES85如果有那么（見(jiàn)圖4.8）21 KKCEEP12 KKXEPDC二重二重DES86 如果已知一個(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

48、對(duì)P兩次加密，若結(jié)果等于C，就可確定K1和K2是所要找的密鑰。二重二重DES87 對(duì)已知的明文P，二重DES能產(chǎn)生264個(gè)可能的密文,而可能的密鑰個(gè)數(shù)為2112，所以平均來(lái)說(shuō)，對(duì)一個(gè)已知的明文，有2112/264=248個(gè)密鑰可產(chǎn)生已知的密文。而再經(jīng)過(guò)另外一對(duì)明文密文的檢驗(yàn)，誤報(bào)率將下降到248-64=2-16。所以在實(shí)施中途相遇攻擊時(shí)，如果已知兩個(gè)明文密文對(duì)，則找到正確密鑰的概率為1-2-16。二重二重DES88 抵抗中途相遇攻擊的一種方法是使用3個(gè)不同的密鑰做3次加密，從而可使已知明文攻擊的代價(jià)增加到2112。然而，這樣又會(huì)使密鑰長(zhǎng)度增加到563=168比特，因而過(guò)于笨重。一種實(shí)用的方法是

49、僅使用兩個(gè)密鑰做3次加密，實(shí)現(xiàn)方式為加密|解密|加密，簡(jiǎn)記為EDE( encryptdecryptencrypt)，見(jiàn)圖4.9，即：兩個(gè)密鑰的三重兩個(gè)密鑰的三重DES121 KKKCEDEP89圖4.9 兩個(gè)密鑰的三重DES90兩個(gè)密鑰的三重兩個(gè)密鑰的三重DESDES三重三重DESED1K2KPAB加密DE1K2KCBA解密E1KCD1KP91 此方案已在密鑰管理標(biāo)準(zhǔn)ANS X.917和ISO 8732中被采用。92 三個(gè)密鑰的三重DES密鑰長(zhǎng)度為168比特，加密方式為 令K3=K2或K1=K2，則變?yōu)橐恢谼ES。三個(gè)密鑰的三重DES已在因特網(wǎng)的許多應(yīng)用（如PGP和S/MIME）中被采用。三個(gè)

50、密鑰的三重三個(gè)密鑰的三重DES321 KKKCEDEP93三個(gè)密鑰的三重三個(gè)密鑰的三重DESDES三重三重DESED1K2KPAB加密DE3K2KCBA解密E3KCD1KP94DES的軟件實(shí)現(xiàn)的軟件實(shí)現(xiàn)u用8086/8088宏匯編語(yǔ)言編寫(xiě)DES程序的技巧和要點(diǎn). 將第16輪迭代結(jié)果L16R16的交換與置換IP-1復(fù)合成一個(gè)新的置換(記為IP)：在R16L16中,大于32的位置t應(yīng)出現(xiàn)在L16里，對(duì)應(yīng)在L16R16里便是t-32；32以內(nèi)的位置t應(yīng)出現(xiàn)在R16里，對(duì)應(yīng)在L16R16里便是t+32。8 40 16 48 24 56 32 64 7 39 15 47 23 55 31 63 6 38

51、 14 46 22 54 30 62 5 37 13 45 21 53 29 61 4 36 12 44 20 52 28 60 3 35 11 43 19 51 27 59 2 34 10 42 18 50 26 58 1 33 9 41 17 49 25 57 95DES的軟件實(shí)現(xiàn)的軟件實(shí)現(xiàn)IP,IP,E,P,PC-1,PC-2基于同一個(gè)底層程序來(lái)實(shí)現(xiàn)：該底層程序主要應(yīng)用諸移位指令來(lái)完成數(shù)據(jù)比特的重新選取。按照000000(0,0)，000001(1,0)，011110(0,15)，011111(1,15)100000(2,0)，100001(3,0)，111110(2,15)，111111(3,15)重排每個(gè)S-盒數(shù)