Pensavo di aver capito l'attacco per il compleanno finché non ho provato a implementarlo. O lo sto implementando male, o c'è qualcosa di sbagliato nella mia interpretazione delle probabilità risultanti. Perché quando lo simulo, ci vogliono più di 2 ^ (N / 2) tentativi.
L'ho semplificato al problema di scegliere numeri casuali fino a quando ne ho scelto uno che ho già scelto in precedenza. Già ci possono essere problemi, in quanto la complessità del tempo potrebbe non essere equivalente a un attacco di compleanno realistico. Ma se è sbagliato, prevedo che è sul lato conservatore, poiché questo dovrebbe essere il modo più semplice per trovare una collisione.
Ecco il mio codice completo (Python 3). Cerca di trovare una collisione tra due numeri casuali a 8 bit. Ripete 100.000 volte e riporta il numero medio e mediano di tentativi.
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])
Il risultato è costantemente una media di circa 20,7 tentativi. Ma dovrebbe prendere 16, come 2 ^ (8/2) = 2 ^ 4 = 16!
Cosa mi manca qui e come si eseguirà un appropriato attacco di compleanno 2 ^ (N / 2)?