第9讲--DES安全性.ppt

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