Adler-32 es un algoritmo de suma de comprobación que fue escrito por Mark Adler en 1995, [1] y es una modificación de la suma de comprobación de Fletcher . En comparación con una verificación de redundancia cíclica de la misma longitud, intercambia confiabilidad por velocidad (prefiriendo la última). Adler-32 es más confiable que Fletcher-16 y un poco menos confiable que Fletcher-32 . [2]
Historia
La suma de comprobación de Adler-32 es parte de la biblioteca de compresión zlib ampliamente utilizada , ya que ambas fueron desarrolladas por Mark Adler . En la utilidad rsync se utiliza una versión de " suma de comprobación progresiva " de Adler-32 .
El algoritmo
Una suma de comprobación de Adler-32 se obtiene calculando dos sumas de comprobación A y B de 16 bits y concatenando sus bits en un entero de 32 bits. A es la suma de todos los bytes del flujo más uno, y B es la suma de los valores individuales de A de cada paso.
Al comienzo de una ejecución de Adler-32, A se inicializa a 1, B a 0. Las sumas se realizan en módulo 65521 (el número primo más grande menor que 2 16 ). Los bytes se almacenan en orden de red ( big endian ), ocupando B los dos bytes más significativos.
La función puede expresarse 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 × D 1 + ( n −1) × D 2 + ( n −2) × D 3 + ... + D n + n (mod 65521)Adler-32 ( D ) = B × 65536 + A
donde D es la cadena de bytes para los que la suma de comprobación se calcula, y n es la longitud de D .
Ejemplo
La suma de Adler-32 de la cadena ASCII " Wikipedia
" se calcularía de la siguiente manera:
Personaje | código ASCII | A | B | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
(mostrado como base 10) | |||||||||||
W | 87 | 88 | 88 | ||||||||
I | 105 | 193 | 281 | ||||||||
k | 107 | 300 | 581 | ||||||||
I | 105 | 405 | 986 | ||||||||
pag | 112 | 517 | 1503 | ||||||||
mi | 101 | 618 | 2121 | ||||||||
D | 100 | 718 | 2839 | ||||||||
I | 105 | 823 | 3662 | ||||||||
a | 97 | 920 | 4582 |
A = 920 = 0x398 (base 16)B = 4582 = 0x11E6Salida = 0x11E6 << 16 + 0x398 = 0x11E60398
La operación de módulo no tuvo efecto en este ejemplo, ya que ninguno de los valores alcanzó 65521.
Comparación con la suma de comprobación de Fletcher
La primera diferencia entre los dos algoritmos es que las sumas de Adler-32 se calculan módulo un número primo, mientras que las sumas de Fletcher se calculan módulo 2 4 -1, 2 8 -1 o 2 16 -1 (dependiendo del número de bits utilizados) , que son todos números compuestos . El uso de un número primo hace posible que Adler-32 detecte diferencias en ciertas combinaciones de bytes que Fletcher no puede detectar.
La segunda diferencia, que tiene el mayor efecto sobre la velocidad del algoritmo, es que las sumas de Adler se calculan en bytes de 8 bits en lugar de palabras de 16 bits , lo que da como resultado el doble de iteraciones de bucle. Esto da como resultado que la suma de comprobación de Adler-32 tome entre una y media y dos veces más que la suma de comprobación de Fletcher para datos alineados con palabras de 16 bits. Para datos alineados por bytes, Adler-32 es más rápido que una suma de verificación de Fletcher implementada correctamente (por ejemplo, una que se encuentra en el formato de datos jerárquico ).
Implementación de ejemplo
En C , una implementación ineficiente pero sencilla es:
const uint32_t MOD_ADLER = 65521 ;uint32_t adler32 ( unsigned char * data , size_t len ) / * donde data es la ubicación de los datos en la memoria física y len es la longitud de los datos en bytes * / { uint32_t a = 1 , b = 0 ; size_t index ; // Procesar cada byte de los datos en orden para ( índice = 0 ; índice < len ; ++ índice ) { a = ( a + datos [ índice ]) % MOD_ADLER ; b = ( b + a ) % MOD_ADLER ; } retorno ( b << 16 ) | a ; }
Consulte el código fuente de zlib para una implementación más eficiente que requiere una búsqueda y dos adiciones por byte, con las operaciones de módulo diferidas con dos remanentes calculados cada varios miles de bytes, una técnica descubierta por primera vez para las sumas de comprobación de Fletcher en 1988. js-adler32
proporciona una optimización similar, con la adición de un truco que retrasa el cálculo del "15" en 65536 - 65521 para que los módulos se vuelvan más rápidos: se puede demostrar que ((a >> 16) * 15 + (a & 65535)) % 65521
es equivalente a la acumulación ingenua. [3]
Ventajas y desventajas
- Al igual que el CRC-32 estándar , la suma de comprobación Adler-32 se puede falsificar fácilmente y, por lo tanto, no es segura para protegerla contra modificaciones intencionales .
- Es más rápido que CRC-32 en muchas plataformas. [4]
- Adler-32 tiene una debilidad para los mensajes cortos con unos pocos cientos de bytes, porque las sumas de comprobación para estos mensajes tienen una cobertura deficiente de los 32 bits disponibles.
Debilidad
Adler-32 es débil para mensajes cortos porque la suma A no se ajusta. La suma máxima de un mensaje de 128 bytes es 32640, que está por debajo del valor 65521 utilizado por la operación de módulo, lo que significa que aproximadamente la mitad del espacio de salida no se utiliza y la distribución dentro de la parte utilizada no es uniforme. Se puede encontrar una explicación ampliada en RFC 3309 , que exige el uso de CRC32C en lugar de Adler-32 para SCTP , el Protocolo de transmisión de control de flujo. [5] También se ha demostrado que Adler-32 es débil para pequeños cambios incrementales, [6] y también débil para cadenas generadas a partir de un prefijo común y números consecutivos (como nombres de etiquetas autogenerados por generadores de códigos típicos). [7]
Ver también
Notas
- ^ Primera aparición de Adler-32 (consulte ChangeLog y adler32.c)
- ^ Revisando las sumas de comprobación de Fletcher y Adler
- ^ "adler32.js" . Hoja JS. 3 de julio de 2019.
- ^ Theresa C. Maxino, Philip J. Koopman (enero de 2009). "La eficacia de las sumas de comprobación para redes de control integradas" (PDF) . Transacciones IEEE sobre computación segura y confiable .
- ^ RFC 3309
- ^ http://cbloomrants.blogspot.com/2010/08/08-21-10-adler32.html
- ^ http://www.strchr.com/hash_functions
enlaces externos
- RFC 1950 - especificación, contiene código C de ejemplo
- ZLib : implementa la suma de comprobación de Adler-32 en adler32.c
- Chrome : utiliza una implementación SIMD de Adler-32 adler32_simd.c
- RFC 3309 : información sobre la debilidad de los mensajes cortos y el cambio relacionado en SCTP