第7讲-杂凑函数和数字签名课件

-,*,-,主 要 内 容,一、杂凑函数的概念和基本安全要求,二、MD5杂凑算法,三、数字签名,主 要 内 容一、杂凑函数的概念和基本安全要求,杂凑函数又称为,Hash,函数,、,报文摘要函数,、散列函数,等,。,其目的是将任意长度的报文,m,都压缩成,指定长度,的数据,H(m),H(,m,),又称为,m,的指纹,，代表了消息,m,的身份,。,如下图所示:,报文,报文摘要,杂凑函数H,一、,杂凑函数的概念和基本安全需求,长度是固定的，与报文的长度无关,杂凑函数又称为Hash函数、报文摘要函数、散,杂凑函数的用途:,(1)完整性检验,-利用二元对(,m,H,(,m,),的不可更改性实现,。,此时，,m,的变化将导致,H,(,m,),的变化.,(2)提供文件的指纹.,用于,数字签名,。,只要,H,(,m,)不可替换,就保证,m,不可能再更改,(,3,),将杂凑值作为密钥,，从而压缩掉密钥的冗余度;,(4)伪随机数生成.,一、,杂凑函数的概念和基本安全需求,(续),杂凑函数的用途:一、杂凑函数的概念和基本安,杂凑函数技术,-优缺点,由于报文摘要,不包含,报文持有者的秘密信息，故杂凑函数的：,优点:,任何人都可对报文的“指纹”进行,检验,；,缺点:,掌握报文的人都可,生成,报文的“指纹”,上述缺点导致当将,报文及其指纹放在一起,时，只能检验出对报文,无意的修改,，不能检验出,有意的篡改,或伪造。,报文,报文摘要,杂凑函数H,杂凑函数技术-优缺点 由于报文摘要不包含,(1)单向性,（第一原像不可求）,.,给出一个杂凑值,z,，从计算量上讲，,求出一个,m，或者,以不可忽略的概率求出一个,m,，使得 H(,m,)=,z,成立,是不可行的,。,杂凑函数的安全性要求,报文,m,报文摘要,杂凑函数H,在实际上,求不出,理论方法：,穷举攻击,(1)单向性（第一原像不可求）.杂凑函数,(2)强无碰撞性.,从计算量上讲，,求出,，或者以不可忽略的概率求出，,具有相同杂凑值,H(m,1,)=H(m,2,),的两份报文,m,1,和,m,2,是不可行的,。,杂凑函数的安全性要求,(续1),报文,m,1,报文摘要,杂凑函数H,报文,m,2,杂凑函数H,理论方法：(1),穷举攻击,-固定一个，穷举另一个,(2),碰撞攻击-两个一起“穷举”,(2)强无碰撞性.杂凑函数的安全性要求(续,(3)求第二原像不可行(弱无碰撞性）,任意给定一个报文,m,1,，,找出,或者以不可忽略的概率找出,另一个报文,m,2,，,使得,H(m,2,)=H(m,1,),在计算上不可行,。,意义：,将一份报文的指纹伪造成另一份报文的指纹在计算上是不可行的,。,预先固定的,理论方法：(1),穷举攻击（穷举,m,2,),杂凑函数的安全性要求,(续2),(3)求第二原像不可行(弱无碰撞性）,对杂凑函数的基本攻击方法,-碰撞攻击,目的:,构造报文,m,1,和,报文,m,2,使得,H(m,1,)=H(m,2,),生日悖论:,20个人的生日互不相同的概率是多少,错!,正确答案是:,20个人中至少有两人生日相同的概率是0.632,是20/365吗?,?,对杂凑函数的基本攻击方法-碰撞攻击目的:构造报文m1,对杂凑函数的碰撞攻击算法,Step1,随机,选取N个报文m,1,m,2,m,N,;,Step2,以这N个报文作为杂凑函数的输入,计算出相应的杂凑值,得到集合,S=,(,m,k,H(,m,k,),:k=1,2,N,Step3,根据H(m,k,)的大小，对集合S利用,快速排序算法,重新排序。,在排序过程中，如果找到了使H(m,k,)=H(m,t,)的两个不同元m,k,和m,t,，就将(m,k,m,t,)作为结果输出，算法终止；如果找不到，就报告碰撞攻击失败，算法终止。,对杂凑函数的碰撞攻击算法 Step1 随机选,碰撞攻击算法的性能指标,算法所需的存储量:,需要存储表S，以便进行快速排序，故存储复杂性是表S的规模O(N),S=,(,m,k,H(,m,k,),:k=1,2,N,算法所需的计算量：,(1)该算法生成集合S的计算量是计算N次杂凑函数；,(2)对集合S快速排序并找出全部碰撞的计算量为|N|log,2,|N|次比较。,故总的计算量为,N+|N|log,2,|N|=O(N),碰撞攻击算法的性能指标 算法所需的存储量:需,碰撞攻击算法的性能指标,特别地，当 时，碰撞攻击的成功率近似为,成功率分析：,定理1,设杂凑值为n,比特,且N远小于2,n,则碰撞攻击的成功率近似为,特例：,如果,n,=64,则 N1.42,32,=5.6G，此时碰撞攻击算法可实现。,是存储复杂性和计算复杂性,表S=(,m,k,H(,m,k,):k=1,2,N,的规模,攻击能力,碰撞攻击算法的性能指标特别地，当,能够对抗碰撞攻击的,杂凑函数的安全界限,如果对抗穷举攻击的能力的密钥长度的安全界限为,n,比特，则,对抗碰撞攻击的杂凑算法的杂凑值的比特数的,安全界限应为 2,n,。,能够对抗碰撞攻击的 如果对抗穷举攻击的能力的密,1.,MD,强化技术(,Merkle-Damaard,强化),将,消息,M=(M,1,M,2,M,n,)的最后一个分组M,n,设置为“真正消息”的长度，这个过程称为MD强化。,二,、基于分组密码设计的,杂凑函数,1.MD强化技术(Merkle-Damaa,2.迭代型杂凑函数,一个迭代杂凑函数H(H,0,M)是由一个容易计算的函数h(x,y),确定的一个杂凑函数,H,其中,h:0,1,m,:0,1,t,0,1,m,杂凑函数对给定的初始值,H,0,递归地计算,H,i,=h(H,i-1,M,i,),从而将报文,M=(M,1,M,2,M,n,)杂凑到杂凑值H,n,。,特别地,选取,h=E(x,k),是一个安全的分组密码,则当将,消息,经,MD,强化后,就得到一个安全的杂凑函数,。,新的报文块,M,i,的输入位置是密钥的位置!,被杂凑的消息必须经过,MD强化,!,2.迭代型杂凑函数 一个迭代杂凑函数H(H0,圈函数为,H,i,=,h,(,H,i,-1,M,i,),H,i,-1,3.DM杂凑函数模型(Davies-Meyer,方案,),函数,h,H,i,-1,H,i,M,i,初值H,0,：,是固定的常数,被杂凑的消息必须经过,MD强化,!,特例：,取,h,(,H,i,-1,M,i,),=,DES,Mi,(,H,i,-1,),此时：,消息是56比特为一块，杂凑值是64比特,圈函数为 Hi=h(Hi-1,Mi)Hi-13.,三、MD5算法,MD4 是Ron Rivest 于1990年设计的，MD5是MD4的改进形式。二者的设计思想思想相似。,MD5的特点：,对任意长度的输入，都产生,128位的输出,；其安全性不依赖于任何假设，适合高速实现。,三、MD5算法 MD4 是Ron Rivest,三、MD5算法,MD5的安全分析现状：,2004年夏，山东大学的王小云宣布找到,使MD5的杂凑值相同的两个报文,，这两个报文的差是一个特殊的值，但没有公开构造方法。,之后，王小云教授公布了她的方法。人们后来发现，找出MD5的一个碰撞在PC机是非常容易的事情。,由于能产生碰撞的报文未必有实际的意义，而且按王小云的方法构造的两个报文都不能人为地控制，因而该攻击并不对MD5造成实际的威胁。,三、MD5算法 MD5的安全分析现状：,方法：,设原始报文,x,的长度是,L,比特.,(1),求出,d0，,使得,L+1+d+64,是,512,的倍数；,(2),在原始报文,x,后面先添加一个,1,，,MD5,算法第一步:消息填充,目的:,使,MD,强化后报文长度是512的整数倍,x,|1,|0,d,|,L,扩充后的报文=,然后添加,d,个,0,，,最后将消息的长度,L,用,64,比特表示，加在最后。,(L+1+d+64)mod512=0,d=(L65)mod512,由,方法：设原始报文x的长度是L比特.MD5 算法第一步:,MD5,填充的例子,设,x,是具有,20768,比特的长信息,，,则,d=(L65)mod512,=,(,20768 65)mod512,=,20833mod512,=,(,40512+,353)mod512,=,353mod512,=,512353,=,159,故应在,x,后面添加一个,1,和,159,个0，最后再添加原始消息长度,20768,的64位表示。,MD5 填充的例子设x是具有 20768比特的长信息，则,MD5使用的编码变换,逐位模2加运算,：,x,y,逐位取补运算：,模2,32,位加运算：,x+,y,循环左移s,位,:,x,s,四个密码变换:,面向32字设计-全部采用32位字的运算,逐位与运算：x,y,逐位或运算：x,y,X,Y,Z都是32位字,MD5使用的编码变换 逐位模2加运算：x y 逐位取补,MD5,初始化变量,(1),MD5,的迭代函数一次处理512比特报文块,(2),512比特报文块分为16个32比特字。,(3),N,个32比特字共分为,T=N/16,个512比特块,(4),首先初始化,MD5,的,4,个变量,(A,B,C,D),每个变量,32,位。,4,个变量分别取初始值如下（,16,进制表示）：,记,M=M0M1,MN-1,是,M,的32位字表示。,MD5 初始化变量(1)MD5的迭代函数一次处理512,MD5,的主算法,圈函数模型:,H,i,=h(H,i-1,M,i,),H,i-1,.其中H,i-1,=(A,B,C,D),h,由,round1,round2,round3,和,round4,组成.,DM模型,具体过程:,对,i=0,至,N/16-1,依次执行以下步骤：,/,N/16,是512比特块的个数,Step1,执行,X0,M16i,X1,M16i+1,X15,M16i+15,/,16,是512比特块中32位字的个数,一次处理16个32比特块,Step2,暂存(,A,B,C D),即执行:,AA,A,BB,B,CCC,DD,D,Step3,执行:(,A,B,C D),Round1,(,A,B,C D,X0,X15),Step4,执行:(,A,B,C D),Round2,(,A,B,C D,X0,X15),Step5,执行:(,A,B,C D),Round3,(,A,B,C D,X0,X15),Step7,执行:(,A,B,C D),Round4,(,A,B,C D,X0,X15),Step6,执行:(,A,B,C D),(,A,B,C D),+,(,AA,BB,CC,DD),MD5 的主算法圈函数模型:Hi=h(Hi-1,Mi),函数,Round 1,的结构:,用,a b c d i s t,表示运算,a,(,b,+,a,+,f,(,b,c,d,)+,M,i,+,t,i,)s).,(,仅替换,a,),则,Round1,依次执行下述16层运算:,(执行完左边8列,再,执行右边8列),A B C D 0 7,t,1,A B C D 8 7,t,9,D A B C 1 12,t,2,D A B C 9 12,t,10,C D A B 2 17,t,3,C D A B 10 17,t,11,B C D A 3 22,t,4,B C D A 11 22,t,12,A B C D 4 7,t,5,A B C D 12 7,t,13,D A B C 5 12,t,6,D A B C 13 12,t,14,C D A B 6 17,t,7,C D A B 14 17,t,15,B C D A 7 22,t,8,B C D A 15 22,t,16,(b,c,d),i,s,a,t,(b,c,d),i,s,a,t,t,i,是2,32,abs,(sin,i,)的整数部分.,函数Round 1的结构:则Roun,函数,Round 2,的结构:,用,a b c d i s t,表示运算,a,(,b,+,a,+,g,(,b,c,d,)+,M,i,+,t,i,)s),(,仅替换,a,),(b,c,d),i,s,a,t,(