这个问题在这里已有答案：
给定两个不同的字符串S1和S2（S1！= S2）可能是：
SHA1(S1) == SHA1(S2)
是真的？
-
如果是 - 概率是多少？
-
如果没有 - 为什么不呢？
-
输入字符串的长度是否有上限，获取重复的概率是0？ OR是SHA1的计算（因此重复的概率），与字符串的长度无关？
我想要实现的目标是散列一些敏感的ID字符串（可能与其他字段（如父ID）连接在一起），这样我就可以使用散列值作为ID（例如在数据库中） .
例：
Resource ID: X123
Parent ID: P123
我不想公开我的资源标识的性质，以允许客户端看到“X123-P123” .
相反，我想创建一个新的列散列（“X123-P123”），让我们说它是AAAZZZ . 然后客户端可以请求ID为AAAZZZ的资源，而不知道我的内部id等 .
5 回答
你描述的是一种碰撞 . 冲突必然存在，因为SHA-1接受更多不同的消息作为输入，它可以产生不同的输出（SHA-1可以吃任何比特串，最多2 ^ 64位，但输出只有160位;因此，至少一个输出值必须弹出几次） . 无论函数是否为"good"哈希函数，此观察对输出小于其输入的任何函数都有效 .
假设SHA-1的行为类似于"random oracle"（一个基本上返回随机值的概念对象，唯一的限制是一旦它在输入m上返回输出v，它必须总是在输入m上返回v），然后是碰撞的概率，对于任何两个不同的字符串S1和S2，应该是2 ^（ - 160） . 仍然假设SHA-1表现得像一个随机的oracle，如果你收集了很多输入字符串，那么你应该在收集了大约2 ^ 80个这样的字符串之后开始观察碰撞 .
（那是2 ^ 80而不是2 ^ 160，因为有2 ^ 80个字符串，你可以制作大约2 ^ 159对字符串 . 这通常被称为"birthday paradox"，因为当生日应用于碰撞时，它对大多数人来说是一个惊喜 . 有关此主题，请参阅the Wikipedia page . ）
现在我们强烈怀疑SHA-1并不像一个随机的oracle，因为生日悖论方法是随机预言的最佳碰撞搜索算法 . 然而，已发布的攻击应该在大约2 ^ 63步中发现碰撞，因此比生日悖论算法快2 ^ 17 = 131072倍 . 在真正的随机预言中，这样的攻击不应该是可行的 . 请注意，这次攻击尚未实际完成，它仍然是理论上的（有些人tried but apparently could not find enough CPU power）（截至2017年初，有人用上述方法计算了SHA-1 collision，并且它的工作方式与预测完全相同） . 然而，理论看起来很 Health ，而且看来SHA-1似乎不是一个随机的神谕 . 相应地，关于碰撞的概率，所有的赌注都是关闭的 .
至于你的第三个问题：对于具有n位输出的函数，如果你可以输入超过2 ^ n个不同的消息，即如果最大输入消息长度大于n，则必然存在冲突 . 如果m小于n，则答案并不容易 . 如果函数表现为随机预言，那么碰撞存在的概率随m而下降而不是线性，而是在m = n / 2附近有一个陡峭的截止 . 这与生日悖论的分析相同 . 对于SHA-1，这意味着如果m <80则可能没有碰撞，而m> 80使得至少存在一个碰撞非常可能（m> 160这变得确定） .
请注意"there exists a collision"和"you find a collision"之间存在差异 . 即使必须存在碰撞，每次尝试时仍然有2 ^（ - 160）的概率 . 前一段的意思是，如果你不能（在概念上）尝试2 ^ 160对字符串，例如，这样的概率是没有意义的 . 因为您将自己限制为少于80位的字符串 .
是的，因为pigeon hole principle是可能的 .
大多数哈希（也是sha1）具有固定的输出长度，而输入具有任意大小 . 所以如果你尝试的时间足够长，你可以找到它们 .
但是，加密散列函数（如sha-family，md-family等）旨在最大限度地减少此类冲突 . 已知的最佳攻击需要2 ^ 63次尝试找到碰撞，所以机会是2 ^（ - 63），实际上是0 .
在散列函数中几乎总是可以发生冲突 . 到目前为止，SHA1在产生不可预测的冲突方面非常安全 . 危险在于可以预测冲突时，不必知道原始哈希输入以生成相同的哈希输出 .
例如，针对MD5的攻击已经针对去年的SSL服务器证书签名，例如Security Now播客第179集 . 这使得复杂的攻击者能够为流氓网站生成虚假的SSL服务器证书，并且看起来像是reaol . 因此，强烈建议避免购买MD5签名的证书 .
git使用SHA1哈希作为ID，并且2014年仍然没有已知的SHA1冲突 . 显然，SHA1算法很神奇 . 我认为对于你的长度的字符串存在，因为它们现在已经被发现了 . 但是，如果您不信任魔法并且不是博彩人，则可以生成随机字符串并将其与您的数据库中的ID相关联 . 但是如果您确实使用SHA1哈希并成为第一个发现冲突的哈希，那么您可以在此时将系统更改为使用随机字符串，并将SHA1哈希保留为旧版ID的"random"字符串 .你所说的是一种碰撞 . 这是一篇关于SHA1冲突的文章：http://www.rsa.com/rsalabs/node.asp?id=2927
编辑：所以另一个回答者打我，提到鸽子洞原则大声笑，但澄清这就是为什么它被称为鸽子洞原则，因为如果你有一些洞切出载体鸽子筑巢，但你有更多的鸽子比洞，然后一些鸽子（输入值）必须共享一个洞（输出值） .