使用 SHA1 的前 8 个字符时重复散列的机会
Chance of a duplicate hash when using first 8 characters of SHA1
如果我有一个 URL 索引，并通过 SHA1 哈希的前 8 个字符对它们进行标识，那么两个不同的 URL 具有相同 ID 的概率是多少？
SHA-1 哈希有 40 个 base-16 数字。如果您只查看其中的前 8 个数字，那么第二个 url 具有相同 8 位数字的可能性是 (1/16)^8 ~ 2.32e-10。实际上，这并不取决于有 40 位数字开头，甚至不取决于它是 SHA-1。您需要的唯一假设是 SHA-1 的前 8 位数字独立且分布相同。
@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% 的几率发生冲突。
生日快乐！
如果我有一个 URL 索引，并通过 SHA1 哈希的前 8 个字符对它们进行标识，那么两个不同的 URL 具有相同 ID 的概率是多少？
SHA-1 哈希有 40 个 base-16 数字。如果您只查看其中的前 8 个数字，那么第二个 url 具有相同 8 位数字的可能性是 (1/16)^8 ~ 2.32e-10。实际上，这并不取决于有 40 位数字开头，甚至不取决于它是 SHA-1。您需要的唯一假设是 SHA-1 的前 8 位数字独立且分布相同。
@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% 的几率发生冲突。
生日快乐！