Rappelons qu'une fonction de hachage calcule le résumé d'un texte, et que ce résumé est très sensible au texte initial (une petite modification du texte provoque une grande modification du résumé). Les 2 algorithmes de hachage les plus utilisés sont le SHA (Secure Hash Algorithm) qui calcule un résumé de 160 bits, et le MD5, qui calcule un résumé de 128 bits. Nous vous présentons ce dernier algorithme, qui se déroule en plusieurs étapes.

• Etape 1 : Complétion
    Le message est constitué de b bits m₁...m_b. On complète le message par un 1, et suffisamment de 0 pour que le message étendu ait une longueur congruente à 448, modulo 512. Puis on ajouteà ce message la valeur de b, codée en binaire sur 64 bits (on a donc b qui peut valoir jusque 2⁶⁴... ce qui est énorme). On obtient donc un message dont la longueur totale est un multiple de 512 bits. On va travailler itérativement sur chacun des blocs de 512 bits.
• Etape 2 : Initialisation
    On définit 4 buffers de 32 bits A,B,C et D, initialisés ainsi (les chiffres sont hexadécimaux, ie a=10, b=11...).

  A=01234567
  B=89abcdef
  C=fedcba98
  D=76543210
  

  On définit aussi 4 fonctions F,G,H et I, qui prennent des arguments codés sur 32 bits, et renvoie une valeur sur 32 bits, les opérations se faisant bit à bit.

  F(X,Y,Z) = (X AND Y) OR (not(X) AND Z)
  G(X,Y,Z) = (X AND Z) OR (Y AND not(Z))
  H(X,Y,Z) = X xor Y xor Z
  I(X,Y,Z) = Y xor (X OR not(Z))
  

  Ce qu'il y a d'important avec ces 4 fonctions et que si les bits de leurs arguments X,Y et Z sont indépendants, les bits du résultat le sont aussi.
• Etape 3 : Calcul itératif
    Pour chaque bloc de 512 bits du texte, on fait les opérations suivantes :
  1. on sauvegarde les valeurs des registres dans AA,BB,CC,DD.
  2. on calcule de nouvelles valeurs pour A,B,C,D à partir de leurs anciennes valeurs, à partir des bits du bloc qu'on étudie, et à partir des 4 fonctions F,G,H,I.
  3. on fait A=AA+A, B=BB+B, C=CC+C, D=DD+D.
  Le détail des calculs se trouve en annexe.
• Etape 4 : Ecriture du résumé
    Le résumé sur 128 bits est obtenu en mettant bout à bout les 4 buffers A,B,C,D de 32 bits.

Et encore, dans la cryptographie expliquée...

• La signature électronique, une des applications essentielles des fontions de hachage.
• Le plan de la partie : Méthodes modernes de cryptographie.