數(shù)據(jù)加密標(biāo)準(zhǔn)講義(共45頁(yè)).ppt

1、數(shù)據(jù)加密標(biāo)準(zhǔn)數(shù)據(jù)加密標(biāo)準(zhǔn)（Data Encryption Standard,DES)序列密碼和分組密碼序列密碼和分組密碼n一次只對(duì)明文中的單個(gè)位（有時(shí)對(duì)字節(jié)）運(yùn)一次只對(duì)明文中的單個(gè)位（有時(shí)對(duì)字節(jié)）運(yùn)算的算法稱為算的算法稱為序列算法（序列算法（stream algorithm）或序列密碼（或序列密碼（stream cypher）n另一類算法是對(duì)明文的一組位進(jìn)行運(yùn)算，這另一類算法是對(duì)明文的一組位進(jìn)行運(yùn)算，這些位稱為些位稱為分組（分組（block），），相應(yīng)的算法稱為相應(yīng)的算法稱為分組算法（分組算法（block algorithm）或分組密碼）或分組密碼（block cypher）。）。背景背景發(fā)明

2、人：美國(guó)發(fā)明人：美國(guó)IBM公司公司 W. Tuchman 和和 C. Meyer 1971-1972年研制成功年研制成功基礎(chǔ)：基礎(chǔ)：1967年美國(guó)年美國(guó)Horst Feistel提出的理論提出的理論產(chǎn)生：美國(guó)國(guó)家標(biāo)準(zhǔn)局（產(chǎn)生：美國(guó)國(guó)家標(biāo)準(zhǔn)局（NBS)1973年年5月到月到1974年年8月兩次發(fā)布通告，月兩次發(fā)布通告， 公開(kāi)征求用于電子計(jì)算機(jī)的加密算法。經(jīng)評(píng)選從一大批算法中采納公開(kāi)征求用于電子計(jì)算機(jī)的加密算法。經(jīng)評(píng)選從一大批算法中采納 了了IBM的的LUCIFER方案方案標(biāo)準(zhǔn)化：標(biāo)準(zhǔn)化：DES算法算法1975年年3月公開(kāi)發(fā)表，月公開(kāi)發(fā)表，1977年年1月月15日由美國(guó)國(guó)家日由美國(guó)國(guó)家標(biāo)準(zhǔn)局頒布為

3、數(shù)據(jù)加密標(biāo)準(zhǔn)（標(biāo)準(zhǔn)局頒布為數(shù)據(jù)加密標(biāo)準(zhǔn)（Data Encryption Standard），于），于1977年年7月月15日生效日生效背景背景美國(guó)國(guó)家安全局（美國(guó)國(guó)家安全局（NSA, National Security Agency)參與了參與了美國(guó)國(guó)家標(biāo)準(zhǔn)局制定數(shù)據(jù)加密標(biāo)準(zhǔn)的過(guò)程。美國(guó)國(guó)家標(biāo)準(zhǔn)局制定數(shù)據(jù)加密標(biāo)準(zhǔn)的過(guò)程。NBS接受了接受了NSA的某些建議，對(duì)算法做了修改，并將密鑰長(zhǎng)度從的某些建議，對(duì)算法做了修改，并將密鑰長(zhǎng)度從LUCIFER方方案中的案中的128位壓縮到位壓縮到56位位1979年，美國(guó)銀行協(xié)會(huì)批準(zhǔn)使用年，美國(guó)銀行協(xié)會(huì)批準(zhǔn)使用DES1980年，年，DES成為美國(guó)標(biāo)準(zhǔn)化協(xié)會(huì)成為美國(guó)

4、標(biāo)準(zhǔn)化協(xié)會(huì)(ANSI)標(biāo)準(zhǔn)標(biāo)準(zhǔn)1984年年2月，月，ISO成立的數(shù)據(jù)加密技術(shù)委員會(huì)成立的數(shù)據(jù)加密技術(shù)委員會(huì)(SC20)在在DES基礎(chǔ)上制定數(shù)據(jù)加密的國(guó)際標(biāo)準(zhǔn)工作基礎(chǔ)上制定數(shù)據(jù)加密的國(guó)際標(biāo)準(zhǔn)工作DES概述概述分組加密算法：明文和密文為分組加密算法：明文和密文為64位分組長(zhǎng)度位分組長(zhǎng)度對(duì)稱算法：加密和解密除密鑰編排不同外，使用同一算法對(duì)稱算法：加密和解密除密鑰編排不同外，使用同一算法采用混亂和擴(kuò)散的組合，每個(gè)組合先替代后置換，共采用混亂和擴(kuò)散的組合，每個(gè)組合先替代后置換，共16輪輪只使用了標(biāo)準(zhǔn)的算術(shù)和邏輯運(yùn)算，易于實(shí)現(xiàn)只使用了標(biāo)準(zhǔn)的算術(shù)和邏輯運(yùn)算，易于實(shí)現(xiàn)密鑰長(zhǎng)度：密鑰長(zhǎng)度：56位（位（密鑰通常表

5、示位密鑰通常表示位64位，但第位，但第8 8位、位、1616位位第第6464位都用作奇偶校驗(yàn)位都用作奇偶校驗(yàn)）產(chǎn)生）產(chǎn)生16個(gè)個(gè)48位的子密鑰位的子密鑰Shannonn乘積密碼乘積密碼 設(shè)有兩個(gè)子密碼系統(tǒng)設(shè)有兩個(gè)子密碼系統(tǒng)T1和和T2，則先以，則先以T1對(duì)明文進(jìn)行加密，然對(duì)明文進(jìn)行加密，然后再以后再以T2對(duì)所得結(jié)果進(jìn)行加密。其中，對(duì)所得結(jié)果進(jìn)行加密。其中，T1的密文空間需作的密文空間需作為為T(mén)2的的“明文明文”空間。乘積密碼可表示成空間。乘積密碼可表示成 T=T1T2 利用這兩種方法可將簡(jiǎn)單易于實(shí)現(xiàn)的密碼組合成復(fù)雜的更利用這兩種方法可將簡(jiǎn)單易于實(shí)現(xiàn)的密碼組合成復(fù)雜的更為安全的密碼。為安全的密碼

6、。 擴(kuò)散（擴(kuò)散（diffusion）和混亂（）和混亂（confusion）n擴(kuò)散：擴(kuò)散：就是將明文的統(tǒng)計(jì)特性迅速散布到密文中去，實(shí)現(xiàn)方式是使得明文的每一位影響密文中多位的值，即密文中每一位受明文中多位影響；將密鑰的每位數(shù)字盡可能擴(kuò)散到更多個(gè)密文數(shù)字中去，以防止對(duì)密鑰進(jìn)行逐段破譯。根據(jù)擴(kuò)散原則，分組密碼應(yīng)設(shè)計(jì)成明文的每個(gè)比特與密鑰的每個(gè)比特對(duì)密文的每個(gè)比特都產(chǎn)生影響。n混亂：混亂：的目的在于使明文和密文之間的統(tǒng)計(jì)關(guān)系變得盡可能復(fù)雜。使用復(fù)雜的非線形代換非線形代換算法可得預(yù)期的混淆效果。Feistel網(wǎng)絡(luò)網(wǎng)絡(luò) 很多分組密碼的結(jié)構(gòu)從本質(zhì)上說(shuō)都是基于一個(gè)稱為很多分組密碼的結(jié)構(gòu)從本質(zhì)上說(shuō)都是基于一個(gè)稱為

7、Feistel網(wǎng)絡(luò)網(wǎng)絡(luò)的結(jié)構(gòu)。的結(jié)構(gòu)。Feistel提出利用乘積密碼可提出利用乘積密碼可獲得簡(jiǎn)單的代換密碼，乘積密碼指順序地執(zhí)行獲得簡(jiǎn)單的代換密碼，乘積密碼指順序地執(zhí)行多個(gè)多個(gè)基本密碼系統(tǒng)基本密碼系統(tǒng)，使得最后結(jié)果的密碼強(qiáng)度高于每個(gè)，使得最后結(jié)果的密碼強(qiáng)度高于每個(gè)基本密碼系統(tǒng)產(chǎn)生的結(jié)果?；久艽a系統(tǒng)產(chǎn)生的結(jié)果。Feistel網(wǎng)絡(luò)網(wǎng)絡(luò) 一層結(jié)構(gòu)一層結(jié)構(gòu) 取一個(gè)長(zhǎng)度為取一個(gè)長(zhǎng)度為n的分組（的分組（n為偶數(shù)），然為偶數(shù)），然后把它分為長(zhǎng)度為后把它分為長(zhǎng)度為n/2的兩部分：的兩部分：L和和R。定義一個(gè)迭代的分組密碼算法，其第定義一個(gè)迭代的分組密碼算法，其第i輪輪的輸出取決于前一輪的輸出：的輸出取決于前

8、一輪的輸出：nL（i）= R（i-1）nR（i）= L（i-1） f（R（i-1），K（i）K（i）是是i輪的子密鑰，輪的子密鑰，f是任意輪函數(shù)。是任意輪函數(shù)。容易看出其逆為：容易看出其逆為：nR（i-1） = L（i）nL（i-1） = R（i） f（R（i-1），K（i）= R（i） f（L（i），K（i）L（i-1）R（i-1）n Feistel網(wǎng)絡(luò)網(wǎng)絡(luò)DES工作原理工作原理 基于基于Feistel網(wǎng)絡(luò)網(wǎng)絡(luò)n假定信息空間都是由假定信息空間都是由0，1組成的字符串，信息被分組成的字符串，信息被分成成64比特的塊，密鑰是比特的塊，密鑰是56比特。經(jīng)過(guò)比特。經(jīng)過(guò)DES加密的密文加密的密文也是也

9、是64比特的塊。設(shè)用比特的塊。設(shè)用m表示信息塊，表示信息塊，k表示密鑰，則：表示密鑰，則：nm=m1m2m64 mi = 0或或1 nk=k1k2k64 ki = 0或或1 其中其中k8，k16，k24，k32，k40，k48，k56，k64是奇偶是奇偶校驗(yàn)位，真正起作用的僅為校驗(yàn)位，真正起作用的僅為56位。位。n加密算法：加密算法：Ek（m） = IP-1T16T15T1IP（m）其中其中IP為初始置換，為初始置換，IP-1是是IP的逆，的逆，Ti是一系列是一系列的變換。的變換。n解密算法：解密算法：nm=Ek-1 Ek（m） = IP-1T1T2T16IPEk（m）輸入輸入64比特明文數(shù)據(jù)

10、比特明文數(shù)據(jù)初始置換初始置換IP在密鑰控制下在密鑰控制下16輪迭代輪迭代初始逆置換初始逆置換IP-1輸出輸出64比特密文數(shù)據(jù)比特密文數(shù)據(jù)DES加密過(guò)程加密過(guò)程DES加密過(guò)程加密過(guò)程)(6416, 2 , 1),(16, 2 , 1)64(1616111100LRIPbitikRfLRiRLbitIPRLiiiiii密文輸入碼令令i表示迭代次數(shù)，表示迭代次數(shù)， 表示逐位模表示逐位模2求和，求和，f為為加密函數(shù)加密函數(shù)DES解密過(guò)程解密過(guò)程DES算法實(shí)現(xiàn)過(guò)程算法實(shí)現(xiàn)過(guò)程 （1）初始變換初始變換IP移位操作：僅對(duì)64比特明文(8*8)進(jìn)行操作n列經(jīng)過(guò)偶采樣和奇采樣置換后再對(duì)各行進(jìn)行逆序得到列經(jīng)過(guò)偶采

11、樣和奇采樣置換后再對(duì)各行進(jìn)行逆序得到IP57 58 59 60 61 62 63 642014MMIP57 58 59 60 61 62 63 64一輪一輪DESLi-1（32比特）比特）Ri-1（32比特）比特）Li（32比特）比特）48比特寄存器比特寄存器選擇擴(kuò)展運(yùn)算選擇擴(kuò)展運(yùn)算E48比特寄存器比特寄存器子密鑰子密鑰Ki（48比特）比特）32比特寄存器比特寄存器選擇壓縮運(yùn)算選擇壓縮運(yùn)算S置換運(yùn)算置換運(yùn)算PRi（32比特）比特）Li=Ri-1DES算法實(shí)現(xiàn)過(guò)程算法實(shí)現(xiàn)過(guò)程 （2）選擇擴(kuò)展運(yùn)算選擇擴(kuò)展運(yùn)算n選擇運(yùn)算選擇運(yùn)算E，輸入，輸入32位數(shù)據(jù)，產(chǎn)生位數(shù)據(jù)，產(chǎn)生48位輸出。位輸出。n設(shè)設(shè)B（

12、i）=b1（i）b2（i）b64（i）是第是第i+1次迭代的次迭代的64個(gè)二進(jìn)制個(gè)二進(jìn)制位輸入?yún)^(qū)組，將位輸入?yún)^(qū)組，將B（i）分為左右兩個(gè)大小相等的部分，每部分為左右兩個(gè)大小相等的部分，每部分為一個(gè)分為一個(gè)32位二進(jìn)制的數(shù)據(jù)塊位二進(jìn)制的數(shù)據(jù)塊：nL（i）= l1（i）l2（i）l32（i）= b1（i）b2（i）b32（i）nR（i）= r1（i）r2（i）r32（i）= b33（i）b34（i）b64（i）n分別表示為分別表示為84 86擴(kuò)展置換擴(kuò)展置換-盒盒32位擴(kuò)展到位擴(kuò)展到48位位擴(kuò)展擴(kuò)展DES算法實(shí)現(xiàn)過(guò)程算法實(shí)現(xiàn)過(guò)程 （3）使用密鑰使用密鑰n在第i+1次迭代中，用48位二進(jìn)制的密鑰（由

13、56位密鑰生成）nK（i+1）=k1（i+1）k2（i+1）k48（i+1）n與E（R（i）按位相加（邏輯異或），輸出仍是48位，86DES算法實(shí)現(xiàn)過(guò)程算法實(shí)現(xiàn)過(guò)程 （4）選擇函數(shù)（選擇函數(shù)（壓縮替代壓縮替代S-盒）盒）n48位壓縮到位壓縮到32位位S-盒1S-盒2S-盒3S-盒4S-盒5S-盒6S-盒7S-盒8S-盒實(shí)現(xiàn)盒實(shí)現(xiàn)1 2 3 4 5 61 6262 3 4 521133 911001110019bbbbbbbbSbbbb行：-盒子 行 列列：值：14=1100S-盒是算法的關(guān)鍵所在盒是算法的關(guān)鍵所在nDES中其它算法都是線性的，而S-盒運(yùn)算則是非線性的。nS-盒不易于分析，它提供

14、了更好的安全性。n提供了密碼算法所必須的混亂作用。 DES算法實(shí)現(xiàn)過(guò)程算法實(shí)現(xiàn)過(guò)程 （5）選擇函數(shù)輸出的拼接與換位選擇函數(shù)輸出的拼接與換位 X（i）=f（R（i），K（i+1）p-盒的構(gòu)造準(zhǔn)則盒的構(gòu)造準(zhǔn)則P置換的目的是提供雪崩效應(yīng)置換的目的是提供雪崩效應(yīng)明文或密鑰的一點(diǎn)小的變動(dòng)都引起密文的較大變化明文或密鑰的一點(diǎn)小的變動(dòng)都引起密文的較大變化DES算法實(shí)現(xiàn)過(guò)程算法實(shí)現(xiàn)過(guò)程 （6）一輪輸出一輪輸出n把把L（i）與與X（i）按位相加，形成按位相加，形成R（i+1），且令，且令R（i）為為L(zhǎng)（i+1），即得到經(jīng)第，即得到經(jīng)第i+1次迭代加密后的輸出次迭代加密后的輸出nL（i+1）= R（i）nR（i+

15、1）= L（i） f（R（i），K（i+1） （i=0，1，2，15）n可以看出，DES密碼體制的每一次迭代都用替代法和換位法對(duì)上一次迭代的輸出進(jìn)行加密變換。用硬件實(shí)現(xiàn)DES算法時(shí)，實(shí)際上用替代盒實(shí)現(xiàn)替代函數(shù)用替代盒實(shí)現(xiàn)替代函數(shù)Sj（1j8），用換位盒實(shí)現(xiàn)換位函數(shù)），用換位盒實(shí)現(xiàn)換位函數(shù)P。為了使最后輸出的密碼文與原始輸入的明碼文沒(méi)有明顯的函數(shù)關(guān)系，DES算法采用16次迭代。在前15次迭代中，L（i）表示左32位，R（i）表示右32位。對(duì)最后一次迭代，L（16）表示右32位，R（16）表示左32位，即在最最后一次迭代時(shí)不再左右交換后一次迭代時(shí)不再左右交換，以保證加密和解密的對(duì)稱性。DES算法實(shí)

16、現(xiàn)過(guò)程算法實(shí)現(xiàn)過(guò)程 （7）逆初始變換逆初始變換 n用IP-1 表示，它和IP互逆。例如，第1位經(jīng)過(guò)初始置換后，處于第58位，而通過(guò)逆置換，又將第58位換回到第1位。2014MM1420MMIPIP1 k1 （ 56 位 ） (48 位 ) ki （ 56 位 ） （ 48 位 ） 64 位 密 鑰置 換 選 擇 1 C0（ 28 位 ） D0（ 28 位 ） 循 環(huán) 左 移循 環(huán) 左 移 C1（ 28 位 ） D1（ 28 位 ） 循 環(huán) 左 移循 環(huán) 左 移 Ci（ 28 位 ） Di（ 28 位 ）置 換 選 擇 2置 換 選 擇 2密 鑰 表 的 計(jì) 算 邏 輯循 環(huán) 左 移 ：1 1

17、9 12 1 10 23 2 11 24 2 12 25 2 13 26 2 14 27 2 15 28 2 16 1DES中的子密鑰的生成中的子密鑰的生成密鑰置換算法的構(gòu)造準(zhǔn)則密鑰置換算法的構(gòu)造準(zhǔn)則設(shè)計(jì)目標(biāo)：子密鑰的統(tǒng)計(jì)獨(dú)立性和靈活性設(shè)計(jì)目標(biāo)：子密鑰的統(tǒng)計(jì)獨(dú)立性和靈活性實(shí)現(xiàn)簡(jiǎn)單實(shí)現(xiàn)簡(jiǎn)單速度速度不存在簡(jiǎn)單關(guān)系：不存在簡(jiǎn)單關(guān)系：( 給定兩個(gè)有某種關(guān)系的種子密鑰給定兩個(gè)有某種關(guān)系的種子密鑰,能預(yù)測(cè)它們輪子密能預(yù)測(cè)它們輪子密鑰之間的關(guān)系鑰之間的關(guān)系)種子密鑰的所有比特對(duì)每個(gè)子密鑰比特的影響大致相同種子密鑰的所有比特對(duì)每個(gè)子密鑰比特的影響大致相同從一些子密鑰比特獲得其他的子密鑰比特在計(jì)算上是難的從一些

18、子密鑰比特獲得其他的子密鑰比特在計(jì)算上是難的沒(méi)有弱密鑰沒(méi)有弱密鑰nDES三重三重DES n為了增加密鑰的長(zhǎng)度，人們建議將一種分組密碼進(jìn)行級(jí)聯(lián)，在不同的密鑰作用下，連續(xù)多次對(duì)一組明文進(jìn)行加密，通常把這種技術(shù)稱為多重加密技術(shù)多重加密技術(shù)。對(duì)DES，建議使用3DES增強(qiáng)加密強(qiáng)度。3DES可以用兩個(gè)密鑰對(duì)明文進(jìn)行三次加密，假設(shè)兩個(gè)密鑰是K1和K2：n（1）用密鑰K1進(jìn)行DES加密。n（2）用K2對(duì)步驟1的結(jié)果進(jìn)行DES解密。n（3）對(duì)（2）的結(jié)果使用密鑰K1進(jìn)行DES加密。n3DES的缺點(diǎn)是加、解密速度比DES慢。三重三重DES Triple-DESn加密：加密： C=Ek1Dk2 Ek1(P)n解密

19、：解密： P=Dk1Ek2 Dk1(C)DES的安全性的安全性 F F函數(shù)函數(shù)(S-Box)(S-Box)設(shè)計(jì)原理未知設(shè)計(jì)原理未知 密鑰長(zhǎng)度的爭(zhēng)論密鑰長(zhǎng)度的爭(zhēng)論 DESDES的的破譯破譯 弱密鑰與半弱密鑰弱密鑰與半弱密鑰DES密鑰長(zhǎng)度密鑰長(zhǎng)度關(guān)于關(guān)于DES算法的另一個(gè)最有爭(zhēng)議的問(wèn)題就是擔(dān)心實(shí)際算法的另一個(gè)最有爭(zhēng)議的問(wèn)題就是擔(dān)心實(shí)際56比特的密鑰長(zhǎng)度不足以抵御窮舉式攻擊，因?yàn)槊荑€量只比特的密鑰長(zhǎng)度不足以抵御窮舉式攻擊，因?yàn)槊荑€量只有有 個(gè)個(gè) 早在早在1977年，年，Diffie和和Hellman已建議制造一個(gè)每秒能測(cè)已建議制造一個(gè)每秒能測(cè)試試100100萬(wàn)個(gè)密鑰的萬(wàn)個(gè)密鑰的VLSI芯片。每秒測(cè)試

20、芯片。每秒測(cè)試100100萬(wàn)個(gè)密鑰的萬(wàn)個(gè)密鑰的機(jī)器大約需要一天就可以搜索整個(gè)密鑰空間。他們估計(jì)機(jī)器大約需要一天就可以搜索整個(gè)密鑰空間。他們估計(jì)制造這樣的機(jī)器大約需要制造這樣的機(jī)器大約需要2000萬(wàn)萬(wàn)美元美元1756102DES密鑰長(zhǎng)度密鑰長(zhǎng)度在在CRYPTO93上，上，Session和和Wiener給出了一個(gè)非常詳細(xì)給出了一個(gè)非常詳細(xì)的密鑰搜索機(jī)器的設(shè)計(jì)方案，這個(gè)機(jī)器基于并行運(yùn)算的密的密鑰搜索機(jī)器的設(shè)計(jì)方案，這個(gè)機(jī)器基于并行運(yùn)算的密鑰搜索芯片，所以鑰搜索芯片，所以16次加密能同時(shí)完成。花費(fèi)次加密能同時(shí)完成。花費(fèi)10萬(wàn)萬(wàn)美元，美元，平均用平均用1.5天左右就可找到天左右就可找到DES密鑰密鑰美國(guó)克羅拉多洲的程序員美國(guó)克羅拉多洲的程序員Verser從從1997年年2 2月月18日起，用了日起，用了96天時(shí)間，