Algoritmo de suma de comprobación de 32 bits de mejor calidad que CRC32?

¿Hay cualquier algoritmo de suma de comprobación de 32 bits, ya sea con:Algoritmo de suma de comprobación de 32 bits de mejor calidad que CRC32?

Menor probabilidad de colisión de hash de los datos de entrada de tamaño de 1 KB <?
La colisión golpea con una distribución más uniforme.

Estas relativas a CRC32. Prácticamente no estoy contando con la primera propiedad, debido a la limitación del espacio de almacenamiento de 32 bits. Pero por el segundo ... parece que podría ser mejoras.

¿Alguna idea? Gracias. (Necesito una implementación concreta, mejor en C, pero C++/C# o cualquier cosa para empezar también está bien).

Fuente

2011-12-06 Agnius Vasiliauskas

¿Lo está usando como una suma de comprobación en un sistema de corrección de errores, o lo está utilizando como una función hash para probablemente detectar que las dos entradas son diferentes al comparar sus valores hash? Los códigos de corrección de errores y las funciones hash tienen diferentes propiedades deseables. En el caso de CRC32, está específicamente diseñado para detectar errores del tipo esperado en una línea ruidosa (diferencia de un bit o unos pocos bits, no estoy seguro de cuál). –

Lo estoy usando como función hash para comparar dos paces de datos pequeños. (<1KB) Pero estoy obligado a hash de 32 bits. –

¿Qué tal MurmurHash? Es said, que este hash tiene una buena distribución (pasa las pruebas de chi-cuadrado) y un buen efecto de avalancha. También muy buena velocidad de computación.

Fuente

2011-12-06 09:15:50 werewindle

No corresponde al primer criterio. Cualquier función hash bien diseñada con una salida de 32 bits tiene una probabilidad de 1 en 2^32 de una colisión para cualquier par de entradas. El segundo criterio no está muy bien definido, aunque seguramente existen algunas pruebas estadísticas que podrían usarse, y estoy seguro de que alguien lo ha hecho (¿chi-cuadrado para los intervalos de colisión?). En cuanto a la necesidad de una implementación, le recomiendo encarecidamente que no acepte ningún código propuesto para una función hash que no sea una implementación de un hash bien conocido, ya que existe un alto riesgo de problemas de seguridad o un rendimiento deficiente al transferir su propio hash o cifrado . Una función de hash bien conocida pero mala es mejor que la que diseñaste tú mismo, incluso si la última prueba bien y tiene una distribución de colisiones "buena", simplemente porque la primera tiene más ojos en ella.

Fuente

2011-12-06 09:16:01 Dan

¿Es CRC32 una "función hash bien diseñada" según esta definición? Está diseñado para detectar ciertos tipos de errores, por lo que espero que las entradas con ciertos tipos de diferencias tengan una mayor probabilidad de detección (es decir, diferentes valores de CRC), a expensas de otros tipos de diferencias. –

Algoritmo de suma de comprobación de 32 bits de mejor calidad que CRC32?

Respuesta

Cuestiones relacionadas