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

第四章第四章 分组密码分组密码一、分组密码概述一、分组密码概述二、分组密码运行模式二、分组密码运行模式三、三、DESDES四、四、AESAES五、分组密码的分析五、分组密码的分析2022/12/311四、AES2022/12/312密钥编排密钥编排n轮密钥的比特数等于分组长度乘以轮数加1n种子密钥被扩展为扩展密钥n轮密钥从扩展密钥中按顺序选取2022/12/313分组密码的分析分组密码的分析2022/12/314差分密码分析差分密码分析(Differential cryptanalysis)nDES经经历历了了近近20年年全全世世界界性性的的分分析析和和攻攻击击，提提出出了了各种方法，但破译难度大都停留在各种方法，但破译难度大都停留在255量级上。量级上。n1991年年Biham和和Shamir公公开开发发表表了了差差分分密密码码分分析析法法才才使使对对DES一一类类分分组组密密码码的的分分析析工工作作向向前前推推进进了了一一大大步步。目目前前这这一一方方法法是是攻攻击击迭迭代代密密码码体体制制的的最最佳佳方方法法，它它对对多多种种分分组组密密码码和和Hash 函函数数都都相相当当有有效效，相继攻破了相继攻破了FEAL、LOKI、LUCIFER等密码。等密码。n此法对分组密码的研究设计也起到巨大推动作用。此法对分组密码的研究设计也起到巨大推动作用。2022/12/315差分密码分析差分密码分析(Differential cryptanalysis)n以以这这一一方方法法攻攻击击DES，尚尚需需要要用用247个个选选择择明明文文和和247次次加加密密运运算算。为为什什么么DES在在强强有有力力的的差差值值密码分析攻击下仍能站住脚密码分析攻击下仍能站住脚?n根根据据Coppersmith1992内内部部报报告告透透露露，IBM的的DES研研究究组组早早在在1974年年就就已已知知道道这这类类攻攻击击方方法法，因因此此，在在设设计计S盒盒、P-置置换换和和迭迭代代轮轮数数上上都都做做了了充充分分考考虑虑，从从而而使使DES能能经经受受住住这这一一有有效破译法的攻击。效破译法的攻击。2022/12/316差分密码分析差分密码分析(Differential cryptanalysis)n差差分分密密码码分分析析是是一一种种攻攻击击迭迭代代分分组组密密码码的的选选择择明明文统计分析破译法。文统计分析破译法。n它它不不是是直直接接分分析析密密文文或或密密钥钥的的统统计计相相关关性性，而而是是分析明文差分和密文差分之间的统计相关性。分析明文差分和密文差分之间的统计相关性。n给给定定一一个个r轮轮迭迭代代密密码码，对对已已知知n长长明明文文对对X和和X，定义其差分为定义其差分为 X=X(X)-1 其其中中，表表示示n-bits组组X的的集集合合中中定定义义的的群群运运算算，(X)-1为为X在群中的逆元。在群中的逆元。2022/12/317差分密码分析差分密码分析(Differential cryptanalysis)n在在密密钥钥k作作用用下下，各各轮轮迭迭代代所所产产生生的的中中间间密密文文差分为差分为 Y(i)=Y(i)Y(i)-1 0 i rni=0时，时，Y(0)=X，Y(0)=X，Y(0)=X。ni=r时时，Y=Y(r)，k(i)是是 第第 i轮轮 加加 密密 的的 子子 密密 钥钥，Y(i)=f(Y(i1),k(i)。n由于由于X X，因此，因此，Y(i)e(单位元单位元)。n每每轮轮迭迭代代所所用用子子密密钥钥k(i)与与明明文文统统计计独独立立，且且可可认为服从均匀分布。认为服从均匀分布。2022/12/318差分密码分析差分密码分析(Differential cryptanalysis)r 轮迭代分组密码的差分序列轮迭代分组密码的差分序列 Y(0)=X Y(1)Y(2)Y(r1)Y Y(0)=X Y(1)Y(2)Y(r1)Y(r)f f f k(1)k(2)k(r)f f fX=Y(0)Y(1)Y(2)Y(r1)Y=Y(r)2022/12/319差分密码分析差分密码分析(Differential cryptanalysis)nLai等等引引入入Markov链链描描述述多多轮轮迭迭代代分分组组密密码码的的差差分序列。并定义了分序列。并定义了 Markov密码。密码。nLai等等证证明明，Markov密密码码的的差差分分序序列列 X=Y(0)，Y(1),Y(r)是是一一齐齐次次Markov链链，且且若若 X在在群群的非零元素上均匀分布，则此的非零元素上均匀分布，则此Markov 链是平稳的。链是平稳的。n不不少少迭迭代代分分组组密密码码可可归归结结为为Markov密密码码。如如DESLOK1、FEAL和和REDOC Lai.1992。2022/12/3110差分密码分析差分密码分析(Differential cryptanalysis)n一一个个Markov 型型密密码码，可可以以用用转转移移概概率率P(Y(1)=jX=i)的的所所有有可可能能转转移移值值构构成成的的矩矩阵阵描描述述，称称其其为为齐齐次次Markov 链链的的转移概率矩阵，以转移概率矩阵，以表示。表示。n一一个个n-bits分分组组密密码码有有1 i,j M=2n1。对所有对所有r，有有r=pij(r)=P(Y(r)=jX=i)的的每每一一行行都都是是一一概概率率分分布布，行行元元素素之之和和为为1。2022/12/3111差分密码分析差分密码分析(Differential cryptanalysis)对对于于Markov型型密密码码，当当 X在在非非零零元元素素上上为为均均匀匀分分布布，则则 Y为为一一平平稳稳Markov链，此时对于每个链，此时对于每个j有有 即即各各列列元元素素之之和和亦亦为为1，从从而而可可知知各各列列也也构成一概率分布。构成一概率分布。2022/12/3112差分密码分析差分密码分析(Differential cryptanalysis)n 差差分分密密码码分分析析揭揭示示出出，迭迭代代密密码码中中的的一一个个轮轮迭迭代代函函数数f，若若已已知知三三元元组组 Y(i1),Y(i),Y(i)Y(i)=f(Y(i1),k(i),Y(i)=f(Y(i1),k(i)，则不难决定该轮密钥则不难决定该轮密钥k(i)。n因因此此轮轮函函数数f的的密密码码强强度度不不高高。如如果果已已知知密密文文对对，且且有有办办法法得得到到上上一一轮轮输输入入对对的的差差分分，则则一一般般可可决决定定出出上上一一轮轮的的子子密密钥钥(或其主要部分或其主要部分)。n在在差差分分密密码码分分析析中中，通通常常选选择择一一对对具具有有特特定定差差分分 的的明明文文，它使最后一轮输入对的差值它使最后一轮输入对的差值 Y(r1)为特定值为特定值 的概率很高。的概率很高。2022/12/3113差分密码分析差分密码分析(Differential cryptanalysis)n差差分分密密码码分分析析的的基基本本思思想想是是在在要要攻攻击击的的迭迭代代密密码码系系统统中找出某高概率差分来推算密钥。中找出某高概率差分来推算密钥。n一一个个i轮轮差差分分是是一一(,)对对，其其中中 是是两两个个不不同同明明文文X和和X的差分，的差分，是密码第是密码第i轮输出轮输出Y(i)和和Y(i)之间的差分。之间的差分。n在在给给定定明明文文的的差差分分 X 条条件件下下，第第i轮轮出出现现一一对对输输出出的的差差分分为为 的的条条件件概概率率称称之之为为第第i轮轮差差分分概概率率，以以P(Y(i)=|X)表示。表示。n对对于于Markov密密码码，第第i差差分分概概率率就就是是第第i阶阶转转移移概概率率矩矩阵阵i中的元素中的元素(,)。2022/12/3114r轮迭代密码的差分分析轮迭代密码的差分分析n寻寻 求求 第第(r 1)轮轮 差差 分分(,)使使 概概 率率 P(Y(r1)=|X=)的值尽可能为最大。的值尽可能为最大。n随随机机地地选选择择明明文文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。n重重复复第第2步步，直直到到计计数数的的某某个个或或某某几几个个子子密密钥钥ki(r)的的值值，显显著著大大于于其其它它子子密密钥钥的的计计数数值值，这这一一子子密密钥钥或或这这一一小小的的子密钥集可作为对实际子密钥子密钥集可作为对实际子密钥K(r)的分析结果。的分析结果。2022/12/3115线性攻击线性攻击nRueppel1986的的流流密密码码专专著著中中曾曾提提出出以以最最接接近近的的线线性性函函数数逼逼近近非非线线性性布布尔尔函函数数的的概概念念，Matsui推推广广了了这这一一思思想想以以最最隹隹线线性性函函数数逼逼近近S盒盒输输出出的的非非零零线线性性组组合合1993，即即所所谓谓线线性性攻攻击击，这这是是一一种种已已知明文攻击法。知明文攻击法。n对已知明文对已知明文x密文密文y和特定密钥和特定密钥k，寻求线性表示式寻求线性表示式(ax)(by)=(dk)其其中中(a,b,d)是是攻攻击击参参数数。对对所所有有可可能能密密钥钥，此此表表达式以概率成立。对给定的密码算法，使极大化。达式以概率成立。对给定的密码算法，使极大化。2022/12/3116线性攻击线性攻击n为为此此对对每每一一S盒盒的的输输入入和和输输出出之之间间构构造造统统计计线线性路径，并最终扩展到整个算法性路径，并最终扩展到整个算法。n以此方法攻击以此方法攻击DES的情况如下：的情况如下：nPA-RISC/66MHz工作站，工作站，n对对8轮轮DES可以用可以用221个已知明文在个已知明文在40秒钟内破译；秒钟内破译；n对对12轮轮DES以以233个已知明文用个已知明文用50小时破译；小时破译；n对对16轮轮DES以以247个已知明文攻击下较穷举法要快。个已知明文攻击下较穷举法要快。n如如采采用用12个个HP 9735/PA-RISC99MHz的的工工作作站站联联合合工作，破译工作，破译16轮轮DES用了用了50天。天。2022/12/3117第四章第四章 单钥体制（二）单钥体制（二）分组密码分组密码 本本章章到此到此 结束。结束。谢谢大家！谢谢大家！2022/12/3118第五章第五章 公钥密码公钥密码2022/12/3119公钥密码公钥密码n数论简介数论简介n公钥密码体制的基本概念公钥密码体制的基本概念nRSARSA算法算法n椭圆曲线密码体制椭圆曲线密码体制2022/12/3120数论简介数论简介2022/12/3121素数和互素数素数和互素数n因子因子n整数整数a,ba,b,如果存在如果存在mm，使，使a=a=mbmb，称为，称为b b整除整除a a，记为，记为b|ab|a，称，称b b是是a a的因子。的因子。n性质性质na|1a|1，则，则a=1a=1na|ba|b且且b|ab|a，则，则a=ba=bn对任意对任意b,b0b,b0，则，则b|0b|0nb|g,b|hb|g,b|h,对任意整数对任意整数m,nm,n,有有b|(mg+nhb|(mg+nh)(证明留给大家证明留给大家)2022/12/3122素数和互素数素数和互素数n素数素数n整数整数p(pp(p1)1)为素数，如果为素数，如果p p的因子只有的因子只有1,p1,pn整数分解的唯一性整数分解的唯一性 任一整数任一整数a(aa(a1)1)可唯一的分解为可唯一的分解为其中其中p p1 1pp2 2ppt t是素数，是素数，a ai i0 0例：例：91=71191=711，11011=71111011=7112 213132022/12/3123素数和互素数素数和互素数n整数分解唯一性的另一表示整数分解唯一性的另一表示nP P是所有素数的集合，任一是所有素数的集合，任一a(aa(a1)1)可表示为可表示为na ap p0,0,大多数指数项大多数指数项a ap p为为0 0，任一整数可由非，任一整数可由非0 0指数指数列表表示。例如列表表示。例如1101111011可以表示为可以表示为aa7 7=1,a=1,a11 11=2,=2,a a1313=1=1n两数相乘等价于对应的指数相加两数相乘等价于对应的指数相加n由由a|ba|b可得，对每一素数可得，对每一素数p p，a ap p b bp p2022/12/3124素数和互素数nc c是是a a和和b b的最大公因子，的最大公因子，c=c=gcd(a,bgcd(a,b)nc c是是a a的因子也是的因子也是b b的因子的因子na a和和b b的任一公因子也是的任一公因子也是c c的因子的因子ngcd(a,bgcd(a,b)=1,)=1,称为称为a,ba,b互素互素2022/12/3125