计算160位的哈希冲突

Question

假设哈希函数产生160位的摘要。我们需要散列多少消息才能以大约75%的概率获得冲突？

感谢您的帮助:)

Answer 1

经验法则是，在绘制sqrt(n)数字后，有50%的机会发生冲突。这个数字略高于这个数字，但平方根是一个很好的指导原则。因此，在您的情况下，在2^80次尝试后有50%的机会发生冲突。

另一条经验法则是，在4*sqrt(n)之后，您获得复制的可能性几乎是确定的。

根据https://en.wikipedia.org/wiki/Birthday_problem#Probability_of_a_shared_birthday_(collision)，您可以通过以下方法计算需要绘制的值的数量n，以获得副本的概率p：

n = sqrt(2 * d * ln(1/(1-p)))

其中ln是自然对数，p是从0到1.0的概率。

所以在你的例子中：

n = sqrt(2 * 2^160 * ln(1/.25))
n = sqrt(2^161 * 1.38629)

小于2^81的值。

Answer 2

在2 septillion范围内的某个位置。这是2,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000条消息。这是方程式。

chance of collision = 1 - e^(-n^2 / (2 * d))

其中n是消息的数量，d是可能的数量。因此，如果d是2^160，那么n将位于2^80.7附近。