哈希冲突 - 机会有多大? [英] Hash Collision - what are the chances?

问题描述

我的 PHP 网站上有一些代码可以创建一个随机散列(使用 sha1())，我用它来匹配数据库中的记录.

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.

推荐答案

如果您假设 SHA-1 做得很好，您可以得出结论，两条给定消息具有相同哈希值的几率为 2^160 分之一(因为 SHA-1 会产生一个 160 位的哈希值).

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 是一个大得离谱的数字.大约是 10^48.即使您的数据库中有 100 万个条目，新条目共享相同哈希的几率仍然是 10^42 分之一.

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 已被证明相当不错，所以我认为您根本不需要担心冲突.

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

附带说明，当您使用 SHA-1 时，请使用 PHP 的 raw_output 功能，因为这会导致字符串更短，从而使您的数据库操作速度更快.

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.

为了解决生日悖论，一个包含 10^18(一百万)条目的数据库有大约 0.0000000000003 中的 1 次碰撞机会.真的不值得担心.

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屋！