分组密码 42数据加密标准(DES)(续)

1、密码学第四章 分组密码4.2 数据加密标准(DES) (续)DES加加密密框框图图6464比特明文比特明文fk1L1R1初始置换初始置换6464比特密文比特密文逆初始置换逆初始置换L15R15R16L16L0R0fk16.4.2 数据加密标准(DES) (续)n脱密算法脱密算法nDES算法的安全性分析算法的安全性分析n多重多重DES DES的脱密运算和加密运算用的是同一个算的脱密运算和加密运算用的是同一个算法，二者的法，二者的不同之处不同之处是圈密钥的使用次序相反，是圈密钥的使用次序相反，即脱密过程中第即脱密过程中第 i圈圈(i=1,2,16)的圈密钥是加密的圈密钥是加密过程中第过程中第17-

2、 i圈的圈密钥圈的圈密钥 k17-i 。一、脱密算法一、脱密算法DES脱脱密密框框图图6464比特密文比特密文fk16R15L15初始置换初始置换6464比特明文比特明文逆初始置换逆初始置换R1L1L0R0R16L16fk1.则则DES的圈变换可表示为这两个函数的复合的圈变换可表示为这两个函数的复合( , )( , ),)( ,( , )kD F x yD xf y kyyxf y k有有( , )( , ),)( , )( , ),)( ,)kkkF F x yF xf y kyxf y kf y kyxy( ,)( ,)( ,)D D xyD yxxy若设函数若设函数( , )( , ),

3、),kF x yxf y ky就是说就是说 ， 都是恒等变换都是恒等变换。kkFFID DI( , )( , )D x yy xyx f (y,k)x (32位位)y (32位位)fk一、脱密算法一、脱密算法定理定理1：1()DESDES mm其中其中m为明文数据，为明文数据， 、 分别为加、脱密变换。分别为加、脱密变换。DES1DES证明：证明：设加密过程第设加密过程第i 圈的圈子密钥为圈的圈子密钥为ki，则脱密过程第，则脱密过程第i 圈的圈子密钥为圈的圈子密钥为k17-i，于是，于是1615211( )( )kkkkDES mIPFDFDFDFIP m12151611( )( )kkkkD

4、EScIPFDFDFDFIP c161521111()()kkkkDESDES mDESIPFDFDFDFIP m故故12151616152111( )kkkkkkkkIPFDFDFDFIP IPFDFDFDFIP m12151616152111( )kkkkkkkkIPFDFDFDFIP IPFDFDFDFIP m一、脱密算法一、脱密算法又因为又因为kkFFID DI11IP IPIPIPI故故1()DESDES m12151616152111( )kkkkkkkkIPFDFDFDFIP IPFDFDFDFIP m1215161615211( )kkkkkkkkIPFDFDFD FFDFDF

5、DFIP m121515211( )kkkkkkIPFDFDFD D FDFDFIP mm1()IPIP m一、脱密算法一、脱密算法 定理定理1说明：说明：DES的加、脱密算法用的确实是同的加、脱密算法用的确实是同一个算法，唯一不同的是圈密钥使用次序相反。一个算法，唯一不同的是圈密钥使用次序相反。 加脱密的相似性加脱密的相似性 采用采用Feistel模型设计的分组密码算法的逆向操模型设计的分组密码算法的逆向操作和正向操作实质上具有相同的结构，不同之处是作和正向操作实质上具有相同的结构，不同之处是圈密钥的使用次序相反。圈密钥的使用次序相反。 每圈对圈输入的一半进行变换。这样做似乎使每圈对圈输入的

6、一半进行变换。这样做似乎使得加、脱密速度变慢，但其最大的好处是使得人们得加、脱密速度变慢，但其最大的好处是使得人们可以自由地选择可以自由地选择f函数而不要求其可逆，但能保证圈函数而不要求其可逆，但能保证圈函数可逆。函数可逆。一、脱密算法一、脱密算法6464比特明文比特明文fk1L1R1初始置换初始置换6464比特密文比特密文逆初始置换逆初始置换L15R15R16L16L0R0fk16.二、二、DES算法的算法的安全性分析安全性分析PS1S8S2S7S6S4S35S4821 kkk4821 aaa3221 aaaES5 DES分组密码算法是以分组密码算法是以Shannon提出的乘积密提出的乘积密

7、码为基础设计的码为基础设计的, ,它以代替它以代替（S盒盒）和置换和置换（P盒盒）为基本变换环节，经过十六次迭代来实现所谓的混为基本变换环节，经过十六次迭代来实现所谓的混乱和扩散。乱和扩散。 S盒是一个盒是一个6进进4出的非线性函数，它起到了混出的非线性函数，它起到了混乱和局部扩散的效果，是乱和局部扩散的效果，是DES的核心的核心。 P盒将本圈的一个盒将本圈的一个S盒的输出扩散到下一圈尽可盒的输出扩散到下一圈尽可能多的能多的S盒中，起到了全体扩散的效果盒中，起到了全体扩散的效果。二、二、DES算法的安全性分析算法的安全性分析（一）（一）DES算法的互补对称性算法的互补对称性定理定理2：( ,

8、)( , )DES m kDES m k证明：证明：对于对于DES的的f函数函数，当输入为当输入为 和和 时时，1(,)nnR K1(,)nnRK由于由于11()()nnnnE RKE RK因此因此11(,)(,)nnnnf R Kf R K而而111;(,)nnnnnnLRRLf R K因此当圈输入和圈密钥都取补时，可得：因此当圈输入和圈密钥都取补时，可得：111(,)(,)nnnnnnnLf RKLf R KR1nnLR二、二、DES算法的安全性分析算法的安全性分析又因为当初始密钥取补时，所得圈密钥也取补，又因为当初始密钥取补时，所得圈密钥也取补，并且并且11( )( )IPxIPx( )

9、( )IP mIP m所以有：所以有：( , )( , )DES m kDES m k证毕证毕 定理定理2说明说明：在用在用DES加密时，若原来的明文加密时，若原来的明文和原来的密钥都取补，则相应的加密结果等于对原和原来的密钥都取补，则相应的加密结果等于对原加密结果取补。加密结果取补。 DES的互补对称性的互补对称性二、二、DES算法的安全性分析算法的安全性分析 利用利用DES的互补对称性，在选择明文攻击时可的互补对称性，在选择明文攻击时可减少一半的穷尽量。减少一半的穷尽量。 已知条件为已知条件为c = DES(m, k)，对密钥空间，对密钥空间K穷尽，穷尽，试图恢复当前密钥试图恢复当前密钥k

10、。 任取任取 ，计算，计算 11(,)DES m kc1kK(1) 若若c =c1，则，则k1为真，因为为真，因为DES (m1, k)= c1，否则，否则 (2) 若若 ，则，则 为真为真， 1k2cc选择用当前密钥选择用当前密钥k 加密的两个明密对加密的两个明密对(m1,c1), (m2,c2)c1=DES(m1, k), c2=DES(m2, k)，且，且21mm二、二、DES算法的安全性分析算法的安全性分析因为因为 ，即，即 ，211(,)DES m kcc221(,)DES m kc=由互补对称性知由互补对称性知 ，212(,)DES m kc=又因又因 DES (m2, k)=c2

11、，则，则 为真。为真。 1k(3) 若两种情况都不成立，则重新选取不同的密若两种情况都不成立，则重新选取不同的密钥钥k重复上述过程。重复上述过程。 当我们选取密钥空间中一个密钥当我们选取密钥空间中一个密钥k时，可同时时，可同时验证验证k和和k的补，因此只需搜索密钥空间的补，因此只需搜索密钥空间K中的一半中的一半元素即可，也就是说可减少一半的穷尽量。元素即可，也就是说可减少一半的穷尽量。 二、二、DES算法的安全性分析算法的安全性分析（二）关于逐位模（二）关于逐位模2加运算加运算 逐位模2加(按位异或)运算是最简单的拉丁方变换，它使得变换的输入、输出是相关免疫的。我们以一比特数据为例来说明这一点

12、。设ykx若 k 服从均匀分布，且与 x 独立，则有5 . 0)0()(kPxyP 因此异或运算使得变换前后的数据具有静态相关免疫性。但是从动态的角度来考察，异或运算后输入差与输出差以1的概率保持不变，即我们必须经过S盒的非线性变换来消除这个缺陷。yxp1二、二、DES算法的安全性分析算法的安全性分析（三）关于（三）关于S盒盒 S盒的设计准则：盒的设计准则：1. 每个每个S盒的每一行都是盒的每一行都是0到到15的一个置换。的一个置换。2.每个每个S盒的每一位输出都不是输入的线性或仿射函数。盒的每一位输出都不是输入的线性或仿射函数。3. S盒输入变化盒输入变化1比特，输出至少变化比特，输出至少变

13、化2比特。比特。4. 对任意对任意S盒和盒和任意输入任意输入 x0,16，s(x)和和s(x 001100)至少有两比特不同。至少有两比特不同。5.对任意对任意S盒和盒和任意输入任意输入 x0,16，以及任意的以及任意的a, b 0,1， s(x) s(x 11ab00) 。6. 对任意对任意S盒，盒，当它当它的输入位中某一位固定，其他的输入位中某一位固定，其他5位位变化时，所有输出数字中变化时，所有输出数字中0和和1的总数接近相等的总数接近相等。二、二、DES算法的安全性分析算法的安全性分析（四）关于（四）关于P盒置换盒置换 P盒置换起到了盒置换起到了整体扩散整体扩散的作用，它设计得好的作用

14、，它设计得好坏，对坏，对DES算法的安全强度是非常重要的，算法的安全强度是非常重要的，P盒的盒的设计原则为：设计原则为： 经过经过S盒变换后输出的盒变换后输出的4个比特，经个比特，经P盒变换后盒变换后作为下一圈迭代的输入时，不再进入同一个作为下一圈迭代的输入时，不再进入同一个S盒，盒，保证最大限度的扩散。保证最大限度的扩散。二、二、DES算法的安全性分析算法的安全性分析（五）关于密钥（五）关于密钥 DES的密钥生成算法的设计思想是将的密钥生成算法的设计思想是将56比特比特有效密钥中的每一比特，均匀作用于圈密钥上，有效密钥中的每一比特，均匀作用于圈密钥上，即初始密钥中的每一比特的使用次数基本相同

15、即初始密钥中的每一比特的使用次数基本相同（12次至次至15次之间）次之间）。 在圈密钥生成算法中，每一圈循环左移的位在圈密钥生成算法中，每一圈循环左移的位数不尽相同，这是为了抵抗对数不尽相同，这是为了抵抗对DES实施相关密钥实施相关密钥攻击。攻击。二、二、DES算法的安全性分析算法的安全性分析（六）弱密钥和半弱密钥（六）弱密钥和半弱密钥 DES存在着弱密钥、半弱密钥等，但它们出存在着弱密钥、半弱密钥等，但它们出现的概率极小，以至于小到可以忽略的程度，因现的概率极小，以至于小到可以忽略的程度，因此从应用的角度来看，是没有必要考虑的。此从应用的角度来看，是没有必要考虑的。 对初始密钥对初始密钥k，

16、若通过密钥生成算法生成的圈，若通过密钥生成算法生成的圈密钥都相同，则称密钥都相同，则称k为为弱密钥弱密钥；若通过密钥生成算；若通过密钥生成算法生成的圈密钥只有两种取值，且这两种取值各法生成的圈密钥只有两种取值，且这两种取值各占一半，则称占一半，则称k为为半弱密钥半弱密钥或或二分之一弱密钥二分之一弱密钥；类；类似地，还可以定义四分之一弱密钥等。似地，还可以定义四分之一弱密钥等。二、二、DES算法的安全性分析算法的安全性分析（七）完全性（七）完全性 所谓所谓完全性完全性是指经过若干圈迭代后，输出的是指经过若干圈迭代后，输出的64比特中的每一比特都包含有输入的每一比特信息。比特中的每一比特都包含有输

17、入的每一比特信息。 一个分组密码算法的完全性是其安全性的基本一个分组密码算法的完全性是其安全性的基本要求，要求，DES是通过是通过E盒和盒和S盒的局部混乱和扩散以及盒的局部混乱和扩散以及P盒的整体扩散来实现完全性的。盒的整体扩散来实现完全性的。 DES经过经过几几圈迭代能实现完全性呢？圈迭代能实现完全性呢？二、二、DES算法的安全性分析算法的安全性分析Pa1 a2 a32S1S8S2S7S6S4S3S5DES算法的算法的 f 函数函数Ea1 a2 a3 a48k1 k2 k3 k48将进入将进入4个个S盒盒1iiLR11(,)iiiiRLf Rki圈圈：Li 实现对实现对Ri-1的的1比特扩散

18、；比特扩散； Ri实现对实现对Li-1 的的1比比特扩散和对特扩散和对Ri-1 的的4比特扩散。比特扩散。DES经过经过5圈迭代实现了完全性。圈迭代实现了完全性。二、二、DES算法的安全性分析算法的安全性分析（八）差分与线性密码分析（八）差分与线性密码分析 1990年，年，Eli Biham和和Adi Shamir提出了差分密提出了差分密码分析方法，利用这种方法，他们找到了一个选择码分析方法，利用这种方法，他们找到了一个选择明文的明文的DES攻击方法，对一个攻击方法，对一个16轮轮DES的最佳攻击的最佳攻击需要需要247个选择明文，比穷尽攻击有效。个选择明文，比穷尽攻击有效。 如果利用已知明文

19、攻击，对低于如果利用已知明文攻击，对低于16轮的轮的DES要要比穷尽攻击有效，但恰好比穷尽攻击有效，但恰好16轮时却需要轮时却需要255个已知明个已知明文。因此，差分密码分析对文。因此，差分密码分析对16轮轮DES仅有理论上的仅有理论上的价值。价值。二、二、DES算法的安全性分析算法的安全性分析（八）差分与线性密码分析（八）差分与线性密码分析 1993年，年，Mitsuru Matsui提出了线性密码分析提出了线性密码分析方法，利用这种方法攻击完整的方法，利用这种方法攻击完整的16轮轮DES，当已知，当已知明文的平均数为明文的平均数为243时可得到密钥。到目前为止，它时可得到密钥。到目前为止，

20、它还是最有效的攻击还是最有效的攻击DES的方法。的方法。二、二、DES算法的安全性分析算法的安全性分析（一）密钥长度（一）密钥长度（二）迭代次数（二）迭代次数（三）（三）S盒盒DES的的安全性安全性二、二、DES算法的安全性分析算法的安全性分析 随着密码分析技术和计算能力的提高，随着密码分析技术和计算能力的提高，DES的的安全性受到质疑和威胁。安全性受到质疑和威胁。密钥较短密钥较短是是 DES的一个的一个主要缺陷。为了提高主要缺陷。为了提高DES的安全性能并充分利用有的安全性能并充分利用有关关DES的现有资源，有人提出利用的现有资源，有人提出利用DES和多个密钥和多个密钥进行多次加密，这方面的两个典型例子是双重进行多次加密，这方面的两个典型例子是双重DES和三重和三重DES。三、多重三、多重DES（一）双重（一）双重DES 双重双重DES是分别用两个不同的密钥是分别用两个不同的密钥k1和和k2