Todos sabemos cómo es un hash, pero ¿alguna vez te has preguntado con qué frecuencia se encuentra un personaje en particular en un hash? Me preguntaba Y decidí comprobarlo. Dibujé un script de Python para contar, y esto es lo que salió de él.
Primero, generé una cadena aleatoria de caracteres (longitud de 0 a 1000).
def random_string(from_int, to_int): return str(''.join(random.SystemRandom().choice(string.ascii_letters + string.digits + string.punctuation) for _ in range(random.randint(from_int, to_int))))
Luego, tomé el hash MD5 de la cadena.
def md5_from_string(string): return hashlib.md5(string.encode('utf-8')).hexdigest()
Después: calculé cuántos dígitos del 0 al 9 hay en el hash. En una muestra de 1000 hashes, recibí los siguientes datos:
Aquí la diferencia entre el dígito más frecuente y el más raro (valor delta) es interesante.
Además, para rastrear el cambio en el valor delta, hizo muestras de 10,000, 100,000, 1,000,000, 10,000,000 hashes.
La siguiente es una lista con los valores de los números mínimo y máximo y el valor delta en muestras con diferentes números de hash MD5:
- 100 - min: 179, max: 230, delta: 22.17%
- 1000 - min: 1925, max: 2058, delta: 6.46%
- 10000 - min: 19769, max: 20251, delta: 2.38%
- 100000 - min: 199297, max: 200846, delta: 0.77%
- 1,000,000 - min: 1997650, max: 2001690, delta: 0.20%
- 10000000 - min: 19991830, max: 20004818, delta: 0.06%
Lo que tenemos: con un aumento en el número de hashes en la matriz, el valor delta disminuye y cualquier dígito con casi la misma probabilidad caerá en la matriz. Por lo tanto, cuanto mayor sea la muestra, menor será la diferencia entre los números que se encuentran con frecuencia y los que rara vez se ven. En consecuencia, la probabilidad de obtener un dígito particular en un hash tiende a la uniformidad.
Esta información formó la base del algoritmo que implementamos en la
plataforma de competencia
bepeam.com