Come effetti Lunghezza collisioni
Questa è semplicemente una questione di permutazioni.
Se uso valori hash piccoli (7-8 bit) poi ci sono alcune collisioni
Bene, cerchiamo di analizzare questo. Con 8 bit, ci sono 2^8 sequenze binarie possibili che possono essere generate per ogni dato input. Vale a dire 256 possibili valori hash che possono essere generati, il che significa che, in teoria, ogni valore di digest del messaggio generato da 256 garantisce una collisione. Questo è chiamato il problema del compleanno.
Se aumento i bit nel valore hash per dire 31, allora ci sono 0 collisioni: tutti gli ngram mappano a diversi valori hash.
Bene, applichiamo la stessa logica. Con una precisione di 31 bit, abbiamo combinazioni possibili 2^31. Questo è 2147483648 combinazioni possibili. E possiamo generalizzare questo a:
Let N denote the amount of bits we use.
Amount of different hash values we can generate (X) = 2^N
Assuming repetition of values is allowed (which it is in this case!)
Si tratta di una crescita esponenziale, che è il motivo per cui con 8 bit, avete trovato un sacco di collisioni e con 31 bit, avete trovato molto poco collisioni.
Come funziona questo effetto collisioni?
Bene, con una piccola quantità di valori, e una probabilità uguale per ciascuno di questi valori viene mappato a un ingresso, si hanno che:
Let A denote the number of different values already generated.
Chance of a collision is: A/X
Where X is the possible number of outputs the hashing algorithm can generate.
Quando X uguale 256, voi hanno un 1/256 possibilità di una collisione, la prima volta. Quindi hai una probabilità 2/256 di una collisione quando viene generato un valore diverso. Fino alla fine, hai generato 255 valori diversi e hai una probabilità 255/256 di collisione. La prossima volta, ovviamente, diventa una possibilità 256/256 o 1, che è una certezza probabilistica. Ovviamente di solito non raggiungerà questo punto. Probabilmente una collisione si verificherà molto più di ogni ciclo 256. Infatti, il paradosso del compleanno ci dice che possiamo iniziare ad aspettarci una collisione dopo che sono stati generati i valori di digest del messaggio 2^N/2. Quindi, seguendo il nostro esempio, dopo aver creato gli hasc unici 16. Sappiamo, tuttavia, che deve succedere, al minimo, ogni 256 cicli. Che non va bene!
Ciò significa, a livello matematico, è che la probabilità di una collisione è inversamente proporzionale al possibile numero di uscite, che è il motivo per cui abbiamo bisogno di aumentare la dimensione del nostro messaggio digerire ad una lunghezza ragionevole.
Una nota su algoritmi di hashing
collisioni sono completamente inevitabili. Questo perché, ci sono un numero estremamente grande di possibili input (2^Tutti i possibili codici di caratteri) e un numero finito di output possibili (come dimostrato sopra).
A rischio di tradire la mia totale ignoranza ... sono valori hash non più piccoli sempre più probabile che si scontrano? (Tutto il resto è uguale (per così dire), cioè lo stesso algoritmo.) – harpo