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

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

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

3、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日開始生效。1.數(shù)據(jù)加密標準數(shù)據(jù)加密標準DES的產(chǎn)生的產(chǎn)生6 規(guī)定每隔5年由美國國家保密局（national security agency, NSA）作出評估，并重新批準它是否繼續(xù)作為聯(lián)邦加密標準。最近

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

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

6、具有置換確定的，具有置換和代換的運算。和代換的運算。 (3)置換函數(shù)置換函數(shù)SW(4)復(fù)合函數(shù)復(fù)合函數(shù)fk2(5)初始置換初始置換IP的逆置換的逆置換IP-12.2.簡化的簡化的DESDES9 加密加密S-DESS-DES方案示意圖方案示意圖10bit密鑰 解密解密8bit明文P108bit明文IP移位IP-1P8fkfkSWSW移位P8fkfkIPIP-18bit密文8bit密文K2K2K1K110nIP-1*fk2*SW*fk1*IP也可寫為也可寫為密文密文=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對對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)生的兩個子密鑰分別為兩個子密鑰分別為K1=(1 0 1 0 0 1 0 0),K2=(0 1 0 0 0 0 1 1)12(2) S-DES的加密運算的加密運算: 初始置換用初始置換用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 易見易見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位集的一個映射位集的一個映射, 并不要求是并不要求是1-1的。的。SK為子密鑰。為子密鑰。 對映射對映射F來說：來說： 首先輸入是一個首先輸入是一個4-位數(shù)（位數(shù)（n1,n2,n3,n4），第一步），第一步運算是擴張運算是擴張/置換（置換（E/P）運算：）運

10、算： E/P 4 1 2 3 2 3 4 1 事實上，它的直觀表現(xiàn)形式為：事實上，它的直觀表現(xiàn)形式為： n4 n1 n2 n3 n2 n3 n4 n1168-bit子密鑰：子密鑰： K1=(k11,k12,k13,k14,k15,k16,k17,k18),然后與然后與E/P的結(jié)果作異或運算得：的結(jié)果作異或運算得：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 上述第一行輸入進上述第一行輸入進S-盒盒S0，產(chǎn)生，產(chǎn)生2-位的輸

11、出；位的輸出；第二行的第二行的4位輸入進位輸入進S盒盒S1，產(chǎn)生，產(chǎn)生2-位的輸出。位的輸出。17兩個兩個S盒按如下定義：盒按如下定義：2313312001232301321032100S3012010331023210321032101S18S盒按下述規(guī)則運算：盒按下述規(guī)則運算： 將第將第1和第和第4的輸入比特做為的輸入比特做為2- bit數(shù)，指示為數(shù)，指示為S盒的一個行；將第盒的一個行；將第2和第和第3的輸入比特做為的輸入比特做為S盒的盒的一個列。如此確定為一個列。如此確定為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的安全性分析的安全性分析對10 bit密鑰的強行攻擊是可行的密鑰空間：210=1024密碼分析：利用已知明文攻擊：已知: 明文（p1,p2,p8), 及對應(yīng)的密文（c1,c2,c8),未

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

14、先是一個初始置換IP，用于重排明文分組的64比特數(shù)據(jù)。然后是具有相同功能的16輪變換，每輪中都有置換和代換運算，第16輪變換的輸出分為左右兩半，并被交換次序。最后再經(jīng)過一個逆初始置換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比特密鑰的方法。密鑰首先通過一個置換函數(shù)，然后，對加密過程的每一輪，通過一個左循環(huán)移位和一個置換產(chǎn)生一個子密鑰。其中每輪的置換都相同，但由于密鑰被重復(fù)迭代，所以產(chǎn)生的每輪子密鑰

15、不相同。25DES加密算法描述加密算法描述64比特明文初始置換第1輪第2輪第16輪左右交換初始逆置換64比特密文56比特密鑰置換選擇1左循環(huán)移位置換選擇11K左循環(huán)移位置換選擇12K左循環(huán)移位置換選擇116KDES加密算法框圖加密算法框圖26DES一輪加密的簡圖一輪加密的簡圖Li-1 Ri-1F+Li RiKi27 DES加加密過程密過程描述描述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的圖示中，擴展置換（選擇運算）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置換運算P的定義為：32輪結(jié)構(gòu)輪結(jié)構(gòu)Des加密算法的

17、輪結(jié)構(gòu)1iL32比特1iR32比特擴展/置換（E表）XOR代換/選擇（S盒）置換(p)XORiRiL484832321iC28比特1iD28比特左移位左移位置換選擇2iDiCiK33 首先看圖的左半部分。將64比特的輪輸入分成各為32比特的左、右兩半，分別記為L和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)的計算過程的計算過程 36每個每個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以長以長度為度為3232的比特

19、串的比特串A=RA=R（32bits32bits）作第一個輸）作第一個輸入，以長度為入，以長度為4848的比特串變元的比特串變元J=K(48bits)J=K(48bits)作為第二個輸入。產(chǎn)生的輸出為長度為作為第二個輸入。產(chǎn)生的輸出為長度為3232的的位串。位串。(1)(1)對第一個變元對第一個變元A A，由給定的擴展函數(shù)，由給定的擴展函數(shù)E E，將其擴展成將其擴展成4848位串，位串，E E（A A）(2)(2)計算計算E E（A A）+J+J，并把結(jié)果寫成連續(xù)的，并把結(jié)果寫成連續(xù)的8 8個個6 6位串位串,B=b,B=b1 1b b2 2b b3 3b b4 4b b5 5b b6 6b

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

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

22、行和列選定后，得到其交叉位置的十進制數(shù)，將這個數(shù)表示為4位二進制數(shù)即得這一S盒的輸出。例如，S1 的輸入為011001，行選為01（即第1行），列選為1100（即第12列），行列交叉位置的數(shù)為9，其4位二進制表示為1001，所以S1的輸出為1001。S盒的每一行定義了一個可逆代換，圖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寫成8個6比特串DES

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

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

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

26、值。的的值。i=1,2,9和和16 時移時移1個位置，否則移個位置，否則移2位置。位置。Ki=PC-2(CiDi), PC-2為固定置。為固定置。n注：注：一共一共16輪，每一輪使用輪，每一輪使用K中中48位組成一個位組成一個48比特比特密鑰?？伤愠雒荑€?？伤愠?6個表，第個表，第i個表中的元素可對應(yīng)上第個表中的元素可對應(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的密鑰擴展的密鑰擴展各輪迭代一共使用16個加密子密鑰K1,K2,K16，它們依據(jù)所給56bit主密鑰K按下述擴展算法產(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)左移一個或兩個位置其中i為1，2，9，16移一個位置其余移兩個位置5257494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124141711241328156212319124261672720134152313747304051453344493956344642503629PC-1置換PC-2置換在前面密鑰擴展的圖示中，置換PC-1與選取PC-2分別為：53DES的描述的描述注. 對i=1,2,Ci、Di分別是由C0、D0左

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

47、明。所以使用二重DES產(chǎn)生的映射不會等價于單重DES加密。但對二重DES有以下一種稱為中途相遇攻擊的攻擊方案，這種攻擊不依賴于DES的任何特性，因而可用于攻擊任何分組密碼。其基本思想如下：二重二重DES85如果有那么（見圖4.8）21 KKCEEP12 KKXEPDC二重二重DES86 如果已知一個明文密文對(P,C)，攻擊的實施可如下進行：首先，用256個所有可能的K1對P加密，將加密結(jié)果存入一表并對表按X排序，然后用256個所有可能的K2對C解密，在上述表中查找與C解密結(jié)果相匹配的項，如果找到，則記下相應(yīng)的K1和K2。最后再用一新的明文密文對(P,C)檢驗上面找到的K1和K2，用K1和K2

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

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

50、密鑰的三重三個密鑰的三重DES321 KKKCEDEP93三個密鑰的三重三個密鑰的三重DESDES三重三重DESED1K2KPAB加密DE3K2KCBA解密E3KCD1KP94DES的軟件實現(xiàn)的軟件實現(xiàn)u用8086/8088宏匯編語言編寫DES程序的技巧和要點. 將第16輪迭代結(jié)果L16R16的交換與置換IP-1復(fù)合成一個新的置換(記為IP)：在R16L16中,大于32的位置t應(yīng)出現(xiàn)在L16里，對應(yīng)在L16R16里便是t-32；32以內(nèi)的位置t應(yīng)出現(xiàn)在R16里，對應(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的軟件實現(xiàn)的軟件實現(xiàn)IP,IP,E,P,PC-1,PC-2基于同一個底層程序來實現(xiàn)：該底層程序主要應(yīng)用諸移位指令來完成數(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)重排每個S-盒數(shù)