简介
Hash函数也叫杂凑函数、散列函数、哈希函数，可以把消息或数据压缩成固定长度的摘要
性质
- 等长性：给出任意的输入，得到的输出（摘要）长度不变。比如sha-1得到的摘要固定是160位，md5为128位
- 单向性：任给x，得到 y = h ( x ) y=h(x) y=h(x)是容易的，任给 y = h ( x ) y=h(x) y=h(x)，得到x是困难的
- 抗弱碰撞性：已知x，找到不与x相等的y满足 h ( x ) = h ( y ) h(x)=h(y) h(x)=h(y)是不可行的
- 抗强碰撞性：找到任意两个不同的输入 x ， y x，y x，y使得 h ( x ) = h ( y ) h(x)=h(y) h(x)=h(y)是不可行的
哈希碰撞
- 根据抗碰撞性，不会有两个不同的输入，使得哈希运算后的输出相等
- 如果找到反例，比如上图中John和Sandra的输出相等，则称产生了哈希碰撞
空间分析
16个二进制位的哈希值，产生碰撞的可能性是 65536 分之一。也就是说，如果有65537个用户，就一定会产生碰撞。哈希值的长度扩大到32个二进制位，碰撞的可能性就会下降到 4,294,967,296 分之一。
生日悖论
在一个房间中，如果有23人，则存在两个人的生日相同的概率要大于50%。这个“悖论”并非是逻辑中的悖论，而是与直观感觉相悖，因此被称为生日悖论。当人数增加时，该概率也会增加。若人数为50，则存在两个人的生日相同的概率要大于97%。
n个人中，每个人的生日日期都不同的概率：
p ˉ ( n ) = 1 ⋅ ( 1 − 1 365 ) ⋅ ( 1 − 2 365 ) ⋯ ( 1 − n − 1 365 ) = 365 365 ⋅ 364 365 ⋅ 363 365 ⋅ 362 365 ⋯ 365 − n + 1 365 {\bar {p}}(n)=1\cdot \left(1-{\frac {1}{365}}\right)\cdot \left(1-{\frac {2}{365}}\right)\cdots \left(1-{\frac {n-1}{365}}\right)={\frac {365}{365}}\cdot {\frac {364}{365}}\cdot {\frac {363}{365}}\cdot {\frac {362}{365}}\cdots {\frac {365-n+1}{365}} pˉ(n)=1⋅(1−3651)⋅(1−3652)⋯(1−365n−1)=365365⋅365364⋅365363⋅365362⋯365365−n+1
p(n）表示n个人中至少2人生日相同的概率
p ( n ) = 1 − p ˉ ( n ) = 1 − 365 ! 36 5 n ( 365 − n ) ! p(n)=1-{\bar {p}}(n)=1-{365! \over 365^{n}(365-n)!} p(n)=1−pˉ(n)=1−365n(365−n)!365!
哈希碰撞
- 因此，由上可知，如果哈希值的取值空间是365，只要计算23个哈希值，就有50%的可能产生碰撞
- 为了防止哈希碰撞，需要增大哈希映射的空间
