现代密码学 (9).ppt

2020 2 8 1 第四章分组密码 一 分组密码概述二 分组密码运行模式三 DES四 AES五 分组密码的分析 2020 2 8 2 四 AES 2020 2 8 3 密钥编排 轮密钥的比特数等于分组长度乘以轮数加1种子密钥被扩展为扩展密钥轮密钥从扩展密钥中按顺序选取 2020 2 8 4 分组密码的分析 2020 2 8 5 差分密码分析 Differentialcryptanalysis DES经历了近20年全世界性的分析和攻击 提出了各种方法 但破译难度大都停留在255量级上 1991年Biham和Shamir公开发表了差分密码分析法才使对DES一类分组密码的分析工作向前推进了一大步 目前这一方法是攻击迭代密码体制的最佳方法 它对多种分组密码和Hash函数都相当有效 相继攻破了FEAL LOKI LUCIFER等密码 此法对分组密码的研究设计也起到巨大推动作用 2020 2 8 6 差分密码分析 Differentialcryptanalysis 以这一方法攻击DES 尚需要用247个选择明文和247次加密运算 为什么DES在强有力的差值密码分析攻击下仍能站住脚 根据Coppersmith 1992内部报告 透露 IBM的DES研究组早在1974年就已知道这类攻击方法 因此 在设计S盒 P 置换和迭代轮数上都做了充分考虑 从而使DES能经受住这一有效破译法的攻击 2020 2 8 7 差分密码分析 Differentialcryptanalysis 差分密码分析是一种攻击迭代分组密码的选择明文统计分析破译法 它不是直接分析密文或密钥的统计相关性 而是分析明文差分和密文差分之间的统计相关性 给定一个r轮迭代密码 对已知n长明文对X和X 定义其差分为 X X X 1其中 表示n bits组X的集合中定义的群运算 X 1为X 在群中的逆元 2020 2 8 8 差分密码分析 Differentialcryptanalysis 在密钥k作用下 各轮迭代所产生的中间密文差分为 Y i Y i Y i 10 i ri 0时 Y 0 X Y 0 X Y 0 X i r时 Y Y r k i 是第i轮加密的子密钥 Y i f Y i 1 k i 由于X X 因此 Y i e 单位元 每轮迭代所用子密钥k i 与明文统计独立 且可认为服从均匀分布 2020 2 8 9 差分密码分析 Differentialcryptanalysis r轮迭代分组密码的差分序列 2020 2 8 10 差分密码分析 Differentialcryptanalysis Lai等引入Markov链描述多轮迭代分组密码的差分序列 并定义了Markov密码 Lai等证明 Markov密码的差分序列 X Y 0 Y 1 Y r 是一齐次Markov链 且若 X在群的非零元素上均匀分布 则此Markov链是平稳的 不少迭代分组密码可归结为Markov密码 如DESLOK1 FEAL和REDOC Lai 1992 2020 2 8 11 差分密码分析 Differentialcryptanalysis 一个Markov型密码 可以用转移概率P Y 1 j X i 的所有可能转移值构成的矩阵描述 称其为齐次Markov链的转移概率矩阵 以 表示 一个n bits分组密码有1 i j M 2n 1 对所有r 有 r pij r P Y r j X i 的每一行都是一概率分布 行元素之和为1 2020 2 8 12 差分密码分析 Differentialcryptanalysis 对于Markov型密码 当 X在非零元素上为均匀分布 则 Y为一平稳Markov链 此时对于每个j有即各列元素之和亦为1 从而可知各列也构成一概率分布 2020 2 8 13 差分密码分析 Differentialcryptanalysis 差分密码分析揭示出 迭代密码中的一个轮迭代函数f 若已知三元组 Y i 1 Y i Y i Y i f Y i 1 k i Y i f Y i 1 k i 则不难决定该轮密钥k i 因此轮函数f的密码强度不高 如果已知密文对 且有办法得到上一轮输入对的差分 则一般可决定出上一轮的子密钥 或其主要部分 在差分密码分析中 通常选择一对具有特定差分 的明文 它使最后一轮输入对的差值 Y r 1 为特定值 的概率很高 2020 2 8 14 差分密码分析 Differentialcryptanalysis 差分密码分析的基本思想是在要攻击的迭代密码系统中找出某高概率差分来推算密钥 一个i轮差分是一 对 其中 是两个不同明文X和X 的差分 是密码第i轮输出Y i 和Y i 之间的差分 在给定明文的差分 X 条件下 第i轮出现一对输出的差分为 的条件概率称之为第i轮差分概率 以P Y i X 表示 对于Markov密码 第i差分概率就是第i阶转移概率矩阵 i中的元素 2020 2 8 15 r轮迭代密码的差分分析 寻求第 r 1 轮差分 使概率P Y r 1 X 的值尽可能为最大 随机地选择明文X 计算X 使X 与X之差分为 在密钥k下对X和X 进行加密得Y r 和Y r 寻求能使 Y r 1 的所有可能的第r轮密钥K r 并对各子密钥ki r 计数 若选定的 X X X 对在ki r 下产生的 Y Y 满足 Y r 1 就将相应ki r 的计数增加1 重复第2步 直到计数的某个或某几个子密钥ki r 的值 显著大于其它子密钥的计数值 这一子密钥或这一小的子密钥集可作为对实际子密钥K r 的分析结果 2020 2 8 16 线性攻击 Rueppel 1986 的流密码专著中曾提出以最接近的线性函数逼近非线性布尔函数的概念 Matsui推广了这一思想以最隹线性函数逼近S盒输出的非零线性组合 1993 即所谓线性攻击 这是一种已知明文攻击法 对已知明文x密文y和特定密钥k 寻求线性表示式 a x b y d k 其中 a b d 是攻击参数 对所有可能密钥 此表达式以概率成立 对给定的密码算法 使极大化 2020 2 8 17 线性攻击 为此对每一S盒的输入和输出之间构造统计线性路径 并最终扩展到整个算法 以此方法攻击DES的情况如下 PA RISC 66MHz工作站 对8轮DES可以用221个已知明文在40秒钟内破译 对12轮DES以233个已知明文用50小时破译 对16轮DES以247个已知明文攻击下较穷举法要快 如采用12个HP9735 PA RISC99MHz的工作站联合工作 破译16轮DES用了50天 2020 2 8 18 第四章单钥体制 二 分组密码 本章到此结束 谢谢大家 2020 2 8 19 第五章公钥密码 2020 2 8 20 公钥密码 数论简介公钥密码体制的基本概念RSA算法椭圆曲线密码体制 2020 2 8 21 数论简介 2020 2 8 22 素数和互素数 因子整数a b 如果存在m 使a mb 称为b整除a 记为b a 称b是a的因子 性质a 1 则a 1a b且b a 则a b对任意b b 0 则b 0b g b h 对任意整数m n 有b mg nh 证明留给大家 2020 2 8 23 素数和互素数 素数整数p p 1 为素数 如果p的因子只有 1 p整数分解的唯一性任一整数a a 1 可唯一的分解为其中p1 p2 pt是素数 ai 0例 91 7 11 11011 7 112 13 2020 2 8 24 素数和互素数 整数分解唯一性的另一表示P是所有素数的集合 任一a a 1 可表示为ap 0 大多数指数项ap为