密码编码学与网络安全培训教材课件

密码编码学与网络安全

电子工业出版社2006-2007密码编码学与网络安全

电子工业出版社第3章对称算法DES3.1分组密码算法原理 ↓3.2DES算法 ↓3.3DES强度 ↓3.4差分分析和线性分析 ↓3.5分组密码设计原理 ↓* 3.ADESin/etc/passwd ↓* 3.BDESinOpenSSL ↓第3章对称算法DES3.1分组密码算法原理 ↓密码技术发展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密码技术发展1918，WilliamF.Friedman3.1分组密码算法原理分组密码算法BlockCipher明文被分为固定长度的块(即分组)，对每个分组用相同的算法和密钥加解密分组一般为n＝64比特，或更长(Padding)密文分组和明文分组同样长对某个密钥可以构造一个明密文对照表Codebook(SubstitutionTable)所以分组的长得至少64比特才好密钥空间2^k<<可逆映射个数(2^n)!3.1分组密码算法原理分组密码算法BlockCiph序列密码算法(流密码算法)流密码算法StreamCipher每次可以加密一个比特适合比如远程终端输入等应用流密码可用伪随机数发生器实现密钥做为随机数种子，产生密钥流keystream(不重复,或极大周期)XOR(plaintext，key-stream)One-timePad序列密码算法(流密码算法)流密码算法StreamCip比较基本区别粒度8字节分组vs.1比特或1字节各自适应不同的应用数据格式Padding对相同的明文分组，总是输出相同的密文分组； 而流密码却输出不同的密文比特流密码一般快很多分组密码多些，是主流分组密码也可以用作流模式安全性对比比较基本区别BlockCipherPrinciples00001110000101000010110100110001010000100101111101101011011110001000001110011010101001101011110011000101110110011110000011110111000011100001001100100100001110000100000101011100011010100111111110000111100111011010100110110110110010111101001011100000

乘积密码：

重复使用代替和置换，实现混乱和扩散。BlockCipherPrinciples乘积密码：

Feistel(DES)加密框架明文分组的长n＝2w分左右两半L0R0密钥K产生子钥：K→k1，k2，…，kr

r是轮数，比如16轮⊕是异或函数XORp⊕x⊕x=p函数F是散列混乱函数可以是手工精心构造的查表函数Feistel(DES)加密框架明文分组的长n＝2w Feistel网络

Feistel网络

Feistel解密

Feistel解密Feistel–‘for’Loop加密计算序列

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）解密计算Feistel–‘for’Loop加密计算序列2轮解密举例假设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轮解密举例假设n＝2轮，C＝（L2，R2）L1L0Feistel伪代码明文m长度n＝2t，记为m0m1，每个长度为t密钥k产生r个子密钥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唯一的非线性结构就是F可以重复使用两个变量即可Feistel伪代码明文m唯一的非线性结构就是F可以重复使用Feistel参数特性分组大小密钥大小循环次数一般仅几轮是不够的，得十几轮才好，如16轮子钥产生算法越复杂越好轮函数Round关键其他考虑速度（尤其是软件实现的速度）便于分析（使用简洁的结构）Feistel参数特性分组大小Feistel类算法举例DES、CAST、Blowfish/(Twofish?)、RC6(/5)不是Feistel结构的AES、IDEA*绝大数分组密码属于或类似Feistel结构多轮每轮有XOR（或能恢复的操作）轮函数Feistel类算法举例DES、CAST、Blowfish/3.2DESDataEncryptionStandard1971IBMHorstFeistel－Lucifer→DES，key由128bit→56bit1973NBS，77NISTFIPS-46－NBS/NIST、IBM、NSA1994最后一次延长到1999年－AES取代之参数Feistel体制分组密码分组大小64bit，密钥大小56bit，轮数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，并同时左移Roundnumber12345678910111213141516Bitsrotated1122222212222221PC-214171124153288×6初始置换及逆置换InitialPermutation（IP/IP-1）5850423426181026052443628201246254463830221466456484032241685749413325179159514335271911361534537292113563554739312315740848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725初始明文按照IP重排；16轮后的密文按照IP-1重排即为最后密文oddeven初始置换及逆置换InitialPermutation（I轮OneRound

轮OneRound扩展置换ExpansionPermutation

3212345456789891011121312131415161716171819202120212223242524252627282928293031321Ri的32bit→48bit两边的是重复选中的6×8扩展置换ExpansionPermutation32轮函数RoundFunction

轮函数RoundFunctionS盒S-Boxes：1/4两边2比特选择行号中间4比特选择列号S盒S-Boxes：1/4两边2比特选择行号S-Boxes：5-8S-Boxes：5-8从S盒出来后重排：PermutationFunction P8×4 167202129122817 11523265183110 282414322739 19133062211425从S盒出来后重排：PermutationFunction DESReviewDESReview 一个DES计算实例p=0123456789ABCDEFk=133457799BBCDFF1

……

c=85E813540F0AB405 一个DES计算实例p=0123456789ABCDEF使用OpenSSL库的DES函数明文64bit “plaintxt”8字节Key56bit “password”取低7bits×8

手工运算

vs. voidDES_ecb_encrypt(const_DES_cblock*input, DES_cblock*output, DES_key_schedule*ks, intenc);密文8B 3297230f813edaaf使用OpenSSL库的DES函数明文64bit “plai3.3DES安全强度对DES的争议集中在密钥空间太小Keyspace从Lucifer的2^128降到DES的2^56DESChallengeIII,22hours15minutesS盒S-BoxesS盒的设计准则？陷门？trapdoorsbyNSA(?) “Formsurprisetosuspicion”从惊喜(甚至能够抵御很后来才发现的各种攻击)到怀疑(n年前就如此厉害的NSA现在究竟有多厉害)3.3DES安全强度对DES的争议集中在密钥大小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蛮力攻击对明文内容的要求*问题：如何辨别出来？ 对给定的某个密文，任何一个密钥都可以解密出一个可能的明文，但是其中应该只有一个是正确的明文。 必须事先知道明文的结构，比如已经知道这是文字文本、源程序（图像、声音、压缩的？）如果有两个密钥，解密出来的两个明文都有意义？可能性极小因为密钥空间2^k<<可逆映射个数(2^n)!Onetimepad就是让对手分辨不出哪个更像正确明文蛮力攻击对明文内容的要求*问题：如何辨别出来？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（两个子密钥，互为加解密）

01FE01FE01FE01FE FE01FE01FE01FE01

1FE01FE00EF10EF1 E01FE01FF10EF10E

01E001E001F101F1 vs E001E001F101F101

1FFE1FFE0EFE0EFE FE1FFE1FFE0EFE0E

011F011F010E010E 1F011F010E010E01

E0FEE0FEF1FEF1FE FEE0FEE0FEF1FEF1DES可能的弱密钥：24（四个子密钥）…DES弱密钥DES弱密钥：4(子密钥相同)3.4差分分析和线性分析蛮力攻击计时攻击差分分析线性分析正面分析密码算法的新技术， 在很多算法上取得很好的效果3.4差分分析和线性分析蛮力攻击差分分析DifferentialCryptanalysisBiham,Shamir(‘S’)1991NSA,1974攻击实例对8轮DES，只需微机几分钟对16轮DES，复杂度为2^47需这么多的选择明文，使本方法只有理论意义DifferentialCryptanalysisoftheFull16-roundDES差分分析DifferentialCryptanalysi线性分析LinearCryptanalysis线性分析LinearCryptanalysisDES其他DES肯定能破译不单是RSAchallengeDES算法仍值得信赖但是关键场合不要用DES对一般个人用户仍是安全的RSAchallenge反而给了信心DES还是AES，或者其他DES模块仍广泛存在，AES还没有普及如果软件实现，任何一个经过考验的算法都好DES/3DES、AES、RC4、RC5、IDEA、BlowfishFree/OpenDES其他DES肯定能破译3.5分组密码的设计原理DESDesignCriteria设计准则asreportedbyCoppersmithin[COPP94]7criteriaforS-boxesprovidefornon-linearityresistancetodifferentialcryptanalysisgoodconfusion3criteriaforpermutationPprovideforincreaseddiffusion3.5分组密码的设计原理DESDesignCriter分组密码设计原理轮数轮函数FS盒雪崩效应密钥使用方法子钥衍生方法雪崩效应分组密码设计原理轮数轮函数F及S盒的设计轮函数F雪崩效应准则 strictavalanchecriterion独立准则 bitindependencecriterionS盒构造方法随机方法随机加测试方法人工构造方法数学构造方法

轮函数F及S盒的设计轮函数F查阅和学习查阅和学习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()函数crypt#define_XOPEN_SOURCE#include<unistd.h> char*crypt(constchar*key,constchar*salt);passwdspace128-32-’7f’=95个可用字符95^nsalt两个字符，每个可从[a-zA-Z0-9./]中选出来，即有4096种不同取值抵制字典攻击中的预算值crypt()函数cryptcrypt()描述从passwd到keypadding形成8字符的组每组产生56bits＝8×7的密钥如果多于1组，则XOR累计重复加密64比特0到25回中间置换，受salt控制，计有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算法很复杂，实现起来非常琐碎，在性能和移植性上也难于友好，因此如果软件实现提倡使用开放源码的实现，如OpenSSL等。OpenSSL是SSL/TLS协议的开放实现，其中也实现了几十种密码算法。OpenSSL部署广泛，使用OpenSSL中的DES非常便利。OpenSSL的使用说明参见“OpenSSL使用指南-x.xx.doc”3.BDESinOpenSSLDES算法很复杂，实现起OpenSSL库结构图SSL（ssleay32.dll）密码算法（libeay32.dll）应用程序(openssl.exe)对称：DESAESRC4IDEA…非对称：RSADHDSAECC…散列：MD5SHA1SHA256…随机数等：RANDBN…OpenSSL库结构图SSL（ssleay32.dll）密码DESAPI（关于ECB和CBC模式）程序示例DESAPIinOpenSSL主程序见备注行intdes_ecb_encrypt(input,output,schedule,enc)

DESAPI（关于ECB和CBC模式）关键术语KeyTermsavalancheeffect blockcipherconfusion DataEncryptionStandard(DES)differentialcryptanalysisdiffusion Feistelcipherirreversiblemapping keylinearcryptanalysis permutationproductcipher reversiblemappinground roundfunctionsubkey substitution关键术语KeyTermsavalancheeffect小结了解DES的基本原理和对DES的批评，清楚DES的安全强度。虽然关键场合不能继续使用DES，但是通常个人用户使用DES不会有问题。如果是在软件程序中使用，DES之外还有很多更好的选择。小结Q&AQ&A演讲完毕，谢谢观看！演讲完毕，谢谢观看！密码编码学与网络安全

电子工业出版社2006-2007密码编码学与网络安全

电子工业出版社第3章对称算法DES3.1分组密码算法原理 ↓3.2DES算法 ↓3.3DES强度 ↓3.4差分分析和线性分析 ↓3.5分组密码设计原理 ↓* 3.ADESin/etc/passwd ↓* 3.BDESinOpenSSL ↓第3章对称算法DES3.1分组密码算法原理 ↓密码技术发展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密码技术发展1918，WilliamF.Friedman3.1分组密码算法原理分组密码算法BlockCipher明文被分为固定长度的块(即分组)，对每个分组用相同的算法和密钥加解密分组一般为n＝64比特，或更长(Padding)密文分组和明文分组同样长对某个密钥可以构造一个明密文对照表Codebook(SubstitutionTable)所以分组的长得至少64比特才好密钥空间2^k<<可逆映射个数(2^n)!3.1分组密码算法原理分组密码算法BlockCiph序列密码算法(流密码算法)流密码算法StreamCipher每次可以加密一个比特适合比如远程终端输入等应用流密码可用伪随机数发生器实现密钥做为随机数种子，产生密钥流keystream(不重复,或极大周期)XOR(plaintext，key-stream)One-timePad序列密码算法(流密码算法)流密码算法StreamCip比较基本区别粒度8字节分组vs.1比特或1字节各自适应不同的应用数据格式Padding对相同的明文分组，总是输出相同的密文分组； 而流密码却输出不同的密文比特流密码一般快很多分组密码多些，是主流分组密码也可以用作流模式安全性对比比较基本区别BlockCipherPrinciples00001110000101000010110100110001010000100101111101101011011110001000001110011010101001101011110011000101110110011110000011110111000011100001001100100100001110000100000101011100011010100111111110000111100111011010100110110110110010111101001011100000

乘积密码：

重复使用代替和置换，实现混乱和扩散。BlockCipherPrinciples乘积密码：

Feistel(DES)加密框架明文分组的长n＝2w分左右两半L0R0密钥K产生子钥：K→k1，k2，…，kr

r是轮数，比如16轮⊕是异或函数XORp⊕x⊕x=p函数F是散列混乱函数可以是手工精心构造的查表函数Feistel(DES)加密框架明文分组的长n＝2w Feistel网络

Feistel网络

Feistel解密

Feistel解密Feistel–‘for’Loop加密计算序列

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）解密计算Feistel–‘for’Loop加密计算序列2轮解密举例假设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轮解密举例假设n＝2轮，C＝（L2，R2）L1L0Feistel伪代码明文m长度n＝2t，记为m0m1，每个长度为t密钥k产生r个子密钥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唯一的非线性结构就是F可以重复使用两个变量即可Feistel伪代码明文m唯一的非线性结构就是F可以重复使用Feistel参数特性分组大小密钥大小循环次数一般仅几轮是不够的，得十几轮才好，如16轮子钥产生算法越复杂越好轮函数Round关键其他考虑速度（尤其是软件实现的速度）便于分析（使用简洁的结构）Feistel参数特性分组大小Feistel类算法举例DES、CAST、Blowfish/(Twofish?)、RC6(/5)不是Feistel结构的AES、IDEA*绝大数分组密码属于或类似Feistel结构多轮每轮有XOR（或能恢复的操作）轮函数Feistel类算法举例DES、CAST、Blowfish/3.2DESDataEncryptionStandard1971IBMHorstFeistel－Lucifer→DES，key由128bit→56bit1973NBS，77NISTFIPS-46－NBS/NIST、IBM、NSA1994最后一次延长到1999年－AES取代之参数Feistel体制分组密码分组大小64bit，密钥大小56bit，轮数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，并同时左移Roundnumber12345678910111213141516Bitsrotated1122222212222221PC-214171124153288×6初始置换及逆置换InitialPermutation（IP/IP-1）5850423426181026052443628201246254463830221466456484032241685749413325179159514335271911361534537292113563554739312315740848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725初始明文按照IP重排；16轮后的密文按照IP-1重排即为最后密文oddeven初始置换及逆置换InitialPermutation（I轮OneRound

轮OneRound扩展置换ExpansionPermutation

3212345456789891011121312131415161716171819202120212223242524252627282928293031321Ri的32bit→48bit两边的是重复选中的6×8扩展置换ExpansionPermutation32轮函数RoundFunction

轮函数RoundFunctionS盒S-Boxes：1/4两边2比特选择行号中间4比特选择列号S盒S-Boxes：1/4两边2比特选择行号S-Boxes：5-8S-Boxes：5-8从S盒出来后重排：PermutationFunction P8×4 167202129122817 11523265183110 282414322739 19133062211425从S盒出来后重排：PermutationFunction DESReviewDESReview 一个DES计算实例p=0123456789ABCDEFk=133457799BBCDFF1

……

c=85E813540F0AB405 一个DES计算实例p=0123456789ABCDEF使用OpenSSL库的DES函数明文64bit “plaintxt”8字节Key56bit “password”取低7bits×8

手工运算

vs. voidDES_ecb_encrypt(const_DES_cblock*input, DES_cblock*output, DES_key_schedule*ks, intenc);密文8B 3297230f813edaaf使用OpenSSL库的DES函数明文64bit “plai3.3DES安全强度对DES的争议集中在密钥空间太小Keyspace从Lucifer的2^128降到DES的2^56DESChallengeIII,22hours15minutesS盒S-BoxesS盒的设计准则？陷门？trapdoorsbyNSA(?) “Formsurprisetosuspicion”从惊喜(甚至能够抵御很后来才发现的各种攻击)到怀疑(n年前就如此厉害的NSA现在究竟有多厉害)3.3DES安全强度对DES的争议集中在密钥大小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蛮力攻击对明文内容的要求*问题：如何辨别出来？ 对给定的某个密文，任何一个密钥都可以解密出一个可能的明文，但是其中应该只有一个是正确的明文。 必须事先知道明文的结构，比如已经知道这是文字文本、源程序（图像、声音、压缩的？）如果有两个密钥，解密出来的两个明文都有意义？可能性极小因为密钥空间2^k<<可逆映射个数(2^n)!Onetimepad就是让对手分辨不出哪个更像正确明文蛮力攻击对明文内容的要求*问题：如何辨别出来？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（两个子密钥，互为加解密）

01FE01FE01FE01FE FE01FE01FE01FE01

1FE01FE00EF10EF1 E01FE01FF10EF10E

01E001E001F101F1 vs E001E001F101F101

1FFE1FFE0EFE0EFE FE1FFE1FFE0EFE0E

011F011F010E010E 1F011F010E010E01

E0FEE0FEF1FEF1FE FEE0FEE0FEF1FEF1DES可能的弱密钥：24（四个子密钥）…DES弱密钥DES弱密钥：4(子密钥相同)3.4差分分析和线性分析蛮力攻击计时攻击差分分析线性分析正面分析密码算法的新技术， 在很多算法上取得很好的效果3.4差分分析和线性分析蛮力攻击差分分析DifferentialCryptanalysisBiham,Shamir(‘S’)1991NSA,1974攻击实例对8轮DES，只需微机几分钟对16轮DES，复杂度为2^47需这么多的选择明文，使本方法只有理论意义DifferentialCryptanalysisoftheFull16-roundDES差分分析DifferentialCryptanalysi线性分析LinearCryptanalysis线性分析LinearCryptanalysisDES其他DES肯定能破译不单是RSAchallengeDES算法仍值得信赖但是关键场合不要用DES对一般个人用户仍是安全的RSAchallenge反而给了信心DES还是AES，或者其他DES模块仍广泛存在，AES还没有普及如果软件实现，任何一个经过考验的算法都好DES/3DES、AES、RC4、RC5、IDEA、BlowfishFree/OpenDES其他DES肯定能破译3.5分组密码的设计原理DESDesignCriteria设计准则asreportedbyCoppersmithin[COPP94]7criteriaforS-boxesprovidefornon-linearityresistancetodifferentialcryptanalysisgoodconfusion3criteriaforpermutationPprovideforincreaseddiffusion3.5分组密码的设计原理DESDesignCriter分组密码设计原理轮数轮函数FS盒雪崩效应密钥使用方法子钥衍生方法雪崩效应分组密码设计原理轮数轮函数F及S盒的设计轮函数F雪崩效应准则 strictavalanchecriterion独立准则 bitindependencecriterionS盒构造方法随机方法随机加测试方法人工构造方法数学构造