哈希碰撞 - 有什么机会？ [英] Hash Collision - what are the chances?

问题描述

我在PHP网站上有一些代码来创建随机哈希（使用 sha1（）），我用它来匹配数据库中的记录。

有什么碰撞的机会？我应该生成哈希值，然后检查它是否在数据库中（我宁愿避免额外的查询），或者根据其可能不会与另一个冲突的概率自动插入。

解决方案

如果你假设SHA-1做得很好，你可以得出结论，两个给定的消息具有相同的散列（因为SHA-1产生160位散列）。

2 ^ 160是一个可笑的数字。大概是10 ^ 48。即使你的数据库中有一百万条记录，这仍然是一个10 ^ 42的机会，一个新条目将共享相同的哈希。

SHA-1已经证明相当不错，所以我不认为你需要担心碰撞。

作为一个附注，使用PHP的 raw_output 当您使用SHA-1时，功能将导致较短的字符串，从而使您的数据库操作更快。

编辑：为了解决生日悖论，a数据库与10 ^ 18（一百万万）条目有机会约1在0.0000000000003的碰撞。 不要担心。

I have some code on my PHP powered site that creates a random hash (using sha1()) and I use it to match records in the database.

What are the chances of a collision? Should I generate the hash, then check first if it's in the database (I'd rather avoid an extra query) or automatically insert it, based on the probability that it probably won't collide with another.

解决方案

If you assume that SHA-1 does a good job, you can conclude that there's a 1 in 2^160 chance that two given messages have the same hash (since SHA-1 produces a 160-bit hash).

2^160 is a ridiculously large number. It's roughly 10^48. Even if you have a million entries in your database, that's still a 1 in 10^42 chance that a new entry will share the same hash.

SHA-1 has proved to be fairly good, so I don't think you need to worry about collisions at all.

As a side note, use PHP's raw_output feature when you use SHA-1 as this will lead to a shorter string and hence will make your database operations a bit faster.

EDIT: To address the birthday paradox, a database with 10^18 (a million million million) entries has a chance of about 1 in 0.0000000000003 of a collision. Really not worth worrying about.

这篇关于哈希碰撞 - 有什么机会？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！