Joh*_*usa 49 math md5 sha1 digest hash-collision
给定两个不同的消息,A和B(可能是20-80个字符的文本,如果大小完全重要),A的MD5摘要与B的MD5摘要相同且 A的SHA1摘要的概率是多少？与B的SHA1摘要相同？那是:
(MD5(A) == MD5(B)) && (SHA1(A) == SHA1(B))
假设没有恶意意图,即没有选择消息以找到冲突.我只是想知道这种情况发生的可能性.
我认为机会是"天文数字低",但我不确定如何验证这一点.
更多信息:可能消息池的大小受到限制,但是很大(几亿).生日悖论的情况正是我所担心的.
Wel*_*bog 63
假设在随机字符串的MD5和SHA-1哈希范围内均匀分布(事实并非如此),并假设我们只讨论两个字符串而不是在谈论字符串池(所以我们避免生日悖论)型复杂性):
MD5散列是128位宽,SHA-1是160.在上述假设下,如果两个散列都发生碰撞,则两个字符串A和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
同样,如果你有一个字符串池并且你正试图确定与池碰撞的可能性,那么你就处于生日悖论的范畴内,而我在这里计算的这个概率并不适用.那些和哈希并不像它们应该的那样统一.实际上你会有更高的碰撞率,但它仍然很小.
编辑
由于您正处理生日悖论的情况,因此应将与解决方案相同的逻辑应用于生日悖论.让我们从一个哈希函数的角度来看它:
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)!)
简而言之,我甚至不想考虑计算这个数字.我甚至不确定你如何估算它.你至少需要一个能够处理巨大因子而不会死亡的任意精度计算器.
请注意,概率将遵循从接近0时开始的曲线,当N = 1 or 2它N >= 2^288与形状类似于维基百科页面上的生日悖论时,它将达到1 .
生日悖论P = .5何时达到N = 23.换句话说,当N是S的6%时,碰撞的概率是50%.如果那个尺度(我不确定它是否确实),这意味着当你有碰撞时有50%的碰撞几率2 ^ 288个哈希值的6%.2 ^ 288的6%约为2 ^ 284.你的N(几亿)的价值远不及那个.与你的S相比,它实际上是微不足道的,所以我认为你没有什么可担心的.碰撞的可能性不大.
Welbog的帖子附录:
通过使用斯特林的近似,可以在不使用任意精度算术的情况下计算大因子的比率:
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 ≈Ë 斧持有正→∞(或者至少变得非常大)
**因此,这意味着(1 +(N /(SN)))SN ≈Ë Ñ为SN >> N.
所以我希望如此
(S!)/(S ^ N*(S-N)!)≈sqrt(1 + N /(SN))*e N*e -N = sqrt(1 + N /(SN))SN >> ñ....
除了这大于1 ...所以其中一个近似值不够好.:p
(**警告:N/S必须很小:N = 22,S = 365,这是2倍)