哈希碰撞 - 有什么机会？

我在我的PHP驱动的站点上有一些代码创建一个随机哈希(使用sha1()),我用它来匹配数据库中的记录.

发生碰撞的几率是多少？我应该生成哈希,然后首先检查它是否在数据库中(我宁愿避免额外的查询)或自动插入它,基于它可能不会与另一个冲突的概率.

1> Artelius..：

---

如果您认为SHA-1做得很好,您可以得出结论,两个给定消息具有相同的散列(由于SHA-1产生160位散列),因此存在1 ^ 2 ^ 160的可能性.

2 ^ 160是一个非常大的数字.它大概是10 ^ 48.即使您的数据库中有一百万个条目,新的条目共享相同的哈希值的可能性仍为1/10.

事实证明SHA-1相当不错,所以我认为你根本不需要担心碰撞.

作为旁注,在使用SHA-1时使用PHP的raw_output功能,因为这会导致更短的字符串,因此会使您的数据库操作更快一些.

编辑:为了解决生日悖论,一个包含10 ^ 18(百万亿)条目的数据库有可能在0.0000000000003的碰撞中大约1.真的不值得担心.

---

对于那些真正相信碰撞自由的人,请记住生日效应.你的第一次碰撞比你想象的更容易发生.所以要小心吧

---

@Seun:不,那是完全错的.了解生日悖论.

---

在第一次2 ^ 80次哈希之后,第一次碰撞有50%的几率发生.

---

但是当发生冲突时.你能想象试图调试问题!

2> David Schmit..：

---

使用对称加密方案和专用服务器密钥在将ID(和其他值)发送到客户端并在接收时再次解密时对其进行加密.请注意您的加密功能提供机密性和完整性检查.

这使您可以在与DB进行通信时使用合理的值而不会发生任何冲突,在与客户端交谈时具有极高的安全性,并且降低了在日常WWF上降落大约2 ^ 160的可能性.

另见敲钉子:旧鞋子或玻璃瓶？!

3> nickf..：

---

为什么不做一些保证不会发生冲突的事情,以及确保没有人可以改变GET参数来查看它们不应该的东西:使用salt,组合id和它的哈希.

$salt = "salty";
$key = sha1($salt . $id) . "-" . $id;
// 0c9ab85f8f9670a5ef2ac76beae296f47427a60a-5

即使你不小心偶然发现两个具有完全相同的sha1哈希(用你的盐)的数字,那么$ key仍然会有所不同,你将避免所有的冲突.

4> Martin v. Lö..：

---

如果使用数字增加的ID作为输入,那么SHA-1将碰撞的几率几乎为零.

如果ID是唯一的输入,那么SHA-1似乎有点过分 - 从32位整数产生160位散列.我宁愿使用模幂运算,例如选择一个大的(32位)素数p,计算该组的模块生成器g,然后使用g ^ id.这将保证无冲突,并且只能提供32位"哈希".

---

然后只生成160个随机位将是足够独特的 - 不需要生成任何东西的散列(它不会通过散列变得更加独特,也不会变得更随机).