2020-07-20Algorithms5 分钟读完 (大约 697 个字)

哈希碰撞

哈希函数（hash function）就是将不同的输入映射为独一无二的固定长度的哈希值。

哈希是对输入信息的一种summarize，故而存在输出相同的情况，这种情况就称之为哈希碰撞。

hash

由于hash是压缩映射，故而必然会导致哈希碰撞。

那么如何降低哈希碰撞的概率呢？

最简单粗暴的方法就是增加哈希值的取值范围，或者说增加哈希值的长度。
但是更长的哈希值也意味着占用的存储空间和消耗的cpu时间也会随之增长。

我们在实际开发中要做的就是在消耗资源的量和安全性之间找到balance使得我们能在有很高安全性的同时尽可能使用较少的资源消耗。

生日攻击

假设哈希值是均匀分布的，那么影响哈希碰撞的因素有以下两点：

在数学中有一个生日问题，就是说假设全班有n个同学，一年365天（简化模型），那么班上有同学生日为同一天的概率有多大。

答案很出人意料。如果至少两个同学生日相同的概率不超过5%，那么这个班只能有7个人。事实上，一个23人的班级有50%的概率，至少两个同学生日相同；50人班级有97%的概率，70人的班级则是99.9%的概率。

这意味着，如果哈希值的取值空间是365，只要计算23个哈希值，就有50%的可能产生碰撞。也就是说，哈希碰撞的可能性，远比想象的高。实际上，有一个近似的公式。

$$
\sqrt{\frac{\pi}{2} N}
$$

50%的哈希碰撞概率所需要的计算次数，N表示哈希的取值空间。生日问题的 N 就是365，算出来是 23.9。

这个公式告诉我们，哈希碰撞所需耗费的计算次数，跟取值空间的平方根是一个数量级。

这种利用哈希空间不足够大，而制造碰撞的攻击方法，就被称为生日攻击（birthday attack）。

这里省略了计算过程。

$$
p(n, d) \approx 1-e^{\frac{-n(n-1)}{2 d}}
$$

const calculate = (d, n) => {
  const exponent = (-n * (n - 1)) / (2 * d)
  return 1 - Math.E ** exponent;
}