《数据加密标准》由会员分享，可在线阅读，更多相关《数据加密标准（97页珍藏版）》请在金锄头文库上搜索。
1、Cryptography and Network Security the Data Encryption Standard 数据加密标准 内容n1. DESn2. DES说明n3. 分组密码设计理论n4. DES分析n5. DES改进Modern Block Ciphersnwill now look at modern block ciphersnone of the most widely used types of cryptographic algorithms nprovide secrecy and/or authentication servicesnin particular
2、 will introduce DES (Data Encryption Standard)Block vs Stream Ciphersnblock ciphers process messages in into blocks, each of which is then en/decrypted nlike a substitution on very big charactersn64-bits or more nstream ciphers process messages a bit or byte at a time when en/decryptingnmany current
3、 ciphers are block ciphersnhence are focus of course一Data Encryption Standard (DES)nmost widely used block cipher in world nadopted in 1977 by NBS (now NIST)nas FIPS PUB 46nencrypts 64-bit data using 56-bit keynhas widespread usenhas been considerable controversy over its securityDES HistorynIBM dev
4、eloped Lucifer ciphernby team led by Feistelnused 64-bit data blocks with 128-bit keynthen redeveloped as a commercial cipher with input from NSA and othersnin 1973 NBS issued request for proposals for a national cipher standardnIBM submitted their revised Lucifer which was eventually accepted as th
5、e DESDES Design Controversynalthough DES standard is publicnwas considerable controversy over design nin choice of 56-bit key (vs Lucifer 128-bit)nand because design criteria were classified nsubsequent events and public analysis show in fact design was appropriatenDES has become widely used, especi
6、ally in financial applicationsDES数据加密系统流程 64位明文输入 初始置换IP 乘积变换 逆初始置换 64位密文输出DES EncryptionFeistel Cipher StructureDES Round Structurenuses two 32-bit L & R halvesnas for any Feistel cipher can describe as:Li = Ri1Ri = Li1 xor F(Ri1, Ki)ntakes 32-bit R half and 48-bit subkey and:nexpands R to 48-bits
7、using perm Enadds to subkeynpasses through 8 S-boxes to get 32-bit resultnfinally permutes this using 32-bit perm PDES nDES定义n加密过程n解密过程nDES的互补性n保密强度DES Decryptionndecrypt must unwind steps of data computation nwith Feistel design, do encryption steps again nusing subkeys in reverse order (SK16 SK1)n
8、note that IP undoes final FP step of encryption n1st round with SK16 undoes 16th encrypt roundn.n16th round with SK1 undoes 1st encrypt round nthen final FP undoes initial encryption IP nthus recovering original data value 二、DES说明n1.加密密钥表n2.DES每圈密钥向量的产生n3.弱密钥和半弱密钥n4.初始置换IP与逆初始置换InverIPn5.加密函数n6.S 盒函
9、数方案的考虑n7.DES方案的注释 n8.DES操作过程的总结DES Key Schedulenforms subkeys used in each roundnconsists of:ninitial permutation of the key (PC1) which selects 56-bits in two 28-bit halves n16 stages consisting of: nselecting 24-bits from each half npermuting them by PC2 for use in function f, nrotating each half
10、separately either 1 or 2 places depending on the key rotation schedule K1.加密密钥表 密 钥 置换选择1 C0 D0 左移 左移 C1 D1 置换选择2 k(1) 左移 左移 C2 D2 置换选择2 k(2) 左移 左移 C16 D16 置换选择2 k(16) 迭代圈数 左移位数 1 7 13 1 2 2 2 8 14 1 2 2 3 9 15 2 1 2 4 10 16 2 2 1 5 11 2 2 6 12 2 22.DES每圈密钥向量的产生n密钥K=k1，k2，k64n置换选择1C0=57,49,41,33,25,
11、17,9,1,58,50,42,34,26,18,10,2,59,51,43,35,27,19,11,3,60,52,44,36,D0=63,55,47,39,31,23,15,7,62,54,46,38,30,22,14,6,61,53,45,37,29,21,13,5,28,20,12,4, n置换选择2nCi： (9,18,22,15) 14,17,11,24,1,5,3,28,15,6,21,10,23,19,12,4,26,8,16,7,27,20,13,2nDi: (35,38,43,54) 41,52,31,37,47,55,30,40,51,45,33,48, 44,49,39
12、,56,34,53,46,42,50,36,29,32 n注意：C16=C0 ， D16=D03.弱密钥和半弱密钥nDES算法数学上的复杂度也就是它的密钥强度。n弱密钥: k(1)=k(2)=k(16) 存在4种：64bit 0101010101010101 1F1F1F1F1F1F1F1F E0E0E0E0E0E0E0E0 FEFEFEFEFEFEFEFE 半弱密钥n只产生两种不同的内部密钥，每种出现8次。n条件：1）寄存器C（或D）：01010101 或 10101010 2）另一寄存器D（或C）：00000000，11111111，01010101，或10101010 n说明： 弱密钥和
13、半弱密钥并不构成对算法保密性的威胁。4.初始置换IP与逆初始置换nfirst step of the data computation nIP reorders the input data bits neven bits to LH half, odd bits to RH half nquite regular in structure (easy in h/w)nsee text Table 3.2nexample:IP(675a6967 5e5a6b5a) = (ffb2194d 004df6fb) Initial Permutation IPn明文X=x1，x2，x64nIP： L(
14、0)=58,50,42,34,26,18,10,2,60,52,44,36,28,20,12,4,62,54,46,38,30,22,14,6,64,56,48,40,32,24,16,8 R(0)=57,49,41,33,25,17,9,1,59,51,43,35,27,19,11,3,61,53,45,37,29,21,13,5,63,55,47,39,31,23,15,7 n逆置换： 40，8，48，16，56，24，64，32，39，7，47，15，55，23，63，31，38，6，46，14，54，22，62，30，37，5，45，13，53，21，61，29，36，4，44，12，
15、52，20，60，28，35，3，43，11，51，19，59，27，34，2，42，10，50，18，58，26，33，1，41，9，49，17，57，255.加密函数n E 扩展盒：32bit扩展成48bitn1,2,3,4 32,1,2,3,4,5n5,6,7,8 4,5,6,7,8,9n9,10,11,12 8,9,10,11,12,13n n n29,30,31,32 28,29,30,31,32,1DES Round Structure nP盒：置换n16,7,20,21,29,12,28,17,1,15,23,26,5,18,31,10,2,8,24,14,32,27,3,9,1
16、9,13,30,6,22,11,4,256.S 盒函数方案的考虑n密码强度似乎与S盒逻辑电路的数目有关。nS盒是一个由6比特输入（x1，x2，x3，x4，x5，x6）映射到4比特输出（y1，y2，y3，y4）的函数，而且每一输出比特yi可以表示为6比特输入的布尔表达式。n即yi可以用一个或多个小项通过逻辑“或”的组合来表示。 e.g: 3个输入，2个输出，S盒的例子。 （x2，x1） 0 1 2 3（x3）0 1 3 2 0 1 2 1 0 3 输入（x1，x2，x3） 输出（y1，y2） X3 x2 X1 y2 y1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1
17、 1 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 1 n布尔表达式：n利用逻辑图（卡诺图）导出布尔式的简化。nS盒的项数Substitution Boxes Snhave eight S-boxes which map 6 to 4 bits neach S-box is actually 4 little 4 bit boxes nouter bits 1 & 6 (row bits) select one rows ninner bits 2-5 (col bits) are substituted nresult is 8 lots of 4 bits,
18、or 32 bitsnrow selection depends on both data & keynfeature known as autoclaving (autokeying)nexample:S(18 09 12 3d 11 17 38 39) = 5fd25e03 7.DES方案的注释nP盒、S盒的设计标准n置换表必须保证每一输出比特在经过最少加密圈数后是全部输入比特的一个函数。nS盒函数是根据保密强度和实现的难易程度来选择的。n在1974年是单个芯片能容纳的最大尺寸。8.DES操作过程的总结n预置初始值n外部提供64比特密钥n构造16个密钥向量n外部提供64比特明文n从X求出
19、L(0),R(0)n置迭代计数器i=1，迭代in求扩展函数E，从R(i-1)得出E(R(i-1) n加密用K(i),解密用K(17-i).n将上两步结果模二加，结果为48比特An构成S盒，得出32比特向量Bn利用置换函数P置换B ，导出P(B)nP(B)与L(i-1)相加，得出R(i)n定义L(i)=R(i-1)n迭代计数器i+1n计数器=16,迭代，否则产生输出。三、分组密码设计理论n设计原则：n一般设计原则：混乱原则、扩散原则n实现的设计原则：软件、硬件n简单性原则：实现和分析的简单性n必要条件：能抗击已有分析或预想的未知攻击。n可扩展性：可变分组或密钥长。Block Cipher Pri
20、nciplesnmost symmetric block ciphers are based on a Feistel Cipher Structurenneeded since must be able to decrypt ciphertext to recover messages efficientlynblock ciphers look like an extremely large substitution nwould need table of 264 entries for a 64-bit block ninstead create from smaller buildi
21、ng blocks nusing idea of a product cipher 1. Claude Shannon and Substitution-Permutation Ciphersnin 1949 Claude Shannon introduced idea of substitution-permutation (S-P) networksnmodern substitution-transposition product cipher nthese form the basis of modern block ciphers nS-P networks are based on
22、 the two primitive cryptographic operations we have seen before: nsubstitution (S-box)npermutation (P-box)nprovide confusion and diffusion of message Confusion and Diffusionncipher needs to completely obscure statistical properties of original messagena one-time pad does thisnmore practically Shanno
23、n suggested combining elements to obtain:ndiffusion dissipates statistical structure of plaintext over bulk of ciphertextnconfusion makes relationship between ciphertext and key as complex as possible分组密码的结构n易于实现“简单”n难于分析“复杂”n迭代结构（Feistel结构）n总体结构：Feistel网络 SP网络2. Feistel Cipher StructurenHorst Feist
24、el devised the feistel ciphernbased on concept of invertible product ciphernpartitions input block into two halvesnprocess through multiple rounds whichnperform a substitution on left data halfnbased on round function of right half & subkeynthen have permutation swapping halvesnimplements Shannons s
25、ubstitution-permutation network conceptFeistel Cipher Design Principlesnblock size nincreasing size improves security, but slows cipher nkey size nincreasing size improves security, makes exhaustive key searching harder, but may slow cipher nnumber of rounds nincreasing number improves security, but
26、 slows cipher nsubkey generation ngreater complexity can make analysis harder, but slows cipher nround function ngreater complexity can make analysis harder, but slows cipher nfast software en/decryption & ease of analysisnare more recent concerns for practical use and testingFeistel Cipher Decrypti
27、on四、DES分析n迭代次数nS盒的设计n密钥调度nDES的安全性nDES与RSA的安全性Block Cipher Design Principlesnbasic principles still like Feistel in 1970snnumber of roundsnmore is better, exhaustive search best attacknfunction f:nprovides “confusion”, is nonlinear, avalanchenkey schedulencomplex subkey creation, key avalanche1.迭代次数n
28、迭代次数n16次？ 多不多 、 烦不烦n迭代次数的选择原则：要使已知的密码分析工作量大于简单的穷举式密钥搜索的工作量。n码间相关性：第一次迭代 40% 第五次迭代后 100%2. S盒的设计n轮函数的设计：提供混乱的作用，它应该是非线性的。n其中最重要的S盒没有公开nS盒各列的线性组合应该符合bent函数。Avalanche Effect 雪崩效应nkey desirable property of encryption algnwhere a change of one input or key bit results in changing approx half output bitsn
29、making attempts to “home-in” by guessing keys impossiblenDES exhibits strong avalanche严格雪崩准则SACnStick Avalanche Criterion：n将完备性和雪崩效应组合在一起。n输入i，输出j，若i变，则j变的概率为50%。比特独立准则BICnBit Independence Criterion：n输入i，输出j，k，若i变，则j，k应该独立的变。保证雪崩原则GACnS盒满足序为r的GA是指：1位输入的变化，至少引起r位输出的变化。nGA在2-5之间，则它具有强扩散特征。3.密钥调度n准则：选择
30、子密钥时要使得推测各个子密钥和由此推出主密钥的难度尽可能大。n密钥功能过于简单。4. DES的安全性n焦点主要集中于密钥的长度和算法本身的安全性。n1）56位密钥的使用：穷举攻击n2）DES算法本身的安全性：n3）计时攻击n4）差分分析n5）线性分析 密钥大小 密钥数量 所需时间（1次/微妙） 32bit 4.3 109 35.8m 56 7.2 1016 1142y 128 3.4 1038 5.4 1024y 168 3.7 1050 5.9 1036y注：平均地说，穷举成功必须尝试所有可能密钥中的一半。Strength of DES Key Sizen56-bit keys have 2
31、56 = 7.2 x 1016 valuesnbrute force search looks hardnrecent advances have shown is possiblenin 1997 on Internet in a few months nin 1998 on dedicated h/w (EFF) in a few days nin 1999 above combined in 22hrs!nstill must be able to recognize plaintextnnow considering alternatives to DESStrength of DES
32、 Timing Attacksnattacks actual implementation of ciphernuse knowledge of consequences of implementation to derive knowledge of some/all subkey bitsnspecifically use fact that calculations can take varying times depending on the value of the inputs to itnparticularly problematic on smartcards Strengt
33、h of DES Analytic Attacksnnow have several analytic attacks on DESnthese utilise some deep structure of the cipher nby gathering information about encryptions ncan eventually recover some/all of the sub-key bits nif necessary then exhaustively search for the rest ngenerally these are statistical att
34、acksnincludendifferential cryptanalysis nlinear cryptanalysis nrelated key attacks Differential Cryptanalysisnone of the most significant recent (public) advances in cryptanalysis nknown by NSA in 70s cf DES designnMurphy, Biham & Shamir published 1990npowerful method to analyse block ciphers nused
35、to analyse most current block ciphers with varying degrees of successnDES reasonably resistant to it, cf LuciferDifferential Cryptanalysisna statistical attack against Feistel ciphers nuses cipher structure not previously used ndesign of S-P networks has output of function f influenced by both input
36、 & keynhence cannot trace values back through cipher without knowing values of the key nDifferential Cryptanalysis compares two related pairs of encryptionsDifferential Cryptanalysis Compares Pairs of Encryptions nwith a known difference in the input nsearching for a known difference in outputnwhen
37、same subkeys are usedDifferential Cryptanalysisnhave some input difference giving some output difference with probability pnif find instances of some higher probability input / output difference pairs occurringncan infer subkey that was used in roundnthen must iterate process over many rounds (with
38、decreasing probabilities)Differential CryptanalysisDifferential Cryptanalysisnperform attack by repeatedly encrypting plaintext pairs with known input XOR until obtain desired output XOR nwhen foundnif intermediate rounds match required XOR have a right pairnif not then have a wrong pair, relative r
39、atio is S/N for attack ncan then deduce keys values for the roundsnright pairs suggest same key bitsnwrong pairs give random values nfor large numbers of rounds, probability is so low that more pairs are required than exist with 64-bit inputs nBiham and Shamir have shown how a 13-round iterated char
40、acteristic can break the full 16-round DES Linear Cryptanalysisnanother recent development nalso a statistical method nmust be iterated over rounds, with decreasing probabilitiesndeveloped by Matsui et al in early 90snbased on finding linear approximationsncan attack DES with 247 known plaintexts, s
41、till in practise infeasibleLinear Cryptanalysisnfind linear approximations with prob p != Pi1,i2,.,ia(+)Cj1,j2,.,jb = Kk1,k2,.,kcwhere ia,jb,kc are bit locations in P,C,K ngives linear equation for key bitsnget one key bit using max likelihood algnusing a large number of trial encryptions neffective
42、ness given by: |p|5. DES与RSA的安全性n硬件实现时，RSA体制比DES慢1000倍。且要求10倍长的密钥。n软件实现时，DES大约比RSA快100倍。n对密码系统的软件攻击比硬件攻击大约慢1000倍。 n攻击难度相同的对称密钥和公开密钥长度。n对称密钥长度 公开密钥长度n 56 384n 64 512n 80 768n 112 1792n 128 2304应用场合n公开密钥密码学目前仅限于密钥管理和签名中。n对称密码适合于数据加密，它速度极快并且对选择密文攻击不敏感。五、DES改进n分组密码的运行模式nTDESn短块加密1Modes of Operation(工作模式
43、)nblock ciphers encrypt fixed size blocksneg. DES encrypts 64-bit blocks, with 56-bit key nneed way to use in practise, given usually have arbitrary amount of information to encrypt nfour were defined for DES in ANSI standard ANSI X3.106-1983 Modes of Usensubsequently now have 5 for DES and AESnhave
44、 block and stream modes1)Electronic Codebook Book (ECB)nmessage is broken into independent blocks which are encrypted neach block is a value which is substituted, like a codebook, hence name neach block is encoded independently of the other blocks Ci = DESK1 (Pi)nuses: secure transmission of single
45、valuesElectronic Codebook Book (ECB)Advantages and Limitations of ECBnrepetitions in message may show in ciphertext nif aligned with message block nparticularly with data such graphics nor with messages that change very little, which become a code-book analysis problem nweakness due to encrypted mes
46、sage blocks being independent nmain use is sending a few blocks of data 2).Cipher Block Chaining (CBC) nmessage is broken into blocks nbut these are linked together in the encryption operation neach previous cipher blocks is chained with current plaintext block, hence name nuse Initial Vector (IV) t
47、o start process Ci = DESK1(Pi XOR Ci-1)C-1 = IV nuses: bulk data encryption, authenticationCipher Block Chaining (CBC)Advantages and Limitations of CBCneach ciphertext block depends on all message blocks nthus a change in the message affects all ciphertext blocks after the change as well as the orig
48、inal block nneed Initial Value (IV) known to sender & receiver nhowever if IV is sent in the clear, an attacker can change bits of the first block, and change IV to compensate nhence either IV must be a fixed value (as in EFTPOS) or it must be sent encrypted in ECB mode before rest of message nat en
49、d of message, handle possible last short block nby padding either with known non-data value (eg nulls)nor pad last block with count of pad size neg. b1 b2 b3 0 0 0 0 5 - 3 data bytes, then 5 bytes pad+count 3).Cipher FeedBack (CFB)nmessage is treated as a stream of bits nadded to the output of the b
50、lock cipher nresult is feed back for next stage (hence name) nstandard allows any number of bit (1,8 or 64 or whatever) to be feed back ndenoted CFB-1, CFB-8, CFB-64 etc nis most efficient to use all 64 bits (CFB-64)Ci = Pi XOR DESK1(Ci-1)C-1 = IV nuses: stream data encryption, authenticationCipher
51、FeedBack (CFB)Advantages and Limitations of CFBnappropriate when data arrives in bits/bytes nmost common stream mode nlimitation is need to stall while do block encryption after every n-bits nnote that the block cipher is used in encryption mode at both ends nerrors propagate for several blocks afte
52、r the error 4).Output FeedBack (OFB)nmessage is treated as a stream of bits noutput of cipher is added to message noutput is then feed back (hence name) nfeedback is independent of message ncan be computed in advanceCi = Pi XOR Oi Oi = DESK1(Oi-1)O-1 = IVnuses: stream encryption over noisy channelsO
53、utput FeedBack (OFB)Advantages and Limitations of OFBnused when error feedback a problem or where need to encryptions before message is available nsuperficially similar to CFB nbut feedback is from the output of cipher and is independent of message na variation of a Vernam cipher nhence must never r
54、euse the same sequence (key+IV) nsender and receiver must remain in sync, and some recovery method is needed to ensure this occurs noriginally specified with m-bit feedback in the standards nsubsequent research has shown that only OFB-64 should ever be used5).Counter (CTR)na “new” mode, though propo
55、sed early onnsimilar to OFB but encrypts counter value rather than any feedback valuenmust have a different key & counter value for every plaintext block (never reused)Ci = Pi XOR Oi Oi = DESK1(i)nuses: high-speed network encryptionsCounter (CTR)Advantages and Limitations of CTRnefficiencyncan do pa
56、rallel encryptionsnin advance of needngood for bursty high speed linksnrandom access to encrypted data blocksnprovable security (good as other modes)nbut must ensure never reuse key/counter values, otherwise could break (cf OFB)2.Triple DESnclear a replacement for DES was neededntheoretical attacks
57、that can break itndemonstrated exhaustive key search attacksnAES is a new cipher alternativenprior to this alternative was to use multiple encryption with DES implementationsnTriple-DES is the chosen formWhy Triple-DES?nwhy not Double-DES?nNOT same as some other single-DES use, but havenmeet-in-the-
58、middle attacknworks whenever use a cipher twicensince X = EK1P = DK2Cnattack by encrypting P with all keys and storenthen decrypt C with keys and match X valuencan show takes O(256) stepsTriple-DES with Two-Keysnhence must use 3 encryptionsnwould seem to need 3 distinct keysnbut can use 2 keys with
59、E-D-E sequencenC = EK1DK2EK1Pnnb encrypt & decrypt equivalent in securitynif K1=K2 then can work with single DESnstandardized in ANSI X9.17 & ISO8732nno current known practical attacksTriple-DES with Three-Keysnalthough are no practical attacks on two-key Triple-DES have some indicationsncan use Tri
60、ple-DES with Three-Keys to avoid even thesenC = EK3DK2EK1Pnhas been adopted by some Internet applications, eg PGP, S/MIMETDESn优点：1.它的密钥长度是168（112）位，能克服所面临的穷举攻击问题。2.TDES对密码分析攻击有很强的免疫力。n缺点：1.用软件实现该算法比较慢2.分组长度为64位3.短块加密n填充n使用序列密码的操作方式n密文挪用方式Summarynhave considered:nblock cipher design principlesnDESndetailsnstrengthnDifferential & Linear CryptanalysisnModes of Operation nECB, CBC, CFB, OFB, CTR
