（计算机软件与理论专业论文）高级加密标准的差分分析和积分分析的研究.pdf

独创性声明 本人声明 所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果 尽我所知 除文中已经标明引用的内容外 本论文不包含任何其他个人或集 体已经发表或撰写过的研究成果 对本文的研究做出贡献的个人和集体 均已在文中 以明确方式标明 本人完全意识到本声明的法律结果由本人承担 学位论文作者签名 彩铷矗 日期 坍弘年j 月r 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留 使用学位论文的规定 即 学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版 允许论文被查阅和借阅 本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索 可以采用影印 缩印或扫描等复制手段保存和汇编本学位论文 保密口 在年解密后适用本授权书 本论文属于 不保密回 请在以上方框内打 4 学位论文作者签名 日期 夯娥 l 其兮e l 指删币虢崔闺竽 日期 舻壬月r 日 下 华中科技大学硕士学位论文 l 绪论 1 1 课题背景 本课题来自 十五 国家密码发展基金 随着计算机和通信技术的发展 用户对 信息的安全存储 安全处理和安全传输的需求越来越迫切 特别地 随着互联网的广 泛应用 以及个人通信 多媒体通信 办公自动化 电子邮件 电子自动转账支付系 统和自动零售业务网的建立与实现 信息的安全保护问题就显得更加重要 解决这个 问题的有效的手段之一就是使用分组密码技术 fj 由于现在的计算机技术的飞速发展 原来的d e s d a t ae n e r y p t i o ns t a n d a r d 2 1 密码已经不能满足要求了 美国在1 9 9 7 年发起 了征集a e s a d v a n c e de n c r y p t i o ns t a n d a r d j 的活动 a e s 的征集掀起了分组密码研究 的新高潮 1 5 个a e s 候选算法反映了当前分组密码设计的水平 可以说是几年来研 究成果的一个汇总 最后r i j n d a e l l 4 1 算法被定为新一代的高级加密标准a e s m j n d a e l 算法的分组长度和密钥长度都是可变的 它们都可以单独地取为1 2 8 比特 1 9 2 比特 和2 5 6 比特中的任意一种 在r i j n d a e i 算法得到广泛的使用之前 必须要对其安全性 进行分析 因此 对r i j n d a e l 算法的安全性分析已成为密码学家目前研究热点 差分密码分析技术 5 是分组密码分析技术的一种 属于比较通用的分析方法 对 分组密码具有很强的攻击性 本课题的工作主要集中在两个方面 一是如何利用差分 密码分析技术和变形的差分密码分析技术 6 来对m j n d a e l 算法进行分析 求解出相应 的分析过程及分析代价 二是如何利用s q u a r e 方法对m j n d a e l 算法进行更深入的研究 目前 国外关于r 日n d a e l 算法的分析技术不是很多 由于r i j n d a e l 算法是在众多 的分组密码分析技术发现了以后才出现的 而且a e s 的要求就是它能抵抗现有的任何 方法的攻击 因此对此密码分析有相当的难度 耻j n d a e l 算法是个新的算法 目前国 际和国内都还没有在差分密码技术对m j n d a e l 算法得到重大的突破 为了能紧跟甚至 赶超国外研究机构在密码分析方面的研究水平 我们借鉴密码分析的关键理论技术 决心在r i j n d a e l 算法的密码分析上做出自己的贡献 在本课题研究中 将差分密码分 析技术用于对低圈次r i j n d a e l 算法的分析 由于m j n d a e l 算法是一个类s q u a r e 密码1 7 j 的算法 本课题将在已有的s q u a r e 攻击方法哺 的基础上 对其进行更深一步的研究 对于已经有的攻击方法 本课题将对p d j n d a e l 算法进行安全性强化 使它更好地抵抗 现有的攻击 l 华中科技大学硕士学位论文 1 2 国内外研究概况 1 2 1 现代分组密码技术的发展 现代分组密码技术的研究始于2 0 世纪7 0 年代中期 至今已有近3 0 年的历史 这 期间人们在这 领域已经取得了丰硕的成果 大体上 分组密码的研究包括以下的三 个方面一j 分组密码的设计原理 分组密码的安全性分析和分组密码的统计性能的测 试 分组密码的设计与分析口o 是两个即相互对立又相互依存的研究方向 正是由于这 种对立促进了分组密码的飞速发展 早期的研究基本上围绕着d e s 进行 推出了许多 的类似于d e s 的密码 例如 l o k i f e a l g o s t 等 进入了9 0 年代 人们对d e s 类密码的研究更加深入 特别是差分密码分析和线性密码分析 1 的提出 追使人们不 得不研究新的密码结构 i d e a 密码 1 2 j 的出现打破了d e s 类密码的垄断局面 i d e a 密码的设计思想是混合使用来自不同代数群中的运算 随后出现的s q u a r e s h a r k 和s a f e r 6 4 都采用了结构非常清晰的代替 置换网络 l3 1 这种结构的每一轮由混淆 层和扩散层组成 该结构的最大的优点是能够从理论上给出最大差分特性和最佳线性 逼近优势的界 也就是密码对差分密码分析和线性密码分析是可以证明安全的 1 4 目前分组密码所采用的整体结构大致可分为3 类 1 5 1 f e i s t e l 结构 采用这种结构的算d e s c a s t 2 5 6 d e a l d f c 和e 2 等 2 s p 网络 这类密码有s a f e r 和s e r p e n t 等 3 其他密码结构 如f r o g 和h p c 等 f e i s t e l 结构由于d e s 的公布而广为人知 已经被许多分组密码采用 f e i s t e l 结构的最大特点是容易保证加解密的相似 这一点在实现中尤其重要 它保证了加解 密算法可以使用同一个算法 从而减少了算法的复杂性和内存的使用 而s p 网络比 较难做到这一点 它的加解密过程一般不相同 采用求逆元来实现 但是s p 网络的 扩散性比较好 l6 1 在现有的分组密码中 所用的基本运算有异或 加 减 查表 乘 及数据依赖循环等 查表运算提供了d e s 的安全基础 仔细地选择s 盒 能比较好地 抵抗差分和线性密码分析 提供较好的数据及密钥比特的雪崩特性 不过 s 盒需要 存储器进行存储 所以 s 盒的规模不能太大 1 5 个a e s 算法所采用的s 盒的规模有 6 种 i 分别是4 4 8 8 8 3 2 1 1 8 1 3 8 与8 3 2 s 盒的另一种称呼是黑盒子 它常给人造成的故意设置陷门的嫌疑 因此 s a f e r 等选取公开的数学函数 避免 了嫌疑 s 盒的设计与分板是分组密码设计中的重要环节 1 8 2 们 它的好坏直接影响到 2 华中科技大学硕士学位论文 一 密码体制的安全性 目前对s 一盒的设计并没有一个完备的要求 但总希望是增强s 盒 的非线性度 差分均匀性和分量函数的代数次数和项数 2 如d e s 的s 盒的设计原则 是 1 s 盒不是其输入的线性或仿射函数 2 改变s 盒的一个输入比特至少导致两个输出比特的改变 3 s x 和s x 0 0 0 1 1 0 0 至少应两个比特不同 4 对任意选择的e 和f s x s 0 1l e f t 0 5 当任何一个比特保持固定时 s 盒的选择使得任 个s 盒输出中的 l 和 0 的个数之间的差最小 自1 9 7 7 年d e s 被采用以来 出版了大量有关分组密码分析的文献 但是公开文 献中尚未报道有能将密码分析的复杂度减小为穷尽搜索一半的简化算法 目前对分组 密码安全性的讨论主要包括差分密码分析 线性密码分析和强力攻击等 从理论上讲 差分密码分析和线性密码分析是目前攻击分组密码的最有效的方法 而从实际上说 强力攻击是攻击分组密码最可靠的方法 到目前为止 已有大量的文献讨论各种分组 密码的安全性 同时推出了截断差分分析口 非线性密码分析 2 2 1 和插值攻击 2 3 1 等多种 分析方法 自从a e s 候选算法公布以后 国内外许多的专家学者致力于候选算法的安 全性分析 尤其是对r i j n d a e l 算法的分析 又出现了一些新的分析方法 例如能量分 析阱 等 分组密码是现代密码学中一个重要的研究分支 其诞生和发展有着广泛的 实用背景和重要的理论价值 1 2 2 高级加密标准算法 随着现代计算机的计算处理能力的增强 d e s 算法可以在不到一天的时间内被强 行攻破 2 5 因此 迫切需要一种新的分组密码算法来代替d e s 在1 9 9 7 年 美国开 始征集a e s 算法 共有1 5 个候选算法参选 经过2 轮严格的淘汰 最终 由两个比 利时的密码学家设计的r 萄n d a e l 算法 以其没有显著的攻击方法 编码易于实现和加 解密速度快等优点 被美国国家科学技术研究所 n i s t 选作为a e s r i j n d a e l 算法 是在知道了现有的各种攻击方法之后所设计的 而且要成为政府机关和商业银行等单 位的加密算法 因此 它必定要具有的设计目标 2 6 j 是 1 抗己知攻击的强度 首先 要无d e s 型的对称性和弱密钥1 2 7 尽管有大量的 对称性 但已经注意到采取措施来消除该密码性能中的对称性 这已通过每圈使用不 同的圈常数来得到了消除 密码自身及其逆密码使用不同的构成变换这一事实 实际 上消除了诸如d e s 中存在的弱密钥和半弱密钥的可能性 密钥扩散的非线性实际上消 华中科技大学硕士学位论文 除了等价密钥的可能性 2 要对差分密码分析免疫 如果除了少数几圈外 其它所有圈都存在可以预测 的差分扩散 且有远远高于2 的扩散率口踟的话 d c d i f f e r e n t i a l c r y p t a n a l y s i s 攻击 是可能的 其中n 是分组的长度 一个差分扩散是由差分轨迹构成的 其扩散率是具 有特定的输入和输出差分模式的所有差分轨迹的扩散率之和 因此 抵抗d c 攻击的一 个必要的要求是不存在可预测的扩散率高于2 的差分轨迹 3 要对线性密码分析也免疫 如果除了少数几圈外 其它所有圈都存在可以预 测的线性扩散 且有大大的高于2 1 陀的扩散率 的话 l c l i n e a lc r y p t a n a l y s i s 攻击 是可能的 其中n 是分组的长度 一个输入输出相关性是由线性轨迹构成的 其线性 相关值是具有特定的输入和输出选取模式的所有线性轨迹的相关系数的乘积 线性轨 迹的相关系数标有符号且它们的符号取决于圈密钥的值 抵抗l c 攻击的 个必要的条 件是不存在相关系数高于2 1 的线性轨迹 4 可供政府和商业使用的功能强大的加密算法 3 0 作为d e s 的继任者 a e s 算法也是提供给政府和商业部门免费使用 而且功能要强大 不会随着现在的计算机 的处理能力的提高而对其安全性造成影响 5 支持标准密码本方式 加密的模式很多 标准密码本方式是最经常使用的一 种 而且操作简单 所以必须要支持 6 要明显比d e s31 3 l i 有效 现在银行系统中大部分的加密算法都是采用d e s 3 也就是三重的d e s 它有两个密钥 长度都是5 6 位 但是要执行3 次的d e s 的加密 操作 速度比较慢 而且也不是很安全 a e s 算法必须要具有明显比d e s 3 更优越的 性能 才可能在银行等系统中得到广泛的应用 7 密钥大小可变 这样就可在必要时增加安全性 原来的分组密码的密钥都是 固定长度的 不可变 而在a e s 算法中 密钥的长度可变 给应用带来了很大的灵活 性 也给密码分析者带来了更大的挑战 8 以公正和公开的方式进行选择 d e s 是由i b m 进行设计的 被怀疑有限门 而a e s 算法要排除这些可能性 可以被美国以外的其它国家或者机构放心使用 9 设计策略 r i j n d a e l 算法采用一种称为宽轨迹的设计策略 3 引 通过选取一个 其最大的扩散率和最大输入输出相关系数尽可能小的s 盒 用这样一种方法构造的扩 散层 该方法使得不存在多重的圈轨迹 而这些多重轨迹又几乎没有活动的s 盒 1 2 3 差分密码分析技术 差分密码分析是迄今为止已知的攻击迭代密码最为有效的方法之一 其基本的思 4 华中科技大学硕士学位论文 想是 通过分析明文对的差分值对密文对的差分的影响来恢复某些密钥比特 这种方 法通常利用生成的密文对分析具有同样特定差分的许多的明文对 在对低圈次的d e s 密码分析中 差分密码分析技术是 项很奏效的攻击方法眦3 3 l 在1 5 圈以下 差分密 码分析都可以以低于穷举的计算量将其攻破 国外学者将差分密码分析技术运用于攻 击各种的分组密码体制1 3 取得了一定的成效 如混沌密码体制等 差分密码分析技术还可以与其他的密码分析技术相结合 它与能量分析技术相结 合 形成了差分能量分析 该方法是攻击r i j n d a e l 的有效的方法之一 截断差分密码 分析也是一项在差分的基础上的攻击方法 该方法对圈密钥中的部分密钥进行差分分 析 但是差分密码分析也有其缺点 在信噪比不大于l 的情况下 就失效了 而且差 分密码分析所需要的明密文对的个数一般都很大 所需要的计算量也很大 差分密码分析技术的关键就是找到一个高概率的差分 用这个差分来随机构造一 定量的明密文对 利用明密文对的差分 从而求出相应的加密密钥 差分的形式随着 密码体制的不用也可能有所不同 对于密钥是简单异或的密码算法 其差分一般都是 选择两个明文的异或 而其它的密码算法 可能有其它更为有效的差分形式 差分密码分析技术也有其缺点 那就是随着加密圈数的增多 所需要的明密文对 的数量将按照几何级数的增长 所以它一般用来攻击圈次比较低的分组密码算法 除了差分密码分析技术以外 还有其他的一些密码分析技术 下面是其中比较常 用的几种 1 线性密码分析 线性密码分析本质上是一种己知明文攻击的方法 这种方法 可以进行推广为多重线性密码分析 非线性密码分析和划分密码分析 线性密码分析 的基本思想是通过寻找一个给定密码算法的有效的线性近似表达式来破译密码系统 2 能量密码分析 现代密码装置都是用半导体逻辑门来实现的 在操作的过程 中消耗一定的能量并且产生电磁波 而要测量密码装置所消耗的能量 在现代社会并 不难 能量分析又能细分为简单的能量分析 3 5 和差分的能量密码分析 3 6 简单能量分 析能揭示所执行的指令的顺序 而有些密码实现的指令的顺序和所执行的数据有关 因此 简单能量分析可以获取这些密码的密钥信息 除了指令序列造成的能量变化外 被执行的数据也可以造成能量变化 这些变化一般情况下比较小 容易被噪声等淹没 但是利用适当的统计函数 差分的能量分析仍然可以用这些变化破译密码 3 插值攻击 插值攻击刚的基本思想基于拉格郎日插值公式 采用逼近的方法 来求出密钥 它可以从整体上进行攻击 也可以从恢复密钥的角度进行攻击 还可以 利用中间相遇的方法进行攻击 不过 这种攻击只对圈数很少的轮函数次数很低的密 码算法才有用 华中科技大学硕士学位论文 4 差分一线性攻击 强力攻击 差分密码分析和线性密码分析是对d e s 类的三种 主要的攻击方法 对于1 6 圈的d e s 来说 由于差分密码分析和线性密码分析所需的选 择明文的个数太大 所以强力攻击仍是目前最有效的攻击 但是对差分密码分析和线 性密码分析的改进 降低它们的复杂度仍是理论研究的热点 差分 线性密码分析口砌 就是综多的改进之一 它利用了差分密码分析和线性密码分析相结合的技术 用差分 线性密码分析能攻击8 圈的d e s 可以决定 0 比特的子密钥 需要的选择明文的个数为 7 6 8 成功的概率为9 5 5 相关密钥攻击 相关密钥攻击1 3 9 反映了密钥扩展算法对分组密码的安全性的 影响 在某些分组密码中 密钥扩展算法可以看作是一些子算法的集合 每个子算法 是从前几轮子密钥导出某个特定的子密钥的过程 基于相关密钥攻击中 需要的数据 是两个具有某种关系的相关的密钥和几个明密文对 攻击者仅知道两个密钥的关系 而不知道密钥的本身 这种攻击方法可以将l o k l 8 9 攻破 i 2 4 积分攻击方法 s q u a r e 攻击是针对s q u a r e 密码而提出的一种特殊的攻击的方法 它跟踪s q u a r e 密码的面向字节 4 0 的结构进行变换的过程 这一攻击对r i j n d a e l 密码也是合适的 这 是因为r i j n d a e l 密码继承了许多s q u a r e 密码的性质 s q u a r e 攻击是一种选择明文攻击 并且与b y t e s u b 的特定选取 m i x c o l u m n 的乘积多项式和密钥调度无关 它跟踪活动 的s 盒的变化来求出相应的密钥 这种攻击方法在国外已经有了比较深入的研究 国 外的密码分析学家用该方法从理论上攻破了4 圈至6 圈的r i j n d a e l 算法1 4 1 但是 目 前该方法对更高圈次的r i j n d a e l 算法没有攻击力 1 3 课题主要研究工作 1 分析r i j n d a e l 算法的s 盒 要对p i 3 n d a e l 密码算法进行密码分析 对算法本身进行充分的了解是很有必要的 只有对算法的设计思想和实现方法进行深入的分析 尤其是字节代换中的s 盒进行仔 细的分析 找出其差分的可行性或不可行性 结合其他的密码分析方法 主要是s q u a r e 密码分析方法 对r i j n d a e l 密码算法进行理论上的强度分析 并在实验中证明分析的 结果 2 采用差分分析和s q u a r e 分析方法对r i j n d a e l 进行攻击 分组密码的分析方法有很多种 其中差分密码分析和线性密码分析是大多数分组 密码的最为有效的分析方法 s q u a r e 密码分析方法是对r j n d a e l 类面向字节的分组密 6 华中科技大学硕士学位论文 4 差分一线性攻击 强力攻击 差分密码分析和线性密码分析是对d e s 类的三种 主要的攻击方法 对于1 6 圈的d e s 来说 由于差分密码分析和线性密码分析所需的选 择明文的个数太大 所以强力攻击仍是目前最有效的攻击 但是对差分密码分析和线 性密码分析的改进 降低它们的复杂度仍是理论研究的热点 差分 线性密码分析口砌 就是综多的改进之一 它利用了差分密码分析和线性密码分析相结合的技术 用差分 线性密码分析能攻击8 圈的d e s 可以决定 0 比特的子密钥 需要的选择明文的个数为 7 6 8 成功的概率为9 5 5 相关密钥攻击 相关密钥攻击1 3 9 反映了密钥扩展算法对分组密码的安全性的 影响 在某些分组密码中 密钥扩展算法可以看作是一些子算法的集合 每个子算法 是从前几轮子密钥导出某个特定的子密钥的过程 基于相关密钥攻击中 需要的数据 是两个具有某种关系的相关的密钥和几个明密文对 攻击者仅知道两个密钥的关系 而不知道密钥的本身 这种攻击方法可以将l o k l 8 9 攻破 i 2 4 积分攻击方法 s q u a r e 攻击是针对s q u a r e 密码而提出的一种特殊的攻击的方法 它跟踪s q u a r e 密码的面向字节 4 0 的结构进行变换的过程 这一攻击对r i j n d a e l 密码也是合适的 这 是因为r i j n d a e l 密码继承了许多s q u a r e 密码的性质 s q u a r e 攻击是一种选择明文攻击 并且与b y t e s u b 的特定选取 m i x c o l u m n 的乘积多项式和密钥调度无关 它跟踪活动 的s 盒的变化来求出相应的密钥 这种攻击方法在国外已经有了比较深入的研究 国 外的密码分析学家用该方法从理论上攻破了4 圈至6 圈的r i j n d a e l 算法1 4 1 但是 目 前该方法对更高圈次的r i j n d a e l 算法没有攻击力 1 3 课题主要研究工作 1 分析r i j n d a e l 算法的s 盒 要对p i 3 n d a e l 密码算法进行密码分析 对算法本身进行充分的了解是很有必要的 只有对算法的设计思想和实现方法进行深入的分析 尤其是字节代换中的s 盒进行仔 细的分析 找出其差分的可行性或不可行性 结合其他的密码分析方法 主要是s q u a r e 密码分析方法 对r i j n d a e l 密码算法进行理论上的强度分析 并在实验中证明分析的 结果 2 采用差分分析和s q u a r e 分析方法对r i j n d a e l 进行攻击 分组密码的分析方法有很多种 其中差分密码分析和线性密码分析是大多数分组 密码的最为有效的分析方法 s q u a r e 密码分析方法是对r j n d a e l 类面向字节的分组密 6 华中科技大学硕士学位论文 码比较有效的攻击手段 在对上述密码分析技术上的比较于分析 找出适合各种 r i j n d a e l 圈次算法的分析方法 7 华中科技大学硕士学位论文 2 差分密码分析在高级加密标准上的运用 本章主要对差分密码分析涉及的理论和技术以及r i j n d a e l 算法的结构进行分析 在全面介绍了差分密码分析技术和r i j n d a e l 算法流程的内容后 对差分密码分析技术 如何攻击2 圈r i j n d a e l 算法进行了分析研究 对差分密码分析技术的变形一不可能差 分密码分析技术在攻击5 圈的基础上如何攻击6 圈r i j n d a e l 算法进行了分析 并给出 了分析的算法和结果 2 1 分组密码分析技术 分组密码算法就是要为数据的传输提供一个端到端的通信的安全通道 为了使得 数据传输的过程中保持数据的隐秘性 分组加密算法的强度就很重要了 一个强度很 高的分组算法 使得攻击者在有限的时间内没有办法攻破该算法 从而恢复明文 分析 分组加密算法的强度有很多种分析方法 这些分柝方法有些是通用的 有些是专门为 某种加密算法而设计的攻击方法 这些分析方法的使用为分析分组密码算法的强度分 析提供了有力的帮助 更为重要的是 这些分析方法的出现 加速了分组密码算法的 发展 一直以来 分组密码的设计与分组密码的分析技术共同发展的 在种类繁多的 分组密码分析技术中 差分密码分析技术就是其中最典型的通用的分析方法 本节将 全面介绍差分密码分析技术所涉及到的理论知识 并对差分密码分析技术的一般步骤 进行了论述 2 1 1 差分密码分析技术 差分密码分析技术是在对d e s 算法的分析过程中发现的 后来 密码学家发现差 分密码分析技术对大部分的类d e s 算法都具有很强的攻击力 尤其是对低圈次的算 法 差分密码分析是迄今为止已知的攻击迭代密码最为有效的方法之一 要熟练使用 差分密码分析技术 就需要对差分密码分析技术有个比较清晰的了解 其基本的思想 是 通过分析明文对的差分值对密文对的差分的影晌来恢复某些密钥比特 这种方法 通常利用生成的密文对分析具有同样特定差分的许多的明文对 要熟悉差分密码分析 技术 首先要明白差分密码分析中的几个概念 这几个概念将在下面的论述中要使用 到 1 差分 对分组长度为n 的 轮迭代密码 将两个n 比特串x i 和工 的差分定义 华中科技大学硕士学位论文 2 差分密码分析在高级加密标准上的运用 本章主要对差分密码分析涉及的理论和技术以及r i j n d a e l 算法的结构进行分析 在全面介绍了差分密码分析技术和r i j n d a e l 算法流程的内容后 对差分密码分析技术 如何攻击2 圈r i j n d a e l 算法进行了分析研究 对差分密码分析技术的变形一不可能差 分密码分析技术在攻击5 圈的基础上如何攻击6 圈r i j n d a e l 算法进行了分析 并给出 了分析的算法和结果 2 1 分组密码分析技术 分组密码算法就是要为数据的传输提供一个端到端的通信的安全通道 为了使得 数据传输的过程中保持数据的隐秘性 分组加密算法的强度就很重要了 一个强度很 高的分组算法 使得攻击者在有限的时间内没有办法攻破该算法 从而恢复明文 分析 分组加密算法的强度有很多种分析方法 这些分柝方法有些是通用的 有些是专门为 某种加密算法而设计的攻击方法 这些分析方法的使用为分析分组密码算法的强度分 析提供了有力的帮助 更为重要的是 这些分析方法的出现 加速了分组密码算法的 发展 一直以来 分组密码的设计与分组密码的分析技术共同发展的 在种类繁多的 分组密码分析技术中 差分密码分析技术就是其中最典型的通用的分析方法 本节将 全面介绍差分密码分析技术所涉及到的理论知识 并对差分密码分析技术的一般步骤 进行了论述 2 1 1 差分密码分析技术 差分密码分析技术是在对d e s 算法的分析过程中发现的 后来 密码学家发现差 分密码分析技术对大部分的类d e s 算法都具有很强的攻击力 尤其是对低圈次的算 法 差分密码分析是迄今为止已知的攻击迭代密码最为有效的方法之一 要熟练使用 差分密码分析技术 就需要对差分密码分析技术有个比较清晰的了解 其基本的思想 是 通过分析明文对的差分值对密文对的差分的影晌来恢复某些密钥比特 这种方法 通常利用生成的密文对分析具有同样特定差分的许多的明文对 要熟悉差分密码分析 技术 首先要明白差分密码分析中的几个概念 这几个概念将在下面的论述中要使用 到 1 差分 对分组长度为n 的 轮迭代密码 将两个n 比特串x i 和工 的差分定义 华中科技大学硕士学位论文 为 j x o x l 其中 表示 比特串集上的一个特定的群运算 x 一表示x 在此群中的逆元 2 正确对 n 一圈特征和非相关密钥k 的正确对是满足输入差分且对用非相关密钥 加密的前n 圈的每一圈i 第i 圈的输入x o r 等于圈特征中相应的差分 3 错误对 除了正确对以外都是错误对 由加密算法的加密过程可以得到差分序列 馘a 蚁 磷l 蚁 其中x 和x 是明文对 爿 和x 1 i 是第i 轮的输出 它们同时也是第i 1 轮 的输入 假如第i 轮的子密钥为彪 迭代轮函数为f 则置 z 置 对上面的函数进行分析发现 迭代密码的简单的轮函数f 在如下意义下通常是密 码上弱的 对于x f x k 和x y x k 若三元组 硝 五 z 的一个 或多个值是已知的 确定子密钥k 是容易的 从而 若密文对己知 并且晟后一轮的 输入对的差分可以能以某种方式得到 则一般来说 确定最后一轮的子密钥或其一部 分是可行的 在差分密码分析中 通过选择具有特定差分值a 的明文对 五 x 使 得最后一轮的输入差分腊 以很高的概率取特定的值盘 的来达到这一点 对于d e s 和许多其他类d e s 的密码体制 这种差分被选作两个明文对的固定的x o r 值 对于 m j n d a e l 算法 目前也是取其明文对的固定的x o r 值 为了简化我们的数学分析 我们假定所有的子密钥都是非相关的 实验证明用相 关子密钥对各种算法的攻击具有同样成功的概率 但是这种概率的理论分析困难很多 2 1 2 差分密码分析的一般步骤 我们对差分密码分析技术进行概括 发现差分密码分柝算法有它基本的实现步骤 对r 轮迭代密码的差分密码攻击的基本过程可描述为如下的算法 第1 步 找出一个r 一1 轮的特征q a 口 以 使得它的概率达到最大或 几乎最大 所谓 轮特征是指 差分序列 口0 a 1 口2 口r 其中瓯是明文对x 和 的差分 口 1 i 是第i 轮输出x 和z 的差分a r 一 轮特征q 的概率是指在明文x 和子密钥独立 均匀随机时 明文对x 和x 的差分 为瓯的条件下 第f 轮 1 i r 的输出x 和x 的差分为a 的概率 华中科技大学硕士学位论文 第2 步 均匀随机地选择明文 并计算蜀 使得五和氓 的差分为 找出x o 和扎 在实际密钥加密下所得的密文x 和并 若最后一轮的子密钥足 或k 的部分 比特 有2 个可能的值足j 1 k 2 设置相应的2 个计数器a 1 j 2 用 所有的值解密密文 和x 得到文 和x 如果的差分是d 则给相应的计数 器加1 第3 步 重复第2 步 直到一个或几个计数器的值明显高于其他计数器的值 输 出它们所对应的子密钥比特 或部分比特 从上面的算法可知 差分密码分析的数据复杂度两倍于成对加密所需的选择明文 对 z 凰 的个数 差分密码分析的处理复杂度是从 硝 x x r 找出子密钥 世 或k 的部分比特 的计算量 它实际上与r 无关 而且由于轮函数是弱的 所以此 计算量在大多数情况下相对较小 因此 差分密码分析的复杂度取决于它的数据复杂 度 在实际的应用中 攻击者一般是推测世 的部分比特 这是因为k 的可能值太多 以至于第2 步无法实现 把要预测的符 的k 比特的正确值记为 c p k c o r r e c tp a r t i a lk e y 其他不正确的统统记为p p k p s e u d o p a r t i a lk e y 设需 要m 个选择选择明文对 对每个选择明文对 和矾 攻击者在步骤2 中 给出c p k 的一些候选值 令表示每次攻击所给出的侯选值的平均个数 如果x 和凰 是正确对 则c p k 一定在侯选值中 如果瓦和凰 是错误对 则c p k 不 定在侯选值中 在两种 情况下 c p k 被选为候选值 一种是被正确对选中 它的次数是s m p o 一 另一种 是被错误对选定 它的次数是 m x y r x 一2 这是因为错误对选定印 的机会和选定 z 其他阳 的机会相同 而m a 次攻击所预测的值共有m x ax 7 个 其中y 是在攻击 的第2 步中 预先丢掉 部分的错误对后 没有被丢掉的选择明文对的个数与m 之比 差分密码分析的有效性和 的大小有关 越大 差分密码分析的成功率越高 如 1 k 一 果以 兰 半蔓1 则攻击的第3 步无法实现 因此 差分密码分析成功的必要条件 o o r x z 是保证s n 1 s n 的值可以通过下面两个途径提高 一个是寻找高概率特征 另一 个是降低错误对的平均个数 差分密码分析所需的选择明文对的个数和 有关 实验 结果表明 当 丝2 时 攻击需要的选择明文对的个数大约为2 0 4 0 个 因此所需 的选择明文对的个数大约为 当 较大时 有时3 4 个正确对就足够了 差分密码分 析方法攻击8 轮d e s 需要2 埘个选择明文f 1 2 实际上 计算每对记数密钥 五的平均 数通常比单独计算7 和丑的值要简单一些 但若预先知道更多高概率的 一1 轮的圈特 征 则有下述的攻击方法 设一是攻击者预先知道的明文差分的集合 使得对于每个 1 0 华中科技大学硕士学位论文 口 a 都存在一个高概率的r 一1 轮特征d 口 对于每对明密文对 肖o x 和 x o x 如果x o 和j o 的差分是a a 则利用特征 岱2 a 找 出子密钥k 或k 的部分比特 的所有可能的值 并在相应的计数器上加1 对每对这 样的明文对重复上面的操作 若子密钥k 或k 的部分比特 的某些值的计数明显高 于其他值的计数 则这些值被看作为实际的子密钥的可能值 并用其他的方法对它们 做进一步的检测 2 2 高级加密标准算法 在对1 5 个a e s 候选算法进行两轮的严格筛选后 r i j n d a e l 算法成为了新的a e s 标准 要对r i j n d a e l 算法进行攻击 就必须对r i j n d a e l 算法结构的实现过程和算法的 基本理论有个清楚的了解 这些基础知识将会有助于对了解下面的攻击过程起到很大 的帮助作用 2 2 1 数学基础 r i j n d a e l 算法是个面向字节代换的算法 因此大部分运算都是按字节定义的 采 用字节表示有限域g f 2 8 中的元素 而其它的运算是按4 字节的方式定义的 1 有限域g f 2 8 一个有限域中的元素可以用多种不同的方法表示 鉴于实现方面的原因 我们选 择传统的多项式表示 构成的一个字节b 看成系数在 o 1 中的多项式 b 7 x 7 b 6 x 6 b 5 x 5 6 4 x 4 b 3 x 3 6 2 x 2 b t x b o g f 28 中的加法定义为多项式的二元加法 系数为模2 加 1 l o 例如 5 7 8 3 d 4 或用多项式计法为 z 6 x 4 石2 x 1 x7 x 1 x 7 x 6 x 4 x 2 在二元计法中 我们有 0 1 0 1 0 1 1 1 1 0 0 0 0 0 l l 1 l o l o l o o 显然 该加法与简单 的按字节为单位的比特异或e x o r 记为0 是一致的 一个a b e l 群必须满足的所有必要的条件都满足 闭合 结合律 单位元 o o 逆元 每个元素是其自身的加法逆元 及交换律 由于每个元素是其自身的加法逆元 因此 减法与加法相同 g f 2 8 中的乘法定义为一个模8 次不可约二元多项式乘法 个不可约二元多项 式能被1 和自身整除外不能被其它的任何二元多项式整除 对于r n d a e l 密码 这一 个不可约多项式称为m x 由下面式子给出 华中科技大学硕士学位论文 口 a 都存在一个高概率的r 一1 轮特征d 口 对于每对明密文对 肖o x 和 x o x 如果x o 和j o 的差分是a a 则利用特征 岱2 a 找 出子密钥k 或k 的部分比特 的所有可能的值 并在相应的计数器上加1 对每对这 样的明文对重复上面的操作 若子密钥k 或k 的部分比特 的某些值的计数明显高 于其他值的计数 则这些值被看作为实际的子密钥的可能值 并用其他的方法对它们 做进一步的检测 2 2 高级加密标准算法 在对1 5 个a e s 候选算法进行两轮的严格筛选后 r i j n d a e l 算法成为了新的a e s 标准 要对r i j n d a e l 算法进行攻击 就必须对r i j n d a e l 算法结构的实现过程和算法的 基本理论有个清楚的了解 这些基础知识将会有助于对了解下面的攻击过程起到很大 的帮助作用 2 2 1 数学基础 r i j n d a e l 算法是个面向字节代换的算法 因此大部分运算都是按字节定义的 采 用字节表示有限域g f 2 8 中的元素 而其它的运算是按4 字节的方式定义的 1 有限域g f 2 8 一个有限域中的元素可以用多种不同的方法表示 鉴于实现方面的原因 我们选 择传统的多项式表示 构成的一个字节b 看成系数在 o 1 中的多项式 b 7 x 7 b 6 x 6 b 5 x 5 6 4 x 4 b 3 x 3 6 2 x 2 b t x b o g f 28 中的加法定义为多项式的二元加法 系数为模2 加 1 l o 例如 5 7 8 3 d 4 或用多项式计法为 z 6 x 4 石2 x 1 x7 x 1 x 7 x 6 x 4 x 2 在二元计法中 我们有 0 1 0 1 0 1 1 1 1 0 0 0 0 0 l l 1 l o l o l o o 显然 该加法与简单 的按字节为单位的比特异或e x o r 记为0 是一致的 一个a b e l 群必须满足的所有必要的条件都满足 闭合 结合律 单位元 o o 逆元 每个元素是其自身的加法逆元 及交换律 由于每个元素是其自身的加法逆元 因此 减法与加法相同 g f 2 8 中的乘法定义为一个模8 次不可约二元多项式乘法 个不可约二元多项 式能被1 和自身整除外不能被其它的任何二元多项式整除 对于r n d a e l 密码 这一 个不可约多项式称为m x 由下面式子给出 华中科技大学硕士学位论文 m x x 8 x 4 x 3 x l 或用十六进制 1 1 b 表示 例如 5 7 8 3 c 1r 或者 x 6 x4 x 2 x 1 x7 x 1 x 7 x 6 x 4 x 2 x 3 x x 9 x8 x 1 x 7 x5 x 3 x 2 x x 6 十x 4 了2 x 1 m o d x 8 x 4 x 3 x7 x 6 1 显然该结果是次数小于8 的一个二元多项式 不像加法 这里没有简单的按字节 的运算 上面定义的乘法运算满足结合律 且有一个单位元 0 1 对任何次数小于8 的二元多项式b x 欧几里德扩充算法可以用来计算多项式a x e x 使得 b x a x m x c x 1 由此可得 对2 5 6 个可能字节值的集合 以比特异或e x o r 作为集合中元素的加法和以上述定义为乘法作为集合中元素的乘法 则该集台有有限 域o f 2 8 1 的结构 2 系数在o f 2 8 1 中的多项式 多项式可以定义为其系数在o f 2 8 中 在这一方面 4 一字节向量对应于次数小于 4 的多项式 对相应的系数相加就可以实现多项式的相加 由于g f 2 8 中的加法为比特异或 因此 两个向量的加法是一个简单的异或 乘法则比较复杂 假设我们有o f 2 8 上的两个多项式 d x a 3 x 3 a 2 x 2 a l x d o 和6 x b3 x 3 6 2 x 2 6 1 x b o 它f 门的乘积 c x a x b x 由下面给出 c x c 6 2 6 c 5 x 5 c 4 x 4 c3 x 3 c 2 x 2 q x c o 其中 c o b oc 4 a 3 b io a 2 b 20 a l b 3 c 1 a 1 b o0 a o b ic 5 a 3 b 20 a 2 b 3 c 2 a o b 2o q b l0 a 2 b oc 6 a 3 b 3 c 3 a 3 b 0 a 1 b 2o 口2 b lo a o b 3 显然 c x 不再可以表示为4 一字节向量 通过一个4 次多项式来对c x 进行化简 该结果可以化简为一个次数小于4 次的多项式 在r i j n d a e l 密码中 这个模多项式为 m x x 4 1 由于x m o dx 4 1 x r o o d 4 则a x 和b x 取模乘积记为 d x 口 z 0 6 x 这由下面的表达式给出 d x d 3 x 3 d 2 x 2 d l x d o d o a o b 0 0 a 3 b 0 a 2 b 2 0 a l b 3 d l 口o b l o a l b 0 0 口2 b 3 0 a 3 b 2 d 2 b 2 0 口i b 1 0 a 2 b 0 0 a 3 b 3 1 2 华中科技大学硕士学位论文 d 3 a o b 3o 口1 b 2o a 2 6 lo d 3 b 3 被一个固定的多项式口 x 相乘所构成的运算可以写成矩阵乘法 其中的矩阵是一 个循环矩阵 令c x 口 z 0 6 z 则有 c o c l c 2 f 3 日on 3 d l盘0 a 2口1 岛口2 qq 口3口2 口0d 3 盘1辟0 2 2 2 高级加密标准算法描述 为了更好描述r i j n d a e l 算法的流程 定义了 个描述中间结果的术语 状态 s t a t e 以下各个不同的变换都在状态上定义的运算 我们可以用字节的一个矩阵阵列图表示状态 该阵列有4 行 列数记为n b 且等 于分组长度除以3 2 密钥类似地用一个4 行的矩阵阵列图表示 密钥的列数记为n k 且等于密钥长度除蜕3 2 这用图2 i 表示 卸da o j a o a 0 3即 a o j q oa l ja l j a 1 3 a l a l j 屯口妁j 屯 码3 勾 幻j 直a 3 j a 3 3a 3 3 码鼻a 3 j b d l o jk 0 k 0 3 h 卫k uk 1 工 k 1 3 b 上 k j b b 3 kb j 坞jb j 图2 1o 妯 6 和 n k 4 密钥布局的例子 密码的输入 如果是使用e c b 电子密码本方式加密模式 输入就是明文 按 g o o a 1 0 口2 a 啪 a l 口2 的顺序被映射到状态字节 在密码运算结束时 密码输出 结果是以同样的顺序取状态字节来从状态中获得的 分析r i j n d a e l 算法 我们发现是它的加解密过程由几个连续的圈变换及其逆变换 r o u n d s t a t e r o u n d k e y b y t e s u b s t a t e s h i f t r o w s t a t e m i x c o l u m n s t a t e a d d r o u n d k e y s t a t e r o u n d k e y 1 3 华中科技大学硕士学位论文 组成 这些变换都是单独作用在状态上 每个圈变换由四个不同的变换组成 上面就 是它的伪c 代码描述 它的逆变换也由4 个不同变换组成 用伪c 代码进行描述 则 可以表示成为下面的形式 i n v r o u n d s t a t e r o u n d k e y a d d r o u n d k e y s t a t e r o u n d k e y l n m i x c o l u m n s t a t e i n v s h i f t r o w s t a t e j 刖脚t e s u b s t a t e 密码的结尾圈稍微有点不同 它是如下定义的 f i n a l r o u n d s t a t e r o u n d k e y b y t e s u b s t a t e s h i f i r o w s t a t e a d d r o u n d k e y s t a t e r o u n d k e y 它的逆变换为 i n v f i n a l r o u n d s t a t e r o u n d k e y a d d r o u n d k e y s t a t e r o u n d k e y l n v s h i f l r o w s t a t e l n v b y t e s u b s t a t e r i i n d a e l 密码是一个迭代分组密码 为了更好适应商业和政府的需要 其分组长 度和密钥长度都可变 分组长度和密钥长度可以独立地指定为1 2 8 比特 1 9 2 比特或 者2 5 6 比特 加密时的圈数记为n r n r 与n b 和n k 有关 表2 1 给出了n r 与n b 和 n k 之间的关系 要对r i j n d a e l 算法进行攻击 熟悉圈变换中的每一步如何在状态上进行操作就很 有必要了 下面将就圈变换中的字节代换 行移位 列混合和圈密钥加进行详细的论 述 并对圈密钥的产生过程进行分析 1 4 华中科技大学硕士学位论文 表2 1 n r 与n b 和n k 的关系 n rn b 4n b 6 n b 8 n k d1 0