《数据加密标准.ppt》由会员分享，可在线阅读，更多相关《数据加密标准.ppt（97页珍藏版）》请在三一办公上搜索。
1、Cryptography and Network Security,the Data Encryption Standard,数据加密标准,内容,1.DES2.DES说明3.分组密码设计理论4.DES分析5.DES改进,Modern Block Ciphers,will now look at modern block ciphersone of the most widely used types of cryptographic algorithms provide secrecy and/or authentication servicesin particular will intro
2、duce DES(Data Encryption Standard),Block vs Stream Ciphers,block ciphers process messages in into blocks,each of which is then en/decrypted like a substitution on very big characters64-bits or more stream ciphers process messages a bit or byte at a time when en/decryptingmany current ciphers are blo
3、ck ciphershence are focus of course,一Data Encryption Standard(DES),most widely used block cipher in world adopted in 1977 by NBS(now NIST)as FIPS PUB 46encrypts 64-bit data using 56-bit keyhas widespread usehas been considerable controversy over its security,DES History,IBM developed Lucifer cipherb
4、y team led by Feistelused 64-bit data blocks with 128-bit keythen redeveloped as a commercial cipher with input from NSA and othersin 1973 NBS issued request for proposals for a national cipher standardIBM submitted their revised Lucifer which was eventually accepted as the DES,DES Design Controvers
5、y,although DES standard is publicwas considerable controversy over design in choice of 56-bit key(vs Lucifer 128-bit)and because design criteria were classified subsequent events and public analysis show in fact design was appropriateDES has become widely used,especially in financial applications,DE
6、S数据加密系统流程,64位明文输入 初始置换IP 乘积变换 逆初始置换 64位密文输出,DES Encryption,Feistel Cipher Structure,DES Round Structure,uses two 32-bit L&R halvesas for any Feistel cipher can describe as:Li=Ri1Ri=Li1 xor F(Ri1,Ki)takes 32-bit R half and 48-bit subkey and:expands R to 48-bits using perm Eadds to subkeypasses throug
7、h 8 S-boxes to get 32-bit resultfinally permutes this using 32-bit perm P,DES,DES定义加密过程解密过程DES的互补性保密强度,DES Decryption,decrypt must unwind steps of data computation with Feistel design,do encryption steps again using subkeys in reverse order(SK16 SK1)note that IP undoes final FP step of encryption 1s
8、t round with SK16 undoes 16th encrypt round.16th round with SK1 undoes 1st encrypt round then final FP undoes initial encryption IP thus recovering original data value,二、DES说明,1.加密密钥表2.DES每圈密钥向量的产生3.弱密钥和半弱密钥4.初始置换IP与逆初始置换InverIP5.加密函数6.S 盒函数方案的考虑7.DES方案的注释,8.DES操作过程的总结,DES Key Schedule,forms subkeys
9、 used in each roundconsists of:initial permutation of the key(PC1)which selects 56-bits in two 28-bit halves 16 stages consisting of:selecting 24-bits from each half permuting them by PC2 for use in function f,rotating each half separately either 1 or 2 places depending on the key rotation schedule
10、K,1.加密密钥表,密 钥 置换选择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 2,2.DES每圈密钥向量的产生,密钥K=k1，k2，k64置换选择1C0=57,49,41,33,25,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,
11、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,置换选择2Ci：(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,2Di:(35,38,43,54)41,52,31,37,47,55,30,40,51,45,33,48,44,49,39,56,34,53,46,42,50,36,29,32,注意：C16=C0，D16=D0,3.弱密钥和半弱密钥,DES算法数学上的复杂度也就是它的密钥强度。弱密
12、钥:k(1)=k(2)=k(16)存在4种：64bit 0101010101010101 1F1F1F1F1F1F1F1F E0E0E0E0E0E0E0E0 FEFEFEFEFEFEFEFE,半弱密钥只产生两种不同的内部密钥，每种出现8次。条件：1）寄存器C（或D）：01010101 或 10101010 2）另一寄存器D（或C）：00000000，11111111，01010101，或10101010,说明：弱密钥和半弱密钥并不构成对算法保密性的威胁。,4.初始置换IP与逆初始置换,first step of the data computation IP reorders the inpu
13、t data bits even bits to LH half,odd bits to RH half quite regular in structure(easy in h/w)see text Table 3.2example:IP(675a6967 5e5a6b5a)=(ffb2194d 004df6fb),Initial Permutation IP,明文X=x1，x2，x64IP：L(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)
14、=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,逆置换：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，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，25,5.加密函数,E 扩展盒：32bit扩展成
15、48bit1,2,3,4 32,1,2,3,4,55,6,7,8 4,5,6,7,8,99,10,11,12 8,9,10,11,12,13 29,30,31,32 28,29,30,31,32,1,DES Round Structure,P盒：置换16,7,20,21,29,12,28,17,1,15,23,26,5,18,31,10,2,8,24,14,32,27,3,9,19,13,30,6,22,11,4,25,6.S 盒函数方案的考虑,密码强度似乎与S盒逻辑电路的数目有关。S盒是一个由6比特输入（x1，x2，x3，x4，x5，x6）映射到4比特输出（y1，y2，y3，y4）的函数，而
16、且每一输出比特yi可以表示为6比特输入的布尔表达式。即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 1 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 1,布尔表达式：利用逻辑图（卡诺图）导出布尔式的简化。S盒的项数,Substitution Boxes S,have eight S-boxes
17、which map 6 to 4 bits each S-box is actually 4 little 4 bit boxes outer bits 1&6(row bits)select one rows inner bits 2-5(col bits)are substituted result is 8 lots of 4 bits,or 32 bitsrow selection depends on both data&keyfeature known as autoclaving(autokeying)example:S(18 09 12 3d 11 17 38 39)=5fd2
18、5e03,7.DES方案的注释,P盒、S盒的设计标准置换表必须保证每一输出比特在经过最少加密圈数后是全部输入比特的一个函数。S盒函数是根据保密强度和实现的难易程度来选择的。在1974年是单个芯片能容纳的最大尺寸。,8.DES操作过程的总结,预置初始值外部提供64比特密钥构造16个密钥向量外部提供64比特明文从X求出 L(0),R(0)置迭代计数器i=1，迭代i求扩展函数E，从R(i-1)得出E(R(i-1),加密用K(i),解密用K(17-i).将上两步结果模二加，结果为48比特A构成S盒，得出32比特向量B利用置换函数P置换B，导出P(B)P(B)与L(i-1)相加，得出R(i)定义L(i)
19、=R(i-1)迭代计数器i+1计数器=16,迭代，否则产生输出。,三、分组密码设计理论,设计原则：一般设计原则：混乱原则、扩散原则实现的设计原则：软件、硬件简单性原则：实现和分析的简单性必要条件：能抗击已有分析或预想的未知攻击。可扩展性：可变分组或密钥长。,Block Cipher Principles,most symmetric block ciphers are based on a Feistel Cipher Structureneeded since must be able to decrypt ciphertext to recover messages efficiently
20、block ciphers look like an extremely large substitution would need table of 264 entries for a 64-bit block instead create from smaller building blocks using idea of a product cipher,1.Claude Shannon and Substitution-Permutation Ciphers,in 1949 Claude Shannon introduced idea of substitution-permutati
21、on(S-P)networksmodern substitution-transposition product cipher these form the basis of modern block ciphers S-P networks are based on the two primitive cryptographic operations we have seen before:substitution(S-box)permutation(P-box)provide confusion and diffusion of message,Confusion and Diffusio
22、n,cipher needs to completely obscure statistical properties of original messagea one-time pad does thismore practically Shannon suggested combining elements to obtain:diffusion dissipates statistical structure of plaintext over bulk of ciphertextconfusion makes relationship between ciphertext and ke
23、y as complex as possible,分组密码的结构,易于实现“简单”难于分析“复杂”迭代结构（Feistel结构）总体结构：Feistel网络 SP网络,2.Feistel Cipher Structure,Horst Feistel devised the feistel cipherbased on concept of invertible product cipherpartitions input block into two halvesprocess through multiple rounds whichperform a substitution on lef
24、t data halfbased on round function of right half&subkeythen have permutation swapping halvesimplements Shannons substitution-permutation network concept,Feistel Cipher Design Principles,block size increasing size improves security,but slows cipher key size increasing size improves security,makes exh
25、austive key searching harder,but may slow cipher number of rounds increasing number improves security,but slows cipher subkey generation greater complexity can make analysis harder,but slows cipher round function greater complexity can make analysis harder,but slows cipher fast software en/decryptio
26、n&ease of analysisare more recent concerns for practical use and testing,Feistel Cipher Decryption,四、DES分析,迭代次数S盒的设计密钥调度DES的安全性DES与RSA的安全性,Block Cipher Design Principles,basic principles still like Feistel in 1970snumber of roundsmore is better,exhaustive search best attackfunction f:provides“confus
27、ion”,is nonlinear,avalanchekey schedulecomplex subkey creation,key avalanche,1.迭代次数,迭代次数16次？多不多、烦不烦迭代次数的选择原则：要使已知的密码分析工作量大于简单的穷举式密钥搜索的工作量。码间相关性：第一次迭代 40%第五次迭代后 100%,2.S盒的设计,轮函数的设计：提供混乱的作用，它应该是非线性的。其中最重要的S盒没有公开S盒各列的线性组合应该符合bent函数。,Avalanche Effect 雪崩效应,key desirable property of encryption algwhere a
28、change of one input or key bit results in changing approx half output bitsmaking attempts to“home-in”by guessing keys impossibleDES exhibits strong avalanche,严格雪崩准则SAC,Stick Avalanche Criterion：将完备性和雪崩效应组合在一起。输入i，输出j，若i变，则j变的概率为50%。,比特独立准则BIC,Bit Independence Criterion：输入i，输出j，k，若i变，则j，k应该独立的变。,保证雪崩
29、原则GAC,S盒满足序为r的GA是指：1位输入的变化，至少引起r位输出的变化。GA在2-5之间，则它具有强扩散特征。,3.密钥调度,准则：选择子密钥时要使得推测各个子密钥和由此推出主密钥的难度尽可能大。密钥功能过于简单。,4.DES的安全性,焦点主要集中于密钥的长度和算法本身的安全性。1）56位密钥的使用：穷举攻击2）DES算法本身的安全性：3）计时攻击4）差分分析5）线性分析,密钥大小 密钥数量 所需时间（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注：平均地
30、说，穷举成功必须尝试所有可能密钥中的一半。,Strength of DES Key Size,56-bit keys have 256=7.2 x 1016 valuesbrute force search looks hardrecent advances have shown is possiblein 1997 on Internet in a few months in 1998 on dedicated h/w(EFF)in a few days in 1999 above combined in 22hrs!still must be able to recognize plain
31、textnow considering alternatives to DES,Strength of DES Timing Attacks,attacks actual implementation of cipheruse knowledge of consequences of implementation to derive knowledge of some/all subkey bitsspecifically use fact that calculations can take varying times depending on the value of the inputs
32、 to itparticularly problematic on smartcards,Strength of DES Analytic Attacks,now have several analytic attacks on DESthese utilise some deep structure of the cipher by gathering information about encryptions can eventually recover some/all of the sub-key bits if necessary then exhaustively search f
33、or the rest generally these are statistical attacksincludedifferential cryptanalysis linear cryptanalysis related key attacks,Differential Cryptanalysis,one of the most significant recent(public)advances in cryptanalysis known by NSA in 70s cf DES designMurphy,Biham&Shamir published 1990powerful met
34、hod to analyse block ciphers used to analyse most current block ciphers with varying degrees of successDES reasonably resistant to it,cf Lucifer,Differential Cryptanalysis,a statistical attack against Feistel ciphers uses cipher structure not previously used design of S-P networks has output of func
35、tion f influenced by both input&keyhence cannot trace values back through cipher without knowing values of the key Differential Cryptanalysis compares two related pairs of encryptions,Differential Cryptanalysis Compares Pairs of Encryptions,with a known difference in the input searching for a known
36、difference in outputwhen same subkeys are used,Differential Cryptanalysis,have some input difference giving some output difference with probability pif find instances of some higher probability input/output difference pairs occurringcan infer subkey that was used in roundthen must iterate process ov
37、er many rounds(with decreasing probabilities),Differential Cryptanalysis,Differential Cryptanalysis,perform attack by repeatedly encrypting plaintext pairs with known input XOR until obtain desired output XOR when foundif intermediate rounds match required XOR have a right pairif not then have a wro
38、ng pair,relative ratio is S/N for attack can then deduce keys values for the roundsright pairs suggest same key bitswrong pairs give random values for large numbers of rounds,probability is so low that more pairs are required than exist with 64-bit inputs Biham and Shamir have shown how a 13-round i
39、terated characteristic can break the full 16-round DES,Linear Cryptanalysis,another recent development also a statistical method must be iterated over rounds,with decreasing probabilitiesdeveloped by Matsui et al in early 90sbased on finding linear approximationscan attack DES with 247 known plainte
40、xts,still in practise infeasible,Linear Cryptanalysis,find linear approximations with prob p!=Pi1,i2,.,ia(+)Cj1,j2,.,jb=Kk1,k2,.,kcwhere ia,jb,kc are bit locations in P,C,K gives linear equation for key bitsget one key bit using max likelihood algusing a large number of trial encryptions effectivene
41、ss given by:|p|,5.DES与RSA的安全性,硬件实现时，RSA体制比DES慢1000倍。且要求10倍长的密钥。软件实现时，DES大约比RSA快100倍。对密码系统的软件攻击比硬件攻击大约慢1000倍。,攻击难度相同的对称密钥和公开密钥长度。对称密钥长度 公开密钥长度 56 384 64 512 80 768 112 1792 128 2304,应用场合,公开密钥密码学目前仅限于密钥管理和签名中。对称密码适合于数据加密，它速度极快并且对选择密文攻击不敏感。,五、DES改进,分组密码的运行模式TDES短块加密,1Modes of Operation(工作模式),block ciph
42、ers encrypt fixed size blockseg.DES encrypts 64-bit blocks,with 56-bit key need way to use in practise,given usually have arbitrary amount of information to encrypt four were defined for DES in ANSI standard ANSI X3.106-1983 Modes of Usesubsequently now have 5 for DES and AEShave block and stream mo
43、des,1)Electronic Codebook Book(ECB),message is broken into independent blocks which are encrypted each block is a value which is substituted,like a codebook,hence name each block is encoded independently of the other blocks Ci=DESK1(Pi)uses:secure transmission of single values,Electronic Codebook Bo
44、ok(ECB),Advantages and Limitations of ECB,repetitions in message may show in ciphertext if aligned with message block particularly with data such graphics or with messages that change very little,which become a code-book analysis problem weakness due to encrypted message blocks being independent mai
45、n use is sending a few blocks of data,2).Cipher Block Chaining(CBC),message is broken into blocks but these are linked together in the encryption operation each previous cipher blocks is chained with current plaintext block,hence name use Initial Vector(IV)to start process Ci=DESK1(Pi XOR Ci-1)C-1=I
46、V uses:bulk data encryption,authentication,Cipher Block Chaining(CBC),Advantages and Limitations of CBC,each ciphertext block depends on all message blocks thus a change in the message affects all ciphertext blocks after the change as well as the original block need Initial Value(IV)known to sender&
47、receiver however if IV is sent in the clear,an attacker can change bits of the first block,and change IV to compensate hence either IV must be a fixed value(as in EFTPOS)or it must be sent encrypted in ECB mode before rest of message at end of message,handle possible last short block by padding eith
48、er with known non-data value(eg nulls)or pad last block with count of pad size eg.b1 b2 b3 0 0 0 0 5-3 data bytes,then 5 bytes pad+count,3).Cipher FeedBack(CFB),message is treated as a stream of bits added to the output of the block cipher result is feed back for next stage(hence name)standard allow
49、s any number of bit(1,8 or 64 or whatever)to be feed back denoted CFB-1,CFB-8,CFB-64 etc is most efficient to use all 64 bits(CFB-64)Ci=Pi XOR DESK1(Ci-1)C-1=IV uses:stream data encryption,authentication,Cipher FeedBack(CFB),Advantages and Limitations of CFB,appropriate when data arrives in bits/byt
50、es most common stream mode limitation is need to stall while do block encryption after every n-bits note that the block cipher is used in encryption mode at both ends errors propagate for several blocks after the error,4).Output FeedBack(OFB),message is treated as a stream of bits output of cipher i
