Para la mayoría de las aplicaciones (no criptográficas), podemos razonar sobre MD5 como si fuera una función aleatoria. Bajo ese supuesto, cualquier par de valores distintos es una colisión MD5 con probabilidad [matemática] \ tfrac {1} {2 ^ {128}} [/ matemática]. Por linealidad de expectativa, entre cualquier valor [math] k [/ math] distinto, esperamos [math] \ tfrac {1} {2 ^ {128}} \ tbinom k2 [/ math] colisiones.
(Como un caso especial, con solo entradas [matemáticas] k = 2 ^ {64} [/ matemáticas], esperamos una colisión con una probabilidad de alrededor del 50%. Esto se conoce como la paradoja del cumpleaños ).
Aunque no podemos saber con certeza que MD5 realmente se comporta al azar para este propósito (porque las colisiones MD5 “naturales” son demasiado raras), hay buenas razones para creer que sí. Podemos hacer el experimento para una versión intencionalmente truncada de MD5. Aquí hay algunos datos de colisiones parciales de los primeros 16 bits de resúmenes MD5 (código en comentarios); puede ver que el número real de colisiones es muy cercano al número que esperaría estadísticamente, y mucho mayor que el límite inferior que obtendría si los resúmenes se distribuyeran “óptimamente” en lugar de al azar.
- Encuentre el dominio de la función [matemáticas] f (x) = \ frac {1} {x} + \ sqrt {2x + 3} + \ sqrt [3] {1 - x}? [/ Matemáticas]
- ¿Es f * (z) = f (z *)?
- ¿Qué son los símbolos?
- 4, 8, 10, 18, 20, 24, ___. ¿Qué viene después en la serie?
- Cómo encontrar el infimum y el supremum de [matemáticas] A = \ {\ frac {xy} {x + y + 3}; x \ in [-1,1], y \ in [-1,1] \} [/ math]
#digests colisiones esperadas lowbound
128 0 0.1 0
256 1 0,5 0
512 3 2 0
1024 5 8 0
2048 25 32 0
4096 119 128 0
8192 505 512 0
16384 2109 2048 0
32768 8045 8192 0
65536 32634 32768 0
131072 131033 131071 65536
262144 525449 524286 393216
524288 2096093 2097148 1835008
1048576 8386142 8388600 7864320
2097152 33547396 33554416 32505856
4194304 134202102 134217696 132120576
8388608 536862976 536870848 532676608
16777216 2147428485 2147483520 2139095040
