密碼編碼學(xué)與網(wǎng)絡(luò)安全：ch03-對(duì)稱算法DES

1、B第3章 對(duì)稱算法DES 3.1 分組密碼算法原理 3.2 DES算法 3.3 DES強(qiáng)度 3.4 差分分析和線性分析 3.5 分組密碼設(shè)計(jì)原理* 3.A DES in /etc/passwd* 3.B DES in OpenSSLB密碼技術(shù)發(fā)展 1918，William F. Friedman，The Index of Coincidence and Its Applications in Cryptography 1949，Claude Shannon，The Communication Theory of Secrecy Systems 1967，David Kahn，The Codeb

2、reakers 1970s，NBS/NIST，DES （90s, AES） 1976，Diffie, Hellman，New Directory in Cryptography 1984，C.H. Bennett，Quantum Cryptography: Public Key Distribution and Coin Tossing 1985，N. Koblitz，Elliptic Curve Cryptosystem 2000，AESB3.1 分組密碼算法原理 分組密碼算法 Block Cipher 明文被分為固定長度的塊(即分組)，對(duì)每個(gè)分組用相同的算法和密鑰加解密 分組一般為n64比

3、特，或更長 (Padding) 密文分組和明文分組同樣長 對(duì)某個(gè)密鑰可以構(gòu)造一個(gè)明密文對(duì)照表 Codebook (Substitution Table) 所以分組的長得至少64比特才好 密鑰空間2k 可逆映射個(gè)數(shù)(2n)!B序列密碼算法(流密碼算法) 流密碼算法 Stream Cipher 每次可以加密一個(gè)比特 適合比如遠(yuǎn)程終端輸入等應(yīng)用 流密碼可用偽隨機(jī)數(shù)發(fā)生器實(shí)現(xiàn) 密鑰做為隨機(jī)數(shù)種子，產(chǎn)生密鑰流keystream (不重復(fù),或極大周期) XOR (plaintext，key-stream ) One-time PadB比較 基本區(qū)別 粒度 8字節(jié)分組 vs. 1比特或1字節(jié) 各自適應(yīng)不同的

4、應(yīng)用數(shù)據(jù)格式各自適應(yīng)不同的應(yīng)用數(shù)據(jù)格式 Padding 對(duì)相同的明文分組，總是輸出相同的密文分組；對(duì)相同的明文分組，總是輸出相同的密文分組；而流密碼卻輸出不同的密文比特而流密碼卻輸出不同的密文比特 流密碼一般快很多 分組密碼多些，是主流 分組密碼也可以用作流模式 安全性對(duì)比BBlock Cipher Principles0000 11100001 01000010 11010011 00010100 00100101 11110110 10110111 10001000 00111001 10101010 01101011 11001100 01011101 10011110 00001111

5、 01110000 11100001 00110010 01000011 10000100 00010101 11000110 10100111 11111000 01111001 11011010 10011011 01101100 10111101 00101110 0000 乘積密碼： 重復(fù)使用代替和置換，實(shí)現(xiàn)混亂和擴(kuò)散。BFeistel(DES)加密框架 明文分組的長n2w分左右兩半L0 R0 密鑰K產(chǎn)生子鑰：Kk1，k2，kr r是輪數(shù)，比如16輪 是異或函數(shù)XORp x x = p 函數(shù)F是散列混亂函數(shù)可以是手工精心構(gòu)造的查表函數(shù)BFeistel網(wǎng)絡(luò) BFeistel解密 BFei

6、stel for Loop 加密計(jì)算序列L0左半 R0右半L1R0 R1L0 F(k1,R0)L2R1R2L1 F(k2,R1)L3R3R3L2 F(k3,R2)LiRi-1 RiLi-1 F(ki,Ri-1)LnRn-1 RnLn-1 F(kn,Rn-1)密文即（Ln，Rn） 解密計(jì)算B2輪解密舉例 假設(shè)n2輪，C （L2，R2）加密明文半半L0+R0L1R0 R1L0 F(k1,R0)L2R1R2L1 F(k2,R1) 解密密文半半L2R2R1L2L1R2 F(k2,R1)R0L1L0R1 F(k1,R0)明文L0R0L1R2 F(k2,R1)L1 F(k2,R1) F(k2,R1)L1L

7、0R1 F(k1,R0)L0 F(k1,R0) F(k1,R0)L0BFeistel偽代碼 明文明文m 長度長度n2t，記為，記為m0m1，每個(gè)長度為，每個(gè)長度為t 密鑰密鑰k 產(chǎn)生產(chǎn)生r個(gè)子密鑰個(gè)子密鑰k1,k2 ,.,kr 加密加密Em：for i=2 to r+1 do0, 1mimi-2 XOR f(mi-1, ki-1)i, i+1 - ki得密文（得密文（mr，mr+1）r, r+1 Recent news in 1997 on Internet in a few months (Rocke,96days) in 1998 on dedicated h/w in a few day

8、s (DES II-2 EFF, 56 hrs) in 1999 above combined in 22hrs 15 mins“Deep Crack” by EFFB窮舉(蠻力)攻擊Cost/Time表 Key search machine unitexpected search time$ 100,00035 hours$ 1,000,0003.5 hours$10,000,00021 mins wiener93efficient.pdf A Brute Force Search of DES Keyspacehttp:/ 按照NIST的提議，98年以后DES不應(yīng)繼續(xù)使用 3DES、AES

9、、RC5、IDEA 等B“Deep Crack” Hardware Cracker Developed by theElectronic Frontier Foundation Cost US$210,000 $80,000 design $210,000 materials (chips, boards, chassis etc)BVLSI Chip Developed by AdvancedWireless Technologies 24 search units per chip 40 MHz 16 cycles per encryption 2.5 million keys/s Boa

10、rd contains 64 chips 6 cabinets holding 29 boardsBDeep Crack System 90 billion keys/s 37,000 search units c.f. Distributed Nets 34 billion keys/s Controlled by PC checks possible all ASCII candidate solutions from the search units Solved RSAs DES-III in 22 hours Jan 18, 1999B蠻力攻擊對(duì)明文內(nèi)容的要求* 問題：如何辨別出來？

11、如何辨別出來？對(duì)給定的某個(gè)密文，任何一個(gè)密鑰都可以解密出一個(gè)可能的明文，但是其中應(yīng)該只有一個(gè)是正確的明文。 必須事先知道明文的結(jié)構(gòu)，比如已經(jīng)知道這是 文字文本、源程序（圖像、聲音、壓縮的？） 如果有兩個(gè)密鑰，解密出來的兩個(gè)明文都有意義？ 可能性極小因?yàn)槊荑€空間2k - * * /etc/shadow passwd username:passwd:last:may:must:warn:expire:disable:reserved sample username:Npge08pfz4wuk:503:100:FN:/home/username:/bin/sh username:x:503:100:

12、FN:/home/username:/bin/sh 1/2 username:Npge08pfz4wuk:9479:0:10000: 2/2Bcrypt()函數(shù) crypt#define _XOPEN_SOURCE#include char *crypt(const char *key, const char *salt); passwd space 128-32-7f = 95個(gè)可用字符 95n salt 兩個(gè)字符，每個(gè)可從a-zA-Z0-9./中選出來，即有4096種不同取值 抵制字典攻擊中的預(yù)算值Bcrypt()描述 從passwd到key padding 形成8字符的組 每組產(chǎn)生56b

13、its87的密鑰 如果多于1組，則XOR累計(jì) 重復(fù)加密64比特0到25回 中間置換，受salt控制，計(jì)有4096種不同的置換 輸出211字符 2字符是明碼salt 11字符是編碼后的DES的64bits輸出密文Bcrypt() Fig BPasswd Cracker 基于字典的口令猜測(cè)攻擊 字典的構(gòu)造 普通字典 用戶相關(guān)的詞語 John the Ripper password cracker http:/ http:/ L0phtCrack /wiki/L0phtCrack 更多安全工具 /tools2.htmlB

14、Zip cracker sampleAdvanced ZIP Password Recovery statistics:Encrypted ZIP-file: sdjfks.zipTotal passwords: 2,091,362,752Total time: 6m 58s 725ms Average speed (passwords/s): 4,994,597Password for this file: 7uee23Password in HEX: 37 75 65 65 32 33B3.B DES in OpenSSL DES算法很復(fù)雜，實(shí)現(xiàn)起來非常瑣碎，在性能和移植性上也難于友好，因

15、此如果軟件實(shí)現(xiàn)提倡使用開放源碼的實(shí)現(xiàn)，如OpenSSL等。 OpenSSL是SSL/TLS協(xié)議的開放實(shí)現(xiàn)，其中也實(shí)現(xiàn)了幾十種密碼算法。 OpenSSL部署廣泛，使用OpenSSL中的DES非常便利。 OpenSSL的使用說明參見 “OpenSSL使用指南-x.xx.doc”BOpenSSL庫結(jié)構(gòu)圖SSL（ssleay32.dll）密碼算法（密碼算法（libeay32.dll）應(yīng)用程序應(yīng)用程序(openssl.exe)對(duì)稱：對(duì)稱：DESAESRC4IDEA非對(duì)稱：非對(duì)稱：RSADHDSAECC散列：散列：MD5SHA1SHA256隨機(jī)數(shù)等：隨機(jī)數(shù)等：RANDBNBDES API （關(guān)于ECB和CBC模式） 程序示例DES API in OpenSSL 主程序見備注行 int des_ecb_encrypt(input, output, schedule, enc) Demo_des.zipB關(guān)鍵術(shù)語 Key Terms avalanche effectblock cipher confusion Data Encryption Standard (DES) differential cryptanalysis diffusionFe