第四章-分组密码5-现代密码学课件.ppt

第四章第四章 分组密码分组密码一、分组密码概述一、分组密码概述二、分组密码运行模式二、分组密码运行模式三、三、DESDES四、四、AESAES五、分组密码的分析五、分组密码的分析2023/3/291四、AES2023/3/292密钥编排密钥编排n轮密钥的比特数等于分组长度乘以轮数加1n种子密钥被扩展为扩展密钥n轮密钥从扩展密钥中按顺序选取2023/3/293分组密码的分析分组密码的分析2023/3/294差分密码分析差分密码分析(Differential cryptanalysis)n以以这这一一方方法法攻攻击击DES，尚尚需需要要用用247个个选选择择明明文文和和247次次加加密密运运算算。为为什什么么DES在在强强有有力力的的差差值值密码分析攻击下仍能站住脚密码分析攻击下仍能站住脚?n根根据据Coppersmith1992内内部部报报告告透透露露，IBM的的DES研研究究组组早早在在1974年年就就已已知知道道这这类类攻攻击击方方法法，因因此此，在在设设计计S盒盒、P-置置换换和和迭迭代代轮轮数数上上都都做做了了充充分分考考虑虑，从从而而使使DES能能经经受受住住这这一一有有效破译法的攻击。效破译法的攻击。2023/3/296差分密码分析差分密码分析(Differential cryptanalysis)n差差分分密密码码分分析析是是一一种种攻攻击击迭迭代代分分组组密密码码的的选选择择明明文统计分析破译法。文统计分析破译法。n它它不不是是直直接接分分析析密密文文或或密密钥钥的的统统计计相相关关性性，而而是是分析明文差分和密文差分之间的统计相关性。分析明文差分和密文差分之间的统计相关性。n给给定定一一个个r轮轮迭迭代代密密码码，对对已已知知n长长明明文文对对X和和X，定义其差分为定义其差分为 X=X(X)-1 其其中中，表表示示n-bits组组X的的集集合合中中定定义义的的群群运运算算，(X)-1为为X在群中的逆元。在群中的逆元。2023/3/297差分密码分析差分密码分析(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)与与明明文文统统计计独独立立，且且可可认为服从均匀分布。认为服从均匀分布。2023/3/298差分密码分析差分密码分析(Differential cryptanalysis)nLai等等引引入入Markov链链描描述述多多轮轮迭迭代代分分组组密密码码的的差差分序列。并定义了分序列。并定义了 Markov密码。密码。nLai等等证证明明，Markov密密码码的的差差分分序序列列 X=Y(0)，Y(1),Y(r)是是一一齐齐次次Markov链链，且且若若 X在在群群的非零元素上均匀分布，则此的非零元素上均匀分布，则此Markov 链是平稳的。链是平稳的。n不不少少迭迭代代分分组组密密码码可可归归结结为为Markov密密码码。如如DESLOK1、FEAL和和REDOC Lai.1992。2023/3/2910差分密码分析差分密码分析(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。2023/3/2911差分密码分析差分密码分析(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)为特定值为特定值 的概率很高。的概率很高。2023/3/2913r轮迭代密码的差分分析轮迭代密码的差分分析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)的分析结果。的分析结果。2023/3/2915线性攻击线性攻击nRueppel1986的的流流密密码码专专著著中中曾曾提提出出以以最最接接近近的的线线性性函函数数逼逼近近非非线线性性布布尔尔函函数数的的概概念念，Matsui推推广广了了这这一一思思想想以以最最隹隹线线性性函函数数逼逼近近S盒盒输输出出的的非非零零线线性性组组合合1993，即即所所谓谓线线性性攻攻击击，这这是是一一种种已已知明文攻击法。知明文攻击法。n对已知明文对已知明文x密文密文y和特定密钥和特定密钥k，寻求线性表示式寻求线性表示式(ax)(by)=(dk)其其中中(a,b,d)是是攻攻击击参参数数。对对所所有有可可能能密密钥钥，此此表表达式以概率成立。对给定的密码算法，使极大化。达式以概率成立。对给定的密码算法，使极大化。2023/3/2916第四章第四章 单钥体制（二）单钥体制（二）分组密码分组密码 本本章章到此到此 结束。结束。谢谢大家！谢谢大家！2023/3/2918第五章第五章 公钥密码公钥密码2023/3/2919公钥密码公钥密码n数论简介数论简介n公钥密码体制的基本概念公钥密码体制的基本概念nRSARSA算法算法n椭圆曲线密码体制椭圆曲线密码体制2023/3/2920数论简介数论简介2023/3/2921素数和互素数素数和互素数n因子因子n整数整数a,b,a,b,如果存在如果存在mm，使，使a=mba=mb，称为，称为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|h,b|g,b|h,对任意整数对任意整数m,n,m,n,有有b|(mg+nh)b|(mg+nh)(证明留给大家证明留给大家)2023/3/2922素数和互素数素数和互素数n整数分解唯一性的另一表示整数分解唯一性的另一表示nP P是所有素数的集合，任一是所有素数的集合，任一a(a1)a(a1)可表示为可表示为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 p2023/3/2924素数和互素数nc c是是a a和和b b的最大公因子，的最大公因子，c=gcd(a,b)c=gcd(a,b)nc c是是a a的因子也是的因子也是b b的因子的因子na a和和b b的任一公因子也是的任一公因子也是c c的因子的因子ngcd(a,b)=1,gcd(a,b)=1,称为称为a,ba,b互素互素2023/3/2925