- Adler-32
-
Adler-32 est une fonction de hashage inventée par Mark Adler et dérivée de la fonction de Fletcher.
Sommaire
Caractéristiques
Adler-32 est une fonction rapide à calculer, notamment sans support matériel, ce qui lui donne un avantage de vitesse sur CRC-32.
Elle est cependant facile à collisioner, ce qui limite son usage à la détection de corruptions non intentionnelles.
Adler-32 est peu fiable sur de petites quantités de données ; elle est notamment moins robuste que CRC-32[1].
Algorithme[2]
La valeur Adler-32 est composée de deux checksum 16-bits s1 et s2.
- s1 est initialisée à 1 et fait la somme des octets de données modulo 65521.
- s2 est initialisée à 0 et fait la somme des valeurs successives de s1 modulo 65521.
La valeur finale 32 bits est obtenue en plaçant s2 dans les 16-bits de poids fort, et s1 dans les 16-bits de poids faibles.
Optimisation
En calculant s1 et s2 sur 32-bits, on peut factoriser le calcul du modulo 65521 tous les 5552 octets de données.
Améliorations par rapport à la somme de Fletcher
- La somme de Fletcher est sur 16-bits (s1 et s2 étant sur 8-bits chacun)
- Fletcher utilise un modulo 255, ce qui ne permet pas de détecter un octet qui serait passé de la valeur 0 à la valeur 255, ou inversement. L'utilisation du nombre premier 65521 comme modulo empêche la non-détection d'une erreur sur un seul octet, et la probabilité de non-détection d'une erreur sur plusieurs octets devient très faible, quoique non nulle.
- Fletcher initialise les deux sommes à 0. L'initialisation de s1 à 1 permet d'intégrer la taille des données dans le calcul. (Une séquence de caractères nuls a toujours une somme de Fletcher de 0, ce qui n'est plus le cas d'une somme Adler-32.)
Implémentations
L'implémentation de référence de Adler-32 est celle présente dans la bibliothèque de compression de données Zlib, également développée par Mark Adler.
Voir aussi
Articles connexes
Liens externes
- (en) RFC1950
Références
- (en) http://tools.ietf.org/html/rfc3309
- (en) http://tools.ietf.org/html/rfc1950 RFC1950
Catégories :- Algorithme de hachage
- Somme de contrôle
Wikimedia Foundation. 2010.
