一、概念

将任意长度的输入变换为固定长度的输出的不可逆的单向密码体制。

Hash函数H将可变长度的数据块M作为输入，产生固定长度的Hash值：h = H(M)。其中h是定长的散列值，H是哈希函数，M是一个变长消息。

称M是h的原像。因为H是多对一的映射，所以对于任意给定的Hash值h，对应有多个原像。如果满足x≠y且H(x)=H(y)，则称为碰撞。

Hash函数在数字签名和消息完整性检测等方面有着广泛的应用。Hash函数同时是一种具有压缩特性的单向函数，其像通常称为数字指纹，消息摘要或散列值。

散列函数主要用于消息认证和数字签名，因此需要具备以下特性：

性质2是哈希函数的基本特性，性质3是哈希函数的可用性，性质4，5，6是哈希函数为满足不同应用而需具备的基本安全性质。

弱Hash函数：只满足以上前五个要求的Hash函数。

强Hash函数：满足以上前六个要求的Hash函数。

强Hash函数能够保证免受以下攻击：假设Bob写一条借据消息并发送给Alice，Alice在借据上签名认可。Bob如果能找到两条消息具有同样的Hash值，其中一个借据消息要求Alice归还金额较小，另一个金额很大，那么让Alice签下第一个小额借据后，Bob就能声称第二个借据是真实的（将Alice在第一个借据的签名附到第二个借据中）。

下图展示了抗原像攻击、抗弱碰撞攻击和抗强碰撞攻击三者之间的关系

在传统观念中并没有把伪随机性作为密码学Hash函数的安全性需求，但在实际应用中或多或少有所要求。密码学Hash函数通常用于密钥产生、伪随机数发生器以及消息完整性应用，上述三个应用都要求Hash函数的输出是随机的。

二、对Hash函数的攻击

　　1、穷举攻击

　　a) 原像攻击和第二原像攻击

　　攻击者对给定的Hash值h，试图找到满足H(y) = h的y。穷举攻击的方法是随机选择y，尝试计算其Hash值知道碰撞出现。对于m位的Hash值，穷举的规模大约是2的m次方,对于攻击者平均尝试次数为2的m-1次方，才能找到一个满足H(y)=h的y值。

　　b) 碰撞攻击

　　对于碰撞攻击，攻击者试图找到两个消息或数据块x和y，满足H(x)=H(y)，与原像攻击和第二原像攻击相比，其穷举的规模相对更小一些，这也通过数学上的生日悖论得到印证。本质上，如果我们在均匀分布的0到N-1的范围内选择随机整数变量，那么在N的1/2次方 次选择后发生重复的概率就会超过0.5。因此，对于m位的Hash值，如果我们随机选择数据块，预计在2的m/2次方 次尝试后就能找到两个具有相同Hash值的数据块。

　　Yuval提出以下策略进行碰撞攻击：

　　2、密码分析

　　对Hash函数的密码分析攻击，也是利用算法的某种性质而不是通过穷举来进行攻击的。理想的Hash函数算法要求密码分析攻击所需的代价大于或等于穷举攻击所需的代价。

三、哈希算法