两条消息具有相同MD5摘要和相同SHA1摘要的可能性有多大?

假设随机字符串在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

同样,如果您有一个字符串池,并且您试图确定与该池发生冲突的概率,那么您就在 birthday paradox

编辑

由于您正在处理生日悖论的情况,请应用与生日悖论解决方案相同的逻辑。让我们从一个散列函数的角度来看:

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)!)

P = (2^288!)/(2^288^(2^29) * (2^288 - 2^29)!)

简言之,我甚至不想考虑计算这个数字。我甚至不知道你怎么去估计它。你至少需要一个任意精度的计算器,可以处理巨大的阶乘而不会死亡。

请注意,概率将遵循一条曲线,当 N = 1 or 2 ,当 N >= 2^288 ,形状与维基百科页面上的生日悖论相似。

生日悖论 P = .5 N = 23 . 换句话说,当N是S的6%时,冲突的概率是50%。如果按比例计算(我不确定是否如此),这意味着当您有6%的2^288个哈希时,冲突的概率将是50%。2^288的6%约为2^284。你的价值N(几亿)远没有达到这个水平。与你的s相比,它实际上微不足道,所以我认为你没有什么可担心的。碰撞的可能性不大。

韦尔博格职位的增编:

大阶乘的比率可以通过使用 Stirling's approximation :

^N

所以(S!)/(S^N*(S-N)!)≈ sqrt(2πS)/sqrt(2π(S-N))*(S/e) / ^N

^S-N *e ^-N

=sqrt(1+α)*(1+α) ^S-N *e ^-N 其中α=N/(S-N)很小。

^{nx 斧头} 保持为n→ ∞ (或者至少变得非常大)

**这意味着(1+(N/(S-N))) ^S-N ≈ E ^N

所以我希望

(S!)/(S^N*(S-N)!)≈ sqrt(1+N/(S-N))*e ^{N -N} =S-N的sqrt(1+N/(S-N))>&燃气轮机;N

除了这个大于1。。。所以其中一个近似值不够好:P

(**注意事项:N/S必须很小:对于N=22,S=365,这是关闭的2倍)

通常,当随机选取N个元素时,计算预期碰撞次数比计算碰撞概率更容易。由于预期的碰撞次数不能小于碰撞概率,因此可以经常将其用作合适的上限。

假定 是两个随机拾取的元素碰撞的概率。如果我们选取N个随机元素,则有N*(N-1)/2对元素,因此预期的碰撞次数为

p*N*(N-1)/2。

^-288 然后即使随机挑选了2个 我们仍然只期望2个元素 ^-89

另一个例子:如果我们选择2 ^{30 -128} 这给出了预期的2个数字 ^-59 关于碰撞的次数。因此,即使MD5散列对两个输入发生冲突的概率也已经非常小了。

2^-61 * 2^-18 =2^79中发生一次碰撞。

如果可以将这些概率相乘(我不确定)。

这是可以做到的(不到几个月,每年下降)由超级计算机今天。

现在,一种不同的情况是为一个数组的一对哈希(SHA1和MD5)查找冲突 消息这将带你走出bday悖论的领域,难度要大几个数量级。我不确定这是2^(-61*2)*2^(-18*2)还是其他什么。

现在你问:

给出两条不同的消息,A和B(如果大小重要的话,可能是20-80个字符的文本)

是的,尺寸很重要。单击指向2^-18图的链接,您将看到该值适用于两个输入块。在MD5中,输入块是512字节。20-80个字符的文本太小,单个块值为2^41。

因此,对于这一数量的数据,可以得到2^-61(我认为)*2^-41=2^-102。

那么这个尺寸呢 seems safe