清华大学第5章散列函数和消息鉴别课件

《清华大学第5章散列函数和消息鉴别课件》由会员分享，可在线阅读，更多相关《清华大学第5章散列函数和消息鉴别课件（27页珍藏版）》请在金锄头文库上搜索。

1、第1章 密码学概述 第2章 古典密码技术 第3章 分组密码 第4章 公钥密码体制 第5章 散列函数与消息鉴别 第6章 数字签名技术 第7章 密钥管理技术 第8章 身份鉴别技术 第9章 序列密码 第10章 密码技术应用,课程主要内容,第5章 散列函数与消息鉴别,本章主要内容 散列函数的概念 散列函数的构造与设计 安全散列算法SHA 对散列函数的攻击 消息鉴别,第5章 散列函数与消息鉴别,5.1 散列函数的概念 密码学中的散列函数又称为哈希函数（Hash函数）、杂凑函数，它是一种单向密码体制，是一个从明文到密文的不可逆映射，只有加密过程，不能解密。 散列函数的性质,设散列函数为h(m)，具有以下基

2、本特性： （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、可行。,第5章 散列函数与消息鉴别,散列函数的应用 散列函数的主要应用有以下三个方面： 1）保证数据的完整性 2）单向数据加密 3）数字签名 应用散列函数实现数据完整性保护的模型：,注：实际应用中，未必一定是如h(mk)的计算方式，明文与密钥k的组合方式因不同的实现可以不同。,第5章 散列函数与消息鉴别,算法中重复使用一个函数f 。函数f的输入有两项，一项是上一轮（第i-1轮）的输出CVi-1，称为链接变量，另一项是算法在本轮（第i轮）b位的输入分组mi。,5.2 散列函数的构造与设计,迭代型散列函数的一般结构,整个散列函数的逻辑关系可表示为： CV0 =IV； CVi = f（CVi-1，m

4、i）；1it； h（M）= CVt,第5章 散列函数与消息鉴别,虽然在合理的假设下，可以证明这类散列函数是安全的，由于它的计算效率太低，所以这一类散列函数并没有什么实用价值。,散列函数的基本设计方法有：基于公开密钥密码算法的设计、基于对称分组密码算法的设计以及直接设计法。,1.基于公开密钥密码算法设计散列函数,散列函数的设计方法,以CBC模式利用公开密钥算法，使用公钥PK以及初始变量IV对消息分组进行加密，并输出最后一个密文分组ct作为散列函数输出值，如图5.3所示。,第5章 散列函数与消息鉴别,基于分组密码的CBC工作模式和CFB工作模式的散列函数中，密钥k不能公开。如果密钥k公开，则会使得

5、攻击者构造消息碰撞十分容易。,通常，可以使用对称密钥分组密码算法的CBC模式或CFB模式来产生散列值，如图5.4、图5.5所示。,2.基于对称分组密码算法设计散列函数,第5章 散列函数与消息鉴别,3.直接设计散列函数,这类散列函数并不基于任何假设和密码体制，它是通过直接构造复杂的非线性关系达到单向性要求来设计单向散列函数。这类散列算法典型的有：MD2、MD4、MD5、SHA-1等算法。,5.3 安全散列算法SHA,1. SHA-1,SHA-1是数字签名标准DSS（Digtial Signature Standard）中使用的散列算法。它能够处理最大长度为264位的输入数据，输出为160位的散列

6、函数值，SHA-1的输出正好适合作为数字签名算法DSA（Digtial Signature Algorithm)的输入。,.基本操作和元素:,(1)逐位逻辑运算,(2) 加法运算,(3) 移位操作,第5章 散列函数与消息鉴别,(1) 消息分割与填充 (2) 初始化缓冲区 (3) 处理第i个数据块xi (4) 4轮循环，80步操作完成后，保存散列中间结果，再与第一轮的输入相加（模232） (5) 然后，以H0(i) ，H1(i) ，H2(i) ，H3(i) ，H4(i)作为寄存器初值，用于对分组xi+1进行散列处理。,SHA-1压缩函数操作过程，如图5.9所示(下页)，是处理一个512位分组的4

7、次循环中每一循环的基本压缩操作流程。,.SHA的散列过程,.SHA-1的压缩操作,.示例,【例5.1】计算字符串“abc”的SHA-1散列值。,字符串“abc”的二进制表示为：01100001 01100010 01100011，共有24位的长度。按照SHA-1的填充要求，应该填充一个“1”(界符)和423个“0”，最后有两个字“00000000 00000018”(十六进制)，表明原始消息的长度为24位。本例中共只有一个分组。,第5章 散列函数与消息鉴别,第5章 散列函数与消息鉴别,初始五个寄存器的初始值为： H0(0)=67452301，H1(0)=EFCDAB89，H2(0)=98BAD

8、CFE， H3(0)=10325476，H4(0)=C3D2E1F0 进行迭代计算，前16个32位字的值刚好取自这个分组的所有字，即： W0=61626380(即01100001 01100010 01100011 10000000)， W1=W2=W14=00000000，W15=00000018。对t=079计算得到各个寄存器中的值。 最后得到结果为： H0=67452301+42541B35=A9993E36， H1=EFCDAB89+5738D5E1=4706816A， H2=98BADCFE+21834873=BA3E2571， H3=10325476+681E6DF6=7850C2

9、6C， H4=C3D2E1F0+D8FDF6AD=9CD0D89D。 于是：SHA-1(“abc”)= A9993E36 4706816A BA3E2571 7850C26C 9CD0D89D，共160位，20个字节。,第5章 散列函数与消息鉴别,.其他SHA算法,2002年，NIST在FIPS l80-1的基础上做了修改，发布了推荐的修订版本FIPS 180-2。在这个标准中，除了SHA-1外，还新增了SHA-256、SHA-398和SHA-512三个散列算法标准，它们的消息摘要长度分别为256位、398位和512位，以便与AES的使用相匹配。SHA系列散列算法的基本运算结构有很大的相似性。

10、,SHA-1，SHA-256的数据分组都是512位。 SHA-384，SHA-512的数据分组则是1024位。,SHA-1，SHA-256，SHA-384，SHA-512的比较 表5.4是它们基本参数的比较：,第5章 散列函数与消息鉴别,目前对于散列函数的攻击方法可以分为两类：,对散列函数的攻击是指攻击者寻找一对产生碰撞的消息的过程。评价散列函数的有效方法就是看一个攻击者找到一对产生碰撞的消息所花的代价有多高。,第一类称为穷举攻击（或暴力攻击），它能对任何类型的散列函数进行攻击，其中最典型的方法就是“生日攻击”。 第二类称为密码分析法，这类攻击方法依赖于对散列函数的结构和代数性质分析，采用针对

11、散列函数弱性质的方法进行攻击。这类攻击方法有中间相遇攻击、修正分组攻击和差分分析等等。,生日悖论 我们来考虑这样一个有趣的问题：在一个教室中最少应有多少学生才使得至少有两个学生的生日在同一天的概率大于0.5？计算与此相关的概率被称为生日悖论问题。,5.4 对散列函数的攻击,第5章 散列函数与消息鉴别,生日攻击,与散列函数相关的类似问题可表述如下：给定一个散列函数h的输出长度为m位，共有2m个可能的散列值输出，如果让散列函数h接收k个随机输入产生集合X，再使用另外k个随机输入产生集合Y，问k必须为多大才能使两个集合产生相同散列值输出的概率大于0.5？ 这种寻找散列函数h的具有相同输出的两个任意输

12、入的攻击方式称为生日攻击。,5.5 消息鉴别,消息鉴别是一个过程，用以验证接收消息的真实性（的确是由它所声称的实体发来的）和完整性（未被篡改、插入、删除），同时还用于验证消息的顺序性和时间性（未被重排、重放、延迟等）。,消息鉴别对于开放的网络中的各种信息系统的安全性具有重要作用。,大体来说，实现消息鉴别的手段可以分为两类：基于加密技术的消息鉴别和基于散列函数的消息鉴别。,第5章 散列函数与消息鉴别,基于加密技术的消息鉴别,从消息鉴别的目的出发，无论是对称密码体制，还是公钥密码体制，对于消息本身的加密都可以看作是一种鉴别的手段。,（1）利用对称加密体制实现消息鉴别,如图5.10所示，发送方A和接

13、收方B共享密钥k。A用密钥k对消息M加密后通过公开信道传送给B。B接收到密文消息之后，通过是否能用密钥k将其恢复成合法明文，来判断消息是否来自A，信息是否完整。,第5章 散列函数与消息鉴别,该方法的特点是： 1）它能提供机密性：只有A和B知道密钥k； 2）提供鉴别：只能发自A，传输中未被改变； 3）不能提供数字签名：接收方可以伪造消息，发送方可以抵赖消息的发送。,（2）利用公钥密码体制实现消息鉴别, 提供消息鉴别,如图5.11所示，发送方A用自己的私钥SKA对消息进行加密运算（但并不能提供机密性保护，请思考为什么？），再通过公开信道传送给接收方B。接收方B用A的公钥PKA对得到的消息进行解密运

14、算并完成鉴别。,第5章 散列函数与消息鉴别,这种方法的特点是：能实现数字签名的功能，可以抗抵赖，并提供鉴别。,提供消息鉴别和机密性保护,如图5.12所示，在发送方A用自己的私钥SKA进行加密运算（实现数字签名）之后，还要用接收方B的公钥PKB进行加密，从而实现机密性。,缺点：一次完整的通信需要执行公钥算法的加密、解密操作各两次。 优点：提供机密性、数字签名和鉴别。,第5章 散列函数与消息鉴别,(1)消息鉴别码的概念,基于散列函数的消息鉴别,消息鉴别码(MAC，Message Authentication Code)或报文鉴别码，是 用于提供数据原发鉴别和数据完整性的密码校验值。MAC是使用一个

15、特定的密钥将消息通过一种鉴别算法处理所得出的一串代码。,一个MAC算法是由一个秘密密钥k和参数化的一簇函数hk构成。这簇函数具有如下特性：,第5章 散列函数与消息鉴别, 提供消息鉴别的方法（图5.13）：, 提供消息鉴别和机密性的方法（图5.14，图5.15）：,第5章 散列函数与消息鉴别,（2）基于散列函数的消息鉴别,散列函数具有以下特点：输入是可变大小的消息M，输出固定长度的散列值(即消息摘要)；计算简单，不需要使用密钥，具有强抗碰撞性。,基于散列函数的消息鉴别方法如图5.16所示，有以下几种情况：,（1）用对称密码体制加密消息及其散列值，如图5.16(a)。,（2）用对称密码体制只对消息

16、的散列值进行加密，如图5.16(b)。,（3）用公钥密码体制只对散列值进行加密运算，如图5.16(c)。,第5章 散列函数与消息鉴别,（4）结合使用公钥密码体制和对称密码体制，这种方法用发送方的私钥对散列值进行数字签名，用对称密码体制加密消息M和得到的数字签名，如图5.16(d)。,（5）这种方法使用了散列算法，但未使用加密算法。,（6）在方法(5)的基础上，使用对称密码体制对消息M和生成的散列值进行保护，如图5.16(f)。,第5章 散列函数与消息鉴别,第5章 散列函数与消息鉴别,HMAC算法,基于散列函数的消息鉴别码构造的基本思想就是将某个散列函数嵌入到消息鉴别码的构造过程中。HMAC作为这种构造方法的代表，已经作为RFC 2104公布，并在IPSec和其他网络协议(如SSL)中得到应用。,1.HMAC算法的设计要求：,按照RFC 2104，HMAC希望达到以下的设计要求：,第5章 散列函数与消息鉴别,2.HMAC算法描述,图5.17是HMAC算法的实现