1、數(shù)據(jù)加密標(biāo)準(zhǔn)數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)應(yīng)用密碼學(xué)應(yīng)用密碼學(xué)背景資料背景資料1973年年NBS國家標(biāo)準(zhǔn)局國家標(biāo)準(zhǔn)局 （NIST國家標(biāo)準(zhǔn)與技術(shù)研究所）國家標(biāo)準(zhǔn)與技術(shù)研究所）算法要求：算法要求： 算法公開，安全性依賴于密鑰而不是算法算法公開，安全性依賴于密鑰而不是算法 算法應(yīng)能測試和驗(yàn)證算法應(yīng)能測試和驗(yàn)證 不同的設(shè)備可以相互通信不同的設(shè)備可以相互通信背景資料背景資料19681974，IBM研制研制1976 被定為聯(lián)邦標(biāo)準(zhǔn)被定為聯(lián)邦標(biāo)準(zhǔn) 并命名為并命名為DES(Data Encryption Standard)1981、1987、1993 分別被分別被NIST再次認(rèn)證再次認(rèn)證Feistel網(wǎng)絡(luò)網(wǎng)絡(luò)加密過程

2、：加密過程：1. 把一個(gè)分組分成長度相等的把一個(gè)分組分成長度相等的 左右兩部份：左右兩部份：L,R2. 進(jìn)行進(jìn)行n次疊代，次疊代， 其第其第i 輪的輸出取決于前一輪的輸出：輪的輸出取決于前一輪的輸出： Li=Ri-1 Ri=Li -1 (Ri-1，Ki) Ki是第是第i輪使用的子密鑰輪使用的子密鑰 是任意的輪函數(shù)是任意的輪函數(shù)3. 最后交換左右兩部分最后交換左右兩部分Feistel網(wǎng)絡(luò)網(wǎng)絡(luò)解密過程與加密過程的區(qū)別解密過程與加密過程的區(qū)別: 子密鑰的順序正好相反：子密鑰的順序正好相反：加密：加密： K1, K2, K3, K(n-1), Kn 解密：解密： Kn, K(n-1), K3, K2,

3、 K1L0R0R2L2L2=R1R2L1=R0R1(R0,K1)(R1,K2)K1K2加密加密R2L2L0R0R0L0L2R0(L2,K2)(R0,K1)K2K1解密解密1010,11100011,11100001,10011111,1010加密加密1010,11100011,11100100,11011000,10011000,10010100,11010011,11101000,10010010,01110111,00110001,10011111,1010加密加密0100,11011000,10011111,10100001,1001解密解密0100,11011000,10011010,

4、11100011,11100011,11101010,11101000,10010011,11100111,00110010,01111111,10100001,1001解密解密采用采用Feistel網(wǎng)絡(luò)的著名的分組密碼網(wǎng)絡(luò)的著名的分組密碼DESFEAL：由日本電報(bào)電話公司的：由日本電報(bào)電話公司的 Akihiro Shimizu 和和 Shooji Miyaguchi 設(shè)計(jì)設(shè)計(jì) LOKI： 由澳大利亞人于由澳大利亞人于 1990 年首先提出作為年首先提出作為DES的一種潛的一種潛在替換算法在替換算法 GOST 是前蘇聯(lián)設(shè)計(jì)的分組密碼算法是前蘇聯(lián)設(shè)計(jì)的分組密碼算法 CAST 由加拿大的由加拿大的

5、 C.Adams 和和 S.Tavares 設(shè)計(jì)設(shè)計(jì) Blowfish 由由 Bruce Schneier 設(shè)計(jì)設(shè)計(jì) DES的參數(shù)：的參數(shù)：分組長度：分組長度：64位位密鑰長度：密鑰長度：64位位 其中第其中第8，16，24，56,64為校驗(yàn)位為校驗(yàn)位有效密鑰長度：有效密鑰長度：56位位密鑰空間：密鑰空間：256DES的加密過程：的加密過程： 64位明文位明文初始置換初始置換乘積變換乘積變換逆初始變換逆初始變換64位密文位密文初始置換初始置換58504234261810260524436282012462544638302214664564840322416857494133251791595

6、143352719113615345372921135635547393123157逆初始置換逆初始置換40848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725乘積變換乘積變換16次疊代的次疊代的Feistel網(wǎng)絡(luò)網(wǎng)絡(luò)需要解決的問題：需要解決的問題： 1. 函數(shù)的構(gòu)造函數(shù)的構(gòu)造 2. 把把64位主密鑰轉(zhuǎn)換為位主密鑰轉(zhuǎn)換為16個(gè)個(gè)48位的子密鑰位的子密鑰函數(shù)函數(shù) P盒置換盒置換子密鑰子密鑰Ki48bit48bit32

7、bit32bit擴(kuò)展置換擴(kuò)展置換 下圖顯示了擴(kuò)展置換，有時(shí)它也叫做下圖顯示了擴(kuò)展置換，有時(shí)它也叫做E盒。對每個(gè)盒。對每個(gè)4位輸入分組，第位輸入分組，第1和第和第4位分別表示輸出分組中的兩位分別表示輸出分組中的兩位，而第位，而第2和第和第3位分別表示輸出分組中的一位。位分別表示輸出分組中的一位。擴(kuò)展置換擴(kuò)展置換下表是從下表是從32位到位到48位的擴(kuò)展置換，給出了哪一輸出位對應(yīng)于位的擴(kuò)展置換，給出了哪一輸出位對應(yīng)于哪一輸入位。例如，處于輸入分組中第哪一輸入位。例如，處于輸入分組中第3位的位置的位移到位的位置的位移到了輸出分組中第了輸出分組中第4位的位置，而輸入分組中第位的位置，而輸入分組中第21位

8、的位置的位的位置的位移到了輸出分組中第位移到了輸出分組中第30和第和第32位的位置。位的位置。盡管輸出分組大于輸入分組，但每一個(gè)輸入分組產(chǎn)生唯一的盡管輸出分組大于輸入分組，但每一個(gè)輸入分組產(chǎn)生唯一的輸出分組。輸出分組。3212345456789891011121312131415161716171819202120212223242524252627282928293031321S-S-盒代替盒代替S1S2S3S4S5S6S7S848位輸入位輸入32位輸出位輸出6bit4bitSi: 416矩陣矩陣S10123456789abcdef014413121511831061259071015741

9、42131106121195382411481362111512973105031512824917511314100613b0b1b2b3b4b5行號：行號：03列號：列號：015S盒的設(shè)計(jì)準(zhǔn)則盒的設(shè)計(jì)準(zhǔn)則沒有一個(gè)沒有一個(gè)S的輸出位是接近輸入位的線性函數(shù)的輸出位是接近輸入位的線性函數(shù)如果將輸入位的最左及最右端的位固定，變化中間如果將輸入位的最左及最右端的位固定，變化中間的的4位，每個(gè)可能的位，每個(gè)可能的4位數(shù)出只能得到一次位數(shù)出只能得到一次如果如果s盒的兩個(gè)輸入僅有盒的兩個(gè)輸入僅有1位的差異，則輸出至少必位的差異，則輸出至少必須有須有2位不同位不同如果如果s盒的兩個(gè)輸入僅有中間盒的兩個(gè)輸入僅

10、有中間2位不同，則輸出至少位不同，則輸出至少必須有必須有2位不同位不同如果如果s盒的兩個(gè)輸入僅前盒的兩個(gè)輸入僅前2位不同，后位不同，后2位已知則輸出位已知則輸出必不同必不同對于輸入之間的任何非零的對于輸入之間的任何非零的6位差分，位差分，32對中至多有對中至多有8對顯示出的差分導(dǎo)致了相同的輸出差分對顯示出的差分導(dǎo)致了相同的輸出差分P盒置換盒置換 S盒代替運(yùn)算后的盒代替運(yùn)算后的32位輸出依照位輸出依照P盒進(jìn)行置換。該置換把每盒進(jìn)行置換。該置換把每輸入位映射到輸出位，任意一位不能被映射兩次，也不能輸入位映射到輸出位，任意一位不能被映射兩次，也不能被略去，這個(gè)置換叫做直接置換。下表給出了每位移到的被

11、略去，這個(gè)置換叫做直接置換。下表給出了每位移到的位置。例如，第位置。例如，第21位移到了第位移到了第4位處，同時(shí)第位處，同時(shí)第4位移到了第位移到了第31位處。最后，將位處。最后，將P盒置換的結(jié)果與最初的盒置換的結(jié)果與最初的64位分組的左位分組的左半部分異或，然后左、右半部分交換，接著開始另一輪。半部分異或，然后左、右半部分交換，接著開始另一輪。1672021291228171152326518311028241432273919133062211425子密鑰生成子密鑰生成PC-1密鑰置換密鑰置換PC-15749413325179158504234261810259514335271911360

12、524436635547393123157625446383022146615345372921135282012464比特的密鑰比特的密鑰K，經(jīng)過經(jīng)過PC-1后，生成后，生成56比特的串。其下比特的串。其下標(biāo)如表所示：標(biāo)如表所示： PC-2壓縮置換壓縮置換PC-21417112415328156211023191242681672720132415231374755304051453348444939563453464250362932每輪移位的位數(shù)每輪移位的位數(shù)迭代順序迭代順序12345678910111213141516左移位數(shù)左移位數(shù)1122222212222221DES解密解密加密和

13、解密可使用相同的算法。加密和解密可使用相同的算法。DES使得用相同的函數(shù)來加密或解密每個(gè)分組成為使得用相同的函數(shù)來加密或解密每個(gè)分組成為可能，二者的唯一不同之處是密鑰的次序相反。這可能，二者的唯一不同之處是密鑰的次序相反。這就是說，如果各輪的加密密鑰分別是就是說，如果各輪的加密密鑰分別是K1，K2，K3，K16, 那么解密密鑰就是那么解密密鑰就是K16，K15，K14，K1。差分密碼分析差分密碼分析1900年年Eli Biham 和和Adi Shamir 提出了差分密碼分提出了差分密碼分析。析。利用這種方法，利用這種方法， Eli Biham 和和Adi Shamir 對對DES算算法進(jìn)行了選

14、擇明文攻擊，比窮舉攻擊有效法進(jìn)行了選擇明文攻擊，比窮舉攻擊有效對于對于DES的差分密碼分析，如果選擇明文攻擊，需的差分密碼分析，如果選擇明文攻擊，需要要247對于對于DES的差分密碼分析，如果已知明文攻擊，需的差分密碼分析，如果已知明文攻擊，需要要255線性密碼分析線性密碼分析線性密碼分析是線性密碼分析是Mitsuru Matsui提出的提出的是一種已知明文攻擊是一種已知明文攻擊如果將明文的一些位、密文的一些位進(jìn)行異或運(yùn)算如果將明文的一些位、密文的一些位進(jìn)行異或運(yùn)算，然后再對這兩個(gè)結(jié)果異或，那么將得到一個(gè)位，然后再對這兩個(gè)結(jié)果異或，那么將得到一個(gè)位，這一位是將密鑰的一些位進(jìn)行異或運(yùn)算的結(jié)果這一

15、位是將密鑰的一些位進(jìn)行異或運(yùn)算的結(jié)果對于對于DES的線性密碼分析，已知明文攻擊數(shù)為的線性密碼分析，已知明文攻擊數(shù)為243X X1717Y Y33Y Y88Y Y1414Y Y25=25=K Ki,26i,261/2-5/161/2-5/16 DES的安全強(qiáng)度的安全強(qiáng)度 密鑰長度問題密鑰長度問題56-bit 密鑰有密鑰有256 = 72,057,584,037,927,936 7.2億億億億之多之多技術(shù)進(jìn)步使窮舉搜索成為可能技術(shù)進(jìn)步使窮舉搜索成為可能1997年年1月月28日，日，RSA公司發(fā)起破譯公司發(fā)起破譯RC4、RC5、MD2、MD5，以及，以及DES的活動，破譯的活動，破譯DES獎勵獎勵1

16、0000美金。明文是：美金。明文是：Strong cryptography makes the world a safer place. 結(jié)果僅搜索了結(jié)果僅搜索了24.6%的密鑰空間便得到結(jié)果，耗時(shí)的密鑰空間便得到結(jié)果，耗時(shí)96天。天。1998年在一臺專用機(jī)上年在一臺專用機(jī)上(EFF)只要幾天時(shí)間即可只要幾天時(shí)間即可 1999年在超級計(jì)算機(jī)上只要年在超級計(jì)算機(jī)上只要22小時(shí)小時(shí)! S-box問題，其設(shè)計(jì)標(biāo)準(zhǔn)沒有公開問題，其設(shè)計(jì)標(biāo)準(zhǔn)沒有公開 線性密碼分析攻擊問題，線性密碼分析攻擊問題，DES不能抵御線形分析不能抵御線形分析二重二重DES 為了提高為了提高DES的安全性，并利用實(shí)現(xiàn)的安全性，并利用

17、實(shí)現(xiàn)DES的現(xiàn)有軟硬件，的現(xiàn)有軟硬件，可將可將DES算法在多密鑰下多重使用。算法在多密鑰下多重使用。 二重二重DES是多重使用是多重使用DES時(shí)最簡單的形式，如圖時(shí)最簡單的形式，如圖3.8所示。所示。其中明文為其中明文為P，兩個(gè)加密密鑰為兩個(gè)加密密鑰為K1和和K2，密文為：密文為： 解密時(shí)，以相反順序使用兩個(gè)密鑰：解密時(shí)，以相反順序使用兩個(gè)密鑰：21 KKCEEP12 KKPDDC二重二重DES對二重對二重DES的中途相遇攻擊的中途相遇攻擊21 KKCEEP12 KKXEPDC對二重對二重DES的中途相遇攻擊的中途相遇攻擊 如果已知一個(gè)明文密文對如果已知一個(gè)明文密文對(P,C)，攻擊的實(shí)施可如

18、下攻擊的實(shí)施可如下進(jìn)行：進(jìn)行： 首先，用首先，用256個(gè)所有可能的個(gè)所有可能的K1對對P加密，將加密結(jié)果加密，將加密結(jié)果存入一表并對表按存入一表并對表按X排序，排序， 然后用然后用256個(gè)所有可能的個(gè)所有可能的K2對對C解密，在上述表中查解密，在上述表中查找與找與C解密結(jié)果相匹配的項(xiàng)，如果找到，則記下相應(yīng)解密結(jié)果相匹配的項(xiàng)，如果找到，則記下相應(yīng)的的K1和和K2。 最后再用一新的明文密文對最后再用一新的明文密文對(P,C)檢驗(yàn)上面找到的檢驗(yàn)上面找到的K1和和K2，用用K1和和K2對對P兩次加密，若結(jié)果等于兩次加密，若結(jié)果等于C，就可確定就可確定K1和和K2是所要找的密鑰。是所要找的密鑰。對二重對二