当散列时，较长的消息是否有更高的碰撞几率？

Question

在讨论最大密码长度时，一位海报发表了以下评论：

允许的输入越长，就越容易提供可能导致哈希冲突的输入。

为了解释这一点(因为缺乏上下文可能会使声明不明确)，海报上说，如果密码长度较长，则更容易找到哈希冲突。我以前没听说过，现在我很好奇。我自己(无可否认)的期望是，碰撞概率应该与消息大小相当独立，因为碰撞发生在摘要空间，并且摘要长度是固定的。

我漏掉了什么拼图？找到碰撞的容易程度取决于输入长度吗？

Answer 1

我漏掉了什么拼图？找到碰撞的容易程度取决于输入长度吗？

为了找到冲突，不相关字符串的长度(除了计算散列所需的时间--实际上长字符串的时间更长)，而是您尝试了多少不同的字符串。因为有越多不同的输入，就越有可能导致相同的(固定长度)哈希值，即冲突。与短字符串相比，有更多不同的长字符串。

例如:有10^3 =1000个带有3位数的字符串，但是已经有10^6 = 1000000个字符串和6位数。如果您想象一个由4位组成的散列，那么可能会与3位字符串发生冲突，但是在6位字符串中肯定会有很多冲突，因为字符串值比散列值多得多。

允许的输入越长，就越容易提供可能导致哈希冲突的输入。

你引用的陈述在目前的形式中是错误的。的确，你找到的字符串很长的机会更高。但是，由于有比短字符串更长的字符串，这并不能使找到冲突变得更加容易。同样，重要的是不同输入的数量，而不是长度。

Answer 2

我认为这篇评论的海报所指的是：

随着输入空间的大小(所有可能的输入字符串)的增加，当耗尽空间时发现冲突的概率增加，当输入空间的大小大于所有可能的散列值的大小时，则最终达到100%。

示例：

假设一个32位行为良好的散列函数。如果只允许字符串"0“和"1”作为输入，则哈希冲突的概率很低，因为输入值(2)的数量远远小于哈希值的数量(2^32 = 4,294,967,296)。碰撞的几率实际上是1/ 2^32。

但是，如果您允许所有可能的字符串恰好是8个小写字母字符，则可以保证最终找到一个散列冲突，因为现在有26^8 = 208,827,064,576输入值，这比2^32大得多。

编辑:我想把这个作为评论发布，但还不能评论.