资源描述：
《第9讲--des安全性》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、DES算法的安全性分析王滨2005年3月18日1主要内容穷举攻击分析Feistel模型分析S盒的设计标准DES算法的互补对称性DES算法的加强方案----多重DES2穷举攻击分析穷举攻击就是对所有可能的密钥逐个进行脱密测试,直到找到正确密钥为止的一种攻击方法.穷举攻击判断正确密钥的方法：将利用试验密钥脱密得到的可能明文与已掌握的明文的信息相比较，并将最吻合的那个试验密钥作为算法输出的正确密钥。穷举攻击又称为穷尽攻击、强力攻击、蛮干攻击等。只要明文不是随机的，就可实施穷举攻击。3穷举攻击的算法已知条
2、件：已知密文c及对应的明文m.Step1对每个可能密钥k,计算c’=D(k,m),并判断c’=c是否成立.不成立时返回Step1检验下一个可能密钥,成立时将k作为候选密钥,并执行Step2.Step2利用其它条件对作k进一步确认.确认通过时输出,算法终止.否则返回Step1检验下一个可能密钥.4穷举攻击算法的计算复杂性定理设密钥在密钥空间K中服从均匀分布，且没有等效密钥,则穷举攻击平均需要检验完个密钥后才找到正确密钥。结论:对DES算法的穷举攻击平均计算复杂性为255.5一、Feistel模型分析
3、Li（32位）Ri（32位）Li-1（32位）Ri-1（32位）f1.设计容易:f函数不要求可逆,加、脱密脱算法结构相同；2.强度高：如果f函数是随机的,则连续若干圈复合形成的函数与随机置换是无法区分的.优点:6Li（32位）Ri（32位）Li-1（32位）Ri-1（32位）f每圈加密时输入有一半没有改变;左右块的加密处理不能并行实施缺点:7Feistel模型实现完全性的性能分析定义2如果对每个密钥k,迭代次数为m的加密变换Ek(x)的每个输入比特的变化都可能会影响到每个输出比特的变化,则称Ek(
4、x)是完全的.意义:实现了Shannon提出的扩散性原则.扩散原则(Diffusion)让明文中的每一位影响密文中的尽可能多的位，或者说让密文中的每一位都受到明文中的尽可能多位的影响。因为在检验完全性时,无法对所有的密钥都来检验影响的必然性,只好退而求其次,来分析这种可能性.8结论:(1)Feistel模型至少需要3圈才可实现完全性.(2)如果Feistel模型的f函数需要T圈迭代才能实现完全性,则Feistel模型经T+2圈迭代可实现完全性.(3)DES算法需且只需5圈即可实现完全性!9结论:(
5、1)Feistel模型至少需要3圈才可实现完全性,且当其f函数具有完全性时,只需3圈即可实现完全性.证明:设(x,y)是Feistel模型的输入,则其第1圈至第3圈的输出依次为如果函数f是完全的,当不考虑变换结果的抵消时,则无论改变x或y的一个比特,第3圈的输出的左半和右半的每个比特都可能改变,这说明此时3圈能够实现完全性.10二、DES的S盒的设计标准DES算法的设计者迫于公众压力公布的S盒的设计标准为1.S盒的每一位输出都不是输入的线性或仿射函数。3.当固定S盒的1位输入时，S盒的每一位输出中
6、0和1的个数尽可能平衡。2.S盒的输入发生1比特变化，输出至少有2比特发生变化。111.S盒的每一位输出都不是输入的线性或仿射函数。仿射函数的定义设f是n元布尔函数,如果则称f是仿射函数;又若仿射函数满足f(0)=0,则f为线性函数.等价定义:设f是n元布尔函数,则f是仿射函数等价于存在常数c1,c2,…,cn和a使对所有x,都有此时,如果a=0,则f为线性函数.仿射函数的缺点:(1)输入与输出之间的代数关系太简单;(2)输入的变化与输出的变化之间的代数关系太简单.仿射函数的优点:实现简单12线性
7、性质是密码设计的大敌!13S盒是DES算法中唯一的非线性变换，是在DES算法起核心作用的密码变换!S盒的设计标准对于实现DES算法的完全性，对于实现混乱和扩散原则，对于确保DES算法的密码强度，具有十分重要的作用。S盒实现了局部的混乱和扩散；这种局部的混乱和扩散通过E盒和P盒并借助于多次迭代实现了整个密码算法的混乱和扩散。S盒只要稍有改变，其密码强度就会大大降低，因此，不要试图改变一个密码算法中的任何细节！14三、DES算法的互补对称性证明：由于DES的F函数具有性质：从而DES算法的圈函数满足圈
8、变换Qk故若记,则有,令D是左右块对换,则证毕定理15互补对称性的缺点:结论:利用DES算法的互补对称性,利用选择明文进行穷举攻击时可将密钥的加密测试量降低一半.攻击方案:Step1选择两个明密对和Step2令K(0)是最低位为0的所有密钥构成的集合.Step3对K(0)中的每个元k,计算c`=Ek(m),并检验c`=c1是否成立.若成立,则判定k为候选密钥;若不成立,基于利用明密对检验是否为正确密钥,即检验是否成立.若成立,则判定为候选密钥,否则返回Step3检验K(0)中的下个
