《DES算法的安全性分析.ppt》由会员分享，可在线阅读，更多相关《DES算法的安全性分析.ppt（26页珍藏版）》请在三一文库上搜索。
1、1,DES算法的安全性分析,2,主要内容 穷举攻击分析 Feistel模型分析 S盒的设计标准 DES算法的互补对称性 DES算法的加强方案-多重DES,3,穷举攻击分析,穷举攻击就是对所有可能的密钥逐个进行脱密测试, 直到找到正确密钥为止的一种攻击方法. 穷举攻击判断正确密钥的方法： 将利用试验密钥脱密得到的可能明文与已掌握的明文的信息相比较，并将最吻合的那个试验密钥作为算法输出的正确密钥。 穷举攻击又称为穷尽攻击、强力攻击、蛮干攻击等。只要明文不是随机的，就可实施穷举攻击。,4,穷举攻击的算法,已知条件：已知密文c及对应的明文m. Step 1 对每个可能密钥k,计算c=D(k,m),并判
2、断c=c是否成立.不成立时返回Step1检验下一个可能密钥,成立时将k作为候选密钥,并执行Step 2. Step 2 利用其它条件对作k进一步确认.确认通过时输出,算法终止.否则返回Step1检验下一个可能密钥.,5,穷举攻击算法的计算复杂性,定理 设密钥在密钥空间K中服从均匀分布，且没有等效密钥,则穷举攻击平均需要检验完 个密钥后才找到正确密钥。 结论: 对DES算法的穷举攻击平均计算复杂性为255.,6,一、 Feistel模型分析,1. 设计容易:f 函数不要求可逆,加、脱密脱算法结构相同； 2.强度高：如果f 函数是随机的,则连续若干圈复合形成的函数与随机置换是无法区分的.,优点:,
3、7,每圈加密时输入有一半没有改变; 左右块的加密处理不能并行实施,缺点:,8,Feistel模型实现完全性的性能分析,定义2 如果对每个密钥k,迭代次数为m的加密变换Ek(x)的每个输入比特的变化都可能会影响到每个输出比特的变化,则称 Ek(x)是完全的. 意义: 实现了Shannon提出的扩散性原则. 扩散原则(Diffusion) 让明文中的每一位影响密文中的尽可能多的位，或者说让密文中的每一位都受到明文中的尽可能多位的影响。 因为在检验完全性时,无法对所有的密钥都来检验影响的必然性, 只好退而求其次,来分析这种可能性.,9,结论: (1) Feistel模型至少需要3圈才可实现完全性.
4、(2) 如果Feistel模型的 f 函数需要T圈迭代才能实现完全性,则Feistel模型经T+2圈迭代可实现完全性. (3) DES算法需且只需5圈即可实现完全性!,10,结论: (1) Feistel模型至少需要3圈才可实现完全性,且当其f 函数具有完全性时,只需3圈即可实现完全性. 证明: 设(x,y)是Feistel模型的输入,则其第1圈至第3圈的输出依次为,如果函数f是完全的, 当不考虑变换结果的抵消时,则无论改变x或y的一个比特, 第3圈的输出的左半和右半的每个比特都可能改变,这说明此时3圈能够实现完全性.,11,二、DES的S盒的设计标准,DES算法的设计者迫于公众压力公布的S盒
5、的设计标准为,1. S盒的每一位输出都不是输入的线性或仿射函数。,3. 当固定S盒的1位输入时，S盒的每一位输出中0和1的个数尽可能平衡。,2. S盒的输入发生1比特变化，输出至少有2比特发生变化。,12,1. S盒的每一位输出都不是输入的线性或仿射函数。,仿射函数的定义 设 f是n元布尔函数,如果 则称f 是仿射函数;又若仿射函数满足f(0)=0,则 f 为线性函数.,等价定义: 设 f是n元布尔函数,则 f是仿射函数等价于存在常数c1,c2,cn和a使对所有x,都有 此时,如果a=0,则 f为线性函数.,仿射函数的缺点: (1) 输入与输出之间的代数关系太简单; (2) 输入的变化与输出的
6、变化之间的代数关系太简单. 仿射函数的优点: 实现简单,13,线性性质是密码设计的大敌!,14,S盒是DES算法中唯一的非线性变换，是在DES算法起核心作用的密码变换! S盒的设计标准对于实现DES算法的完全性，对于实现混乱和扩散原则，对于确保DES算法的密码强度，具有十分重要的作用。 S盒实现了局部的混乱和扩散；这种局部的混乱和扩散通过E盒和P盒并借助于多次迭代实现了整个密码算法的混乱和扩散。 S盒只要稍有改变，其密码强度就会大大降低，因此，不要试图改变一个密码算法中的任何细节！,15,三、DES算法的互补对称性,证明：由于DES的F函数具有性质：,从而DES算法的圈函数满足,故若记,则有,
7、令D是左右块对换,则,证毕,定理,16,互补对称性的缺点:,结论: 利用DES算法的互补对称性,利用选择明文进行穷举攻击时可将密钥的加密测试量降低一半.,攻击方案:,Step1 选择两个明密对 和,Step2 令K(0)是最低位为0的所有密钥构成的集合.,Step3 对K(0)中的每个元k,计算c=Ek(m),并检验c=c1是否成立.若成立,则判定k为候选密钥;若不成立,基于,利用明密对 检验 是否为正确密钥,即检验 是否成立.若成立,则判定 为候选密钥,否则返回Step3检验K(0)中的下个元.,17,四、DES的加强方法,DES算法从一出生就受到密钥太短的责难,但NSA却声称它具有足够的安
8、全性。尽管如此,人们仍希望将其密钥变长。 将DES算法的密钥变长的一个可能方法是重新设计密钥生成算法，但这时的密码算法就不再是DES了，其密码强度必须重新分析，而且如此修改的密码算法无法与别人使用的DES互通，因而是不可取的。 此外，DES算法已经做成了一个加密芯片或加密模块，如果基于这个已有的产品来加强DES，就可降低成本。 使用不同的密钥利用DES算法对明文连续加密就是一种选择方案，这就产生了二重DES和三重DES。,18,1. 双重DES,双重DES是分别用两个不同的密钥k1和k2对明文进行两次DES变换以实现对数据的加密保护，即,19,双重DES的密钥长度是562=112比特。 但是,
9、双重DES可利用计算复杂性和存储复杂性都为256的中间相遇攻击方案攻破. 中间相遇攻击是一种以空间换时间的攻击方法.,双重DES的分析,20,对双重DES 的中间相遇攻击,Step1 以k1的256个可能值k1为DES的密钥对m加密,并将所得的256个加密结果DESk1(m)与所用密钥k1一起,按加密结果的大小排序,得到有序表 L=(DESk1(m) ,k1):k10,156. Step2 对k2的每个可能值k2为DES的密钥对c脱密,并检查脱密结果DESk2-1 (c)是否在表L中.如果 DESk2-1(c)= DESk1(m) 则判定(k1,k2)为候选密钥,否则返回Step2检验下个可能密钥.直到检验找到正确密钥为止. 成功率=1; 存储复杂性为256,最大计算复杂性为257. 数据复杂性为2个已知的明文分组.,原理:,21,双重DES的解密,22,2. 三重DES,该加密方案使用两个不同的密钥k1和k2对明文进行三次DES加密或DES脱密变换，加密函数采用一个加密-脱密-加密序列：,两个密钥的三重DES的有效密钥长度是112比特。它是一种较受欢迎的DES替代方案,目前仍然是安全的。 当k1=k2时,三重DES就是DES,因而三重DES与DES算法兼容.,23,24,下节内容,分组密码的工作模式,DES的 F 函数,