Se la funzione hash e’ ben disegnata, l’attacco birthday rimane un punto di riferimento e difficilmetne si potrebbe fare meglio. Possiamo vedere questo paradosso implementato in una versione naive, prima ancora per problemi di tempo anche per problemi di spazio. Esiste un algoritmo molto piu’ astuto che viene usato anche per altri scopi, come fattorizzazione di interi - > Metodo Rho
Questo fa praticamente qualche analisi in piu’ e usa solamente spazio costante. come funziona? l’analisi non e’ matematicamente rigorosa all’interno del notebook ma i res sono in accordo con la pratica, quindi chissene alla fine. L’assunzione quale sarebbe rispetto al birthday? che i valori hash siano veramente casuali.
il metoto si applica in questo modo: la funzione hash si applica solamente a valori hash stessi, quindi praticamente R (codominio) → R. Quindi abbiamo una funzione hash arbitraria che ha come dominio U e come codominio R, ma diamo come input alla funzione i valori di R in realta’. Facciamo partire due successioni:
praticamente la lepre fa un doppio hash rispetto al primo. Il cacciatore raggiunge la lepre perche’ il codominio e’ finito e prima o poi i valori si ripetono! La lepre fa un certo numero di salti in avanti e poi ne fa un altro numero sigma di balzi. Ci sono un primo tratto i cui i valori non si ripetono e poi invece abbiamo un segmento periodico. Gli esempi sono fatti tutti con una semplice funzione hash non crittografica, ma che puo’ essere usata in ambito data structure e con valori iniziale 9, ma i disegni sono fatti su quel valore iniziale. la lepre fa 9 11 33 3 12 13 25 10 51 52 12, quindi abbiamo una sorta di anti periodo e poi un periodo lungo sigma che alla fine si ripete sempre praticamente.
Si chiama metodo rho. la ragione per cui si chiama cosi’ e’ per al forma di questa successione numerica diciamo, e’ come la rho greca.
Il rho del cacciatore parte da 9 e fa 9 21 11 1 33 0 3 19 12 7 13 6 25 31 10 41 51 28 52 19
Come vedi praticamente ad un certo punto si viene catturati.
[10:15]
La lepre non si puo’ salvare perche’ comunque il cacciatore fa sempre un passo e la lepre due e prima o poi si incontrano sicuramente. la lunghezza del gambo e’ k volte sigma - r
l =ksigma - r
queste due successioni, dopo avere scoperto dove si incontrano, so quando si incontrano al punto di giunzione. Se mettiamo tutto insieme posso fare una funzione che praticamente mi trova questa collisione:
questa mi trova le collisioni con il metodo rho.