Numero possibile di collisioni in una funzione di hashing con dimensioni di messaggio costanti

1

Saltare alle conclusioni del mio domanda , possiamo prevedere il numero possibile di collisioni per un determinato messaggio in un determinato algoritmo di hashing.

Dire che sto usando SHA-1 che emette 160 caratteri stringa, e la mia stringa di input è di 161 caratteri, quindi vuol dire che ciascuno dei miei messaggi di 161 caratteri ha al massimo collisioni illimitate e almeno 10 collisioni / pre-immagini ciascuna di 161 personaggi. La mia comprensione è corretta?

    
posta Firdous 15.05.2016 - 09:17
fonte

1 risposta

2

Say I am using SHA-1 which outputs 160 characters string, and my input string is 161 characters, so does that mean each of my 161 character message has at most unlimited collisions and at least 10 collisions/pre-images each of 161 characters. Is my understanding correct?

No.

Innanzitutto non può avere collisioni illimitate poiché il numero di messaggi con 161 caratteri è limitato da solo. Ciò significa che anche per il peggiore algoritmo di hash che associa tutto ad un valore hash costante, ci saranno solo 256 ^ 161 immagini che mappano allo stesso valore di hash (assumendo che il carattere sia un ottetto).

Inoltre non è necessario che ci sia alcuna collisione per un dato valore hash e non è nemmeno garantito che ci sia un'immagine all'interno del set per ogni possibile valore hash.

Ciò che puoi dire è che otterrai in media 10 immagini con lo stesso valore hash. E con un buon hash crittografico come SHA-1 otterrete anche solo una piccola deviazione da questa media.

    
risposta data 15.05.2016 - 13:25
fonte

Leggi altre domande sui tag