Adler-32

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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

Caractéristiques[modifier | modifier le code]

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][modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

  • 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[modifier | modifier le code]

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[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Références[modifier | modifier le code]

  1. (en) http://tools.ietf.org/html/rfc3309
  2. (en) http://tools.ietf.org/html/rfc1950 RFC1950