《DES安全性》PPT课件.ppt

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