现代密码学课件--第9讲 分组密码5.ppt

1、2020/10/9,1,第四章 分组密码,一、分组密码概述 二、分组密码运行模式 三、DES 四、AES 五、分组密码的分析,2020/10/9,2,四、AES,2020/10/9,3,密钥编排,轮密钥的比特数等于分组长度乘以轮数加1 种子密钥被扩展为扩展密钥 轮密钥从扩展密钥中按顺序选取,2020/10/9,4,分组密码的分析,2020/10/9,5,差分密码分析(Differential cryptanalysis),DES经历了近20年全世界性的分析和攻击，提出了各种方法，但破译难度大都停留在255量级上。 1991年Biham和Shamir公开发表了差分密码分析法才使对DES一类分组密

2、码的分析工作向前推进了一大步。目前这一方法是攻击迭代密码体制的最佳方法，它对多种分组密码和Hash 函数都相当有效，相继攻破了FEAL、LOKI、LUCIFER等密码。 此法对分组密码的研究设计也起到巨大推动作用。,2020/10/9,6,差分密码分析(Differential cryptanalysis),以这一方法攻击DES，尚需要用247个选择明文和247次加密运算。为什么DES在强有力的差值密码分析攻击下仍能站住脚? 根据Coppersmith1992内部报告透露，IBM的DES研究组早在1974年就已知道这类攻击方法，因此，在设计S盒、P-置换和迭代轮数上都做了充分考虑，从而使DES

3、能经受住这一有效破译法的攻击。,2020/10/9,7,差分密码分析(Differential cryptanalysis),差分密码分析是一种攻击迭代分组密码的选择明文统计分析破译法。 它不是直接分析密文或密钥的统计相关性，而是分析明文差分和密文差分之间的统计相关性。 给定一个r轮迭代密码，对已知n长明文对X和X，定义其差分为 X=X(X)-1 其中，表示n-bits组X的集合中定义的群运算，(X)-1为X在群中的逆元。,2020/10/9,8,差分密码分析(Differential cryptanalysis),在密钥k作用下，各轮迭代所产生的中间密文差分为 Y(i)=Y(i)Y(i)-1

4、 0ir i=0时，Y(0)=X，Y(0)=X，Y(0)=X。 i=r时，Y=Y(r)，k(i)是第i轮加密的子密钥，Y(i)=f(Y(i1), k(i)。 由于XX，因此，Y(i)e(单位元)。 每轮迭代所用子密钥k(i)与明文统计独立，且可认为服从均匀分布。,2020/10/9,9,差分密码分析(Differential cryptanalysis),r 轮迭代分组密码的差分序列,2020/10/9,10,差分密码分析(Differential cryptanalysis),Lai等引入Markov链描述多轮迭代分组密码的差分序列。并定义了 Markov密码。 Lai等证明，Markov密

5、码的差分序列X=Y(0)，Y(1), , Y(r)是一齐次Markov链，且若X在群的非零元素上均匀分布，则此Markov 链是平稳的。 不少迭代分组密码可归结为Markov密码。如DESLOK1、FEAL和REDOC Lai. 1992。,2020/10/9,11,差分密码分析(Differential cryptanalysis),一个Markov 型密码，可以用转移概率P(Y(1)=jX=i)的所有可能转移值构成的矩阵描述，称其为齐次Markov 链的转移概率矩阵，以表示。 一个n-bits分组密码有1i, jM=2n1。对所有r，有 r=pij (r)=P(Y(r)=jX=i) 的每一

6、行都是一概率分布，行元素之和为1。,2020/10/9,12,差分密码分析(Differential cryptanalysis),对于Markov型密码，当X在非零元素上为均匀分布，则Y为一平稳Markov链，此时对于每个j有 即各列元素之和亦为1，从而可知各列也构成一概率分布。,2020/10/9,13,差分密码分析(Differential cryptanalysis),差分密码分析揭示出，迭代密码中的一个轮迭代函数f，若已知三元组Y(i1), Y(i), Y(i) Y(i)=f(Y(i1), k(i), Y(i)=f(Y(i1), k(i)，则不难决定该轮密钥k(i)。 因此轮函数f的

7、密码强度不高。如果已知密文对，且有办法得到上一轮输入对的差分，则一般可决定出上一轮的子密钥(或其主要部分)。 在差分密码分析中，通常选择一对具有特定差分的明文，它使最后一轮输入对的差值Y(r1)为特定值的概率很高。,2020/10/9,14,差分密码分析(Differential cryptanalysis),差分密码分析的基本思想是在要攻击的迭代密码系统中找出某高概率差分来推算密钥。 一个i轮差分是一(, )对，其中是两个不同明文X和X的差分，是密码第i轮输出Y(i)和Y(i)之间的差分。 在给定明文的差分X条件下，第i轮出现一对输出的差分为的条件概率称之为第i轮差分概率，以P(Y(i)=|

8、X)表示。 对于Markov密码，第i差分概率就是第i阶转移概率矩阵i中的元素(, )。,2020/10/9,15,r轮迭代密码的差分分析,寻求第(r1)轮差分(, )使概率P(Y(r1)=|X=)的值尽可能为最大。 随机地选择明文X，计算X使X与X之差分为，在密钥k下对X和X进行加密得Y(r)和Y(r)，寻求能使Y(r1)=的所有可能的第r轮密钥K(r)，并对各子密钥ki(r)计数，若选定的X=，(X, X)对在ki(r)下产生的(Y, Y)满足Y(r1)=，就将相应ki(r)的计数增加1。 重复第2步，直到计数的某个或某几个子密钥ki(r)的值，显著大于其它子密钥的计数值，这一子密钥或这一

9、小的子密钥集可作为对实际子密钥K(r)的分析结果。,2020/10/9,16,线性攻击,Rueppel1986的流密码专著中曾提出以最接近的线性函数逼近非线性布尔函数的概念，Matsui推广了这一思想以最隹线性函数逼近S盒输出的非零线性组合1993，即所谓线性攻击，这是一种已知明文攻击法。 对已知明文x密文y和特定密钥k，寻求线性表示式 (ax)(by)=(dk) 其中(a, b, d)是攻击参数。对所有可能密钥，此表达式以概率成立。对给定的密码算法，使极大化。,2020/10/9,17,线性攻击,为此对每一S盒的输入和输出之间构造统计线性路径，并最终扩展到整个算法。 以此方法攻击DES的情况

10、如下： PA-RISC/66MHz工作站， 对8轮DES可以用221个已知明文在40秒钟内破译； 对12轮DES以233个已知明文用50小时破译； 对16轮DES以247个已知明文攻击下较穷举法要快。 如采用12个HP 9735/PA-RISC99MHz的工作站联合工作，破译16轮DES用了50天。,2020/10/9,18,第四章 单钥体制（二）分组密码,本章到此 结束。 谢谢大家！,2020/10/9,19,第五章 公钥密码,2020/10/9,20,公钥密码,数论简介 公钥密码体制的基本概念 RSA算法 椭圆曲线密码体制,2020/10/9,21,数论简介,2020/10/9,22,素数

11、和互素数,因子 整数a,b,如果存在m，使a=mb，称为b整除a，记为b|a，称b是a的因子。 性质 a|1，则a=1 a|b且b|a，则a=b 对任意b,b0，则b|0 b|g,b|h,对任意整数m,n,有b|(mg+nh) (证明留给大家),2020/10/9,23,素数和互素数,素数 整数p(p1)为素数，如果p的因子只有1,p 整数分解的唯一性 任一整数a(a1)可唯一的分解为 其中p1p2pt是素数，ai0 例：91=711，11011=711213,2020/10/9,24,素数和互素数,整数分解唯一性的另一表示 P是所有素数的集合，任一a(a1)可表示为 ap0,大多数指数项ap为0，