Después de investigar con expertos en esta materia, programadores de deferentes áreas y profesores hemos dado con la solución a la cuestión y la compartimos en esta publicación.
Solución:
CRC32 funciona muy bien como un algoritmo hash. El todo el punto de un CRC es hacer un hash de un flujo de bytes con la menor cantidad de colisiones posible. Dicho esto, hay algunos puntos a considerar:
-
Los CRC no son seguros. Para un hash seguro, necesita un algoritmo mucho más costoso desde el punto de vista informático. Para un simple hash de cubo, la seguridad generalmente no es un problema.
-
Existen diferentes sabores de CRC con diferentes propiedades. Asegúrese de utilizar el algoritmo correcto, por ejemplo, con el polinomio hash 0x11EDC6F41 (CRC32C), que es la opción óptima de uso general.
-
Como compensación entre velocidad y calidad de hash, la instrucción x86 CRC32 es difícil de superar. Sin embargo, esta instrucción no existe en las CPU más antiguas, así que tenga cuidado con los problemas de portabilidad.
—- EDITAR —-
Mark Adler proporcionó un enlace a un artículo útil para la evaluación de hash de Bret Mulvey. Utilizando el código fuente proporcionado en el artículo, ejecuté la “prueba de cubo” tanto para CRC32C como para Jenkins96. Estas tablas muestran la probabilidad de que una distribución verdaderamente uniforme sea peor que el resultado medido por casualidad. Entonces, números más altos son mejores. El autor consideró que 0.05 o menos es débil y 0.01 o menos es muy débil. Confío completamente en el autor en todo esto y solo estoy informando los resultados.
Coloqué un * en todas las instancias donde CRC32C funcionó mejor que Jenkins96. Según este simple recuento, CRC32C fue un hash más uniforme que Jenkins96 54 de 96 veces. Especialmente Si puede utilizar la instrucción x86 CRC32, la compensación de velocidad y rendimiento es excelente.
CRC32C (0x1EDC6F41)
Uniform keys Text keys Sparse keys
Bits Lower Upper Lower Upper Lower Upper
1 0.671 *0.671 *1.000 0.120 *0.572 *0.572
2 *0.706 *0.165 *0.729 *0.919 0.277 0.440
3 *0.878 *0.879 *0.556 0.362 *0.535 *0.542
4 0.573 0.332 0.433 0.462 *0.855 0.393
5 0.023 *0.681 0.470 0.907 0.266 0.059
6 *0.145 *0.523 0.354 *0.172 *0.336 0.588
7 0.424 0.722 0.172 *0.736 0.184 *0.842
8 *0.767 0.507 *0.533 0.437 0.337 0.321
9 0.480 0.725 *0.753 *0.807 *0.618 0.025
10 *0.719 0.161 *0.970 *0.740 *0.789 0.344
11 *0.610 0.225 *0.849 *0.814 *0.854 *0.003
12 *0.979 *0.239 *0.709 0.786 0.171 *0.865
13 *0.515 0.395 0.192 0.600 0.869 *0.238
14 0.089 *0.609 0.055 *0.414 *0.286 *0.398
15 *0.372 *0.719 *0.944 0.100 *0.852 *0.300
16 0.015 *0.946 *0.467 0.459 0.372 *0.793
Y para Jenkins96, que el autor del artículo consideró un excelente hash:
Jenkins96
Uniform keys Text keys Sparse keys
Bits Lower Upper Lower Upper Lower Upper
1 0.888 0.572 0.090 0.322 0.090 0.203
2 0.198 0.027 0.505 0.447 0.729 0.825
3 0.444 0.510 0.360 0.444 0.467 0.540
4 0.974 0.783 0.724 0.971 0.439 0.902
5 0.308 0.383 0.686 0.940 0.424 0.119
6 0.138 0.505 0.907 0.103 0.300 0.891
7 0.710 0.956 0.202 0.407 0.792 0.506
8 0.031 0.552 0.229 0.573 0.407 0.688
9 0.682 0.990 0.276 0.075 0.269 0.543
10 0.382 0.933 0.038 0.559 0.746 0.511
11 0.043 0.918 0.101 0.290 0.584 0.822
12 0.895 0.036 0.207 0.966 0.486 0.533
13 0.290 0.872 0.902 0.934 0.877 0.155
14 0.859 0.568 0.428 0.027 0.136 0.265
15 0.290 0.420 0.915 0.465 0.532 0.059
16 0.155 0.922 0.036 0.577 0.545 0.336
Obviamente podrías, pero no deberías. Un crc32 distribuye mal los bits de entrada al hash. Además, ciertamente no debería usarse nunca como un hash unidireccional, ya que no lo es. Es muy fácil modificar un mensaje para producir un crc determinado.
Utilice un algoritmo hash diseñado para el propósito que tiene en mente, sea lo que sea.
No sé por qué Mark Adler dijo que “crc32 distribuye mal los bits de entrada al hash”. No hay un solo bit en el hash crc32 que sea exactamente igual a los bits de entrada. Cualquier bit del hash es una combinación lineal de los bits de entrada. En segundo lugar, crc siempre asigna uniformemente el mismo número de diferentes secuencias de entrada a un valor hash dado. Por ejemplo, si tiene un mensaje de 1000 bits de longitud, después de crc32, siempre puede encontrar 2 ^ (1000-32) secuencias que produzcan un valor hash dado, ni más ni menos.
Si no necesita la función de seguridad, crc puede servir perfectamente como hash.
En realidad, creo que otras funciones hash no seguras pueden ser más simples que crc, si necesita tener un crc más largo, por ejemplo, crc-256.
Calificaciones y reseñas
Eres capaz de sostener nuestra función ejecutando un comentario y dejando una valoración te estamos eternamente agradecidos.