第5章散列函数和消息鉴别1

第1章密码学概述 第2章古典密码技术 第3章分组密码第4章公钥密码体制第5章散列函数与消息鉴别第6章数字签名技术

第7章密钥管理技术第8章身份鉴别技术第9章序列密码第10章密码技术应用附录课程主要内容第5章散列函数与消息鉴别本章主要内容

散列函数的概念

散列函数的构造与设计 安全散列算法SHA对散列函数的攻击消息鉴别

第5章散列函数与消息鉴别5.1散列函数的概念

密码学中的散列函数又称为哈希函数（Hash函数）、杂凑函数，它是一种单向密码体制，是一个从明文到密文的不可逆映射，只有加密过程，不能解密。

散列函数的性质设散列函数为h(m)，具有以下基本特性：

（1）h(m)算法公开，不需要密钥。（2）具有数据压缩功能，可将任意长度的输入数据转换成一个固定长度的输出。（3）对任何给定的m，h(m)易于计算。散列函数必须满足以下安全性要求：（1）具有单向性。给定消息的散列值h(m)，要得到消息m在计算上不可行；（2）具有弱抗碰撞性（Weakcollisionresistance）。对任何给定的消息m，寻找与m不同的消息m’，使得它们的散列值相同，即h(m’)＝h(m)，在计算上不可行。（3）具有强抗碰撞性（Strongcollisionresistance)。寻找任意两个不同的消息m和m’，使得h(m)＝h(m’)在计算上不可行。第5章散列函数与消息鉴别散列函数的应用散列函数的主要应用有以下三个方面：

1）保证数据的完整性

2）单向数据加密

3）数字签名应用散列函数实现数据完整性保护的模型：

注：实际应用中，未必一定是如h(m‖k)的计算方式，明文与密钥k的组合方式因不同的实现可以不同。第5章散列函数与消息鉴别

算法中重复使用一个函数f

。函数f的输入有两项，一项是上一轮（第i-1轮）的输出CVi-1，称为链接变量，另一项是算法在本轮（第i轮）b位的输入分组mi。5.2散列函数的构造与设计

迭代型散列函数的一般结构整个散列函数的逻辑关系可表示为：CV0=IV；CVi=f（CVi-1，mi）；1≤i≤t；h（M）=CVt第5章散列函数与消息鉴别虽然在合理的假设下，可以证明这类散列函数是安全的，由于它的计算效率太低，所以这一类散列函数并没有什么实用价值。

散列函数的基本设计方法有：基于公开密钥密码算法的设计、基于对称分组密码算法的设计以及直接设计法。1.基于公开密钥密码算法设计散列函数散列函数的设计方法以CBC模式利用公开密钥算法，使用公钥PK以及初始变量IV对消息分组进行加密，并输出最后一个密文分组ct作为散列函数输出值，如图5.3所示。第5章散列函数与消息鉴别

基于分组密码的CBC工作模式和CFB工作模式的散列函数中，密钥k不能公开。如果密钥k公开，则会使得攻击者构造消息碰撞十分容易。

通常，可以使用对称密钥分组密码算法的CBC模式或CFB模式来产生散列值，如图5.4、图5.5所示。2.基于对称分组密码算法设计散列函数第5章散列函数与消息鉴别3.直接设计散列函数这类散列函数并不基于任何假设和密码体制，它是通过直接构造复杂的非线性关系达到单向性要求来设计单向散列函数。这类散列算法典型的有：MD2、MD4、MD5、SHA-1等算法。5.3安全散列算法SHA

1.SHA-1SHA-1是数字签名标准DSS（DigtialSignatureStandard）中使用的散列算法。它能够处理最大长度为2^{64}位的输入数据，输出为160位的散列函数值。

Ⅰ.基本操作和元素:(1)逐位逻辑运算(2)加法运算(3)移位操作f1,K,W[0…19]20stepsf2,K,W[20…39]20stepsf3,K,W[40…59]20stepsf4,K,W[60…79]20steps++++ABCEAEAEAEH(i-1)16032Xi512H(i)160SHA-1Processingofasingle512-bitblock+ismod232DBCDBCDBCD+Step FunctionName FunctionValue(0t19) ft=f(t,B,C,D) (BC)(￢BD)(20t39) f2=f(t,B,C,D) BCD(40t59) f3=f(t,B,C,D) (BC)(BD)(CD)(60t79) f4=f(t,B,C,D) BCDWt=(Wt-16

Wt-14Wt-8Wt-3)<<<1Yq512bitsW0W1W15W16

S1XORW0W2W8W13Wt

S1XORWt-16Wt-14Wt-8Wt-3W79

S1XORW63W65W71W76第5章散列函数与消息鉴别(1)消息分割与填充(2)初始化缓冲区(3)处理第i个数据块xi(4)4轮循环，80步操作完成后，保存散列中间结果，再与第一轮的输入相加（模2^{32}）(5)然后，以H0(i)

，H1(i)

，H2(i)

，H3(i)

，H4(i)作为寄存器初值，用于对分组xi+1进行散列处理。SHA-1压缩函数操作过程，如图5.9所示(下页)，是处理一个512位分组的4次循环中每一循环的基本压缩操作流程。Ⅱ.SHA的散列过程Ⅲ.SHA-1的压缩操作第5章散列函数与消息鉴别Ⅳ.示例

【例5.1】计算字符串“abc”的SHA-1散列值。字符串“abc”的二进制表示为：011000010110001001100011，共有24位的长度。按照SHA-1的填充要求，应该填充一个“1”(界符)和423个“0”，最后有两个字“0000000000000018”(十六进制)，表明原始消息的长度为24位。本例中共只有一个分组。第5章散列函数与消息鉴别初始五个寄存器的初始值为：

H0(0)=67452301，H1(0)=EFCDAB89，H2(0)=98BADCFE，H3(0)=10325476，H4(0)=C3D2E1F0进行迭代计算，前16个32位字的值刚好取自这个分组的所有字，即：

W0=61626380(即01100001011000100110001110000000)，

W1=W2=……=W14=00000000，W15=00000018。对t=0～79计算得到各个寄存器中的值。最后得到结果为：H0=67452301+42541B35=A9993E36，H1=EFCDAB89+5738D5E1=4706816A，H2=98BADCFE+21834873=BA3E2571，H3=10325476+681E6DF6=7850C26C，H4=C3D2E1F0+D8FDF6AD=9CD0D89D。于是：SHA-1(“abc”)=A9993E364706816ABA3E25717850C26C9CD0D89D，共160位，20个字节。

第5章散列函数与消息鉴别Ⅴ.其他SHA算法2002年，NIST在FIPSl80-1的基础上做了修改，发布了推荐的修订版本FIPS180-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是它们基本参数的比较：第5章散列函数与消息鉴别目前对于散列函数的攻击方法可以分为两类：对散列函数的攻击是指攻击者寻找一对产生碰撞的消息的过程。评价散列函数的有效方法就是看一个攻击者找到一对产生碰撞的消息所花的代价有多高。第一类称为穷举攻击（或暴力攻击），它能对任何类型的散列函数进行攻击，其中最典型的方法就是“生日攻击”。第二类称为密码分析法，这类攻击方法依赖于对散列函数的结构和代数性质分析，采用针对散列函数弱性质的方法进行攻击。这类攻击方法有中间相遇攻击、差分分析等。生日悖论

我们来考虑这样一个有趣的问题：在一个教室中最少应有多少学生才使得至少有两个学生的生日在同一天的概率大于0.5？计算与此相关的概率被称为生日悖论问题。5.4对散列函数的攻击第5章散列函数与消息鉴别生日攻击与散列函数相关的类似问题可表述如下：给定一个散列函数h的输出长度为m位，共有2m个可能的散列值输出，如果让散列函数h接收k个随机输入产生集合X，再使用另外k个随机输入产生集合Y，问k必须为多大才能使两个集合产生相同散列值输出的概率大于0.5？这种寻找散列函数h的具有相同输出的两个任意输入的攻击方式称为生日攻击。5.5消息鉴别消息鉴别是一个过程，用以验证接收消息的真实性（的确是由它所声称的实体发来的）和完整性（未被篡改、插入、删除），同时还用于验证消息的顺序性和时间性（未被重排、重放、延迟等）。消息鉴别对于开放的网络中的各种信息系统的安全性具有重要作用。大体来说，实现消息鉴别的手段可以分为两类：基于加密技术的消息鉴别和基于散列函数的消息鉴别。第5章散列函数与消息鉴别基于加密技术的消息鉴别从消息鉴别的目的出发，无论是对称密码体制，还是公钥密码体制，对于消息本身的加密都可以看作是一种鉴别的手段。（1）利用对称加密体制实现消息鉴别如图5.10所示，发送方A和接收方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对得到的消息进行解密运算并完成鉴别。第5章散列函数与消息鉴别这种方法的特点是：能实现数字签名的功能，可以抗抵赖，并提供鉴别。②提供消息鉴别和机密性保护如图5.12所示，在发送方A用自己的私钥SKA进行加密运算（实现数字签名）之后，还要用接收方B的公钥PKB进行加密，从而实现机密性。缺点：一次完整的通信需要执行公钥算法的加密、解密操作各两次。优点：提供机密性、数字签名和鉴别。第5章散列函数与消息鉴别(1)消息鉴别码的概念基于散列函数的消息鉴别消息鉴别码(MAC，MessageAuthenticationCode)或报文鉴别码，是用于提供数据原发鉴别和数据完整性的密码校验值。MAC是使用一个特定的密钥将消息通过一种鉴别算法处理所得出的一串代码。一个MAC算法是由一个秘密密钥k和参数化的一簇函数hk构成。这簇函数具有如下特性：a)容易计算——对于一个已知函数h，给定一个值k和一个输入x，hk(x)是容易计算的。这个计算的结果被称为消息鉴别码值或消息鉴别码。b)压缩——hk把任意具有有限长度（比特数）的一个输入x映射成一个具有固定长度的输出hk(x)。c)强抗碰撞性——要找到两个不同消息x和y，使得hk(x)=hk(y)是计算上不可行的。第5章散列函数与消息鉴别①提供消息鉴别的方法（图5.13）：②提供消息鉴别和机密性的方法（图5.14，图5.15）：第5章散列函数与消息鉴别（2）基于散列函数的消息鉴别散列函数具有以下特点：输入是可变大小的消息M，输出固定长度的散列值(即消息摘要)；计算简单，不需要使用密钥，具有强抗碰撞性。基于散列函数的消息鉴别方法如图5.16所示，有以下几种情况：（1）用对称密码体制加密消息及其散列值，如图5.16(a)。（2）用对称密码体制只对消息的散列值进行加密，如图5.16(b)。（3）用公钥密码体制只对散列值进行加密运算，如图5.16(c)。第5章散列函数与消息鉴别（4）结合使用公钥密码体制和对称密码体制，这种方法用发送方的私钥对散列值进行数字签名，用对称密码体制加密消息M和得到的数字签名，如图5.16(d)。（5）这种方法使用了散列算法，但未使用加密算法。（6）在方法(5)的基础上，使用对称密码体制对消息M和生成的散列值进行保护，如图5.16(f)。第5章散列函数与消息鉴别第5章散列函数与消息鉴别HMAC算法基于散列函数的消息鉴别码构造的基本思想就是将某个散列函数嵌入到消息鉴别码的构造过程中。HMAC作为这种构造方法的代表，已经作为RFC2104公布，并在IPSec和其他网络协议(如SSL)中得到应用。1.HMAC算法的设计要求：按照RFC2104，HMAC希望达到以下的设计要求：（1）——可不经修改而使用现有的散列函数，特别是那些易于软件实现的、源代码可方便获取且免费使用的散列函数。（2）——其中嵌入的散列函数可以易于替换为更快或更安全的散列函数，以适应不同的安全需求。（3）——保持嵌入的散列函数的原有性能，不因用于HAMC而使其性能降低。（4）——密钥的使用和处理简单方便。（5）——以嵌入的散列函数安全假设为基础，易于分析HMAC用于鉴别时的安全强度。第5章散列函数与消息鉴别

2.HMAC算法描述图5.17是HMAC算法的实现框图。其中h为嵌入的散列函数(如MD5、SHA-1);输入消息M=(Y0，Y1，……，YL-1)，

Yi(0≤i≤L-1)是b位的一个分组，M包含了散列函数的填充位。

n为嵌入的散列函数输出值的长度，