8Hash函数与数字摘要071025.ppt

1、2020/7/22,李辉 副教授,Hash函数与数字摘要,Ray ,2020/7/22,6. Hash函数和数字摘要,内 容,数字摘要 Hash函数 冲突 生日悖论 Chaum-van Heijst-Pfitzmann Hash Function 扩展hash函数 MD5 时戳,2020/7/22,6. Hash函数和数字摘要,数字摘要,数字签名的实施问题 签名比原文长 分割 长度问题 速度问题 完整性问题,2020/7/22,6. Hash函数和数字摘要,数字摘要和Hash函数,2020/7/22,6. Hash函数和数字摘要,Hash函数,Hash函数适用任意信息长度 产生的摘要是定长的

2、易于计算 通过摘要得到原信息计算上不可行 无冲突,2020/7/22,6. Hash函数和数字摘要,弱无冲突与强无冲突,弱无冲突（weakly collision-free） 给定消息x，如果寻找一个xx，使得h(x)=h(x)在计算上不可行，相应的hash函数h(x)是弱无冲突的。 强无冲突（strongly collision-free） 寻找一对消息xx，使得h(x)=h(x)在计算上不可行，相应的hash函数h(x)是强无冲突的。 ONE-WAY 称Hash函数是ONE-WAY FUNCTION: 给定摘要z，如果寻找一个消息x使h(x)=z计算上不可行。,2020/7/22,6. H

3、ash函数和数字摘要,生日悖论,生日悖论： 随机选取23人作为一组，则至少两人同生日的概率是1/2. k个球扔进n个篮子,2020/7/22,6. Hash函数和数字摘要,2020/7/22,6. Hash函数和数字摘要,Hash攻击,40位的数字摘要足够安全 建议采用128位以上的数字摘要 DSS采用160位的数字摘要,2020/7/22,6. Hash函数和数字摘要,Chaum-van Heijst-Pfitzmann Hash Function,2020/7/22,6. Hash函数和数字摘要,MD5,MD算法由Ron Rivest提出(the “R” in RSA) 信息任意长度，摘要

4、128位。 MD5由MD4修改得到。,2020/7/22,6. Hash函数和数字摘要,1. 补,目标长度448 mod 512 . 即：差64位成为512的整倍数。 即使原始信息长度符合该要求，仍要补。 补丁包括1个1，剩下全是0.,2020/7/22,6. Hash函数和数字摘要,2. 追加长度标识,补前长度由64位表示，被追加到已补的信息后。 如果信息长度超过 264, 只使用低64位。 追加长度标识后，信息总长是512的倍数。,2020/7/22,6. Hash函数和数字摘要,3. 初始化MD缓冲区,128位缓冲区用于接受hash函数中间结果和最终结果。 将缓冲区分成4等份，即4个32

5、位寄存器 (A,B,C,D)，也即4个字。 赋初值: A: 01 23 45 67 B: 89 AB CD EF C: FE DC BA 98 D: 76 54 32 10,2020/7/22,6. Hash函数和数字摘要,Message,1000,message length,L 512 bits,Block0,.,.,512 bits,Block1,Blockn,BlockL-1,HMD5,HMD5,HMD5,HMD5,512,MD buffer0,128,128-bit digest,MD buffer1,MD buffern,MD bufferL-1,HMD5 = 4回合压缩算法,20

6、20/7/22,6. Hash函数和数字摘要,4. 数据处理,消息分512位的块进行处理。 每一块进行 4回合的压缩处理，结果是128位。 最后得到的128位就是128位的摘要。,2020/7/22,6. Hash函数和数字摘要,Buffer q +1,Block q,512,A,B,C,D,+,+,+,+,32,128,Buffer q,128,第一回合,第二回合,第三回合,第四回合,2020/7/22,6. Hash函数和数字摘要,A,B,C,D,+,+,+,+,g,Xk,Ti,CLSs,A,B,C,D,2020/7/22,6. Hash函数和数字摘要,g：基本函数，每一回合对应一个基本函

7、数。 Xk =512位块中第k个32位字。 Ti = 232 abs(sin(i) 第一回合 g(b,c,d) = (b AND c) OR (NOT b AND d) k = 0.15 i = 1.16 第二回合 g(b,c,d) = (b AND d) OR (c AND NOT d) k = (1 + 5j)mod 16 where j = 116 i = 1732,2020/7/22,6. Hash函数和数字摘要,第三回合 g(b,c,d) = b XOR c XOR d k = (5 + 3j)mod 16 where j = 116 i = 3348 第四回合 g(b,c,d) = c XOR (b OR NOT d) k = 7j mod 16 where j = 116 i = 496