Accueil🇫🇷Chercher

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

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.