密码学课件：九、散列函数和消息鉴别

1、散列函数主要内容概述散列函数针对的攻击类型、散列函数的定义、性质、分类和应用散列函数的构造与设计MD算法SHA消息鉴别概述散列函数概述散列函数又称为哈希（Hash）函数、杂凑函数、消息摘要函数、单向函数、压缩函数、缩短函数等是一种压缩函数：将任意长的输入消息（message）压缩为某一个固定长度的摘要（message digest,MD）的函数。摘要又称为散列码。只有加密过程，不能解密。用于生成文件或数据块的“数字指纹”。散列函数通常应用于消息鉴别中对抗主动攻击。概述攻击的类型被动攻击和主动攻击示意图：概述攻击的类型概述攻击的类型伪造：包括身份伪造和内容伪造。冒充是指冒充接收者或发送者，实际是

2、身份伪造。篡改：将消息的标签、内容、属性、接受者和始发者等信息进行修改。插入：在消息中插入新的消息删除：删除原消息或其部分重排：将原消息的顺序变换后发送重放：将窃取的整条合法信息保存，在适当的时机再次发送。延迟：将原消息延迟发送。概述攻击的类型业务拒绝：通过正常的方式恶意耗尽系统资源。参与方抵赖：发送方否认发送过消息，接收方否认接收过消息。获取消息内容（窃取）：通过电磁辐射侦收或在信息存储和处理过程中窃取等。业务流分析（推断）：将窃取到的信息进行统计分析，通过了解信息流大小的变化、信息交换频繁的程序，再结合其他方面的信息，推断出有价值的内容。概述攻击的防范通过加密技术可抵抗被动攻击。通过消息鉴

3、别可抵抗攻击分类中的大部分主动攻击，具体介绍如下：概述消息鉴别的具体功能验证消息来源的真实性：的确是有它所声称的实体发来的，无冒充验证消息的完整性：未被篡改、插入、删除验证消息的实际顺序和时间性：未经重排、重放、延迟验证消息的抗抵赖性：防止通信双方对所传输的消息的否认，通过数字签名实现，数字签名也是一种认证。概述消息鉴别的具体技术基于散列函数(Hash)基于消息认证码（MAC）基于加密技术消息鉴别在有的资料上称为消息认证或报文鉴别。下面先介绍Hash函数。散列函数的定义定义：将一个任意长的二进制串映射为一个定长的二进制串（长为k），即h:0,1* 0,1 k。给定m0,1*，计算h(m)容易。

4、散列函数的性质散列函数h(m)，具有以下特性（1）具有单向性。给定h(m)，要得到m在计算上不可行。（2）具有弱抗碰撞性。对任何给定的消息m，寻找与m不同的消息m，使得他们的散列值相同，即h(m)=h(m)，在计算上不可行。（3）具有强抗碰撞性。寻找任意两个不同的消息m和m，使得h(m)=h(m)，在计算上不可行。散列函数的性质散列函数h(m)，具有以下特性（4）严格雪崩准则（strict avalanche criteria,SAC）：当一个输入位发生改变时，要求输出位中将有至少一半发生改变。（5）Hash率：对于基于分组密码E构建的Hash函数，如果处理每个消息分组需要进行s次E操作，那么

5、Hash率就为1/s。显然，Hash率越高，算法运行越快。散列函数的性质散列函数h(m)，具有以下特性碰撞的不可避免性：散列函数输出的散列值的长度是固定的，如假设散列值长度为160位，显然可能的散列值的总数为2160，但由于输入的消息是任意的，所以不同的消息就有可能会产生相同的散列值，即散列函数具有碰撞的不可避免性。因此要求找到一个碰撞在计算上不可行。很多情况下弱抗碰撞已经可以满足安全要求，但有些情况需要强抗碰撞。散列函数的分类散列函数主要有两类：带密钥的散列函数和不带密钥的散列函数。不带密钥的散列函数任何人都可以用来计算散列值，它仅仅是输入串的函数；带密钥的散列函数是输入串和密钥的散列函数，

6、只有持有密钥的人才能计算出散列码。散列函数的构造与设计散列函数要求将任意长度的输入值压缩为一个定长的输出值，由于很难直接构造出一个这样的函数，实际设计的散列函数都是通过迭代处理固定长度的压缩函数来构造的，通常称为MD方法。迭代型散列函数的一般构造迭代型散列函数的一般构造MD方法如图：对消息进行分组，最后部分按需要进行填充。F为压缩函数，接收r位的输入，产生n位的输出（通常rn）。迭代型散列函数的一般构造目前使用的大多数散列函数，如MD5、SHA等的结构都是迭代型的。输入消息M，将M分成t个分组（m1,m2,mt），每组b位。如果最后一个分组的长度不够，需要对其他进行填充。迭代型散列函数的一般构

7、造函数f的输入有两项，一项是上一轮的输出CVi-1，另一项是本轮分组mi。CVi-1称为链接变量。函数f的输出为n位的CVi。最后一轮输出的链接变量CVi即为最终产生的散列值。通常分组长度b大于散列值长度n，f称为压缩函数。散列函数的设计方法散列函数不要求求逆，设计的空间比较大。有基于公开密钥密码算法的设计、基于对称分组密码算法的设计以及直接设计三种方式。散列函数的设计方法1.基于公开密钥密码算法设计散列函数CBC模式：密码分组链接模式散列函数的设计方法1.基于公开密钥密码算法设计散列函数散列函数的逻辑关系表示为如果丢弃用户的私钥SK，产生的散列函数无法解密，满足单向性要求。散列函数的设计方法

8、2.基于对称分组密码算法设计散列函数基于分组密码的压缩函数早前很少被采用，一方面是效率不高，另一方面是分组长度对Hash函数应用来说太短。AES的出现改变了现状，它有足够的分组长度，没有弱密钥，能抵抗差分攻击。基于分组密码的Hash函数体制，简称PGV体制。散列函数的设计方法2.基于对称分组密码算法设计散列函数压缩函数f：0,1n0,1n0,1n，一般表达如下：f(h,x)=Ea(b)c其中a,b,ch,x,hx,v，v是一个固定的n位常量，|h|=|x|=n。如图所示：散列函数的设计方法2.基于对称分组密码算法设计散列函数针对f(h,x)=Ea(b)c，a,b,ch,x,hx,v，有444=

9、64种方案，其中有12种方案被证明具有足够的安全性。散列函数的设计方法2.基于对称分组密码算法设计散列函数前5种方案：散列函数的设计方法2.基于对称分组密码算法设计散列函数前5种方案：散列函数的设计方法3.直接设计散列函数不基于任何假设和密码体制，通过直接构造复杂的非线性关系达到单向性要求来设计单向性散列函数。典型的有：MD2，MD4，MD5，SHA系列等算法。下面介绍MD和SHA系列算法。消息摘要（MD）概述MD(Message Digest，消息摘要)算法是由Ron Rivest（ Rivest是RSA公司的科学家，MIT博士）在1990年10月提出，通常称之为MD4。MD4是一种单独设计

10、的散列算法，不基于任何密码体制和已知的单向函数，产生128位的消息摘要。针对MD4可能存在的安全性问题，Ron Rivest对MD4进行改进，在1991提出MD5。1992年提出SHA，1993年5月采纳作为标准。MD系列和SHA系列都源于同一思想，下面介绍MD4和MD5。MD4MD4算法中涉及的基本运算：（1）XY：逻辑与运算（2）XY：逻辑或运算（3）XY：逻辑异或运算（4）X ：逻辑非运算（5）X+Y：模232加法运算（6）Xs：X循环左移s位，0s31MD4MD4算法的具体过程：预处理：首先对输入消息x分组，每个分组M长为512位，再将M分成长为32位的16块：M=M0M1Mn-1其中

11、，|Mi|=32，0in-1，n0 mod 16。按需要对最后一组进行填充。MD4MD4算法的具体过程：散列函数h(x)构造如下：（1）给定4个32位寄存器A,B,C,D，赋初值(十六进制)：A=67452301B=efcdab89C=98badcfeD=10325476MD4MD4算法的具体过程：（2）将x的各个分组M的值装入到X：Xj=M16i+j其中，i为分组的序号，j为分组中块的序号， 0i(n/16)-1， 0j15，Xj共512位。（3）将已有的4个寄存器A,B,C,D中的数组分别存放到另外4个寄存器AA,BB,CC,DD中。MD4MD4算法的具体过程：（4）执行第一轮操作，每次处

12、理4个块，16个块4次处理完，具体内容包括：A=(A+F(B,C,D)+X4k)3D=(D+F(A,B,C)+X4k+1)7C=(C+F(D,A,B)+X4k+2)11B=(B+F(C,D,A)+X4k+3)19其中，0k3，F(X,Y,Z)=(XY)(XZ)MD4MD4算法的具体过程：（5）执行第二轮操作，具体内容包括：A=(A+G(B,C,D)+Xk+5a827999)3D=(D+G(A,B,C)+X4+k+5a827999)5C=(C+G(D,A,B)+X8+k+5a827999)9B=(B+G(C,D,A)+X12+k+5a827999)13其中，0k3,G(X,Y,Z)=(XY)(X

13、Z)(YZ)MD4MD4算法的具体过程：（6）执行第三轮操作，具体内容包括：A=(A+H(B,C,D)+X0+6ed9ebal)3D=(D+H(A,B,C)+X8+6ed9ebal)9C=(C+H(D,A,B)+X4+6ed9ebal)11B=(B+H(C,D,A)+X12+6ed9ebal)15A=(A+H(B,C,D)+X2+6ed9ebal)3D=(D+H(A,B,C)+X10+6ed9ebal)9C=(C+H(D,A,B)+X6+6ed9ebal)11B=(B+H(C,D,A)+X14+6ed9ebal)15MD4MD4算法的具体过程：（6）执行第三轮操作，具体内容包括：A=(A+H(

14、B,C,D)+X1+6ed9ebal)3D=(D+H(A,B,C)+X9+6ed9ebal)9C=(C+H(D,A,B)+X5+6ed9ebal)11B=(B+H(C,D,A)+X13+6ed9ebal)15A=(A+H(B,C,D)+X3+6ed9ebal)3D=(D+H(A,B,C)+X11+6ed9ebal)9C=(C+H(D,A,B)+X7+6ed9ebal)11B=(B+H(C,D,A)+X15+6ed9ebal)15其中，H(X,Y,Z)=XYZMD4MD4算法的具体过程：（7）A=A+AA，B=B+BB，C=C+CC，D=D+DD（8）输出h(x)=A|B|C|D得到128位的消

15、息摘要。MD5与MD4相同，MD5算法的分组长度也是512位，每个分组再被划分成16个32位的块。输出的散列值也为128位。预处理：对消息x进行预处理，按需要进行填充后使得长度是512位的整数倍。另外，最后一个512位分组的后64位用于存放消息x的长度length(x)，如果消息x的长度值不足64位，在长度前填充0。MD5MD5算法的具体过程：（1）给定4个寄存器A,B,C,D，赋初值(十六进制)：A=01234567B=89abcdefC=fedcba98D=76543210MD5MD5算法的具体过程：（2）循环中的4轮操作将以上的寄存器A,B,C,D的值赋给变量AA,BB,CC,DD。然后

16、对所有的512位的分组中的每个块循环进行4轮操作（MD4中只有3轮）。4轮操作中的4个非线性函数分别定义为：F(X,Y,Z)=(XY)(X)Z)G(X,Y,Z)=(XZ)(Y(Z)H(X,Y,Z)=XYZI(X,Y,Z)=Y(X(Z)MD5MD5算法的具体过程：（2）循环中的4轮操作另外定义FF、GG、HH、II函数：AA=FF(AA,BB,CC,DD,Mj,s,tj)=BB+(AA+F(BB,CC,DD)+Mj+tj)S)AA=GG(AA,BB,CC,DD,Mj,s,tj)=BB+(AA+G(BB,CC,DD)+Mj+tj)S)AA=HH(AA,BB,CC,DD,Mj,s,tj)=BB+(A

17、A+H(BB,CC,DD)+Mj+tj)S)AA=II(AA,BB,CC,DD,Mj,s,tj)=BB+(AA+I(BB,CC,DD)+Mj+tj)S)其中，tj是常数。MD5MD5算法的具体过程：（2）循环中的4轮操作四轮操作具体如下。第一轮(16次操作)：FF(AA,BB,CC,DD,M0,7,d76aa478)FF(DD,AA,BB,CC,M1,12,e8c7b756)FF(BB,CC,DD,AA,M15,22,49b40821)MD5MD5算法的具体过程：（2）循环中的4轮操作四轮操作具体如下。第二轮(16次操作)：GG(AA,BB,CC,DD,M1,5,f61e2562)GG(DD,

18、AA,BB,CC,M6,9,c040b340)GG(BB,CC,DD,AA,M12,20,8d2a4c8a)MD5MD5算法的具体过程：（2）循环中的4轮操作四轮操作具体如下。第三轮(16次操作)：HH(AA,BB,CC,DD,M5,4,fffa3942)HH(DD,AA,BB,CC,M8,11,8771f681)HH(BB,CC,DD,AA,M2,23,c4ac5665)MD5MD5算法的具体过程：（2）循环中的4轮操作四轮操作具体如下。第四轮(16次操作)：II(AA,BB,CC,DD,M0,6,f4292244)II(DD,AA,BB,CC,M7,10,432aff97)II(BB,CC

19、,DD,AA,M9,21,eb86d391)MD5MD5算法的具体过程：（3）A=A+AA，B=B+BB，C=C+CC，D=D+DD（4）输出h(x)=A|B|C|D得到128位的消息摘要MD5MD5与MD4进行比较，MD5的改进如下：（1）增加主循环中的操作次数，由三轮改为四轮（2）操作的每一步都有唯一的加法常数（3）为了减弱函数G的对称性，函数定义由(XY)(XZ)(YZ)改为(XZ)(Y(Z)。（4）改变第二轮和第三轮中消息分组访问的次序，使得形式的不相似程度更大（5）每一轮中的循环移位量各不相同，进行了优化。对MD5的攻击对散列函数的攻击是指攻击者找到一对产生碰撞的消息的过程。2004

20、年8月17日，美国加州圣巴巴拉的国际密码学会议（Crypto2004），山东大学的王小云教授做了破译MD5、HAVAL-128、MD4和RIPEMD算法的报告。在会场上，当她公布MD系列算法的破解方法和结果之后，报告被激动的掌声打断。王小云教授的报告轰动了全场，得到了与会专家的赞叹。并证明了160位的SHA-1只需要计算大约269次就能找到碰撞，而理论值是280次。对MD5的攻击Rivest说：“MD5函数十几年来经受住了众多密码学专家的攻击，而王小云教授却成功破解，这实在是一种令人印象极深的卓越成就，是高水平的世界级研究成果。”安全散列算法SHA概述SHA（Secure Hash Algor

21、ithm）最初由NIST（美国国家标准与技术研究所）作为联邦信息处理标准FIPS PUB 180在1993年发布。SHA-1是1995年发布，对FIPS PUB 180版本的修订，版本号为FIPS PUB 180-1SHA-1在数字签名标准DSS中使用，能够处理最大长度264位的输入数据，输出160位的散列值。安全散列算法SHA-11.基本操作和元素（1）逐位逻辑运算安全散列算法SHA-11.基本操作和元素（2）加法运算安全散列算法SHA-11.基本操作和元素（3）移位操作安全散列算法SHA-12.SHA-1的散列过程（1）消息分割和填充SHA-1算法的分组大小为512位，当消息的长度大于51

22、2位时，需要对消息进行分割与填充。将消息x按照每块512位，分割成x1,x2,xn，最后一个块进行填充。length(x)表示消息的总长度，为64位，如果length(x)不足64位，在其左边补0。数据部分与填充部分用1分开。安全散列算法SHA-12.SHA-1的散列过程（1）消息分割和填充当消息x分割成x1,x2,xn后，将每个512位的xi分成16个字，每个字32位，记为：以下具体分析消息块xi的处理过程。安全散列算法SHA-12.SHA-1的散列过程（2）初始化缓冲区SHA-1的缓冲区为160位，5个32的数据块H0,H1,H2,H3,H4，最后的散列结果为H(i)=(H0(i),H1(

23、i),H2(i),H3(i),H4(i)。在实现时另外设置5个32位的寄存器A,B,C,D,E保存中间结果，初始化如下：安全散列算法SHA-12.SHA-1的散列过程（3）对xi进行处理包含4个循环模块，每个循环20个处理步骤，共80步，用t表示。每个循环的输入是512位的xi和160位的ABCDE值。 ABCDE的初始值为：A=H0(i-1), B=H1(i-1), C=H2, (i-1) D=H3(i-1), E=H4(i-1)。安全散列算法SHA-12.SHA-1的散列过程（3）对xi进行处理每个循环的Kt，0t79，取值如下：安全散列算法SHA-12.SHA-1的散列过程（3）对xi进

24、行处理每个循环的ft，0t79，输入是3个32位的字，如下：安全散列算法SHA-12.SHA-1的散列过程（3）对xi进行处理80步中，需要80个不同的32位字Wt作为输入参数。安全散列算法SHA-12.SHA-1的散列过程（4）4轮循环共80步完成后，保存散列中间结果，再与第一轮的输入相加（模232）H0(i)=H0(i-1)+AH1(i)=H1(i-1)+BH2(i)=H2(i-1)+CH3(i)=H3(i-1)+DH4(i)=H4(i-1)+E安全散列算法SHA-12.SHA-1的散列过程（5）然后以H0(i),H1(i),H2(i),H3(i),H4(i)作为寄存器初值，用于对xi+1

25、进行处理.当对最后一个数据分组xn处理完成后，既得整个输入消息x的160位的散列值：SHA-1(x)=H(n)=(H0(n)|H1(n)|H2(n)|H3(n)|H4(n)安全散列算法SHA-13.SHA-1的压缩操作压缩函数操作过程如图，是处理一个512位分组的4次循环中每一循环的基本压缩操作流程。安全散列算法SHA-13.SHA-1的压缩操作表示为：A(E+ft(B,C,D)+A5+Wt+Kt)BACB0.5的最小k值。首先考虑k个数中，任意两个取值都不相同的概率，记为Q(365,k)。如果k365，则使得任意两个数都不相同是不可能的，因此假设k0.5，解得生日攻击生日悖论类似的集合相交问

26、题：设取整数的随机变量服从1n之间的均匀分布，另有两个含有k个如此随机变量的集合，若使两个集合中至少有一个元素取值相同的概率大于0.5，则k至少多大？用相同的分析方法，可得生日攻击生日攻击散列函数的生日攻击问题：给定一个散列函数h，输出长度为m位，则共有2m个可能的散列值。构造散列函数的两个输入集合X和Y，集合元素的个数都是k。问k必须多大才能使两个集合产生相同的散列值的概率大于0.5？根据结论：n= 2m，kn1/22m/2这种寻找散列函数的具有相同散列值，但是是不同输入的攻击方式称为生日攻击。对于160位的SHA-1，产生碰撞的概率大于0.5的次数为280.山东大学教授理论证明只需269次

27、。生日攻击生日攻击举例：Alice是一家公司的经理，要从Bob的公司购买一批计算机。经过双方协商，确定为每台5000元。于是卖方Bob将合同的电子文本发给买方Alice征得其同意，并让其进行电子签名。Alice收到合同后，确认是每台5000元，并计算出该合同电子文本的散列值，用自己的私钥进行数字签名后发回给Bob，以此作为Alice对合同的认可。下面Bob要伪造另外一份合同，但合同中价格比5000元高（比如每台10000元），但是伪造的合同的散列值与Alice 保存的价格是每台5000元的合同的散列值相同。生日攻击生日攻击举例：Bob在发给Alice合同样本之前，首先写好一份正确的合同，合同中

28、的价格为5000元，然后标出这份合同中无关紧要的地方。由于一份合同中总是有许许多多的句子可采用其他不同的表达方式，但是 表达的意思却相同。现在Bob把这些意思相同但表达方式不同的合同都列出来，组成一个集合，Bob再把合同中的价格5000元改成10000元后组成另外一个集合，接着Bob把所有的合同的散列值都计算一遍，挑出一对散列值相同的合同。把5000元的合同作为样本发给Alice，10000元的合同自己保存。生日攻击生日攻击举例：根据生日攻击方法，假设散列函数的输出为64位，那么Bob只要找到合同中32个无关紧要的地方，来分别构造5000元和10000元的两组合同，两个组各自的合同数都为232

29、，就有0.5以上的概率在这两组合同中找到散列值相同的两份不同合同，实现诈骗行为。消息鉴别消息鉴别的定义：消息鉴别是一个过程，用以验证接收到的消息的真实性（无身份冒充、重放、延迟），完整性（未被篡改、插入、删除、重排）以及抗抵赖性（收发双方无否认）。消息鉴别消息鉴别的三种实现方式：基于加密技术的消息鉴别基于散列函数的消息鉴别基于消息认证码（MAC） 的消息鉴别基于加密技术的消息鉴别1.利用对称加密体制实现消息鉴别目的：鉴别消息是否来自于发送方A（真实性），消息是否完整（完整性）。发送方A和接收方B共享密钥k。A用密钥k对消息M加密后通过公开信道传送给B。B收到后，用密钥k解密。如果能够顺利解密，

30、则说明确为A发送，解密后根据明文的语法结构判断是否被插入、删除、篡改。基于加密技术的消息鉴别1.利用对称加密体制实现消息鉴别该方法的特点：（1）能提供机密性：只有用户A和B知道密码k（2）提供真实性、完整性：只能发自A，可确认密文在传输中未被改变。如果源文件就没有语法结构，如二进制文件，则不能判断是否被插入、删除或篡改（3）无抗抵赖性：接收方可否认收到消息，并可伪造一条不同的消息；发送方可以抵赖发送过消息基于加密技术的消息鉴别1.利用对称加密体制实现消息鉴别针对特点（2），一种可能的解决办法是增加错误检测码FCS：在加密前使用公开的函数F产生消息M的错误检测码FCS，如图，如果密文被修改，则计

31、算出来的FCS与收到的FCS无法匹配。基于加密技术的消息鉴别1.利用对称加密体制实现消息鉴别针对特点（2），使用FCS进行鉴别的执行顺序很重要，如图是一种错误的顺序，攻击者可构造正确的FCS，则无法实现鉴别。基于加密技术的消息鉴别2.利用公钥密码体制实现消息鉴别有两种方式。（1）提供抗抵赖性、真实性（身份真实），无机密性发送方A用私钥SKA对消息进行加密，结果通过公开的信道发送给B，B收到后用A的公钥PKA进行解密。因A加密的私钥SKA是私有的，解密的公钥PKA 只有A才能产生，所以消息一定来自于A，无法抵赖，完成鉴别。此种情况完整性没有意义。基于加密技术的消息鉴别2.利用公钥密码体制实现消息鉴别（2）提供抗抵赖性、真实性、完整性、机密性上一种方案只能提供抗抵赖性、真实性，不能提供机密性保护，因只要拥有公钥就能解密。下一种方案可以兼顾两种，缺点是一次完整的通信过程需要执行两次公钥密码算法的加、解密。基于消息认证码的消息鉴别1.消息认证码的概念消息认证码（Message Authentication Code, MAC）：通过一个密钥k和一种鉴别算法hk对消息进行处理得到。鉴别算法hk可以是带密钥的散列函数，也可以是其他的函数。基于消息认证码的消息鉴别