algorithm - 哈希什么时候发生冲突？

Question

据我了解，根据鸽巢原则，如果元素数量大于容器数量，则至少一个容器将包含不止一件元素。它是哪个容器重要吗？这如何应用于 MD5、SHA1、SHA2 哈希？

Answer 1

不，它是哪个容器并不重要，事实上这对加密散列来说并不那么重要； 远更重要的是 birthday paradox ，它表示在发现碰撞之前，您平均只需要散列 sqrt(numberNeededByPigeonHolePrincipal) 值。

因此，哈希需要足够大，搜索空间的平方根太大而无法暴力破解。 SHA1 的搜索空间平方根是 2⁸⁰，截至 2012 年 3 月，还没有发现两个具有相同 SHA1 哈希值的值(尽管我预测这将发生在未来一两年..)；与 SHA2 相同，这是一个哈希家族，它们都具有更大的搜索空间。 MD5一直是broken for a while虽然。