Pensé que entendía el ataque de cumpleaños hasta que intenté implementarlo. O lo estoy implementando mal, o hay algo mal con mi interpretación de las probabilidades resultantes. Porque cuando lo simulo, toma más de 2 ^ (N / 2) intentos.
Lo simplifiqué al problema de elegir números aleatorios hasta que elija uno que ya he elegido antes. Ya puede haber problemas, ya que la complejidad del tiempo puede no ser equivalente a un ataque de cumpleaños realista. Pero si está mal, espero que sea del lado conservador, ya que esta debería ser la forma más fácil de encontrar una colisión.
Aquí está mi código completo (Python 3). Intenta encontrar una colisión entre dos números aleatorios de 8 bits. Se repite 100.000 veces, e informa el promedio y el número medio de intentos.
import random
def birthday_attack(choices):
tries = 0
max_tries = choices**2
chosen = set()
choice = None
while choice not in chosen and tries < max_tries:
tries += 1
if choice is not None:
chosen.add(choice)
choice = random.randrange(choices)
return tries
trials = 100000
tries = [birthday_attack(2**8) for i in range(trials)]
print(sum(tries)/trials)
tries.sort()
print(tries[trials//2])
El resultado es consistentemente un promedio de aproximadamente 20.7 intentos. ¡Pero debería tomar 16, como 2 ^ (8/2) = 2 ^ 4 = 16!
¿Qué me estoy perdiendo aquí y cómo se realizaría un ataque de cumpleaños de 2 ^ (N / 2)?