密碼編碼學(xué)與網(wǎng)絡(luò)安全培訓(xùn)教材課件

密碼編碼學(xué)與網(wǎng)絡(luò)安全

電子工業(yè)出版社2006-2007密碼編碼學(xué)與網(wǎng)絡(luò)安全

電子工業(yè)出版社第3章對(duì)稱算法DES3.1分組密碼算法原理 ↓3.2DES算法 ↓3.3DES強(qiáng)度 ↓3.4差分分析和線性分析 ↓3.5分組密碼設(shè)計(jì)原理 ↓* 3.ADESin/etc/passwd ↓* 3.BDESinOpenSSL ↓第3章對(duì)稱算法DES3.1分組密碼算法原理 ↓密碼技術(shù)發(fā)展1918，WilliamF.Friedman，TheIndexofCoincidenceandItsApplicationsinCryptography1949，ClaudeShannon，TheCommunicationTheoryofSecrecySystems1967，DavidKahn，TheCodebreakers1970s，NBS/NIST，DES（90s,AES）1976，Diffie,Hellman，NewDirectoryinCryptography1984，C.H.Bennett，QuantumCryptography:PublicKeyDistributionandCoinTossing1985，N.Koblitz，EllipticCurveCryptosystem2000，AES密碼技術(shù)發(fā)展1918，WilliamF.Friedman3.1分組密碼算法原理分組密碼算法BlockCipher明文被分為固定長(zhǎng)度的塊(即分組)，對(duì)每個(gè)分組用相同的算法和密鑰加解密分組一般為n＝64比特，或更長(zhǎng)(Padding)密文分組和明文分組同樣長(zhǎng)對(duì)某個(gè)密鑰可以構(gòu)造一個(gè)明密文對(duì)照表Codebook(SubstitutionTable)所以分組的長(zhǎng)得至少64比特才好密鑰空間2^k<<可逆映射個(gè)數(shù)(2^n)!3.1分組密碼算法原理分組密碼算法BlockCiph序列密碼算法(流密碼算法)流密碼算法StreamCipher每次可以加密一個(gè)比特適合比如遠(yuǎn)程終端輸入等應(yīng)用流密碼可用偽隨機(jī)數(shù)發(fā)生器實(shí)現(xiàn)密鑰做為隨機(jī)數(shù)種子，產(chǎn)生密鑰流keystream(不重復(fù),或極大周期)XOR(plaintext，key-stream)One-timePad序列密碼算法(流密碼算法)流密碼算法StreamCip比較基本區(qū)別粒度8字節(jié)分組vs.1比特或1字節(jié)各自適應(yīng)不同的應(yīng)用數(shù)據(jù)格式Padding對(duì)相同的明文分組，總是輸出相同的密文分組； 而流密碼卻輸出不同的密文比特流密碼一般快很多分組密碼多些，是主流分組密碼也可以用作流模式安全性對(duì)比比較基本區(qū)別BlockCipherPrinciples00001110000101000010110100110001010000100101111101101011011110001000001110011010101001101011110011000101110110011110000011110111000011100001001100100100001110000100000101011100011010100111111110000111100111011010100110110110110010111101001011100000

乘積密碼：

重復(fù)使用代替和置換，實(shí)現(xiàn)混亂和擴(kuò)散。BlockCipherPrinciples乘積密碼：

Feistel(DES)加密框架明文分組的長(zhǎng)n＝2w分左右兩半L0R0密鑰K產(chǎn)生子鑰：K→k1，k2，…，kr

r是輪數(shù)，比如16輪⊕是異或函數(shù)XORp⊕x⊕x=p函數(shù)F是散列混亂函數(shù)可以是手工精心構(gòu)造的查表函數(shù)Feistel(DES)加密框架明文分組的長(zhǎng)n＝2w Feistel網(wǎng)絡(luò)

Feistel網(wǎng)絡(luò)

Feistel解密

Feistel解密Feistel–‘for’Loop加密計(jì)算序列

L0＝左半 R0＝右半

L1＝R0 R1＝L0⊕F(k1,R0) L2＝R1 R2＝L1⊕F(k2,R1) L3＝R3 R3＝L2⊕F(k3,R2) … Li＝Ri-1 Ri＝Li-1⊕F(ki,Ri-1) … Ln＝Rn-1 Rn＝Ln-1⊕F(kn,Rn-1)

密文即（Ln，Rn）解密計(jì)算Feistel–‘for’Loop加密計(jì)算序列2輪解密舉例假設(shè)n＝2輪，C＝（L2，R2） 加密 明文＝半＋半＝L0+R0 L1＝R0 R1＝L0⊕F(k1,R0) L2＝R1 R2＝L1⊕F(k2,R1)解密 密文＝半＋半＝L2＋R2 R1＝L2 L1＝R2⊕F(k2,R1) R0＝L1 L0＝R1⊕F(k1,R0)

明文＝L0＋R0L1＝R2⊕F(k2,R1)＝L1⊕F(k2,R1)⊕F(k2,R1)＝L1L0＝R1⊕F(k1,R0)＝L0⊕F(k1,R0)⊕F(k1,R0)＝L02輪解密舉例假設(shè)n＝2輪，C＝（L2，R2）L1L0Feistel偽代碼明文m長(zhǎng)度n＝2t，記為m0m1，每個(gè)長(zhǎng)度為t密鑰k產(chǎn)生r個(gè)子密鑰k1,k2,...,kr加密E m：

fori=2tor+1do 0,1 mi＝mi-2XORf(mi-1,ki-1) i,i+1<-ki

得密文（mr，mr+1） r,r+1<-kr解密D fori=rto1do mi-1＝mi+1XORf(mi,ki)

或

fori=r-1to0do mi＝mi+2XORf(mi+1,ki+1)

＝miXORf(mi+1,ki+1)XORf(mi+1,ki+1)

＝mi唯一的非線性結(jié)構(gòu)就是F可以重復(fù)使用兩個(gè)變量即可Feistel偽代碼明文m唯一的非線性結(jié)構(gòu)就是F可以重復(fù)使用Feistel參數(shù)特性分組大小密鑰大小循環(huán)次數(shù)一般僅幾輪是不夠的，得十幾輪才好，如16輪子鑰產(chǎn)生算法越復(fù)雜越好輪函數(shù)Round關(guān)鍵其他考慮速度（尤其是軟件實(shí)現(xiàn)的速度）便于分析（使用簡(jiǎn)潔的結(jié)構(gòu)）Feistel參數(shù)特性分組大小Feistel類算法舉例DES、CAST、Blowfish/(Twofish?)、RC6(/5)不是Feistel結(jié)構(gòu)的AES、IDEA*絕大數(shù)分組密碼屬于或類似Feistel結(jié)構(gòu)多輪每輪有XOR（或能恢復(fù)的操作）輪函數(shù)Feistel類算法舉例DES、CAST、Blowfish/3.2DESDataEncryptionStandard1971IBMHorstFeistel－Lucifer→DES，key由128bit→56bit1973NBS，77NISTFIPS-46－NBS/NIST、IBM、NSA1994最后一次延長(zhǎng)到1999年－AES取代之參數(shù)Feistel體制分組密碼分組大小64bit，密鑰大小56bit，輪數(shù)16輪S-Boxes *3.2DESDataEncryptionStandarDES

DES密鑰置換選擇-1

KeyPermutedChoiceOne(PC-1)574941332517981585042342618161025951433527241911360524436326355473931231540762544638302248146615345372956211352820124647×8K的56比特重新排列，成為C0D0

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364密鑰置換選擇-1

KeyPermutedChoiceOKeyi(48bit)C0D0

…C15D15

Keyi(48bit)C0D0PC-214171124153281562110231912426816727201324152313747553040514533484449395634534642503629328×6未入選的：9、18、22等每輪從56比特中選取48比特即為Ki，并同時(shí)左移Roundnumber12345678910111213141516Bitsrotated1122222212222221PC-214171124153288×6初始置換及逆置換InitialPermutation（IP/IP-1）5850423426181026052443628201246254463830221466456484032241685749413325179159514335271911361534537292113563554739312315740848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725初始明文按照IP重排；16輪后的密文按照IP-1重排即為最后密文oddeven初始置換及逆置換InitialPermutation（I輪OneRound

輪OneRound擴(kuò)展置換ExpansionPermutation

3212345456789891011121312131415161716171819202120212223242524252627282928293031321Ri的32bit→48bit兩邊的是重復(fù)選中的6×8擴(kuò)展置換ExpansionPermutation32輪函數(shù)RoundFunction

輪函數(shù)RoundFunctionS盒S-Boxes：1/4兩邊2比特選擇行號(hào)中間4比特選擇列號(hào)S盒S-Boxes：1/4兩邊2比特選擇行號(hào)S-Boxes：5-8S-Boxes：5-8從S盒出來(lái)后重排：PermutationFunction P8×4 167202129122817 11523265183110 282414322739 19133062211425從S盒出來(lái)后重排：PermutationFunction DESReviewDESReview 一個(gè)DES計(jì)算實(shí)例p=0123456789ABCDEFk=133457799BBCDFF1

……

c=85E813540F0AB405 一個(gè)DES計(jì)算實(shí)例p=0123456789ABCDEF使用OpenSSL庫(kù)的DES函數(shù)明文64bit “plaintxt”8字節(jié)Key56bit “password”取低7bits×8

手工運(yùn)算

vs. voidDES_ecb_encrypt(const_DES_cblock*input, DES_cblock*output, DES_key_schedule*ks, intenc);密文8B 3297230f813edaaf使用OpenSSL庫(kù)的DES函數(shù)明文64bit “plai3.3DES安全強(qiáng)度對(duì)DES的爭(zhēng)議集中在密鑰空間太小Keyspace從Lucifer的2^128降到DES的2^56DESChallengeIII,22hours15minutesS盒S-BoxesS盒的設(shè)計(jì)準(zhǔn)則？陷門？trapdoorsbyNSA(?) “Formsurprisetosuspicion”從驚喜(甚至能夠抵御很后來(lái)才發(fā)現(xiàn)的各種攻擊)到懷疑(n年前就如此厲害的NSA現(xiàn)在究竟有多厲害)3.3DES安全強(qiáng)度對(duì)DES的爭(zhēng)議集中在密鑰大小KeySize密鑰大小KeySize窮舉(蠻力)攻擊Cost/Time表窮舉(蠻力)攻擊Cost/Time表“DeepCrack”HardwareCrackerDevelopedbythe ElectronicFrontierFoundationCostUS$210,000$80,000design$210,000materials(chips,boards,chassisetc)“DeepCrack”HardwareCrackerDVLSIChipDevelopedbyAdvanced WirelessTechnologies24searchunitsperchip40MHz16cyclesperencryption2.5millionkeys/sBoardcontains64chips6cabinetsholding29boardsVLSIChipDevelopedbyAdvancedDeepCrackSystem90billionkeys/s37,000searchunitsc.f.DistributedNet’s34billionkeys/sControlledbyPCcheckspossibleallASCIIcandidatesolutionsfromthesearchunitsSolvedRSA’sDES-IIIin22hoursJan18,1999DeepCrackSystem90billionke蠻力攻擊對(duì)明文內(nèi)容的要求*問(wèn)題：如何辨別出來(lái)？ 對(duì)給定的某個(gè)密文，任何一個(gè)密鑰都可以解密出一個(gè)可能的明文，但是其中應(yīng)該只有一個(gè)是正確的明文。 必須事先知道明文的結(jié)構(gòu)，比如已經(jīng)知道這是文字文本、源程序（圖像、聲音、壓縮的？）如果有兩個(gè)密鑰，解密出來(lái)的兩個(gè)明文都有意義？可能性極小因?yàn)槊荑€空間2^k<<可逆映射個(gè)數(shù)(2^n)!Onetimepad就是讓對(duì)手分辨不出哪個(gè)更像正確明文蠻力攻擊對(duì)明文內(nèi)容的要求*問(wèn)題：如何辨別出來(lái)？S盒特性SizeInputN×outputM8×32，butDES6×42^N→MbitsincontrasttoDES’s2^2×2^4→4NonlinearBentfunctionS-boxes’evolutionBlowfish,butDES’sisman-madeavoidanalyzeinadvanceS盒特性SizeAvalanche

EffectinDES(A)P1：00000…0(64bit)P2：10000…0(相差1bit)K：00000011001011 01001001100010 00111000011000 00111000110010(B)K1：…(56bit)K2：…(相差1bit)P：…(64bit)Avalanche

EffectinDES(A)P1DES弱密鑰DES弱密鑰：4(子密鑰相同)

0101010101010101 00000000000000

1F1F1F1FE0E0E0E0 eq 0000000FFFFFFF

E0E0E0E01F1F1F1F FFFFFFF0000000

FEFEFEFEFEFEFEFE FFFFFFFFFFFFFFDES半弱密鑰：12（兩個(gè)子密鑰，互為加解密）

01FE01FE01FE01FE FE01FE01FE01FE01

1FE01FE00EF10EF1 E01FE01FF10EF10E

01E001E001F101F1 vs E001E001F101F101

1FFE1FFE0EFE0EFE FE1FFE1FFE0EFE0E

011F011F010E010E 1F011F010E010E01

E0FEE0FEF1FEF1FE FEE0FEE0FEF1FEF1DES可能的弱密鑰：24（四個(gè)子密鑰）…DES弱密鑰DES弱密鑰：4(子密鑰相同)3.4差分分析和線性分析蠻力攻擊計(jì)時(shí)攻擊差分分析線性分析正面分析密碼算法的新技術(shù)， 在很多算法上取得很好的效果3.4差分分析和線性分析蠻力攻擊差分分析DifferentialCryptanalysisBiham,Shamir(‘S’)1991NSA,1974攻擊實(shí)例對(duì)8輪DES，只需微機(jī)幾分鐘對(duì)16輪DES，復(fù)雜度為2^47需這么多的選擇明文，使本方法只有理論意義DifferentialCryptanalysisoftheFull16-roundDES差分分析DifferentialCryptanalysi線性分析LinearCryptanalysis線性分析LinearCryptanalysisDES其他DES肯定能破譯不單是RSAchallengeDES算法仍值得信賴但是關(guān)鍵場(chǎng)合不要用DES對(duì)一般個(gè)人用戶仍是安全的RSAchallenge反而給了信心DES還是AES，或者其他DES模塊仍廣泛存在，AES還沒(méi)有普及如果軟件實(shí)現(xiàn)，任何一個(gè)經(jīng)過(guò)考驗(yàn)的算法都好DES/3DES、AES、RC4、RC5、IDEA、BlowfishFree/OpenDES其他DES肯定能破譯3.5分組密碼的設(shè)計(jì)原理DESDesignCriteria設(shè)計(jì)準(zhǔn)則asreportedbyCoppersmithin[COPP94]7criteriaforS-boxesprovidefornon-linearityresistancetodifferentialcryptanalysisgoodconfusion3criteriaforpermutationPprovideforincreaseddiffusion3.5分組密碼的設(shè)計(jì)原理DESDesignCriter分組密碼設(shè)計(jì)原理輪數(shù)輪函數(shù)FS盒雪崩效應(yīng)密鑰使用方法子鑰衍生方法雪崩效應(yīng)分組密碼設(shè)計(jì)原理輪數(shù)輪函數(shù)F及S盒的設(shè)計(jì)輪函數(shù)F雪崩效應(yīng)準(zhǔn)則 strictavalanchecriterion獨(dú)立準(zhǔn)則 bitindependencecriterionS盒構(gòu)造方法隨機(jī)方法隨機(jī)加測(cè)試方法人工構(gòu)造方法數(shù)學(xué)構(gòu)造方法

輪函數(shù)F及S盒的設(shè)計(jì)輪函數(shù)F查閱和學(xué)習(xí)查閱和學(xué)習(xí)3.ADESin/etc/passwdfile‘passwd’formatusername:passwd:UID:GID:full_name:directory:shell{FromShadow-Password-HOWTO}account:password:UID:GID:GECOS:directory:shell{FromRH8}shadow/etc/passwdpasswd--->*/etc/shadowpasswdusername:passwd:last:may:must:warn:expire:disable:reservedsampleusername:Npge08pfz4wuk:503:100:FN:/home/username:/bin/shusername:x:503:100:FN:/home/username:/bin/sh 1/2username:Npge08pfz4wuk:9479:0:10000:::: 2/23.ADESin/etc/passwdfile‘pacrypt()函數(shù)crypt#define_XOPEN_SOURCE#include<unistd.h> char*crypt(constchar*key,constchar*salt);passwdspace128-32-’7f’=95個(gè)可用字符95^nsalt兩個(gè)字符，每個(gè)可從[a-zA-Z0-9./]中選出來(lái)，即有4096種不同取值抵制字典攻擊中的預(yù)算值crypt()函數(shù)cryptcrypt()描述從passwd到keypadding形成8字符的組每組產(chǎn)生56bits＝8×7的密鑰如果多于1組，則XOR累計(jì)重復(fù)加密64比特0到25回中間置換，受salt控制，計(jì)有4096種不同的置換輸出2＋11字符2字符是明碼salt11字符是編碼后的DES的64bits輸出密文crypt()描述從passwd到keycrypt()Fig

crypt()FigPasswdCrackerPasswdCrackerZipcrackersampleAdvancedZIPPasswordRecoverystatistics:EncryptedZIP-file:sdjfks.zipTotalpasswords:2,091,362,752Totaltime:6m58s725msAveragespeed(passwords/s):4,994,597Passwordforthisfile:7uee23PasswordinHEX:377565653233ZipcrackersampleAdvancedZIP3.BDESinOpenSSLDES算法很復(fù)雜，實(shí)現(xiàn)起來(lái)非?，嵥?，在性能和移植性上也難于友好，因此如果軟件實(shí)現(xiàn)提倡使用開(kāi)放源碼的實(shí)現(xiàn)，如OpenSSL等。OpenSSL是SSL/TLS協(xié)議的開(kāi)放實(shí)現(xiàn)，其中也實(shí)現(xiàn)了幾十種密碼算法。OpenSSL部署廣泛，使用OpenSSL中的DES非常便利。OpenSSL的使用說(shuō)明參見(jiàn)“OpenSSL使用指南-x.xx.doc”3.BDESinOpenSSLDES算法很復(fù)雜，實(shí)現(xiàn)起OpenSSL庫(kù)結(jié)構(gòu)圖SSL（ssleay32.dll）密碼算法（libeay32.dll）應(yīng)用程序(openssl.exe)對(duì)稱：DESAESRC4IDEA…非對(duì)稱：RSADHDSAECC…散列：MD5SHA1SHA256…隨機(jī)數(shù)等：RANDBN…OpenSSL庫(kù)結(jié)構(gòu)圖SSL（ssleay32.dll）密碼DESAPI（關(guān)于ECB和CBC模式）程序示例DESAPIinOpenSSL主程序見(jiàn)備注行intdes_ecb_encrypt(input,output,schedule,enc)

DESAPI（關(guān)于ECB和CBC模式）關(guān)鍵術(shù)語(yǔ)KeyTermsavalancheeffect blockcipherconfusion DataEncryptionStandard(DES)differentialcryptanalysisdiffusion Feistelcipherirreversiblemapping keylinearcryptanalysis permutationproductcipher reversiblemappinground roundfunctionsubkey substitution關(guān)鍵術(shù)語(yǔ)KeyTermsavalancheeffect小結(jié)了解DES的基本原理和對(duì)DES的批評(píng)，清楚DES的安全強(qiáng)度。雖然關(guān)鍵場(chǎng)合不能繼續(xù)使用DES，但是通常個(gè)人用戶使用DES不會(huì)有問(wèn)題。如果是在軟件程序中使用，DES之外還有很多更好的選擇。小結(jié)Q&AQ&A演講完畢，謝謝觀看！演講完畢，謝謝觀看！密碼編碼學(xué)與網(wǎng)絡(luò)安全

電子工業(yè)出版社2006-2007密碼編碼學(xué)與網(wǎng)絡(luò)安全

電子工業(yè)出版社第3章對(duì)稱算法DES3.1分組密碼算法原理 ↓3.2DES算法 ↓3.3DES強(qiáng)度 ↓3.4差分分析和線性分析 ↓3.5分組密碼設(shè)計(jì)原理 ↓* 3.ADESin/etc/passwd ↓* 3.BDESinOpenSSL ↓第3章對(duì)稱算法DES3.1分組密碼算法原理 ↓密碼技術(shù)發(fā)展1918，WilliamF.Friedman，TheIndexofCoincidenceandItsApplicationsinCryptography1949，ClaudeShannon，TheCommunicationTheoryofSecrecySystems1967，DavidKahn，TheCodebreakers1970s，NBS/NIST，DES（90s,AES）1976，Diffie,Hellman，NewDirectoryinCryptography1984，C.H.Bennett，QuantumCryptography:PublicKeyDistributionandCoinTossing1985，N.Koblitz，EllipticCurveCryptosystem2000，AES密碼技術(shù)發(fā)展1918，WilliamF.Friedman3.1分組密碼算法原理分組密碼算法BlockCipher明文被分為固定長(zhǎng)度的塊(即分組)，對(duì)每個(gè)分組用相同的算法和密鑰加解密分組一般為n＝64比特，或更長(zhǎng)(Padding)密文分組和明文分組同樣長(zhǎng)對(duì)某個(gè)密鑰可以構(gòu)造一個(gè)明密文對(duì)照表Codebook(SubstitutionTable)所以分組的長(zhǎng)得至少64比特才好密鑰空間2^k<<可逆映射個(gè)數(shù)(2^n)!3.1分組密碼算法原理分組密碼算法BlockCiph序列密碼算法(流密碼算法)流密碼算法StreamCipher每次可以加密一個(gè)比特適合比如遠(yuǎn)程終端輸入等應(yīng)用流密碼可用偽隨機(jī)數(shù)發(fā)生器實(shí)現(xiàn)密鑰做為隨機(jī)數(shù)種子，產(chǎn)生密鑰流keystream(不重復(fù),或極大周期)XOR(plaintext，key-stream)One-timePad序列密碼算法(流密碼算法)流密碼算法StreamCip比較基本區(qū)別粒度8字節(jié)分組vs.1比特或1字節(jié)各自適應(yīng)不同的應(yīng)用數(shù)據(jù)格式Padding對(duì)相同的明文分組，總是輸出相同的密文分組； 而流密碼卻輸出不同的密文比特流密碼一般快很多分組密碼多些，是主流分組密碼也可以用作流模式安全性對(duì)比比較基本區(qū)別BlockCipherPrinciples00001110000101000010110100110001010000100101111101101011011110001000001110011010101001101011110011000101110110011110000011110111000011100001001100100100001110000100000101011100011010100111111110000111100111011010100110110110110010111101001011100000

乘積密碼：

重復(fù)使用代替和置換，實(shí)現(xiàn)混亂和擴(kuò)散。BlockCipherPrinciples乘積密碼：

Feistel(DES)加密框架明文分組的長(zhǎng)n＝2w分左右兩半L0R0密鑰K產(chǎn)生子鑰：K→k1，k2，…，kr

r是輪數(shù)，比如16輪⊕是異或函數(shù)XORp⊕x⊕x=p函數(shù)F是散列混亂函數(shù)可以是手工精心構(gòu)造的查表函數(shù)Feistel(DES)加密框架明文分組的長(zhǎng)n＝2w Feistel網(wǎng)絡(luò)

Feistel網(wǎng)絡(luò)

Feistel解密

Feistel解密Feistel–‘for’Loop加密計(jì)算序列

L0＝左半 R0＝右半

L1＝R0 R1＝L0⊕F(k1,R0) L2＝R1 R2＝L1⊕F(k2,R1) L3＝R3 R3＝L2⊕F(k3,R2) … Li＝Ri-1 Ri＝Li-1⊕F(ki,Ri-1) … Ln＝Rn-1 Rn＝Ln-1⊕F(kn,Rn-1)

密文即（Ln，Rn）解密計(jì)算Feistel–‘for’Loop加密計(jì)算序列2輪解密舉例假設(shè)n＝2輪，C＝（L2，R2） 加密 明文＝半＋半＝L0+R0 L1＝R0 R1＝L0⊕F(k1,R0) L2＝R1 R2＝L1⊕F(k2,R1)解密 密文＝半＋半＝L2＋R2 R1＝L2 L1＝R2⊕F(k2,R1) R0＝L1 L0＝R1⊕F(k1,R0)

明文＝L0＋R0L1＝R2⊕F(k2,R1)＝L1⊕F(k2,R1)⊕F(k2,R1)＝L1L0＝R1⊕F(k1,R0)＝L0⊕F(k1,R0)⊕F(k1,R0)＝L02輪解密舉例假設(shè)n＝2輪，C＝（L2，R2）L1L0Feistel偽代碼明文m長(zhǎng)度n＝2t，記為m0m1，每個(gè)長(zhǎng)度為t密鑰k產(chǎn)生r個(gè)子密鑰k1,k2,...,kr加密E m：

fori=2tor+1do 0,1 mi＝mi-2XORf(mi-1,ki-1) i,i+1<-ki

得密文（mr，mr+1） r,r+1<-kr解密D fori=rto1do mi-1＝mi+1XORf(mi,ki)

或

fori=r-1to0do mi＝mi+2XORf(mi+1,ki+1)

＝miXORf(mi+1,ki+1)XORf(mi+1,ki+1)

＝mi唯一的非線性結(jié)構(gòu)就是F可以重復(fù)使用兩個(gè)變量即可Feistel偽代碼明文m唯一的非線性結(jié)構(gòu)就是F可以重復(fù)使用Feistel參數(shù)特性分組大小密鑰大小循環(huán)次數(shù)一般僅幾輪是不夠的，得十幾輪才好，如16輪子鑰產(chǎn)生算法越復(fù)雜越好輪函數(shù)Round關(guān)鍵其他考慮速度（尤其是軟件實(shí)現(xiàn)的速度）便于分析（使用簡(jiǎn)潔的結(jié)構(gòu)）Feistel參數(shù)特性分組大小Feistel類算法舉例DES、CAST、Blowfish/(Twofish?)、RC6(/5)不是Feistel結(jié)構(gòu)的AES、IDEA*絕大數(shù)分組密碼屬于或類似Feistel結(jié)構(gòu)多輪每輪有XOR（或能恢復(fù)的操作）輪函數(shù)Feistel類算法舉例DES、CAST、Blowfish/3.2DESDataEncryptionStandard1971IBMHorstFeistel－Lucifer→DES，key由128bit→56bit1973NBS，77NISTFIPS-46－NBS/NIST、IBM、NSA1994最后一次延長(zhǎng)到1999年－AES取代之參數(shù)Feistel體制分組密碼分組大小64bit，密鑰大小56bit，輪數(shù)16輪S-Boxes *3.2DESDataEncryptionStandarDES

DES密鑰置換選擇-1

KeyPermutedChoiceOne(PC-1)574941332517981585042342618161025951433527241911360524436326355473931231540762544638302248146615345372956211352820124647×8K的56比特重新排列，成為C0D0

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364密鑰置換選擇-1

KeyPermutedChoiceOKeyi(48bit)C0D0

…C15D15

Keyi(48bit)C0D0PC-214171124153281562110231912426816727201324152313747553040514533484449395634534642503629328×6未入選的：9、18、22等每輪從56比特中選取48比特即為Ki，并同時(shí)左移Roundnumber12345678910111213141516Bitsrotated1122222212222221PC-214171124153288×6初始置換及逆置換InitialPermutation（IP/IP-1）5850423426181026052443628201246254463830221466456484032241685749413325179159514335271911361534537292113563554739312315740848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725初始明文按照IP重排；16輪后的密文按照IP-1重排即為最后密文oddeven初始置換及逆置換InitialPermutation（I輪OneRound

輪OneRound擴(kuò)展置換ExpansionPermutation

3212345456789891011121312131415161716171819202120212223242524252627282928293031321Ri的32bit→48bit兩邊的是重復(fù)選中的6×8擴(kuò)展置換ExpansionPermutation32輪函數(shù)RoundFunction

輪函數(shù)RoundFunctionS盒S-Boxes：1/4兩邊2比特選擇行號(hào)中間4比特選擇列號(hào)S盒S-Boxes：1/4兩邊2比特選擇行號(hào)S-Boxes：5-8S-Boxes：5-8從S盒出來(lái)后重排：PermutationFunction P8×4 167202129122817 11523265183110 282414322739 19133062211425從S盒出來(lái)后重排：PermutationFunction DESReviewDESReview 一個(gè)DES計(jì)算實(shí)例p=0123456789ABCDEFk=133457799BBCDFF1

……

c=85E813540F0AB405 一個(gè)DES計(jì)算實(shí)例p=0123456789ABCDEF使用OpenSSL庫(kù)的DES函數(shù)明文64bit “plaintxt”8字節(jié)Key56bit “password”取低7bits×8

手工運(yùn)算

vs. voidDES_ecb_encrypt(const_DES_cblock*input, DES_cblock*output, DES_key_schedule*ks, intenc);密文8B 3297230f813edaaf使用OpenSSL庫(kù)的DES函數(shù)明文64bit “plai3.3DES安全強(qiáng)度對(duì)DES的爭(zhēng)議集中在密鑰空間太小Keyspace從Lucifer的2^128降到DES的2^56DESChallengeIII,22hours15minutesS盒S-BoxesS盒的設(shè)計(jì)準(zhǔn)則？陷門？trapdoorsbyNSA(?) “Formsurprisetosuspicion”從驚喜(甚至能夠抵御很后來(lái)才發(fā)現(xiàn)的各種攻擊)到懷疑(n年前就如此厲害的NSA現(xiàn)在究竟有多厲害)3.3DES安全強(qiáng)度對(duì)DES的爭(zhēng)議集中在密鑰大小KeySize密鑰大小KeySize窮舉(蠻力)攻擊Cost/Time表窮舉(蠻力)攻擊Cost/Time表“DeepCrack”HardwareCrackerDevelopedbythe ElectronicFrontierFoundationCostUS$210,000$80,000design$210,000materials(chips,boards,chassisetc)“DeepCrack”HardwareCrackerDVLSIChipDevelopedbyAdvanced WirelessTechnologies24searchunitsperchip40MHz16cyclesperencryption2.5millionkeys/sBoardcontains64chips6cabinetsholding29boardsVLSIChipDevelopedbyAdvancedDeepCrackSystem90billionkeys/s37,000searchunitsc.f.DistributedNet’s34billionkeys/sControlledbyPCcheckspossibleallASCIIcandidatesolutionsfromthesearchunitsSolvedRSA’sDES-IIIin22hoursJan18,1999DeepCrackSystem90billionke蠻力攻擊對(duì)明文內(nèi)容的要求*問(wèn)題：如何辨別出來(lái)？ 對(duì)給定的某個(gè)密文，任何一個(gè)密鑰都可以解密出一個(gè)可能的明文，但是其中應(yīng)該只有一個(gè)是正確的明文。 必須事先知道明文的結(jié)構(gòu)，比如已經(jīng)知道這是文字文本、源程序（圖像、聲音、壓縮的？）如果有兩個(gè)密鑰，解密出來(lái)的兩個(gè)明文都有意義？可能性極小因?yàn)槊荑€空間2^k<<可逆映射個(gè)數(shù)(2^n)!Onetimepad就是讓對(duì)手分辨不出哪個(gè)更像正確明文蠻力攻擊對(duì)明文內(nèi)容的要求*問(wèn)題：如何辨別出來(lái)？S盒特性SizeInputN×outputM8×32，butDES6×42^N→MbitsincontrasttoDES’s2^2×2^4→4NonlinearBentfunctionS-boxes’evolutionBlowfish,butDES’sisman-madeavoidanalyzeinadvanceS盒特性SizeAvalanche

EffectinDES(A)P1：00000…0(64bit)P2：10000…0(相差1bit)K：00000011001011 01001001100010 00111000011000 00111000110010(B)K1：…(56bit)K2：…(相差1bit)P：…(64bit)Avalanche

EffectinDES(A)P1DES弱密鑰DES弱密鑰：4(子密鑰相同)

0101010101010101 00000000000000

1F1F1F1FE0E0E0E0 eq 0000000FFFFFFF

E0E0E0E01F1F1F1F FFFFFFF0000000

FEFEFEFEFEFEFEFE FFFFFFFFFFFFFFDES半弱密鑰：12（兩個(gè)子密鑰，互為加解密）

01FE01FE01FE01FE FE01FE01FE01FE01

1FE01FE00EF10EF1 E01FE01FF10EF10E

01E001E001F101F1 vs E001E001F101F101

1FFE1FFE0EFE0EFE FE1FFE1FFE0EFE0E

011F011F010E010E 1F011F010E010E01

E0FEE0FEF1FEF1FE FEE0FEE0FEF1FEF1DES可能的弱密鑰：24（四個(gè)子密鑰）…DES弱密鑰DES弱密鑰：4(子密鑰相同)3.4差分分析和線性分析蠻力攻擊計(jì)時(shí)攻擊差分分析線性分析正面分析密碼算法的新技術(shù)， 在很多算法上取得很好的效果3.4差分分析和線性分析蠻力攻擊差分分析DifferentialCryptanalysisBiham,Shamir(‘S’)1991NSA,1974攻擊實(shí)例對(duì)8輪DES，只需微機(jī)幾分鐘對(duì)16輪DES，復(fù)雜度為2^47需這么多的選擇明文，使本方法只有理論意義DifferentialCryptanalysisoftheFull16-roundDES差分分析DifferentialCryptanalysi線性分析LinearCryptanalysis線性分析LinearCryptanalysisDES其他DES肯定能破譯不單是RSAchallengeDES算法仍值得信賴但是關(guān)鍵場(chǎng)合不要用DES對(duì)一般個(gè)人用戶仍是安全的RSAchallenge反而給了信心DES還是AES，或者其他DES模塊仍廣泛存在，AES還沒(méi)有普及如果軟件實(shí)現(xiàn)，任何一個(gè)經(jīng)過(guò)考驗(yàn)的算法都好DES/3DES、AES、RC4、RC5、IDEA、BlowfishFree/OpenDES其他DES肯定能破譯3.5分組密碼的設(shè)計(jì)原理DESDesignCriteria設(shè)計(jì)準(zhǔn)則asreportedbyCoppersmithin[COPP94]7criteriaforS-boxesprovidefornon-linearityresistancetodifferentialcryptanalysisgoodconfusion3criteriaforpermutationPprovideforincreaseddiffusion3.5分組密碼的設(shè)計(jì)原理DESDesignCriter分組密碼設(shè)計(jì)原理輪數(shù)輪函數(shù)FS盒雪崩效應(yīng)密鑰使用方法子鑰衍生方法雪崩效應(yīng)分組密碼設(shè)計(jì)原理輪數(shù)輪函數(shù)F及S盒的設(shè)計(jì)輪函數(shù)F雪崩效應(yīng)準(zhǔn)則 strictavalanchecriterion獨(dú)立準(zhǔn)則 bitindependencecriterionS盒構(gòu)造方法隨機(jī)方法隨機(jī)加測(cè)試方法人工構(gòu)造方法數(shù)學(xué)構(gòu)造