密码学-散列函数技术总结.pptVIP

散列函数 一、散列函数 1、概况 2、散列函数的需求 3、生日悖论和生日攻击 4、散列函数的有效安全级别 1、散列函数 散列函数以一个变长的报文M作为输入，产生一个定长的输出（散列码）的函数，可记为 h = H(M) （ |M| |h| ) 散列函数的目的是为文件、报文或其他分组数据产生“指纹”，以保障数据的完整性； 散列函数常用于报文鉴别和数字签名； 散列函数是一个多对一的函数； 因此在理论上，必定存在不同的报文对应同样的散列，但这种情况在实际中必须不可能出现(计算上不可行) 散列函数本身不是必威体育官网网址的； 散列函数没有密钥的参与，散列值仅仅是报文的函数 2、散列函数的需求 1、H能用于任意长度的数据分组； 2、H产生定长的输出； 3、对任意给定的X，H(X)要容易计算； 4、对任何给定的h，寻找 x 使得H(x)=h，在计算上不可行（单向特性）； 5、对任意给定的分组 x，寻找不等于 x 的 y，使得 H(x)=H(y), 在计算上不可行（弱抗碰撞）； 6、寻找任意的一对分组(x，y)， 使得 H(x)=H(y)， 在计算上不可行（强抗碰撞）。 不同安全特性的比较 显然，强抗碰撞特性包含弱抗碰撞特性； 另外可以证明，强抗碰撞特性包含单向特性； 因此，散列函数满足强抗碰撞特性是充分的，安全的散列函数只需要满足强抗碰撞特性即可。 3、生日悖论 生日悖论问题 随机选 k个人，要其中至少有两个人生日相同的概率大于 0.5，问 k 的最小值是多少？ 对这个问题直观的考虑可能认为需要 k=100，但实际上可以证明：只需要 23人（k=23），他们中间至少有两人生日相同的概率就会大于0.5。这个结果比人们的直观想象要小得多，因此被称为“悖论”。 与此相对，如要求选择 K 个人，其中至少有一个人的生日和某个指定的生日相同的概率大于 0.5，问 k 的最小值是多少？（结论是 k = 365/2 ≈183） 生日攻击 生日悖论实际上是如下问题的特例：已知一个在 1 到 n 之间均匀分布的整数型随机变量，若该变量的一个 k 个取值的集合中至少有两个取值相同的概率大于 0.5，则 k 至少多大？ 该问题的一般结论是：k≈1.18 * n1/2 例如对于生日悖论，有 n=365，因此 k ≈ 22.5。 通过“生日悖论”可以引出对散列函数的生日攻击法 通过这种方法，只要对超过 n1/2 个随机元素（n 是散列函数输出集合的大小，如散列函数的输出为 m bit，则 n=2m）计算散列值，那么将有 0.5 的概率出现一个碰撞。 生日攻击可能的实施步骤 可用如下方法对散列函数进行生日攻击（假设散列函数的输出长度为 m bit）： 1）攻击者对合法报文创建 2m/2 个变种，所有这些变种本质上都和合法报文表示同样的意思； 2）同样，攻击者再对伪造报文创建 2m/2 个变种； 3）比较这两个集合，以期发现任意一对能产生相同散列值的报文对(合法报文变种、伪造报文变种)，根据生日悖论，找到这样一对报文的概率Pr 0.5； 4）攻击者向签名者出示合法报文变种，让签名者对合法报文变种的散列值签名；然后攻击者用伪造报文变种代替合法报文变种，并声称签名者对伪造报文变种签名了。由于这两个报文具有相同的散列值，因此欺骗总能成功。 生日攻击对散列函数的要求 生日攻击决定了一个仅依赖于散列值的集合大小的散列函数的必要安全条件。 它意味着安全的消息散列的长度有一个下界： 40 bit 的散列长度将非常不安全（因此仅仅在220≈100万 个随机的散列值中就有 50% 的概率发现一个碰撞）； 一般建议最小的报文散列的长度为128bit，实际中常采用160bit。 4、散列函数的有效安全级别 综上，假设散列函数的输出为 m 比特，可以将其抗各种攻击的有效安全级别表示为： 二、散列函数的结构 1、安全散列函数的一般结构； 2、 Merkle-Damgard结构； 1、安全散列算法的一般结构 现代通用的散列函数一般都是通过将一个有限定义域上的散列函数（也称为压缩函数compress），通过迭代方式延拓为具有无限定义域的散列函数； 通过这种方式构造的散列函数称为迭代散列函数。 2、Merkle-Damgard结构 这样一个迭代结构的特例是Merkle-Damgard结构。对于这个结构可以证明，如果压缩函数compress是抗碰撞的, 那么迭代函数的合成值一定也是抗碰撞的。 三、现代实用的散列函数 1、 MD5算法 2、 SHA-1算法 3、RIPEMD-160算法 1、MD5算法 MD5报文摘要算法由Ron Rivest设计 该算法与MD2, MD4算法为一个系列 算法输入是任意长度的报文分组，算法输出为 128 比特的散列值，输入是按512比特的分组进行处理的 直到最近，M