Aller au contenu principal

3. MD5 Algorithm Description (Description de l'algorithme MD5)

Nous commençons en supposant que nous avons un message de b bits en entrée et que nous souhaitons trouver son hachage de message (Message Digest). Ici, b est un entier non négatif arbitraire ; b peut être zéro, il n'est pas nécessaire qu'il soit un multiple de huit, et il peut être arbitrairement grand. Nous imaginons les bits du message écrits comme suit :

m_0 m_1 ... m_{b-1}

Les cinq étapes suivantes sont effectuées pour calculer le hachage de message du message.

3.1 Step 1. Append Padding Bits (Étape 1. Ajouter des bits de remplissage)​

Le message est « rempli » (étendu) de sorte que sa longueur (en bits) soit congrue à 448, modulo 512. C'est-à-dire que le message est étendu de sorte qu'il soit juste 64 bits en deçà d'être un multiple de 512 bits de long. Le remplissage est toujours effectué, même si la longueur du message est déjà congrue à 448, modulo 512.

Le remplissage est effectué comme suit : un seul bit « 1 » est ajouté au message, puis des bits « 0 » sont ajoutés de sorte que la longueur en bits du message rempli devienne congrue à 448, modulo 512. Au total, au moins un bit et au plus 512 bits sont ajoutés.

3.2 Step 2. Append Length (Étape 2. Ajouter la longueur)​

Une représentation de 64 bits de b (la longueur du message avant l'ajout des bits de remplissage) est ajoutée au résultat de l'étape précédente. Dans le cas improbable où b est supérieur à 2^64, alors seuls les 64 bits de poids faible de b sont utilisés. (Ces bits sont ajoutés sous forme de deux mots de 32 bits et ajoutés avec le mot de poids faible en premier conformément aux conventions précédentes.)

À ce stade, le message résultant (après remplissage avec des bits et avec b) a une longueur qui est un multiple exact de 512 bits. De manière équivalente, ce message a une longueur qui est un multiple exact de 16 mots (de 32 bits). Soit M[0 ... N-1] désignant les mots du message résultant, où N est un multiple de 16.

3.3 Step 3. Initialize MD Buffer (Étape 3. Initialiser le tampon MD)​

Un tampon de quatre mots (A, B, C, D) est utilisé pour calculer le hachage de message. Ici, chacun de A, B, C, D est un registre de 32 bits. Ces registres sont initialisés aux valeurs suivantes en hexadécimal, octet de poids faible en premier) :

word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10

3.4 Step 4. Process Message in 16-Word Blocks (Étape 4. Traiter le message par blocs de 16 mots)​

Nous définissons d'abord quatre fonctions auxiliaires qui prennent chacune en entrée trois mots de 32 bits et produisent en sortie un mot de 32 bits.

F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))

Dans chaque position de bit, F agit comme une conditionnelle : si X alors Y sinon Z. La fonction F aurait pu être définie en utilisant + au lieu de v puisque XY et not(X)Z n'auront jamais de 1 dans la même position de bit. Il est intéressant de noter que si les bits de X, Y et Z sont indépendants et non biaisés, chaque bit de F(X,Y,Z) sera indépendant et non biaisé.

Les fonctions G, H et I sont similaires à la fonction F, en ce sens qu'elles agissent en « parallèle bit à bit » pour produire leur sortie à partir des bits de X, Y et Z, de telle manière que si les bits correspondants de X, Y et Z sont indépendants et non biaisés, alors chaque bit de G(X,Y,Z), H(X,Y,Z) et I(X,Y,Z) sera indépendant et non biaisé. Notez que la fonction H est la fonction « xor » ou « parité » bit à bit de ses entrées.

Cette étape utilise une table de 64 éléments T[1 ... 64] construite à partir de la fonction sinus. Soit T[i] désignant le i-ème élément de la table, qui est égal à la partie entière de 4294967296 fois abs(sin(i)), où i est en radians. Les éléments de la table sont donnés en annexe.

Effectuez ce qui suit :

/* Traiter chaque bloc de 16 mots. */
For i = 0 to N/16-1 do

  /* Copier le bloc i dans X. */
  For j = 0 to 15 do
    Set X[j] to M[i*16+j].
  end /* of loop on j */

  /* Sauvegarder A en AA, B en BB, C en CC et D en DD. */
  AA = A
  BB = B
  CC = C
  DD = D

  /* Round 1. */
  /* Soit [abcd k s i] désignant l'opération
       a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
  /* Effectuer les 16 opérations suivantes. */
  [ABCD  0  7  1]  [DABC  1 12  2]  [CDAB  2 17  3]  [BCDA  3 22  4]
  [ABCD  4  7  5]  [DABC  5 12  6]  [CDAB  6 17  7]  [BCDA  7 22  8]
  [ABCD  8  7  9]  [DABC  9 12 10]  [CDAB 10 17 11]  [BCDA 11 22 12]
  [ABCD 12  7 13]  [DABC 13 12 14]  [CDAB 14 17 15]  [BCDA 15 22 16]

  /* Round 2. */
  /* Soit [abcd k s i] désignant l'opération
       a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
  /* Effectuer les 16 opérations suivantes. */
  [ABCD  1  5 17]  [DABC  6  9 18]  [CDAB 11 14 19]  [BCDA  0 20 20]
  [ABCD  5  5 21]  [DABC 10  9 22]  [CDAB 15 14 23]  [BCDA  4 20 24]
  [ABCD  9  5 25]  [DABC 14  9 26]  [CDAB  3 14 27]  [BCDA  8 20 28]
  [ABCD 13  5 29]  [DABC  2  9 30]  [CDAB  7 14 31]  [BCDA 12 20 32]

  /* Round 3. */
  /* Soit [abcd k s t] désignant l'opération
       a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
  /* Effectuer les 16 opérations suivantes. */
  [ABCD  5  4 33]  [DABC  8 11 34]  [CDAB 11 16 35]  [BCDA 14 23 36]
  [ABCD  1  4 37]  [DABC  4 11 38]  [CDAB  7 16 39]  [BCDA 10 23 40]
  [ABCD 13  4 41]  [DABC  0 11 42]  [CDAB  3 16 43]  [BCDA  6 23 44]
  [ABCD  9  4 45]  [DABC 12 11 46]  [CDAB 15 16 47]  [BCDA  2 23 48]

  /* Round 4. */
  /* Soit [abcd k s t] désignant l'opération
       a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
  /* Effectuer les 16 opérations suivantes. */
  [ABCD  0  6 49]  [DABC  7 10 50]  [CDAB 14 15 51]  [BCDA  5 21 52]
  [ABCD 12  6 53]  [DABC  3 10 54]  [CDAB 10 15 55]  [BCDA  1 21 56]
  [ABCD  8  6 57]  [DABC 15 10 58]  [CDAB  6 15 59]  [BCDA 13 21 60]
  [ABCD  4  6 61]  [DABC 11 10 62]  [CDAB  2 15 63]  [BCDA  9 21 64]

  /* Puis effectuer les additions suivantes. (C'est-à-dire incrémenter chacun
     des quatre registres de la valeur qu'il avait avant le début de ce bloc.) */
  A = A + AA
  B = B + BB
  C = C + CC
  D = D + DD

end /* of loop on i */

3.5 Step 5. Output (Étape 5. Sortie)​

Le hachage de message produit en sortie est A, B, C, D. C'est-à-dire que nous commençons par l'octet de poids faible de A et terminons par l'octet de poids fort de D.

Ceci termine la description de MD5. Une implémentation de référence en C est donnée en annexe.

Dernière mise à jour le