lecture06单向散列函数省名师优质课赛课获奖课件市赛课一等奖课件.ppt

本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。谢谢您,第六章 单向散列(,Hash,),函数,单向散列函数是一个单向密码体制，是一个从明文到密文不可逆函数。,单向散列函数应用：,确保数据完整性,应用于口令表加密,应用于数字署名,第1页,单向散列函数应用-,i,第2页,单向散列函数应用-,ii,第3页,单向散列函数应用-,iii,第4页,主要内容：,散列函数概述,MD5,安全散列算法（,SHA-1）,消息判别码,第5页,6.1.1,单向散列函数,散列函数：,M:,变长报文,H(M):,定长散列值,第6页,散列函数要求,H,能用于任意大小分组,H,能产生定长输出,对任何给定,x，H(x),要相对易于计算，使得硬件和软件实现成为实际可能,对任何给定码,h，,寻找,x,使得,H(x)=h,在计算上是不可行，即单向性,第7页,散列函数要求,对任何给定分组,x，,寻找不等于,x,y，,使得,H(x)=H(y),在计算上是不可行，将满足这种性质散列函数称为,弱碰撞自由,。,寻找对任何(,x,y),对使得,H(x)=H(y),在计算上是不可行，将满足这种性质散列函数称为,强碰撞自由,(抵抗“生日攻击”),第8页,6.1.2,单向散列函数设计、结构,由,Merkle,于1989年提出,几乎被全部,hash,算法采取,详细做法:,把原始消息,M,分成一些固定长度块,Y,i,最终一块,padding,并使其包含消息,M,长度,设定初始值,CV,0,压缩函数,f,CV,i,=f(CV,i-1,Y,i-1,),最终一个,CV,i,为,hash,值,第9页,流程图：,第10页,基本设计方法-,i,:,使用公开密钥密码算法设计单向散列函数,以,CBC,模式使用公开密钥算法对消息进行加密，并输出最终一个密文分组作为散列值，若丢弃用户保密密钥，散列值将无法解密，满足散列单向性要求,第11页,c,1,=RSA(m,1,iv)c,2,=RSA(m,2,c,1,).c,n,明文分组,m,1,初始向量,IV,RSA,密钥,k,明文分组,m,2,RSA,输出,第12页,基本设计方法-,ii,:,使用对称分组算法设计单向散列函数,用对称密钥分组密码算法,CBC,模式或,CFB,模式来产生散列值，用一个固定密钥及,IV,加密消息，将最终密文分组作为散列值输出,第13页,CBC,模式下,DES,IV=0,第14页,CFB,模式下,DES,第15页,类似于,CBC,模式：,把消息作为密钥,将上一个分组得到散列值作为分组算法输入,设消息共有,n,个分组,m,1,m,2,m,n,，,用,h,i,表示第,i,个分组散列值，,h,表示最终输出,h,0,=IV,H,i,=E,mi,(h,i-1,),h=h,N,第16页,基本设计方法-,iii,:,直接设计单向散列函数,不基于任何假设和密码体制，经过直接结构复杂非线性关系到达单向性要求,经典有：,MD2,MD4,MD5,SHA-1,等算法,第17页,单向散列函数攻击,对单向散列函数攻击是指攻击者寻找一对产生,碰撞消息,过程。,攻击方法：,强力攻击（生日攻击）,依赖于单向散列函数结构和代数性质,第18页,生日攻击：,在,k,个人中，要最少有两个人生日相同概率大于0.5，,k,最小值是多少？,P(n,k),表示,k,个个体中最少有一个值重复概率,Q(365,k),表示最早推出两两没有重复概率,k,个值不重复数目为,N，,则,N=365*364*(365-k+1)=365!/(365-k)!,除去限制每个个体都有365个选择，总可能数为365,k,没有重复概率为,Q(356,k)=365!/(365-k)!356,k,P(365,k)=1-Q(365,k)=1-365!/(365-k)!356,k,K=23,第19页,6.2 MD5(,消息摘要,),1992,年,Ron Rivest,完成,MD5,MD(Message Digest),MD5,不基于任何假设和密码体制，直接结构，速度快。,第20页,设计目标,MD5,继承了,MD4,设计目标,MD4,设计目标,安全性,直接安全性,速度,简单性和紧凑性,有利,Little-Endian,结构,第21页,Little-Endian,结构：低位字节内容存放在低字节地址上,Big-Endian,结构：低位字节内容存放在高字节地址上,不一样结构处理器上运行时，进行处理,比如：,从低位到高位连续排列四个字节,a,1,a,2,a,3,a,4,在,Big-Endian,结构中：,a,1,2,24,+a,2,2,16,+a,3,2,8,+a,4,在,Little-Endian,结构中：,a,4,2,24,+a,3,2,16,+a,2,2,8,+a,1,第22页,MD5,算法：,输入：任意长度报文,输入分组长度：512,bit,输出：128,bit,报文,第23页,第24页,附加填充比特,对报文进行填充，使其比特数与448模512同余，即填充长度为512整数倍减去64,填充方法：填充比特串最高位为1，其余各位均为0,第25页,附加长度值,|,M2|,为512倍数:,Y0,Y1,YL-1,第26页,比如：设消息为：,abcde,比特串为：01100001 01100010 01100011 01100100 01100101,共40比特，16进制表示为28，,Little-Endian,结构中28000000 00000000,填充比特1后，填充407个比特0，总长度448,61626364 65800000 00000000 00000000,00000000 00000000 00000000 00000000,00000000 00000000 00000000 00000000,00000000 00000000,28000000 00000000,00000000 00000028,Big-Endian,结构,第27页,初始化,MD,缓存,MD,为128,bit，,用于存放散列函数中间及最终止果,MD,可表示为4个32,bit,存放器(,A,B,C,D)，,初始化以下,第28页,以512比特作为分组，从消息开头循环地处理消息序列分组，,循环次数,将是消息中512比特消息分组数目。,主循环中包含了64步操作，使用了4个非线性函数，分为4轮，每轮16步操作,第29页,每一次循环能够表示为以下几步：,将,MD,缓存,A,B,C,D,值分别存放在另外四个中间变量,AA,BB,CC,DD,之中,执行第一轮共16个操作,执行第二轮共16个操作,执行第三轮共16个操作,执行第四轮共16个操作,使用中间变量(,AA,BB,CC,DD),更新,MD,缓存值,A=A+AA,B=B+BB,C=C+CC,D=D+DD,第30页,第31页,第32页,第33页,X0.15:,保留当前512,bit,待处理输入分组值,Xk=Mq,16+k=,在第,q,个,512,位数据块中第,k,个,32,位字,每次循环(4)每步(16)内，,Xi,使用循序各不相同,第34页,对于操作,j，,将使用字,Xk:,K=j j=0,1,15,(1+5(j-16)mod 16 j=16,1731,(5+3(j-32)mod 16 j=32,3347,(7(j-48)mod 16 j=48,4963,第35页,伪代码:,将4个32比特存放器,A,B,C,D,复制到暂时变量中保留,AA=A BB=B CC=C DD=D,第一轮,abcd k s i,代表以下操作,a=b+(a+,F,(b,c,d)+Xk+Ti)s),ABCD 0 7 1 DABC 1 12 2 CDAB 2 17 3 BCDA 3 22 4,ABCD 4 7 5 DABC 5 12 6 CDAB 2 17 7 BCDA 3 22 8,ABCD 8 7 9 DABC 9 12 10 CDAB 2 17 11 BCDA 3 22 12,ABCD 12 7 13DABC 13 12 14CDAB 2 17 14BCDA 3 22 16,D=A+(D+F(A,B,C)+X1+T2)12),第36页,伪代码:,第二轮,a=b+(a+,G,(b,c,d)+Xk+Ti)s),第三轮,a=b+(a+,H,(b,c,d)+Xk+Ti)s),第四轮,a=b+(a+,I,(b,c,d)+Xk+Ti)s),更新：,A=A+AA B=B+BB,C=C+CC D=D+DD,第37页,MD5,作为128比特消息摘要是足够强,给出两个含有相同消息摘要报文将需要2,64,数量级操作,若要寻找消息摘要与指定只相等报文，将需要2,128,数量级操作,只存在对特定条件下,MD5,算法进行攻击（单轮）,MD5,消息摘要长度可能不够,安全性：,第38页,MD5,算法程序界面加密过程,第39页,解密过程,第40页,在解密过程进行中点,保留进度,能够把当前破解进度保留到文件里面,第41页,第42页,6.3 Secure Hash Algorithm,介绍,1992年,NIST,制订了,SHA(128,位),1993年,SHA,成为标准,1994年修改产生,SHA-1(160,位),1995年,SHA-1,成为新标准,SHA-1,要求输入消息长度2,64,SHA-1,摘要长度为160位,基础是,MD4,第43页,SHA,算法步骤,于,MD5,类似,SHA,输出是160比特报文摘要，输入报文长度不超出2,64,比特,步骤1：附加填充比特,步骤2：附加长度值,与,MD5,不一样是附加长度值时64位长度值填充次序，,SHA,采取了,高字优先,次序,第44页,步骤3：初始化,MD,缓存,初始值：存放方式：,H,0,=0 x67452301,字,H,0,：67 45 23 01,H,1,=0 xEFCDAB89,字,H,1,：EF CD BA 89,H,2,=0 x98BADCFE,字,H,2,：98 BA DC FE,H,3,=0 x10325476,字,H,3,：10 32 54 76,H,4,=0 xC3D2E1F0,字,H,4,：C3 D2 E1 F0,第45页,步骤4：以512比特分组处理消息,从消息开头循环地处理消息序列分组，主循环次数是消息中512比特消息分组数目，每一循环处理512比特分组和,MD,缓存,H,0,H,1,H,2,H,3,H,4,输入，更新内容，循环，每一循环分为三个阶段：,阶段1：拷贝中间变量,阶段2：散列压缩,阶段3：更新,MD,缓存,H,0,H,1,H,2,H,3,H,4,第46页,第47页,全部80个操作含有相同算法过程：,TEMP=(A5+f,t,(B,C,D)+E+W,t,+K,t,),E=D,D=C,C=B30,B=A,A=TEMP,第48页,第49页,非线性函数,f,t,(B,C,D)第50页,Wt,把当前处理512比特分组看作为16个32比特字：,M,0,M,1,M,15,Wt=Mt t=0,1,15,t=16,1779,第51页,Kt,Kt,是由算法给出常数,Kt=0 x5A827999 t=0,1,19,Kt=0 x6ED9EBA1 t=20,21,39,Kt=0 x8F1BBCDC t=40,41,59,Kt=0 xCA62C1D6 t=60,61,79,第52页,更新：,H,0,=H,0,+A,H,1,=H,1,+B,H,2,=H,2,+C,H,3,=H,3,+D,H,4,=H,4,+E,模2,32,加法,处理下一个分组，处理完全部分组,步骤5：输出,第53页,安全性,SHA-1,使用,big-endian,抵抗生日攻击:160位,hash,值,没有发觉两个不一样512-,bit,块,它们在,SHA-1,计算下产生相同“,hash”,速度慢于,MD5,安全性优于,MD5,第54页,单向散列函数,缺点,：任何人能够在更改文件之后，产生新散列值，并存放。,使用一个双方共享秘密密钥生成一个固定大小小数据块，并加入到消息中，称消息判别码(,MAC Message Authentication Code),用户,A,和用户,B，,共享密钥,K，,对于,消息,M，MAC=C,K,(M),5.4消息判别码,第55页,第56页,假如接收方计算,MAC,与收到,MAC匹配，则,接收者能够确定消息未被改变,接收者能够消息来自声称发送者,假如消息中包含次序码，则接收者能够确保消息正常次序,第57页,MAC,函数类似于加密函数，但不需要可逆性。所以在数学上比加密算法被攻击弱点要少,经典消息判别码方案：,HMAC(Keyed-Hashing for Message Authentication)，DSA(Digital Shift and Add),等算法,第58页,1996年,Bellare,等人提出,1997年 发表为,RFC 2104,成为,Internet,标准,HMAC,使用了已经有单向散列函数，如,HMAC-MD5 ,HMAC-SHA-1,等,HMAC:,单向散列函数,H,输入分组长度,b,比特,输出长度,l,比特,HMAC,算法,第59页,使用,HMAC,算法对报文,M,计算其判别码步骤：,若密钥,K,长度小于,b,比特，填充一些0，使其长度为,b,S,i,=k,+,ipad 0 x36,重复,b/8,次,计算,H(S,i,|M),S,0,=K,+,opad 0 x5A,重复,b/8,次,S,0,|H(S,i,|M),H(S,0,|H(S,i,|M),第60页,第61页,HMAC,特征：,可直接使用各种,hash,算法,可使用未来愈加安全和愈加紧速,hash,算法,保持原始,hash,算法性能,密钥使用简单,与,hash,函数有同等安全性,第62页,总结:,单向散列函数设计方法,使用公开密钥密码,使用对称分组算法,直接设计,MD5,算法,安全散列函数(,SHA-1),消息判别码(,HMAC),第63页,