Adler-32

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 14 de mayo de 2019; las comprobaciones requieren 5 ediciones .

Adler-32  es una función hash desarrollada por Mark Adler . Es una modificación del checksum de Fletcher . Calcula el valor de la suma de comprobación según RFC 1950 para una matriz de bytes o su fragmento. Este algoritmo de cálculo de suma de comprobación difiere de CRC32 en rendimiento. Adler-32 se utiliza en la biblioteca Zlib . La versión de suma de comprobación móvil de la función se utiliza en la utilidad rsync .

Historia

Al igual que con la suma de verificación de Fletcher, la suma de Adler se diseñó para producir una suma de verificación con una eficiencia de detección de errores comparable a CRC . Aunque el rendimiento de detección de errores de suma de comprobación de Adler y Fletcher es casi el mismo que el de los CRC relativamente débiles, en algunos casos importantes funcionan mucho peor que los CRC buenos.

Algoritmo

La suma de control Adler-32 se obtiene calculando dos sumas de control A y B de 16 bits y concatenando sus bits en un entero de 32 bits. A es igual a la suma de todos los bytes de la cadena más uno, y B es la suma de todos los valores individuales de A en cada paso. Al comienzo de la ejecución de la función Adler-32, A se inicializa en uno y B  se inicializa en cero. Las sumas se toman módulo 65521 (el mayor número primo menor que 2 16 ). Los bytes se escriben en orden de red , B ocupa los 2 bytes más significativos.

La función se puede expresar como:

A = 1 + D 1 + D 2 + ... + D n (mod 65521) B = (1 + D 1 ) + (1 + D 1 + D 2 ) + ... + (1 + D 1 + D 2 + ... + D n ) (mod 65521) = norte × re 1 + ( norte -1) × re 2 + ( norte -2) × re 3 + ... + re norte + norte (mod 65521 ) Adler-32 ( D ) = B × 65536 + A

donde D es la cadena de bytes para la que se calculará la suma de comprobación y n es la longitud de D.

Ejemplo

El valor Adler-32 para la cadena ASCII "Wikipedia" se calcula de la siguiente manera:

Código ASCII AB (decimal) W: 87 1 + 87 = 88 0 + 88 = 88 yo: 105 88 + 105 = 193 88 + 193 = 281 k: 107 193 + 107 = 300 281 + 300 = 581 yo: 105 300 + 105 = 405 581 + 405 = 986 p: 112 405 + 112 = 517 986 + 517 = 1503 e: 101 517 + 101 = 618 1503 + 618 = 2121 d: 100 618 + 100 = 718 2121 + 718 = 2839 yo: 105 718 + 105 = 823 2839 + 823 = 3662 a: 97 823 + 97 = 920 3662 + 920 = 4582 A = 920 = 398 hexadecimal (base 16) B=4582=11E6 hexagonal Salida = 300286872 = 11E60398 hexadecimal

La operación de adición de módulo no tiene efecto en este ejemplo, ya que ninguno de los valores llegó a 65521.

Comparación con la suma de comprobación de Fletcher

El algoritmo de suma de comprobación de Adler es idéntico al algoritmo de suma de Fletcher con algunas diferencias. La primera diferencia es que en el caso de la función Adler, la suma A se inicializa con el valor 1. La segunda diferencia entre los dos algoritmos es que la suma en el algoritmo Adler-32 se calcula módulo el número primo 65521, mientras que la Las sumas de Fletcher se calculan módulo -1, -1 , -1 (dependiendo del número de bits utilizados), que son números compuestos . Este cambio en el algoritmo se realizó para lograr una mejor mezcla de bits. El uso de un número primo le permite a la función Adler-32 notar diferencias en ciertas combinaciones de bytes que la función Fletcher no puede capturar. La tercera diferencia, que afecta más significativamente la velocidad del algoritmo, es que las sumas de la función Adler-32 se calculan sobre palabras de 8 bits en lugar de palabras de 16 bits, lo que duplica el número de iteraciones del ciclo. Esto da como resultado que la suma de verificación de Adler-32 tarde entre una vez y media y dos veces más que la suma de verificación de Fletcher para datos de palabras de 16 bits. Para datos divididos en bytes, Adler-32 es más rápido que el algoritmo de Fletcher.

Aunque la suma de verificación de Adler no está definida oficialmente para otras longitudes de palabras de datos, el número primo mayor menor que 2 4 = 16 y 2 8 = 256 se puede usar para implementar sumas de verificación de Adler de 8 y 16 bits con fines comparativos. Al tener un algoritmo similar, la suma de comprobación de Adler tiene un rendimiento similar al de la suma de Fletcher. Todos los errores de 2 bits se detectan para palabras de datos más cortas que M*(k/2) bits, donde k es el tamaño de la suma de comprobación, M es el módulo de la suma de Adler. Al igual que con la suma de verificación de Fletcher, el peor valor de la probabilidad de error no detectado ocurre cuando hay el mismo número de ceros y unos en cada bloque de datos. Adler-8 y Adler-16 detectan todos los errores de grupo de menos de k/2 bits de longitud. Adler-32 detecta todos los errores de grupo de no más de 7 bits. La Figura 1 muestra la dependencia de la probabilidad de errores no detectados para las sumas de control de Adler y Fletcher para una tasa de error de bit de 10 −5 .

La mejor combinación de bits proporcionada por la suma de comprobación de Adler debería haber resultado en un mejor rendimiento de detección de errores que la suma de Fletcher. Pero como muestra RFC 3385 , Fletcher-32 funciona mejor que Adler-32 a 8 KB. La suma de verificación de Adler supera a la suma de Fletcher solo en el caso de sumas de verificación de 16 bits, y solo en el área de estas sumas donde la distancia de Hamming es 3. El problema es que, a pesar de que el número primo utilizado como el módulo de la operación, da como resultado una mejor mezcla de bits, lo que da como resultado menos valores de suma de comprobación correctos disponibles para las palabras clave. En la mayoría de los casos, esto anula el efecto positivo de una mejor mezcla. Por lo tanto, la suma de comprobación de Fletcher supera a la suma de Adler en todos los casos excepto en la suma de Adler-16 aplicada a palabras de datos cortas. Incluso el aumento en la eficiencia de detección de errores puede no valer la pena el aumento en la sobrecarga computacional que conlleva el uso de operaciones modulares.

Comparación con otras sumas de comprobación

Los autores de RFC 3385 compararon el rendimiento de la detección de errores. Un resumen de sus resultados se presenta en la tabla:

Algoritmo d bloquear yo/byte talla T T-mirada PUDB _ pudín _
Adler-32 3 2 19 3 - - 10 −36 10 −35
Fletcher-32 3 2 19 2 - - 10 −37 10 −36
IEEE-802 3 2 16 2.75 2 18 0.5/b 10 −41 10 −40
CRC32C 3 2 31 −1 2.75 2 18 0.5/b 10 −41 10 −40


En la tabla: d es la distancia mínima en un bloque de Block length, Block es la longitud del bloque en bits, i/byte es el número de instrucciones de programa por byte, T size  es el tamaño de la tabla (si la visualización es necesario), T-look es el número de vistas por byte, P udb  es la probabilidad de errores de grupo no detectados, P uds  es la probabilidad de errores individuales no detectados.
Las probabilidades de errores no detectados en la tabla anterior se calculan asumiendo una distribución de datos uniforme.

Ventajas y desventajas

Una función hash "buena" se caracteriza por una distribución más o menos uniforme de los valores calculados. Obviamente, Adler-32 no cumple este requisito para datos cortos (el valor máximo de A para un mensaje de 128 bytes es 32640, que es menor que 65521, el número sobre el que se toma la operación de módulo). Debido a esta deficiencia, los desarrolladores del protocolo SCTP prefirieron CRC32 a este algoritmo , ya que el hash de secuencias cortas de bytes es necesario en el protocolo de red.

Al igual que para CRC32 , para Adler-32 se puede construir fácilmente una colisión , es decir, para un hash determinado, encontrar otros datos de origen que tengan el mismo valor de función.

Tiene una ventaja sobre CRC32 en que es más rápido de calcular en software.

Ejemplo de implementación en lenguaje C

Una implementación simple del algoritmo en lenguaje C es el siguiente código:

uint32_t adler32 ( const char sin signo * buf , size_t buf_length ) { uint32_t s1 = 1 ; uint32_t s2 = 0 ; mientras ( buf_longitud -- ) { s1 = ( s1 + * ( buf ++ ) ) % 65521 ; s2 = ( s2 + s1 ) % 65521 ; } retorno ( s2 << 16 ) + s1 ; }

Vea el código de la biblioteca zlib para una implementación eficiente .

Adler-32 en otros lenguajes de programación

Notas

  1. ↑ Adler32 (Plataforma Java SE 8) . Fecha de acceso: 24 de diciembre de 2015. Archivado desde el original el 25 de diciembre de 2015.
  2. ↑ Resumen::Adler32 en CPAN . Fecha de acceso: 12 de enero de 2014. Archivado desde el original el 12 de enero de 2014.
  3. ↑ Código Adler32 Archivado el 4 de noviembre de 2007 en Wayback Machine . Archivado el 4 de noviembre de 2007.

Literatura

 Funciones hash
propósito general
Criptográfico
Funciones de generación de claves
Número de cheque ( comparación )
Hachís