信息安全导论课程-ch03-对称算法DES

B密码编码学与网络安全电子工业出版社2006-2007B第3章对称算法DES•3.1分组密码算法原理↓•3.2DES算法↓•3.3DES强度↓•3.4差分分析和线性分析↓•3.5分组密码设计原理↓*3.ADESin/etc/passwd↓*3.BDESinOpenSSL↓B密码技术发展•1918，WilliamF.Friedman，TheIndexofCoincidenceandItsApplicationsinCryptography•1949，ClaudeShannon，TheCommunicationTheoryofSecrecySystems•1967，DavidKahn，TheCodebreakers•1970s，NBS/NIST，DES（90s,AES）•1976，Diffie,Hellman，NewDirectoryinCryptography•1984，C.H.Bennett，QuantumCryptography:PublicKeyDistributionandCoinTossing•1985，N.Koblitz，EllipticCurveCryptosystem•2000，AESB3.1分组密码算法原理•分组密码算法BlockCipher–明文被分为固定长度的块(即分组)，对每个分组用相同的算法和密钥加解密–分组一般为n＝64比特，或更长(Padding)–密文分组和明文分组同样长•对某个密钥可以构造一个明密文对照表–Codebook(SubstitutionTable)–所以分组的长得至少64比特才好–密钥空间2^k可逆映射个数(2^n)!B序列密码算法(流密码算法)•流密码算法StreamCipher–每次可以加密一个比特–适合比如远程终端输入等应用•流密码可用伪随机数发生器实现–密钥做为随机数种子，产生密钥流keystream(不重复,或极大周期)–XOR(plaintext，key-stream)•One-timePadB比较•基本区别–粒度8字节分组vs.1比特或1字节•各自适应不同的应用数据格式•Padding–对相同的明文分组，总是输出相同的密文分组；而流密码却输出不同的密文比特–流密码一般快很多•分组密码多些，是主流–分组密码也可以用作流模式•安全性对比BBlockCipherPrinciples•00001110•00010100•00101101•00110001•01000010•01011111•01101011•01111000•10000011•10011010•10100110•10111100•11000101•11011001•11100000•11110111•00001110•00010011•00100100•00111000•01000001•01011100•01101010•01111111•10000111•10011101•10101001•10110110•11001011•11010010•11100000乘积密码：重复使用代替和置换，实现混乱和扩散。BFeistel(DES)加密框架•明文分组的长n＝2w–分左右两半L0R0•密钥K产生子钥：K→k1，k2，…，kr–r是轮数，比如16轮•⊕是异或函数XOR–p⊕x⊕x=p•函数F是散列混乱函数–可以是手工精心构造的查表函数BFeistel网络•BFeistel解密•BFeistel–‘for’Loop•加密计算序列L0＝左半R0＝右半L1＝R0R1＝L0⊕F(k1,R0)L2＝R1R2＝L1⊕F(k2,R1)L3＝R3R3＝L2⊕F(k3,R2)…Li＝Ri-1Ri＝Li-1⊕F(ki,Ri-1)…Ln＝Rn-1Rn＝Ln-1⊕F(kn,Rn-1)密文即（Ln，Rn）•解密计算B2轮解密举例•假设n＝2轮，C＝（L2，R2）加密明文＝半＋半＝L0+R0L1＝R0R1＝L0⊕F(k1,R0)L2＝R1R2＝L1⊕F(k2,R1)•解密密文＝半＋半＝L2＋R2R1＝L2L1＝R2⊕F(k2,R1)R0＝L1L0＝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)＝L0BFeistel伪代码•明文m–长度n＝2t，记为m0m1，每个长度为t•密钥k–产生r个子密钥k1,k2,...,kr•加密Em：fori=2tor+1do0,1mi＝mi-2XORf(mi-1,ki-1)i,i+1-ki得密文（mr，mr+1）r,r+1-kr•解密Dfori=rto1domi-1＝mi+1XORf(mi,ki)或fori=r-1to0domi＝mi+2XORf(mi+1,ki+1)＝miXORf(mi+1,ki+1)XORf(mi+1,ki+1)＝mi唯一的非线性结构就是F可以重复使用两个变量即可BFeistel参数特性•分组大小•密钥大小•循环次数–一般仅几轮是不够的，得十几轮才好，如16轮•子钥产生算法–越复杂越好•轮函数Round–关键•其他考虑–速度（尤其是软件实现的速度）–便于分析（使用简洁的结构）BFeistel类算法举例•DES、CAST、Blowfish/(Twofish?)、RC6(/5)•不是Feistel结构的–AES、IDEA*绝大数分组密码属于或类似Feistel结构–多轮–每轮有XOR（或能恢复的操作）–轮函数B3.2DES•DataEncryptionStandard–1971IBMHorstFeistel－Lucifer→DES，key由128bit→56bit–1973NBS，77NISTFIPS-46－NBS/NIST、IBM、NSA–1994最后一次延长到1999年－AES取代之•参数–Feistel体制分组密码–分组大小64bit，密钥大小56bit，轮数16轮–S-Boxes*BDES•B密钥置换选择-1KeyPermutedChoiceOne(PC-1)574941332517981585042342618161025951433527241911360524436326355473931231540762544638302248146615345372956211352820124647×8K的56比特重新排列，成为C0D012345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364BKeyi(48bit)•C0D0…•C15D15BPC-214171124153281562110231912426816727201324152313747553040514533484449395634534642503629328×6未入选的：9、18、22等每轮从56比特中选取48比特即为Ki，并同时左移Roundnumber12345678910111213141516Bitsrotated1122222212222221B初始置换及逆置换•InitialPermutation（IP/IP-1）5850423426181026052443628201246254463830221466456484032241685749413325179159514335271911361534537292113563554739312315740848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725初始明文按照IP重排；16轮后的密文按照IP-1重排即为最后密文oddevenB轮OneRound•B扩展置换ExpansionPermutation•3212345456789891011121312131415161716171819202120212223242524252627282928293031321Ri的32bit→48bit两边的是重复选中的6×8B轮函数RoundFunction•BS盒S-Boxes：1/4两边2比特选择行号中间4比特选择列号BS-Boxes：5-8B从S盒出来后重排：PermutationFunctionP8×41672021291228171152326518311028241432273919133062211425BDES•ReviewB一个DES计算实例•p=0123456789ABCDEF•k=133457799BBCDFF1••…•…•••c=85E813540F0AB405B使用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);•密文8B3297230f813edaafB3.3DES安全强度对DES的争议集中在•密钥空间太小Keyspace–从Lucifer的2^128降到DES的2^56–DESChallengeIII,22hours15minutes•S盒S-Boxes–S盒的设计准则？–陷门？trapdoorsbyNSA(?)“Formsurprisetosuspicion”从惊喜(甚至能够抵御很后来才发现的各种攻击)到怀疑(n年前就如此厉害的NSA现在究竟有多厉害)B密钥大小KeySize•2^56≈7×10^16–1Mkeys/Secondmeans1000years•Specialmachinedesigned–Wiener–Cost/timetable•Recentnews–in1997onInternetinafewmonths(Rocke,96days)–in1998ondedicatedh/winafewdays(DESII-2EFF,56hrs)–in1999abovecombinedin22hrs15mins“DeepCrack”byEFFB穷举(蛮力)攻击Cost/Time表•Keysearchmachineunitexpectedsearchtime$100,00035hours$1,000,0003.5hours$10,000,00021mins–EfficientDESKeySearchwiener93efficient.pdf–ABruteForceSearchofDESKeyspace•按照NIST的提议，98年以后DES不应继续使用–3DES、AES、RC5、IDEA等B“DeepCrack”HardwareCracker•DevelopedbytheElectronicFrontierFoundation•CostUS$210,000–$80,000design–$210,000materials(chips,boards,chassisetc)BVLSIChip•DevelopedbyAdvancedWirelessTechnologies–24searchunitsperchip–40MHz–16cyclesperencryption–2.5millionkeys/s•Boardcontains64chips•6cabinetsholding29boardsBDeepCrackSystem•90billionkeys/s–37,000searchunit