第17讲hash函数.

《第17讲hash函数.》由会员分享，可在线阅读，更多相关《第17讲hash函数.（50页珍藏版）》请在金锄头文库上搜索。

1、第8章 Hash 函数,Hash函数定义,数据安全 机密性 完整性 认证性 密码技术主要保证数据的机密性 Hash函数能保证数据的完整性和认证性,Hash函数定义,Hash函数常用来构造数据的短“指纹”：消息的发送者使用所有的消息产生一个附件也就是短“指纹”，并将该短“指纹”与消息一起传输给接收者。 即使数据存储在不安全的地方，接收者重新计算数据的指纹，并验证指纹是否改变，就能够检测数据的完整性。这是因为一旦数据在中途被破坏，或改变，短指纹就不再正确。,Hash函数定义,Hash函数定义：Hash函数是一个将任意长度的消息（message）映射成固定长度消息的函数。 Hash函数是一个函数，它

2、以一个变长的报文作为输入，并产生一个定长的散列码，有时也称为报文摘要，作为函数的输出。 Hash函数（hash function），或称为哈希函数、散列函数。对于任何消息x ，将h(x)称为x的Hash值、散列值、消息摘要（message digest）。,Hash函数作用,Hash函数最主要的作用于是用于鉴别，鉴别在网络安全中起到举足轻重的地位。鉴别的目的有以下两个：第一，验证信息的发送者是真正的，而不是冒充的，同时发信息者也不能抵赖，此为信源识别；第二，验证信息完整性，在传递或存储过程中未被篡改，重放或延迟等。,8.1Hash 函数的性质,Hash函数的碰撞（collision） 设x、x

3、是两个不同的消息，如果 h(x)=h(x) 则称x和x是Hash函数h的一个（对）碰撞.,8. 1 Hash 函数的性质,Hash函数的分类 单向Hash函数（oneway） 给定一个Hash值y，如果寻找一个消息x，使得y=h (x)是计算上不可行的，则称h是单向Hash函数. 弱抗碰撞Hash函数（weakly collisionfree） 任给一个消息x，如果寻找另一个不同的消息x，使得h(x) =h(x)是计算上不可行的，则称h是弱抗碰撞Hash函数. 强抗碰撞Hash函数 （strongly collisionfree） 如果寻找两个不同的消息x和x，使得h(x)=h(x)是计算上不

4、可行的，则称h是强抗碰撞Hash函数.,8. 1 Hash 函数的性质,hash函数在现代密码学中起着重要的作用，主要用于对数据完整性和消息认证 压缩性：任意长度的数据，算出的摘要长度都固定。 容易计算：从原数据容易算出摘要。 抗修改性：对原数据进行任何改动，哪怕只修改1个字节，所得到的摘要都有很大区别。 弱抗碰撞：已知原数据和其摘要，想找到一个具有相同摘要的数据（即伪造数据），在计算上是困难的。 强抗碰撞：想找到两个不同的数据，使它们具有相同的摘要，在计算上是困难的。,Hash函数的安全性,对Hash函数的攻击是指寻找一对碰撞消息的过程 与传统密码体制的攻击方式相比，对散列函数的攻击方法主要

5、有两种： 穷举攻击：它可以用于任何类型的散列函数的攻击，最典型的方式就是所谓的“生日攻击”。采用生日攻击的攻击者将产生许多明文消息，然后计算这些明文消息的指纹（摘要），进行比较。 利用散列函数的代数结构：攻击其函数的弱性质。通常的有中间相遇攻击、修正分组攻击和差分分析攻击等。,生日悖论（birthday paradox） 生日问题：假设每个人的生日是等概率的，每年有365天，在k个人中至少有两个人的生日相同的概率大于1/2，问k最小应是多少？ k人生日都不同的概率是：,有P(365,23)=0.5073。即在23个人中，至少有两个人生日相同的概率大于0.5，这个数字比人们直观猜测的结果小得多，

6、因而称为生日悖论。,生日攻击法 生日悖论原理可以用于构造对Hash函数的攻击 设Hash函数值有n个比特，m是真消息，M是伪造的假消息，分别把消息m和M表示成r和R个变形的消息。消息与其变形消息具有不同的形式，但有相同的含义。将消息表示成变形消息的方法很多，例如增加空格、使用缩写、使用意义相同的单词、去掉不必要的单词等。,Hash函数的安全性,Hash函数的安全性,生日攻击法 分别把消息m和M表示成r和R个变形的消息,生日攻击法 计算真消息m的变形与假消息M的变形发生碰撞的概率 由于n比特长的散列值共有2n个，所以对于给定m的变形mi和M的变形Mj，mi与Mj不碰撞的概率是1-1/2n。由于M

7、共有R个变形，所以M的全部变形都不与mi碰撞的概率是：,Hash函数的安全性,因为消息m共有r个变形，因此m的变形与M的变形都不碰撞的概率是：,m的变形与M的变形发生碰撞的概率是：,生日攻击法,当r=R=2n/2时，P(n)=1e10.63。对于Hash值长度为64比特的Hash函数，生日攻击的时间复杂度约为232，所以是不安全的。,为了抵抗生日攻击，建议Hash值长度至少为128 比特.,Hash函数的安全性,8. 2 基于分组密码的Hash 函数,8.3 hash函数MD4,MD4是麻省理工学院教授Ronald Rivest于1990年设计的一种信息摘要算法。它是一种用来测试信息完整性的密

8、码散列函数的实行。其摘要长度为128位。这个算法影响了后来的算法如MD5、SHA 家族和RIPEMD等。 MD5算法是1991年发布的一项数字签名加密算法，它当时解决了MD4算法的安全性缺陷，成为应用非常广泛的一种算法。,8.3 hash函数MD4,MD4算法的输入可以是任意长度的消息x，对输入消息按512位的分组为单位进行处理，输出128位的散列值MD(x)。整个算法分为五个步骤。 步骤1: 增加填充位 步骤2: 附加消息长度值 步骤3: 初始化MD缓冲区 步骤4: 以512位的分组(16个字)为单位处理消息 步骤5: 输出,消息的预处理步骤：,设x 是一个消息, 用二进制表示。首先由x 生

9、成一个数组,是长度为32 比特(bit)的(0,1) 序列,M 由x 生成：,d = (447 -|x|)mod 512,令l 为 的二进制表示。 l 的长度为64 比特(bit)。 如果l 的长度不足64 比特(bit), 则在l 的左端添0 补足,M =,这里|x|表示x 的长度, |表示序列的联接, 譬如x|y 表示将序列y 排在序列x 的右端。,步骤1: 增加填充位 在消息x右边增加若干比特，使其长度与448模512同余。也就是说，填充后的消息长度比512的某个倍数少64位。 即使消息本身已经满足上述长度要求，仍然需要进行填充。 例如，若消息长为448，则仍需要填充512位使其长度为9

10、60位。填充位数在1到512之间。填充比特的第一位是1，其它均为0。,步骤2: 附加消息长度值,用64位表示原始消息x的长度，并将其附加在步骤1所得结果之后。若填充前消息长度大于等于264，则使用其64位。填充方法是把64比特的长度分成两个32比特的字，低32比特字先填充，高32比特字后填充。,步骤1与步骤2一起称为消息的预处理 经预处理后，原消息长度变为512的倍数 设原消息x经预处理后变为消息 Y=Y0 Y1 YN1， 其中Yi（i =0,1,N1）是32比特 在后面的步骤中，将对512比特的分组Yi进行处理,例8.1 假设消息为: x=“abcde”=01100001 01100010

11、01100011 01100100 01100101=(61 62 63 64 65)16, |x|=40=(28)16. 步骤1在x的右边填充1个“1”和407个“0”，将x变成448比特的x1: x1= x | 1 | 0 (407个) = x | 800000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000. =61626364 65800000 00000000 00000000 00000000 00000000 00

12、000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000.,例8.1 假设消息为: x=“abcde”=01100001 01100010 01100011 01100100 01100101=(61 62 63 64 65)16, |x|=40=(28)16. 经步骤2处理后的比特串为（16进制表示）： x2=x1|28(64位) =61626364 65800000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

13、00000000 00000000 00000000 00000000 28000000 00000000.,步骤3: 初始化MD缓冲区 MD4算法的中间结果和最终结果都保存在128位的缓冲区里，缓冲区用4个32位的寄存器表示。 4个缓冲区记为A、B、C、D，其初始值为下列32位整数（16进制表示）： A=67 45 23 01, B=EF CD AB 89, C=98 BA DC FE, D=10 32 54 76. 上述初始值以小端格式存储(字的最低有效字节存储在低地址位置 )为： 字A=01 23 45 67, 字B=89 AB CD EF, 字C=FE DC BA 98, 字D=76

14、54 32 10.,步骤4: 以512位的分组(16个字)为单位处理消息 MD4是迭代Hash函数, 其压缩函数为:,步骤4是MD4算法的主循环，它以512比特作为分组，重复应用压缩函数HMD4，从消息Y的第一个分组Y0开始，依次对每16个分组Yi进行压缩，直至最后分组N/16-1，然后输出消息x的Hash值。可见，MD4的循环次数等于消息Y中512比特分组的数目L。,步骤5: 输出 依次对消息的L个512比特的分组进行处理，第L个分组处理后的输出值即是消息x的散列值MD(x)。,8. 3 Hash函数MD4,MD4 算法如下,设A、B、C、D 是四个32 位的寄存器, 其初值(用十六进制表示

15、) 分别为 A=67452301、B =efcdab89、C =98badcfe、D=10325476:,对i = 0 至N/16 - 1 执行第3 步至第8 步,对j = 0 至15 执行Xj = M16i + j ,将寄存器A、B、C、D 中的值存储到另外四个寄存器AA、BB、CC、DD 中, AA = A， BB = B， CC = C，DD = D, 执行Round1, 执行Round2, 执行Round3,A = A + AA，B = B + BB，C = C + CC， D = D + DD,8.4安全Hash算法SHA,安全Hash算法SHA（secure hash algori

16、thm）由美国标准与技术研究所（NIST）设计并于1993年作为联邦信息处理标准（FIPS 180）发布 修改版于1995年发布（FIPS 1801），通常称之为SHA1。该标准称为安全Hash函数。 RFC 3174也给出了SHA1，它基本上是复制FIPS 1801的内容，但增加了C代码实现。 SHA1算法的输入是长度小于264的任意消息x，输出160位的散列值。,8.4安全Hash算法SHA,SHA1处理消息的过程与MD4类似，对输入消息按512位的分组为单位进行处理，整个算法分为五个步骤 步骤1: 增加填充位 在消息右边增加若干比特，使其长度与448模512同余。即使消息本身已经满足上述长度要求，仍然需要进行填充。填充位数在1到512之间。填充比特的第一位是“1”，其它均为“0”。,8.4安全Hash算法SHA,步骤2: 附加消息长度值 用64位表示原始消息x的长度，并将其附加在步骤1所得结果之后。