Zum Hauptinhalt springen

3. MD5 Algorithm Description (MD5-Algorithmusbeschreibung)

Wir beginnen mit der Annahme, dass wir eine b-Bit-Nachricht als Eingabe haben und dass wir ihren Message-Digest finden möchten. Hier ist b eine beliebige nichtnegative ganze Zahl; b kann null sein, es muss kein Vielfaches von acht sein, und es kann beliebig groß sein. Wir stellen uns die Bits der Nachricht wie folgt geschrieben vor:

m_0 m_1 ... m_{b-1}

Die folgenden fünf Schritte werden durchgeführt, um den Message-Digest der Nachricht zu berechnen.

3.1 Step 1. Append Padding Bits (Schritt 1. Padding-Bits anhängen)​

Die Nachricht wird „aufgefüllt" (erweitert), sodass ihre Länge (in Bits) kongruent zu 448, modulo 512 ist. Das heißt, die Nachricht wird so erweitert, dass sie genau 64 Bits weniger als ein Vielfaches von 512 Bits lang ist. Das Padding wird immer durchgeführt, auch wenn die Länge der Nachricht bereits kongruent zu 448, modulo 512 ist.

Das Padding wird wie folgt durchgeführt: Ein einzelnes „1"-Bit wird der Nachricht hinzugefügt, und dann werden „0"-Bits hinzugefügt, sodass die Länge in Bits der aufgefüllten Nachricht kongruent zu 448, modulo 512 wird. Insgesamt werden mindestens ein Bit und höchstens 512 Bits hinzugefügt.

3.2 Step 2. Append Length (Schritt 2. Länge anhängen)​

Eine 64-Bit-Darstellung von b (die Länge der Nachricht vor dem Hinzufügen der Padding-Bits) wird dem Ergebnis des vorherigen Schritts hinzugefügt. In dem unwahrscheinlichen Fall, dass b größer als 2^64 ist, werden nur die niederwertigen 64 Bits von b verwendet. (Diese Bits werden als zwei 32-Bit-Wörter hinzugefügt und das niederwertige Wort wird gemäß den vorherigen Konventionen zuerst hinzugefügt.)

An diesem Punkt hat die resultierende Nachricht (nach dem Padding mit Bits und mit b) eine Länge, die ein exaktes Vielfaches von 512 Bits ist. Äquivalent dazu hat diese Nachricht eine Länge, die ein exaktes Vielfaches von 16 (32-Bit-) Wörtern ist. Seien M[0 ... N-1] die Wörter der resultierenden Nachricht, wobei N ein Vielfaches von 16 ist.

3.3 Step 3. Initialize MD Buffer (Schritt 3. MD-Puffer initialisieren)​

Ein Vier-Wort-Puffer (A, B, C, D) wird verwendet, um den Message-Digest zu berechnen. Hier ist jedes von A, B, C, D ein 32-Bit-Register. Diese Register werden auf die folgenden Werte in Hexadezimal initialisiert (niederwertiges Byte zuerst):

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 (Schritt 4. Nachricht in 16-Wort-Blöcken verarbeiten)​

Wir definieren zunächst vier Hilfsfunktionen, die jeweils als Eingabe drei 32-Bit-Wörter nehmen und als Ausgabe ein 32-Bit-Wort erzeugen.

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))

In jeder Bitposition wirkt F als bedingt: wenn X dann Y sonst Z. Die Funktion F hätte mit + anstelle von v definiert werden können, da XY und not(X)Z niemals 1en in derselben Bitposition haben werden. Es ist interessant zu bemerken, dass wenn die Bits von X, Y und Z unabhängig und unverzerrt sind, jedes Bit von F(X,Y,Z) unabhängig und unverzerrt sein wird.

Die Funktionen G, H und I sind ähnlich zur Funktion F, indem sie „bitweise parallel" wirken, um ihre Ausgabe aus den Bits von X, Y und Z zu erzeugen, sodass wenn die entsprechenden Bits von X, Y und Z unabhängig und unverzerrt sind, dann jedes Bit von G(X,Y,Z), H(X,Y,Z) und I(X,Y,Z) unabhängig und unverzerrt sein wird. Beachten Sie, dass die Funktion H die bitweise „xor"- oder „Paritäts"-Funktion ihrer Eingaben ist.

Dieser Schritt verwendet eine 64-Elemente-Tabelle T[1 ... 64], die aus der Sinusfunktion konstruiert wird. Sei T[i] das i-te Element der Tabelle, das gleich dem ganzzahligen Teil von 4294967296 mal abs(sin(i)) ist, wobei i in Radiant ist. Die Elemente der Tabelle sind im Anhang angegeben.

Führen Sie Folgendes aus:

/* Jeden 16-Wort-Block verarbeiten. */
For i = 0 to N/16-1 do

  /* Block i in X kopieren. */
  For j = 0 to 15 do
    Set X[j] to M[i*16+j].
  end /* of loop on j */

  /* A als AA, B als BB, C als CC und D als DD speichern. */
  AA = A
  BB = B
  CC = C
  DD = D

  /* Runde 1. */
  /* Sei [abcd k s i] die Operation
       a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
  /* Die folgenden 16 Operationen durchführen. */
  [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]

  /* Runde 2. */
  /* Sei [abcd k s i] die Operation
       a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
  /* Die folgenden 16 Operationen durchführen. */
  [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]

  /* Runde 3. */
  /* Sei [abcd k s t] die Operation
       a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
  /* Die folgenden 16 Operationen durchführen. */
  [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]

  /* Runde 4. */
  /* Sei [abcd k s t] die Operation
       a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
  /* Die folgenden 16 Operationen durchführen. */
  [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]

  /* Dann die folgenden Additionen durchführen. (Das heißt, jedes der vier 
     Register um den Wert inkrementieren, den es hatte, bevor dieser Block
     gestartet wurde.) */
  A = A + AA
  B = B + BB
  C = C + CC
  D = D + DD

end /* of loop on i */

3.5 Step 5. Output (Schritt 5. Ausgabe)​

Der als Ausgabe erzeugte Message-Digest ist A, B, C, D. Das heißt, wir beginnen mit dem niederwertigen Byte von A und enden mit dem höchstwertigen Byte von D.

Dies schließt die Beschreibung von MD5 ab. Eine Referenzimplementierung in C ist im Anhang angegeben.

Letztes Update am