生日碰撞和哈希函数

背景¶

所谓哈希（hash），就是将不同的输入映射成独一无二的、固定长度的值（又称"哈希值"）。它是最常见的软件运算之一。

如果不同的输入得到了同一个哈希值，就发生了"哈希碰撞"（collision）。

生日攻击¶

哈希碰撞的概率取决于两个因素（假设哈希函数是可靠的，每个值的生成概率都相同）。

• 哈希值的长度
• 整个生命周期中，哈希值的计算次数

这个问题在数学上早有原型，叫做"生日问题"（birthday problem）：一个班级需要有多少人，才能保证每个同学的生日都不一样？

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

=>

依据泰勒展开，指数展开可以写成：

。当x取一个极小数时，上面的公式可以近似转化为。

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

将其形式化生日问题的概率公式变化为：

将取值空间用d表达，则可以形式化为：

这也就是哈希碰撞概率公式。

代码化如下：

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

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

参考文献¶

1. 阮一峰，哈希碰撞与生日攻击，2018