(3个答案)
3年前关闭。
给定两个不同的字符串S1和S2(S1!= S2)，可能:
SHA1(S1) == SHA1(S2)
是真的？
我试图实现的目标是对一些敏感的ID字符串(可能与父ID等其他字段结合在一起)进行哈希处理，以便我可以将哈希值用作ID(例如，在数据库中)。
例:
Resource ID: X123
Parent ID: P123
我不想公开我的资源标识的性质，以允许客户端看到“X123-P123”。
相反，我想创建一个新的列哈希(“X123-P123”)，假设它是AAAZZZ。然后客户端可以请求ID为AAAZZZ的资源，而不知道我的内部ID等。
最佳答案
您所描述的称为碰撞。因为SHA-1接受更多不同的消息作为输入，它可以产生不同的输出，所以冲突必定存在(SHA-1可以吃掉任何字符串，最多2 ^ 64位，但是仅输出160位；因此，至少一个输出值必须弹出几次)。此观察结果对于任何输出小于其输入的函数均有效，无论该函数是否为“良好”哈希函数。
假设SHA-1的行为类似于“随机预言”(一个基本返回随机值的概念对象，唯一的限制是，一旦在输入m上返回输出v，则此后必须始终在输入m上返回v)，然后对于任何两个不同的字符串S1和S2，碰撞的概率应为2 ^(-160)。仍然在SHA-1的行为类似于随机预言的假设下，如果您收集了许多输入字符串，那么在收集了大约2 ^ 80个这样的字符串之后，您将开始观察到冲突。
(这是2 ^ 80，而不是2 ^ 160，因为使用2 ^ 80的字符串，您可以制作大约2 ^ 159对字符串。这通常被称为“生日悖论”，因为当应用于碰撞时，这使大多数人感到惊讶在生日那天。请参阅the Wikipedia page。)
现在，我们强烈怀疑SHA-1的行为并不真正像随机预言机，因为生日悖论方法是随机预言机的最佳冲突搜索算法。然而，有一种已公开的攻击应该以大约2 ^ 63的步长找到冲突，因此比生日悖论算法快2 ^ 17 = 131072倍。在真正的随机预言机上，这种攻击是不可行的。请注意，此攻击实际上尚未完成，仍然是理论上的(有人tried but apparently could not find enough CPU power)(更新:截至2017年初的，有人确实使用上述方法计算了SHA-1 collision，并且完全按预期运行)。但是，该理论看起来很合理，而且看起来SHA-1并不是一个随机的预言。相应地，关于碰撞的可能性，所有赌注都没有了。
关于第三个问题:对于具有n位输出的函数，如果可以输入2个以上的不同消息，即最大输入消息长度大于n，则必然存在冲突。当边界m小于n时，答案就不那么容易了。如果函数表现为随机预言，则发生碰撞的可能性随m降低，而不是线性降低，而是随着m = n / 2的陡峭截止而降低。这与生日悖论相同。对于SHA-1，这意味着如果m 80，则很可能存在至少一个碰撞(当m> 160时，这是确定的)。
注意，“存在碰撞”和“找到碰撞”之间是有区别的。即使必须存在碰撞，每次尝试时仍有2 ^(-160)的概率。上一段的意思是，如果您不能(概念上)尝试2 ^ 160对字符串，例如因为您将自己限制为少于80位的字符串。
关于cryptography - 是否有可能获得相同的SHA1哈希？ ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2479348/