math - 使用 SHA1 的前 8 个字符时出现重复哈希的机会

Question

如果我有一个 URL 索引，并通过 SHA1 哈希的前 8 个字符对它们进行 ID，那么两个不同 URL 具有相同 ID 的概率是多少？

Answer 1

@Teepeemm 已正确回答了相关问题“给定 8 个十六进制数字的特定序列，另一个 SHA-1 哈希以相同的 8 个数字出现的可能性有多大？”这是一个非常小的数字。

然而，这个问题的关键是一个不同的问题:“给定大量的 8 位十六进制数字序列，它们中任意两个相同的可能性有多大？”正如该问题的第一条评论指出的那样，这与birthday paradox有关，这不是“房间里有人和我生日的可能性有多大？”，而是“这个房间里任何两个人生日相同的可能性有多大？”众所周知，那是 50%，只有 23 人。

hash-collision 问题本质上是同一个问题，只是从 N=365 天泛化到 N=16^8 个 8 字节序列，大约是 4.30e9。那是 ‘generalised birthday problem’ .使用此处引用的表达式 (n=sqrt(2*d*ln(1/(1-p)))，d=4.30e9 和 p=0.5，我们发现仅 77000 次试验就有 50% 的机会发生碰撞。如果绘制相应的函数，您会看到概率随着试验次数的增加而迅速增加。

即使有 16 字节的散列(所以 d=16^16)，仅经过 50 亿次试验后就有 50% 的机会发生碰撞。

生日快乐!