algoritmo di checksum a 32 bit migliore qualità rispetto a CRC32?

ci sono eventuali algoritmo di checksum a 32 bit sia con:algoritmo di checksum a 32 bit migliore qualità rispetto a CRC32?

Smaller hash collisione probabilità per i dati di input dimensioni < 1 KB?
Colpi di collisione con distribuzione più uniforme.

Questi relativi a CRC32. Praticamente non sto contando sulla prima proprietà, a causa della limitazione dello spazio di archiviazione di 32 bit. Ma per il secondo ... sembra che ci sia potrebbe essere miglioramenti.

Qualche idea? Grazie. (Ho bisogno di un'implementazione concreta, meglio in C, ma anche C++/C# o qualsiasi cosa per iniziare è OK).

fonte

2011-12-06 Agnius Vasiliauskas

Lo stai utilizzando come checksum in un sistema di correzione degli errori o lo stai utilizzando come funzione di hash per rilevare probabilmente che due input sono diversi confrontando gli hash? I codici di correzione degli errori e le funzioni di hash hanno proprietà desiderabili diverse. Nel caso di CRC32, è specificamente progettato per rilevare errori del tipo che ci si aspetta da una linea rumorosa (un bit o una piccola differenza di bit, non sono sicuro quale). –

Lo sto usando come funzione di hash per confrontare due pezzi di dati piccoli. (<1 KB). Ma sono costretto a un hash a 32 bit. –

Che ne dici di MurmurHash? È said, che questo hash ha una buona distribuzione (supera i test chi-quadrato) e un buon effetto valanga. Ottima anche la velocità di calcolo.

fonte

2011-12-06 09:15:50 werewindle

Non per i primi criteri. Qualsiasi funzione di hash ben progettata con un'uscita a 32 bit ha una probabilità 1 in 2^32 di collisione per qualsiasi coppia di ingressi. Il secondo criterio non è molto ben definito, anche se ci sono sicuramente alcuni test statistici che potrebbero essere utilizzati, e sono sicuro che qualcuno l'ha fatto (chi-quadro per intervalli di collisione?). Per quanto riguarda l'implementazione, raccomando vivamente di non accettare alcun codice proposto per una funzione hash che non è un'implementazione di un hash ben noto, poiché vi è un alto rischio di problemi di sicurezza o scarse prestazioni quando si esegue il proprio hash o crittografia . Una funzione hash ben nota ma sbagliata è migliore di quella che hai progettato tu stesso, anche se quest'ultima prova bene e ha una distribuzione di collisione 'buona', semplicemente perché la prima ha più occhio su di essa.

fonte

2011-12-06 09:16:01 Dan

CRC32 è una "funzione hash ben progettata" da questa definizione? È progettato per rilevare determinati tipi di errori, quindi mi aspetto che gli input con determinati tipi di differenza abbiano una maggiore probabilità di rilevamento (ovvero valori CRC diversi), a scapito di altri tipi di differenze. –

algoritmo di checksum a 32 bit migliore qualità rispetto a CRC32?

risposta

Problemi correlati