DES算法的安全性分析

1 des算法的安全性分析 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加密