Qual è la possibilità di collisione di una funzione di hashing a 128 bit se è sempre alimentata con 256 bit di dati?

4

Intendo collisioni "normali" non basate su alcun attacco.

Come lo calcolo?

    
posta kR105 06.05.2013 - 02:26
fonte

1 risposta

8

Il principio pertinente qui è l' attacco di compleanno . Dichiara approssimativamente che per un algoritmo 2 n , la tua probabilità di una collisione casuale tra due elementi è del 50% quando generi 2 (n / 2) .

Quando si esamina un algoritmo di hashing, l'ingenua considerazione dell'algoritmo è che le probabilità sono basse solo nell'ultima iterazione. In questo modo, un algoritmo a 128 bit non interessa se lo si alimenta a 1 bit o a un milione di bit: le probabilità di collisione dovrebbero essere uguali per un dato numero di ingressi univoci (dato che ovviamente è possibile inserire solo 2 bit diversi valori).

Pertanto, la risposta per un algoritmo a 128 bit è che ha una probabilità del 50% di verificarsi di una collisione tra due valori dopo che sono stati creati 2 64 output.

    
risposta data 06.05.2013 - 03:31
fonte

Leggi altre domande sui tag