清华大学出版社第5章-散列函数和消息鉴别

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

2、设散列函数为h h( (m m) )，具有以下基本特性：，具有以下基本特性： （1 1）h h( (m m) )算法公开，不需要密钥。算法公开，不需要密钥。 （2 2）具有数据压缩功能，可将任意长度的输入数据转换成一）具有数据压缩功能，可将任意长度的输入数据转换成一个固定长度的输出。个固定长度的输出。 （3 3）对任何给定的）对任何给定的m m，h h( (m m) )易于计算。易于计算。散列函数必须满足以下安全性要求：散列函数必须满足以下安全性要求： （1 1）具有单向性。给定消息的散列值）具有单向性。给定消息的散列值h(mh(m) )，要得到消息，要得到消息m m在计算在计算上不可行；上不

3、可行； （2 2）具有弱抗碰撞性（）具有弱抗碰撞性（Weak collision resistanceWeak collision resistance）。对任何）。对任何给定的消息给定的消息m m，寻找与，寻找与m m不同的消息不同的消息mm，使得它们的散列值相同，即，使得它们的散列值相同，即h h( (m m)h h ( (m m) )，在计算上不可行。，在计算上不可行。 （3 3）具有强抗碰撞性（）具有强抗碰撞性（Strong collision resistance) Strong collision resistance) 。寻找。寻找任意两个不同的消息任意两个不同的消息m m和和m

4、m， 使得使得h h( (m m) )h h ( (m m) ) 在计算上不可行在计算上不可行。4/27第5章 散列函数与消息鉴别 散列函数的应用 散列函数的主要应用有以下三个方面： 1）保证数据的完整性 2）单向数据加密 3）数字签名 应用散列函数实现数据完整性保护的模型： 注：实际应用中，未必一定是如注：实际应用中，未必一定是如h(mk)的计算方式，明文与密钥的计算方式，明文与密钥k的的组合方式因不同的实现可以不同。组合方式因不同的实现可以不同。 5/27第5章 散列函数与消息鉴别 算法中重复使用一个函数算法中重复使用一个函数f f 。函数。函数f f的输入有两项，一项是上的输入有两项，一

5、项是上一轮（第一轮（第i i-1-1轮）的输出轮）的输出CVCVi-i-1 1，称为链接变量，另一项是算法在本，称为链接变量，另一项是算法在本轮（第轮（第i i轮）轮）b b位的输入分组位的输入分组m mi i。 5.2 5.2 散列函数的构造与设计散列函数的构造与设计 l 迭代型散列函数的一般结构迭代型散列函数的一般结构整个散列函数的逻辑关系可表示为：整个散列函数的逻辑关系可表示为： CV CV0 0 =IV =IV； CVCVi i = = f f（CVCVi i-1-1，m mi i）；）；11i it t； h h（M M）= = CVCVt t6/27第5章 散列函数与消息鉴别 虽然

6、在合理的假设下，可以证明这类散列函数是安全的，由于它虽然在合理的假设下，可以证明这类散列函数是安全的，由于它的计算效率太低，所以这一类散列函数并没有什么实用价值。的计算效率太低，所以这一类散列函数并没有什么实用价值。 散列函数的基本设计方法有：基于公开密钥密码算法的设计、基于对散列函数的基本设计方法有：基于公开密钥密码算法的设计、基于对称分组密码算法的设计以及直接设计法。称分组密码算法的设计以及直接设计法。1.1.基于公开密钥密码算法设计散列函数基于公开密钥密码算法设计散列函数 散列函数的设计方法散列函数的设计方法 以以CBCCBC模式利用公开密钥算法，使用公钥模式利用公开密钥算法，使用公钥P

7、KPK以及初始变量以及初始变量IVIV对消息分对消息分组进行加密，并输出最后一个密文分组组进行加密，并输出最后一个密文分组c ct t作为散列函数输出值，如图作为散列函数输出值，如图5.35.3所示。所示。7/27第5章 散列函数与消息鉴别 基于分组密码的基于分组密码的CBCCBC工作模式和工作模式和CFBCFB工作模式的散列函数中，密钥工作模式的散列函数中，密钥k k不能公开。如果密钥不能公开。如果密钥k k公开，则会使得攻击者构造消息碰撞十分容易。公开，则会使得攻击者构造消息碰撞十分容易。 通常，可以使用对称密钥分组密码算法的通常，可以使用对称密钥分组密码算法的CBCCBC模式或模式或CF

8、BCFB模式来产模式来产生散列值，如图生散列值，如图5.45.4、图、图5.55.5所示。所示。 2.2.基于对称分组密码算法设计散列函数基于对称分组密码算法设计散列函数8/27第5章 散列函数与消息鉴别3.3.直接设计散列函数直接设计散列函数 这类散列函数并不基于任何假设和密码体制，它是通过直接构造复这类散列函数并不基于任何假设和密码体制，它是通过直接构造复杂的非线性关系达到单向性要求来设计单向散列函数。这类散列算法典杂的非线性关系达到单向性要求来设计单向散列函数。这类散列算法典型的有：型的有：MD2MD2、MD4MD4、MD5MD5、SHA-1SHA-1等算法。等算法。5.3 5.3 安全

9、散列算法安全散列算法SHASHA 1. SHA-11. SHA-1 SHA-1 SHA-1是数字签名标准是数字签名标准DSSDSS（DigtialDigtial Signature Standard Signature Standard）中使用）中使用的散列算法。它能够处理最大长度为的散列算法。它能够处理最大长度为264264位的输入数据，输出为位的输入数据，输出为160160位的位的散列函数值，散列函数值，SHA-1SHA-1的输出正好适合作为数字签名算法的输出正好适合作为数字签名算法DSADSA（DigtialDigtial Signature Algorithm)Signature Al

10、gorithm)的输入。的输入。 . .基本操作和元素基本操作和元素: :(1)(1)逐位逻辑运算逐位逻辑运算(2) (2) 加法运算加法运算(3) (3) 移位操作移位操作9/27第5章 散列函数与消息鉴别(1) (1) 消息分割与填充消息分割与填充(2) (2) 初始化缓冲区初始化缓冲区(3) (3) 处理第处理第i i个数据块个数据块x xi i(4) 4(4) 4轮循环，轮循环，8080步操作完成后，步操作完成后，保存散列中间结果，再与第一轮的输保存散列中间结果，再与第一轮的输入相加（模入相加（模232232） (5) (5) 然后，以然后，以H H0 0( (i i) ) ，H H1

11、 1( (i i) ) ，H H2 2( (i i) ) ，H H3 3( (i i) ) ，H H4 4( (i i) )作为寄存器初值，用于作为寄存器初值，用于对分组对分组x xi+i+1 1进行散列处理。进行散列处理。 SHA-1 SHA-1压缩函数操作过程，如图压缩函数操作过程，如图5.95.9所示所示( (下页下页) )，是处理一个，是处理一个512512位位分组的分组的4 4次循环中每一循环的基本压缩操作流程。次循环中每一循环的基本压缩操作流程。.SHA.SHA的散列过程的散列过程.SHA-1.SHA-1的压缩操作的压缩操作.示例示例 【例例5.15.1】计算字符串计算字符串“ab

12、c”abc”的的SHA-1SHA-1散列值。散列值。 字符串字符串“abc”abc”的二进制表示为：的二进制表示为：01100001 01100010 0110001101100001 01100010 01100011，共有共有2424位的长度。按照位的长度。按照SHA-1SHA-1的填充要求，应该填充一个的填充要求，应该填充一个“1”(1”(界符界符) )和和423423个个“0”0”，最后有两个字，最后有两个字“00000000 00000018”(00000000 00000018”(十六进制十六进制) )，表明，表明原始消息的长度为原始消息的长度为2424位。本例中共只有一个分组。位

13、。本例中共只有一个分组。10/27第5章 散列函数与消息鉴别11/27第5章 散列函数与消息鉴别初始五个寄存器的初始值为： H0(0)=67452301，H1(0)=EFCDAB89，H2(0)=98BADCFE， H3(0)=10325476，H4(0)=C3D2E1F0进行迭代计算，前16个32位字的值刚好取自这个分组的所有字，即： W0=61626380(即01100001 01100010 01100011 10000000)， W1=W2=W14=00000000，W15=00000018。对t=079计算得到各个寄存器中的值。最后得到结果为： H0=67452301+42541B3

14、5=A9993E36， H1=EFCDAB89+5738D5E1=4706816A， H2=98BADCFE+21834873=BA3E2571， H3=10325476+681E6DF6=7850C26C， H4=C3D2E1F0+D8FDF6AD=9CD0D89D。 于是：SHA-1(“abc”)= A9993E36 4706816A BA3E2571 7850C26C 9CD0D89D，共160位，20个字节。 12/27第5章 散列函数与消息鉴别.其他其他SHASHA算法算法 2002 2002年，年，NISTNIST在在FIPS l80-1FIPS l80-1的基础上做了修改，发布了

15、推荐的修订版的基础上做了修改，发布了推荐的修订版本本FIPS 180-2FIPS 180-2。在这个标准中，除了。在这个标准中，除了SHA-1SHA-1外，还新增了外，还新增了SHA-256SHA-256、SHA-398SHA-398和和SHA-512SHA-512三个散列算法标准，它们的消息摘要长度分别为三个散列算法标准，它们的消息摘要长度分别为256256位、位、398398位和位和512512位，以便与位，以便与AESAES的使用相匹配。的使用相匹配。SHASHA系列散列算法的基本运算结构有很大系列散列算法的基本运算结构有很大的相似性。的相似性。 SHA-1SHA-1，SHA-256SH

16、A-256的数据分组都是的数据分组都是512512位。位。 SHA-384 SHA-384，SHA-512SHA-512的数据分组则是的数据分组则是10241024位。位。SHA-1SHA-1，SHA-256SHA-256，SHA-384SHA-384，SHA-512SHA-512的比较的比较 表表5.45.4是它们基本参数的比较：是它们基本参数的比较：13/27第5章 散列函数与消息鉴别 目前对于散列函数的攻击方法可以分为两类：目前对于散列函数的攻击方法可以分为两类： 对散列函数的攻击是指攻击者寻找一对产生碰撞的消息的过程。评价对散列函数的攻击是指攻击者寻找一对产生碰撞的消息的过程。评价散列

17、函数的有效方法就是看一个攻击者找到一对产生碰撞的消息所花的代散列函数的有效方法就是看一个攻击者找到一对产生碰撞的消息所花的代价有多高。价有多高。 第一类称为穷举攻击（或暴力攻击），它能对任何类型的散列函数进行第一类称为穷举攻击（或暴力攻击），它能对任何类型的散列函数进行攻击，其中最典型的方法就是攻击，其中最典型的方法就是“生日攻击生日攻击”。 第二类称为密码分析法，这类攻击方法依赖于对散列函数的结构和代数第二类称为密码分析法，这类攻击方法依赖于对散列函数的结构和代数性质分析，采用针对散列函数弱性质的方法进行攻击。这类攻击方法有中性质分析，采用针对散列函数弱性质的方法进行攻击。这类攻击方法有中间

18、相遇攻击、修正分组攻击和差分分析等等。间相遇攻击、修正分组攻击和差分分析等等。l 生日悖论生日悖论 我们来考虑这样一个有趣的问题：在一个教室中最少应有多少学我们来考虑这样一个有趣的问题：在一个教室中最少应有多少学生才使得至少有两个学生的生日在同一天的概率大于生才使得至少有两个学生的生日在同一天的概率大于0.50.5？计算与此？计算与此相关的概率被称为生日悖论问题。相关的概率被称为生日悖论问题。5.4 5.4 对散列函数的攻击对散列函数的攻击14/27第5章 散列函数与消息鉴别l 生日攻击生日攻击 与散列函数相关的类似问题可表述如下：给定一个散列函数与散列函数相关的类似问题可表述如下：给定一个散

19、列函数h的输出的输出长度为长度为m位，共有位，共有2m个可能的散列值输出，如果让散列函数个可能的散列值输出，如果让散列函数h接收接收k个随个随机输入产生集合机输入产生集合X，再使用另外，再使用另外k个随机输入产生集合个随机输入产生集合Y，问，问k必须为多必须为多大才能使两个集合产生相同散列值输出的概率大于大才能使两个集合产生相同散列值输出的概率大于0.5？ 这种寻找散列函数这种寻找散列函数h的具有相同输出的两个任意输入的攻击方式称为的具有相同输出的两个任意输入的攻击方式称为生日攻击。生日攻击。5.5 5.5 消息鉴别消息鉴别 消息鉴别是一个过程，用以验证接收消息的真实性（的确是由它所消息鉴别是

20、一个过程，用以验证接收消息的真实性（的确是由它所声称的实体发来的）和完整性（未被篡改、插入、删除），同时还用于声称的实体发来的）和完整性（未被篡改、插入、删除），同时还用于验证消息的顺序性和时间性（未被重排、重放、延迟等）。验证消息的顺序性和时间性（未被重排、重放、延迟等）。消息鉴别对于开放的网络中的各种信息系统的安全性具有重要作用。消息鉴别对于开放的网络中的各种信息系统的安全性具有重要作用。 大体来说，实现消息鉴别的手段可以分为两类：基于加密技术的大体来说，实现消息鉴别的手段可以分为两类：基于加密技术的消息鉴别和基于散列函数的消息鉴别。消息鉴别和基于散列函数的消息鉴别。15/27第5章 散列

21、函数与消息鉴别l 基于加密技术的消息鉴别基于加密技术的消息鉴别 从消息鉴别的目的出发，无论是对称密码体制，还是公钥密码体制从消息鉴别的目的出发，无论是对称密码体制，还是公钥密码体制，对于消息本身的加密都可以看作是一种鉴别的手段。，对于消息本身的加密都可以看作是一种鉴别的手段。（1 1）利用对称加密体制实现消息鉴别利用对称加密体制实现消息鉴别 如图如图5.105.10所示，发送方所示，发送方A A和接收方和接收方B B共享密钥共享密钥k k。A A用密钥用密钥k k对消息对消息M M加密后加密后通过公开信道传送给通过公开信道传送给B B。B B接收到密文消息之后，通过是否能用密钥接收到密文消息之

22、后，通过是否能用密钥k k将其恢将其恢复成合法明文，来判断消息是否来自复成合法明文，来判断消息是否来自A A，信息是否完整。，信息是否完整。16/27第5章 散列函数与消息鉴别该方法的特点是：该方法的特点是：1 1）它能提供机密性：只有）它能提供机密性：只有A A和和B B知道密钥知道密钥k k；2 2）提供鉴别：只能发自）提供鉴别：只能发自A A，传输中未被改变；，传输中未被改变；3 3）不能提供数字签名：接收方可以伪造消息，发送方可以抵赖消息）不能提供数字签名：接收方可以伪造消息，发送方可以抵赖消息的发送。的发送。（2 2）利用公钥密码体制实现消息鉴别利用公钥密码体制实现消息鉴别 提供消息

23、鉴别提供消息鉴别 如图如图5.115.11所示，发送方所示，发送方A A用自己的私钥用自己的私钥SKSKA A对消息进行加密运算（但并对消息进行加密运算（但并不能提供机密性保护，请思考为什么？），再通过公开信道传送给接收不能提供机密性保护，请思考为什么？），再通过公开信道传送给接收方方B B。接收方。接收方B B用用A A的公钥的公钥PKPKA A对得到的消息进行解密运算并完成鉴别。对得到的消息进行解密运算并完成鉴别。17/27第5章 散列函数与消息鉴别这种方法的特点是：能实现数字签名的功能，可以抗抵赖，并提供鉴别。这种方法的特点是：能实现数字签名的功能，可以抗抵赖，并提供鉴别。提供消息鉴别和

24、机密性保护提供消息鉴别和机密性保护 如图如图5.125.12所示，在发送方所示，在发送方A A用自己的私钥用自己的私钥SKSKA A进行加密运算（实现数字进行加密运算（实现数字签名）之后，还要用接收方签名）之后，还要用接收方B B的公钥的公钥PKPKB B进行加密，从而实现机密性。进行加密，从而实现机密性。 缺点：一次完整的通信需要执行公钥算法的加密、解密操作各两次。缺点：一次完整的通信需要执行公钥算法的加密、解密操作各两次。优点：提供机密性、数字签名和鉴别。优点：提供机密性、数字签名和鉴别。18/27第5章 散列函数与消息鉴别 (1) (1)消息鉴别码的概念消息鉴别码的概念l 基于散列函数的

25、消息鉴别基于散列函数的消息鉴别 消息鉴别码消息鉴别码(MAC(MAC，Message Authentication Code)Message Authentication Code)或报文鉴别码，是或报文鉴别码，是用于提供数据原发鉴别和数据完整性的密码校验值。用于提供数据原发鉴别和数据完整性的密码校验值。MACMAC是使用一个特定是使用一个特定的密钥将消息通过一种鉴别算法处理所得出的一串代码。的密钥将消息通过一种鉴别算法处理所得出的一串代码。 一个一个MACMAC算法是由一个秘密密钥算法是由一个秘密密钥k k和参数化的一簇函数和参数化的一簇函数h hk k构成。这簇函构成。这簇函数具有如下特性

26、：数具有如下特性：a)a)容易计算容易计算 对于一个已知函数对于一个已知函数h h，给定一个值，给定一个值k k和一个输入和一个输入x x，h hk k( (x x) )是容易计算的。这个计算的结果被称为消息鉴别是容易计算的。这个计算的结果被称为消息鉴别码值或消息鉴别码。码值或消息鉴别码。b) b) 压缩压缩h hk k把任意具有有限长度（比特数）的一个输入把任意具有有限长度（比特数）的一个输入x x映射映射成一个具有固定长度的输出成一个具有固定长度的输出h hk k( (x x) )。c) c) 强抗碰撞性强抗碰撞性 要找到两个不同消息要找到两个不同消息x x和和y y，使得，使得h hk

27、k( (x x)=)=h hk k( (y y) )是计是计算上不可行的。算上不可行的。19/27第5章 散列函数与消息鉴别 提供消息鉴别的方法（图提供消息鉴别的方法（图5.135.13）：）： 提供消息鉴别和机密性的方法（图提供消息鉴别和机密性的方法（图5.145.14，图，图5.155.15）：）：20/27第5章 散列函数与消息鉴别（2 2）基于散列函数的消息鉴别）基于散列函数的消息鉴别 散列函数具有以下特点：输入是可变大小的消息散列函数具有以下特点：输入是可变大小的消息M M，输出固定长度的，输出固定长度的散列值散列值( (即消息摘要即消息摘要) )；计算简单，不需要使用密钥，具有强抗

28、碰撞性。；计算简单，不需要使用密钥，具有强抗碰撞性。 基于散列函数的消息鉴别方法如图基于散列函数的消息鉴别方法如图5.165.16所示，有以下几种情况：所示，有以下几种情况：（1 1）用对称密码体制加密消息及其散列值，如图）用对称密码体制加密消息及其散列值，如图5.16(a)5.16(a)。 （2 2）用对称密码体制只对消息的散列值进行加密，如图）用对称密码体制只对消息的散列值进行加密，如图5.16(b)5.16(b)。 （3 3）用公钥密码体制只对散列值进行加密运算，如图）用公钥密码体制只对散列值进行加密运算，如图5.16(c)5.16(c)。 21/27第5章 散列函数与消息鉴别（4 4）

29、结合使用公钥密码体制和对称密码体制，这种方法用发送方的私钥）结合使用公钥密码体制和对称密码体制，这种方法用发送方的私钥对散列值进行数字签名，用对称密码体制加密消息对散列值进行数字签名，用对称密码体制加密消息M M和得到的数字签名，和得到的数字签名，如图如图5.16(d)5.16(d)。 （5 5）这种方法使用了散列算法，但未使用加密算法。）这种方法使用了散列算法，但未使用加密算法。 （6 6）在方法）在方法(5)(5)的基础上，使用对称密码体制对消息的基础上，使用对称密码体制对消息M M和生成的散列值和生成的散列值进行保护，如图进行保护，如图5.16(f)5.16(f)。 22/27第5章 散

30、列函数与消息鉴别23/27第5章 散列函数与消息鉴别l HMAC HMAC算法算法 基于散列函数的消息鉴别码构造的基本思想就是将某个散列函数嵌入到基于散列函数的消息鉴别码构造的基本思想就是将某个散列函数嵌入到消息鉴别码的构造过程中。消息鉴别码的构造过程中。HMACHMAC作为这种构造方法的代表，已经作为作为这种构造方法的代表，已经作为RFC RFC 21042104公布，并在公布，并在IPSecIPSec和其他网络协议和其他网络协议( (如如SSL)SSL)中得到应用。中得到应用。1.HMAC1.HMAC算法的设计要求：算法的设计要求： 按照按照RFC 2104RFC 2104，HMACHMA

31、C希望达到以下的设计要求：希望达到以下的设计要求：（1 1）可不经修改而使用现有的散列函数，特别是那些易于软可不经修改而使用现有的散列函数，特别是那些易于软件实现的、源代码可方便获取且免费使用的散列函数。件实现的、源代码可方便获取且免费使用的散列函数。（2 2）其中嵌入的散列函数可以易于替换为更快或更安全的散其中嵌入的散列函数可以易于替换为更快或更安全的散列函数，以适应不同的安全需求。列函数，以适应不同的安全需求。（3 3） 保持嵌入的散列函数的原有性能，不因用于保持嵌入的散列函数的原有性能，不因用于HAMCHAMC而使而使其性能降低。其性能降低。（4 4） 密钥的使用和处理简单方便。密钥的使

32、用和处理简单方便。（5 5） 以嵌入的散列函数安全假设为基础，易于分析以嵌入的散列函数安全假设为基础，易于分析HMACHMAC用于用于鉴别时的安全强度。鉴别时的安全强度。24/27第5章 散列函数与消息鉴别 2.HMAC2.HMAC算法描述算法描述 图图5.175.17是是HMACHMAC算法的实现框图。算法的实现框图。 其中其中h h为嵌入的散列函数为嵌入的散列函数( (如如MD5MD5、SHA-1);SHA-1); 输入消息输入消息M=(YM=(Y0 0，Y Y1 1，Y YL-1L-1) )， Y Yi i(0(0i iL-1)L-1)是是b b位的一个分组，位的一个分组，M M包含了散列函数包含了散列函数的填充位。的填充位。 n n为嵌入的散列函数输出值的长度，为嵌入的散列函数输出值的长度， K K为密钥，如果密钥长度大于为密钥，如果密钥长度大于b b，则将密钥输入到散列，则将密钥输入到散列函数中产生一个函数中产生一个n n位的密钥。位的密钥。 K+ K+是左边填充了是左边填充了0 0后的后的K K，其长度为，其长度为b b位，位， ipadipad为为b/8b/8个个0011011000110110序列串，序列串， opadopad为为b/8b/8个个0101101001