Adler-32

Adler-32 est une fonction de hashage inventée par Mark Adler et dérivée de la fonction de Fletcher.

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 sommes de contrôle de 16 bits, nommées 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 faible.

Optimisation

En calculant s1 et s2 sur 32 bits, on peut factoriser le calcul du modulo 65521 tous les 5552 octets de données.

Si on calcule sur 16 bits, un moyen simple de faire une somme modulo 65521 est qu'en cas de retenue on ajoute 15 (qui est 2**16 modulo 65521), et encore 15 si une nouvelle retenue est générée. À la fin (quand il faut générer la somme de contrôle), si la valeur sur 16 bits dépasse 65521, on retranche 65521 de la valeur.

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

Références
  1. (en) http://tools.ietf.org/html/rfc3309
  2. (en) http://tools.ietf.org/html/rfc1950 RFC1950
  • Portail de l’informatique
  • Portail des mathématiques
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.