散列函数的目的是为文件、报文或其他分组数据 产生“指纹”，以保障数据的完整性；
散列函数常用于报文鉴别和数字签名； 散列函数是一个多对一的函数；
因此在理论上，必定存在不同的报文对应同样的散列， 但这种情况在实际中必须不可能出现(计算上不可行)
散列函数本身不是保密的；
散列函数没有密钥的参与，散列值仅仅是报文的函数
1）攻击者对合法报文创建 2m/2 个变种，所有这些变种本质上都和 合法报文表示同样的意思；
2）同样，攻击者再对伪造报文创建 2m/2 个变种； 3）比较这两个集合，以期发现任意一对能产生相同散列值的报文
对(合法报文变种、伪造报文变种)，根据生日悖论，找到这样一对 报文的概率Pr > 0.5； 4）攻击者向签名者出示合法报文变种，让签名者对合法报文变种 的散列值签名；然后攻击者用伪造报文变种代替合法报文变种， 并声称签名者对伪造报文变种签名了。由于这两个报文具有相同 的散列值，因此欺骗总能成功。
与此相对，如要求选择 K 个人，其中至少有一个人的 生日和某个指定的生日相同的概率大于 0.5，问 k 的最 小值是多少？（结论是 k >= 365/2 ≈183）
生日攻击
生日悖论实际上是如下问题的特例：已知一个在 1 到 n 之 间均匀分布的整数型随机变量，若该变量的一个 k 个取值 的集合中至少有两个取值相同的概率大于 0.5，则 k 至少 多大？ 该问题的一般结论是：k≈1.18 * n1/2 例如对于生日悖论，有 n=365，因此 k ≈ 22.5。
在计算上不可行（强抗碰撞）。
不同安全特性的比较
显然，强抗碰撞特性包含弱抗碰撞特性； 另外可以证明，强抗碰撞特性包含单向特
性； 因此，散列函数满足强抗碰撞特性是充分
的，安全的散列函数只需要满足强抗碰撞 特性即可。
3、生日悖论
生日悖论问题
随机选 k个人，要其中至少有两个人生日相同的概率大 于 0.5，问 k 的最小值是多少？ 对这个问题直观的考虑可能认为需要 k>=100，但实际 上可以证明：只需要 23人（k=23），他们中间至少有 两人生日相同的概率就会大于0.5。这个结果比人们的 直观想象要小得多，因此被称为“悖论”。
4、散列函数的有效安全级别
综上，假设散列函数的输出为 m 比特，可以将其 抗各种攻击的有效安全级别表示为：
单向
2m
弱抗碰撞
2m
强抗碰撞
2m/2
二、散列函数的结构
1、安全散列函数的一般结构； 2、 Merkle-Damgard结构；
1、安全散列算法的一般结构
现代通用的散列函数一般都是通过将一个 有限定义域上的散列函数（也称为压缩函 数compress），通过迭代方式延拓为具有 无限定义域的散列函数；
通过“生日悖论”可以引出对散列函数的生日攻击法 通过这种方法，只要对超过 n1/2 个随机元素（n 是散列 函数输出集合的大小，如散列函数的输出为 m bit，则 n=2m）计算散列值，那么将有 0.5 的概率出现一个碰 撞。
生日攻击可能的实施步骤
可用如下方法对散列函数进行生日攻击（假设散列函数的 输出长度为 m bit）：
MD5算法概况图
MD5算法步骤
1、填充报文，使报文长度(比特数)模512等于 448(即填充长度为512的整倍数减去64)
填充比特的最高位为1，其余各位均为0
2、将用64比特表示的初始报文长度附加在步骤1 的结果后，这样填充后的报文长度为512比特的 整倍数
3、初始化由4个32比特寄存器(A,B,C,D)构成的 MD缓存(共128比特)，该缓存用来存放MD5的中 间及最终结果
通过这种方式构造的散列函数称为迭代散 列函数。
2、Merkle-Damgard结构
这样一个迭代结构的特例是Merkle-Damgard结构。对于 这个结构可以证明，如果压缩函数compress是抗碰撞的, 那V0=IV CVi = f(CVi-1, Yi-1) H(M) = CVL
A = 67452301
B = EFCDAB89
C = 98BADCFE
D = 10325476
MD5算法步骤
4、处理512比特(16个字)的报文分组序列
三、现代实用的散列函数
1、 MD5算法 2、 SHA-1算法 3、RIPEMD-160算法
1、MD5算法
MD5报文摘要算法由Ron Rivest设计 该算法与MD2, MD4算法为一个系列 算法输入是任意长度的报文分组，算法输
出为 128 比特的散列值，输入是按512比特 的分组进行处理的 直到最近，MD5算法是使用最为广泛的安 全散列算法 该算法也是Internet 标准 （ RFC 1321）
散列函数
Last Modified: 2008.04
一、散列函数
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)，
生日攻击对散列函数的要求
生日攻击决定了一个仅依赖于散列值的集 合大小的散列函数的必要安全条件。
它意味着安全的消息散列的长度有一个 下界：
40 bit 的散列长度将非常不安全（因此仅仅在 220≈100万 个随机的散列值中就有 50% 的概 率发现一个碰撞）；
一般建议最小的报文散列的长度为128bit，实 际中常采用160bit。