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

如果我有一个URL索引，并用SHA1哈希的前8个字符标识它们，那么两个不同的URL具有相同ID的可能性是多少？

最佳答案

@Teepeemm正确回答了相关问题“给定一个特定的8位十六进制数字序列，又有一个SHA-1哈希值出现相同8位数字的机会是多少？”这是一个很小的数字。

不过，这个问题的关键是另一个问题:“考虑到大量的8位十六进制序列，它们中的任何两个相同的机会是什么？”正如对该问题的第一条评论所指出的那样，这与birthday paradox有关，这不是“房间中某人与我生日相同的机会是多少？”，而是“房间中任何两个人具有相同生日的机会是什么？”众所周知，只有23人，发生这种情况的几率是50％。

哈希冲突问题本质上是相同的问题，但是从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％。

生日快乐!

关于math - 使用SHA1的前8个字符时出现重复哈希的机会，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30561096/