两条消息具有相同的MD5摘要和相同的SHA1摘要的机会是多less？
给定两个不同的消息，A和B（大概20-80个字符的文本，如果大小都有关系），A的MD5摘要与B的MD5摘要相同的概率是多less，A的SHA1摘要是与B的SHA1摘要相同？ 那是：
(MD5(A) == MD5(B)) && (SHA1(A) == SHA1(B)) 假定没有恶意的意图，也就是说，消息不是为了find冲突而select的。 我只想知道这种情况发生的可能性。
我想这个机会是“天文数字低”，但我不知道如何validation这一点。
更多信息：可能的消息池的大小是有限的，但大（几亿）。 生日悖论的情况正是我所担心的。
假设随机string在MD5和SHA-1散列范围内均匀分布（假定情况并非如此），假设我们只谈论两个string而不谈论string池（所以我们避免生日悖论types的复杂性）：
MD5哈希是128位宽，SHA-1是160.有了上述假设，如果两个哈希都发生冲突，两个stringA和B有碰撞概率P. 所以
P(both collide) = P(MD5 collides) * P(SHA-1 collides)
和
P(MD5 collides) = 1/(2^128) P(SHA-1 collides) = 1/(2^160)
所以
P(both) = 2^-128 * 2^-160 = 2^-288 ~= 2.01 x 10^-87
再一次，如果你有一串string，而你试图确定碰撞的概率，那么你就处于生日悖论的范畴，我在这里计算的这个概率并不适用。 这和哈希不是他们应该的统一。 事实上，你将会有更高的碰撞率，但它仍然很小。
编辑
既然你正在处理生日悖论的情况，那么应用与生日悖论的解决scheme相同的逻辑。 我们只从一个散列函数的angular度来看它：
N := the number of hashes in your pool (several hundred million) S := the size of your hash space (2^288) Therefore, P(There are no collisions) = (S!)/(S^N * (S - N)!)
假设我们有2 ^ 29（大约5亿3千万）的哈希值。
P = (2^288!)/(2^288^(2^29) * (2^288 - 2^29)!)
总之，我甚至不想考虑计算这个数字。 我甚至不知道如何去评估它。 你至less需要一个任意精度的计算器，可以处理巨大的阶乘，而不会死亡。
请注意，概率将遵循一条从N = 1 or 2时的近似0开始的曲线，当N >= 2^288 ，概率将达到1，这与维基百科页面上的生日悖论形状相似。
当N = 23时，生日悖论达到P = .5 。 换句话说，当N是S的6％时，碰撞的概率是50％。如果这个比例（我不确定是否确实如此），这意味着当你有碰撞的可能性是50％ 6％的2 ^ 288哈希。 2 ^ 288的6％在2 ^ 284左右。 你的N（几亿）的价值远不止于此。 与你的S相比，这实际上是微不足道的，所以我不认为你有任何担心。 碰撞不太可能。
Welbog的post附录：
通过使用斯特林（Stirling）近似 ，可以不使用任意精度algorithm来计算大型因子的比率：
N！ ≈sqrt（2πn）*（n / e） n
（s）/（s ^ N *（S-N）！）≈sqrt（2πS）/ sqrt（2π（SN））*（S / e） S /（（SN）/ e） SN / S N
= sqrt（S /（SN））*（S /（SN）） SN * e- N
= sqrt（1 +α）*（1 +α） SN * e -N其中α= N /（SN）小。
近似（1 + a / n） nx≈e ax保持为n→∞（或者至less变得非常大）
**所以这意味着（1+（N /（SN））） SN≈NEN对于SN >> N.
所以我期待这一点
（SN +）/（S ^ N *（S-N）！）≈sqrt（1 + N /（SN））* e N * e -N = sqrt（1 + N / ñ….
除了这个大于1 …所以其中一个近似值不够好。 ：p
（**警告：N / S必须很小：对于N = 22，S = 365，这是closures的2倍）
如果消息大小不受限制，则机会渐近接近100％，因为有无限可能的消息和有限数量的散列。
（注意：编辑问题使得现在不那么重要）
通常，当随机选取N个元素时，计算碰撞的预期次数比碰撞的概率更容易。 由于预期的碰撞次数不能小于碰撞概率，因此可以经常用作合适的上界。
假定p是两个随机挑选元素相撞的概率。 如果我们选取N个随机元素，则存在N *（N-1）/ 2个元素对，因此碰撞的预期数量是
p * N *（N-1）/ 2。
例如，如果我们假设MD5和SHA1碰撞的概率是p = 2 -288，那么即使在随机选取2 100个元素之后，我们仍然只能预期大约2-89次的碰撞。
另一个例子：如果我们挑选2个30个随机元素，只计算MD5。 假设两个MD5哈希之间的冲突为p = 2 -128 ，那么碰撞次数的预期值为2-59 。 因此，即使MD5哈希碰撞两个input的概率已经非常小。
select的答案是不正确的，因为它使用了错误的概率。 今天我花了很大一部分时间来研究这个问题（你可以在评论中看到我的思考过程），并且相信实际的答案如下（对于稍微大一些的消息， ：
2 ^ -61 * 2 ^ -18 = 2 ^ 79中的一次碰撞。
这就是如果只是乘以这些概率是可以的（我不确定）。
今天超级计算机是可行的（不到几个月，每年下降）。
请注意，这是基于足够大的消息池（使生日悖论有意义）。 这也是你说的你担心的情况。
现在，不同的情况是发现特定消息的一对哈希（SHA1和MD5）的冲突。 这使你摆脱了bday悖论的境地，并且难度更大。 我不确定那是2 ^（ – 61 * 2）* 2 ^（ – 18 * 2）还是别的。 如果有人知道这是什么，请发表评论这个答案（将超级赞赏！）。
现在你问：
给定两个不同的信息，A和B（如果大小的话，可能是20-80个字符的文本）
是的，尺寸确实重要。 点击2 ^ -18图的链接，你会看到两个input块的值。 在MD5中，input块是512字节。 文本的20-80个字符太小，单个块的值是2 ^ 41。
因此，对于这个数据量，你得到2 ^ -61（我认为）* 2 ^ -41 = 2 ^ -102。
所以对于这个尺寸看起来很安全 （链接包含SHA256的两倍比特币散列率：46626.93 TH /秒）。
