清华大学出版社第5章-散列函数和消息鉴别省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,/27,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,第,1,章 密码学概述,第,2,章 古典密码技术,第,3,章 分组密码,第,4,章 公钥密码体制,第,5,章 散列函数与消息判别,第,6,章 数字署名技术,第,7,章 密钥管理技术,第,8,章 身份判别技术,第,9,章 序列密码,第,10,章 密码技术应用,课程主要内容,1/27,第5章 散列函数与消息判别,本章主要内容,散列函数概念,散列函数结构与设计,安全散列算法,SHA,对散列函数攻击,消息判别,2/27,第5章 散列函数与消息判别,5.1,散列函数概念,密码学中散列函数又称为哈希函数（,Hash,函数）、杂凑函数，它是一个单向密码体制，是一个从明文到密文不可逆映射，只有加密过程，不能解密。,散列函数性质,设散列函数为,h,(,m,),，含有以下基本特征：,（,1,）,h,(,m,),算法公开，不需要密钥。,（,2,）含有数据压缩功效，可将任意长度输入数据转换成一个固定长度输出。,（,3,）对任何给定,m,，,h,(,m,),易于计算。,散列函数必须满足以下安全性要求：,（,1,）含有单向性。给定消息散列值,h(m),，要得到消息,m,在计算上不可行；,（,2,）含有弱抗碰撞性（,Weak collision resistance,）。对任何给定消息,m,，寻找与,m,不一样消息,m,，使得它们散列值相同，即,h,(,m,),h,(,m,),，在计算上不可行。,（,3,）含有强抗碰撞性（,Strong collision resistance),。寻找任意两个不一样消息,m,和,m,，使得,h,(,m,),h,(,m,),在计算上不可行。,3/27,第5章 散列函数与消息判别,散列函数应用,散列函数主要应用有以下三个方面：,1,）确保数据完整性,2,）单向数据加密,3,）数字署名,应用散列函数实现数据完整性保护模型：,注：实际应用中，未必一定是如,h(mk),计算方式，明文与密钥,k,组合方式因不一样实现能够不一样。,4/27,第5章 散列函数与消息判别,算法中重复使用一个函数,f,。函数,f,输入有两项，一项是上一轮（第,i,-1,轮）输出,CV,i-,1,，称为链接变量，另一项是算法在本轮（第,i,轮）,b,位输入分组,m,i,。,5.2,散列函数结构与设计,迭代型散列函数普通结构,整个散列函数逻辑关系可表示为：,CV,0,=IV,；,CV,i,=,f,（,CV,i,-1,，,m,i,）；,1,i,t,；,h,（,M,）,=CV,t,5/27,第5章 散列函数与消息判别,即使在合理假设下，能够证实这类散列函数是安全，因为它计算效率太低，所以这一类散列函数并没有什么实用价值。,散列函数基本设计方法有：基于公开密钥密码算法设计、基于对称分组密码算法设计以及直接设计法。,1.,基于公开密钥密码算法设计散列函数,散列函数设计方法,以,CBC,模式利用公开密钥算法，使用公钥,PK,以及初始变量,IV,对消息分组进行加密，并输出最终一个密文分组,c,t,作为散列函数输出值，如图,5.3,所表示。,6/27,第5章 散列函数与消息判别,基于分组密码,CBC,工作模式和,CFB,工作模式散列函数中，密钥,k,不能公开。假如密钥,k,公开，则会使得攻击者结构消息碰撞十分轻易。,通常，能够使用对称密钥分组密码算法,CBC,模式或,CFB,模式来产生散列值，如图,5.4,、图,5.5,所表示。,2.,基于对称分组密码算法设计散列函数,7/27,第5章 散列函数与消息判别,3.,直接设计散列函数,这类散列函数并不基于任何假设和密码体制，它是经过直接结构复杂非线性关系到达单向性要求来设计单向散列函数。这类散列算法经典有：,MD2,、,MD4,、,MD5,、,SHA-1,等算法。,5.3,安全散列算法,SHA,1.SHA-1,SHA-1,是数字署名标准,DSS,（,Digtial Signature Standard,）中使用散列算法。它能够处理最大长度为,264,位输入数据，输出为,160,位散列函数值，,SHA-1,输出恰好适合作为数字署名算法,DSA,（,Digtial Signature Algorithm),输入。,.基本操作和元素,:,(1),逐位逻辑运算,(2),加法运算,(3),移位操作,8/27,第5章 散列函数与消息判别,(1),消息分割与填充,(2),初始化缓冲区,(3),处理第,i,个数据块,x,i,(4)4,轮循环，,80,步操作完成后，,保留散列中间结果，再与第一轮输入相加（模,232,）,(5),然后，以,H,0,(,i,),，,H,1,(,i,),，,H,2,(,i,),，,H,3,(,i,),，,H,4,(,i,),作为存放器初值，用于对分组,x,i+,1,进行散列处理。,SHA-1,压缩函数操作过程，如图,5.9,所表示,(,下页,),，是处理一个,512,位分组,4,次循环中每一循环基本压缩操作流程。,.SHA,散列过程,.SHA-1,压缩操作,.,示例,【,例,5.1】,计算字符串“,abc”SHA-1,散列值。,字符串“,abc”,二进制表示为：,01100001 01100010 01100011,，共有,24,位长度。按照,SHA-1,填充要求，应该填充一个“,1”(,界符,),和,423,个“,0”,，最终有两个字“,00000000 00000018”(,十六进制,),，表明原始消息长度为,24,位。本例中共只有一个分组。,9/27,第5章 散列函数与消息判别,10/27,第5章 散列函数与消息判别,初始五个存放器初始值为：,H,0,(0),=67452301,，,H,1,(0),=EFCDAB89,，,H,2,(0),=98BADCFE,，,H,3,(0),=10325476,，,H,4,(0),=C3D2E1F0,进行迭代计算，前,16,个,32,位字值刚好取自这个分组全部字，即：,W,0,=61626380(,即,01100001 01100010 01100011 10000000),，,W,1,=,W,2,=,W,14,=00000000,，,W,15,=00000018,。,对,t,=0,79,计算得到各个存放器中值。,最终得到结果为：,H,0,=67452301+42541B35=A9993E36,，,H,1,=EFCDAB89+5738D5E1=4706816A,，,H,2,=98BADCFE+21834873=BA3E2571,，,H,3,=10325476+681E6DF6=7850C26C,，,H,4,=C3D2E1F0+D8FDF6AD=9CD0D89D,。,于是：,SHA-1(“abc”)=A9993E36 4706816A BA3E2571 7850C26C 9CD0D89D,，,共,160,位，,20,个字节。,11/27,第5章 散列函数与消息判别,.,其它,SHA,算法,年，,NIST,在,FIPS l80-1,基础上做了修改，公布了推荐修订版本,FIPS 180-2,。在这个标准中，除了,SHA-1,外，还新增了,SHA-256,、,SHA-398,和,SHA-512,三个散列算法标准，它们消息摘要长度分别为,256,位、,398,位和,512,位，方便与,AES,使用相匹配。,SHA,系列散列算法基本运算结构有很大相同性。,SHA-1,，,SHA-256,数据分组都是,512,位。,SHA-384,，,SHA-512,数据分组则是,1024,位。,SHA-1,，,SHA-256,，,SHA-384,，,SHA-512,比较,表,5.4,是它们基本参数比较：,12/27,第5章 散列函数与消息判别,当前对于散列函数攻击方法能够分为两类：,对散列函数攻击是指攻击者寻找一对产生碰撞消息过程。评价散列函数有效方法就是看一个攻击者找到一对产生碰撞消息所花代价有多高。,第一类称为穷举攻击（或暴力攻击），它能对任何类型散列函数进行攻击，其中最经典方法就是“生日攻击”。,第二类称为密码分析法，这类攻击方法依赖于对散列函数结构和代数性质分析，采取针对散列函数弱性质方法进行攻击。这类攻击方法有中间相遇攻击、修正分组攻击和差分分析等等。,生日悖论,我们来考虑这么一个有趣问题：在一个教室中最少应有多少学生才使得最少有两个学生生日在同一天概率大于,0.5,？计算与此相关概率被称为生日悖论问题。,5.4,对散列函数攻击,13/27,第5章 散列函数与消息判别,生日攻击,与散列函数相关类似问题可表述以下：给定一个散列函数,h,输出长度为,m,位，共有,2,m,个可能散列值输出，假如让散列函数,h,接收,k,个随机输入产生集合,X,，再使用另外,k,个随机输入产生集合,Y,，问,k,必须为多大才能使两个集合产生相同散列值输出概率大于,0.5,？,这种寻找散列函数,h,含有相同输出两个任意输入攻击方式称为生日攻击。,5.5,消息判别,消息判别是一个过程，用以验证接收消息真实性（确实是由它所声称实体发来）和完整性（未被篡改、插入、删除），同时还用于验证消息次序性和时间性（未被重排、重放、延迟等）。,消息判别对于开放网络中各种信息系统安全性含有主要作用。,大致来说，实现消息判别伎俩能够分为两类：基于加密技术消息判别和基于散列函数消息判别。,14/27,第5章 散列函数与消息判别,基于加密技术消息判别,从消息判别目标出发，不论是对称密码体制，还是公钥密码体制，对于消息本身加密都能够看作是一个判别伎俩。,（,1,）,利用对称加密体制实现消息判别,如图,5.10,所表示，发送方,A,和接收方,B,共享密钥,k,。,A,用密钥,k,对消息,M,加密后经过公开信道传送给,B,。,B,接收到密文消息之后，经过是否能用密钥,k,将其恢复成正当明文，来判断消息是否来自,A,，信息是否完整。,15/27,第5章 散列函数与消息判别,该方法特点是：,1,）它能提供机密性：只有,A,和,B,知道密钥,k,；,2,）提供判别：只能发自,A,，传输中未被改变；,3,）不能提供数字署名：接收方能够伪造消息，发送方能够抵赖消息发送。,（,2,）,利用公钥密码体制实现消息判别,提供消息判别,如图,5.11,所表示，发送方,A,用自己私钥,SK,A,对消息进行加密运算（但并不能提供机密性保护，请思索为何？），再经过公开信道传送给接收方,B,。接收方,B,用,A,公钥,PK,A,对得到消息进行解密运算并完成判别。,16/27,第5章 散列函数与消息判别,这种方法特点是：能实现数字署名功效，能够抗抵赖，并提供判别。,提供消息判别和机密性保护,如图,5.12,所表示，在发送方,A,用自己私钥,SK,A,进行加密运算（实现数字署名）之后，还要用接收方,B,公钥,PK,B,进行加密，从而实现机密性。,缺点：一次完整通信需要执行公钥算法加密、解密操作各两次。,优点：提供机密性、数字署名和判别。,17/27,第5章 散列函数与消息判别,(1),消息判别码概念,基于散列函数消息判别,消息判别码,(MAC,，,Message Authentication Code),或报文判别码，是,用于提供数据原发判别和数据完整性密码校验值。,MAC,是使用一个特定密钥将消息经过一个判别算法处理所得出一串代码。,一个,MAC,算法是由一个秘密密钥,k,和参数化一簇函数,h,k,组成。这簇函数含有以下特征：,a),轻易计算,对于一个已知函数,h,，给定一个值,k,和一个输入,x,，,h,k,(,x,),是轻易计算。这个计算结果被称为消息判别码值或消息判别码。,b),压缩,h,k,把任意含有有限长度（比特数）一个输入,x,映射成一个含有固定长度输出,h,k,(,x,),。,c),强抗碰撞性,要找到两个不一样消息,x,和,y,，使得,h,k,(,x,)=,h,k,(,y,),是计算上不可行。,18/27,第5章 散列函数与消息判别,提供消息判别方法（图,5.13,）：,提供消息判别和机密性方法（图,5.14,，图,5.15,）：,19/27,第5章 散列函数与消息判别,（,2,）基于散列函数消息判别,散列函数含有以下特点：输入是可变大小消息,M,，输出固定长度散列值,(,即消息摘要,),；计算简单，不需要使用密钥，含有强抗碰撞性。,基于散列函数消息判别方法如图,5.16,所表示，有以下几个情况：,（,1,）用对称密码体制加密消息及其散列值，如图,5.16(a),。,（,2,）用对称密码体制只对消息散列值进行加密，如图,5.16(b),。,（,3,）用公钥密码体制只对散列值进行加密运算，如图,5.16(c),。,20/27,第5章 散列函数与消息判别,（,4,）结合使用公钥密码体制和对称密码体制，这种方法用发送方私钥对散列值进行数字署名，用对称密码体制加密消息,M,和得到数字署名，如图,5.16(d),。,（,5,）这种方法使用了散列算法，但未使用加密算法。,（,6,）在方法,(5),基础上，使用对称密码体制对消息,M,和生成散列值进行保护，如图,5.16(f),。,21/27,第5章 散列函数与消息判别,22/27,第5章 散列函数与消息判别,HMAC,算法,基于散列函数消息判别码结构基本思想就是将某个散列函数嵌入到消息判别码结构过程中。,HMAC,作为这种结构方法代表，已经作为,RFC 2104,公布，并在,IPSec,和其它网络协议,(,如,SSL),中得到应用。,1.HMAC,算法设计要求：,按照,RFC 2104,，,HMAC,希望到达以下设计要求：,（,1,）,可不经修改而使用现有散列函数，尤其是那些易于软件实现、源代码可方便获取且无偿使用散列函数。,（,2,）,其中嵌入散列函数能够易于替换为更加快或更安全散列函数，以适应不一样安全需求。,（,3,）,保持嵌入散列函数原有性能，不因用于,HAMC,而使其性能降低。,（,4,）,密钥使用和处理简单方便。,（,5,）,以嵌入散列函数安全假设为基础，易于分析,HMAC,用于判别时安全强度。,23/27,第5章 散列函数与消息判别,2.HMAC,算法描述,图,5.17,是,HMAC,算法实现框图。,其中,h,为嵌入散列函数,(,如,MD5,、,SHA-1);,输入消息,M=(Y,0,，,Y,1,，,，,Y,L-1,),，,Y,i,(0,i,L-1),是,b,位一个分组，,M,包含了散列函数填充位。,n,为嵌入散列函数输出值长度，,K,为密钥，假如密钥长度大于,b,，则将密钥输入到散列函数中产生一个,n,位密钥。,K+,是左边填充了,0,后,K,，其长度为,b,位，,ipad,为,b/8,个,00110110,序列串，,opad,为,b/8,个,01011010,序列串。,24/27,第5章 散列函数与消息判别,2.HMAC,算法描述,HMAC,算法可表示为：,HMAC(M,，,K)=,h,(K+opad),h,(K+ipad)M),25/27,第5章 散列函数与消息判别,3.HMAC,安全性,第一个攻击能够认为压缩函数与散列函数等价，,n,位初始链接变量,IV,能够看作,HMAC,密钥。所以攻击能够经过对密钥穷举来进行攻击。对密钥穷举计算复杂度为,O(2,n,),。,第二种攻击要求寻找两个含有相同散列值消息，即实施第,类生日攻击，对于含有,n,位长散列值散列函数而言，其计算复杂度为,O(2,n/2,),。,由,HMAC,结构能够发觉，其安全性依赖于所嵌入散列函数安全性。,对,HMAC,攻击等价于对内嵌散列函数以下攻击之一：,（,1,）攻击者能够计算压缩函数一个输出，即使,IV,是机密或者随机。,（,2,）攻击者能够找到散列函数碰撞，即使,IV,是机密或者随机。,26/27,第5章 散列函数与消息判别,本章小结,本章主要介绍了散列函数概念、结构与设计、以及对散列函数攻击、消息判别和安全散列算法,SHA,。重点介绍了散列函数结构与设计和消息判别。包含,:,散列函数结构与设计,散列函数设计方法,基于公开密钥密码算法设计散列函数,基于对称分组密码算法设计散列函数,直接设计散列函数,消息判别,基于加密技术消息判别,基于散列函数消息判别,HMAC,算法,27/27,