Dipl.-Inform. Carsten Eilers

Aus dem Schlüssel werden die 16 Teilschlüssel K₁ bis K₁₆ erzeugt, einer für jede Iterationsrunde.

Der Ablauf des DES-Algorithmus sieht dann wie in Abbildung 1 aus.

Abb. 1: Ablauf des DES-Algorithmus (Klick für großes Bild)

Die Iterationsrunden

Die Iterationsrunden entsprechen den Runden der Feistel-Netzwerke. Die für die Entschlüsselung notwendige Vertauschung erfolgt nach der 16. Iterationsrunde, der DES-Algorithmus kann also unverändert sowohl zur Ver- als auch Entschlüsselung genutzt werden. Die zum Entschlüsseln notwendige Umkehrung der Reihenfolge der Iterationen erfolgt durch die Umkehrung der Reihenfolge der Teilschlüssel K_i.

Jeder Iterationsrunde i erhält als Eingabe die beiden Blöcke L_i-1 und R_i-1. Die Verschlüsselungsfunktion f verwendet den geheimen Schlüssel K_i, um aus dem gegebenen Block R_i-1 einen (Geheimtext-)block f(R_i-1, K_i) zu erzeugen. Die eigentliche Verschlüsselung erfolgt dann, indem die beiden Halbblöcke vertauscht und L_i-1 mit f(R_i-1, K_i) XOR-verknüpft wird:

Li := Ri-1
Ri := Li-1 ⊕ f(Ri-1, Ki)

Grafisch lässt sich das ganze wie in Abbildung 2 darstellen:

Abb. 2: Eine Iterationsrunde von DES (Klick für großes Bild)

Für die Entschlüsselung muss dieser Prozess umgekehrt werden. Das Ergebnis von Runde i ist

Li := Ri-1
Ri := Li-1 ⊕ f(Ri-1, Ki)

Zum Entschlüsseln werden L_i und R_i getauscht, außerdem wird der Rundenindex i rückwärts statt vorwärts gezählt. Führt man die Runde erneut durch, so ergibt sich

Li =: Ri-1

Li-1 ⊕ f(Ri-1, Ki) ⊕ f(Li, Ki) = 
Li-1 ⊕  f(Li, Ki)  ⊕ f(Li, Ki) =: Li-1

Grafisch lässt sich das ganze wie in Abbildung 3 darstellen:

Abb. 3: Eine Entschlüsselungsrunde von DES (Klick für großes Bild)

Die Verschlüsselungsfunktion

Die Verschlüsselungsfunktion von DES läuft wie in Abbildung 4 gezeigt ab.

Abb. 4: Die Verschlüsselungsfunktion von DES (Klick für großes Bild)

Der 32-Bit-Block R_i-1 wird durch die Expansionspermutation E auf 48 Bit erweitert. Während eine Permutation einzelne Eingabewerte vertauscht, ohne ihre Werte oder Gesamtzahl zu verändern, kommen bei einer Expansionspermutation manche Eingabewerte mehrfach in der Ausgabe vor.

Danach wird der 48 Bit lange Teilschlüssel K_i bitweise modulo 2 hinzuaddiert.

Die Summe wird in acht 6-Bit-Blöcke aufgeteilt, mit denen jeweils ein 4-Bit-Wert aus einer der Substitutionsboxen S₁ bis S₈ (S-Boxen, substitution box) ausgewählt wird. Diese Substitutionsboxen ordnen Werten von 6-Bit-Blöcken Werte von 4-Bit-Blöcken zu und sorgen so für Nichtlinearität.

Die sich ergebenden acht 4-Bit-Werte werden zu einem 32-Bit-Wert zusammengefasst. Auf das Ergebnis wird die Permutation P angewendet, die dann das Ergebnis liefert. P mischt die Ausgaben der 8 Substitutionsboxen, damit in der nächsten Runde die Ausgabe jeder Substitutionsbox in mehrere Substitutionsboxen eingeht.

Die Teilschlüsselerzeugung

Die Erzeugung der Teilschlüssel läuft wie in Abbildung 5 gezeigt ab.

Abb. 5: Die Erzeugung der Teilschlüssel (Klick für großes Bild)

Eine permutierende Auswahlfunktion PC-1 (PC = permuted choice) wählt aus dem 64-Bit-Schlüssel 56 Bits aus und teilt sie auf die beiden 28-Bit-Blöcke C₀ und D₀ auf.

C_i und D_i (i = 1, .., 16) werden erzeugt, indem die Bits in C_i-1 und D_i-1 abhängig von i um 1 oder 2 Stellen nach links rotiert werden (zyklischer Linksshift LS_i).

Die Teilschlüssel K_i werden dann gebildet, indem C_i und D_i verbunden und daraus durch die permutierende Auswahlfunktion PC-2 48 Bits ausgewählt werden.

Die S-Boxen

Jede S-Box ist eine Tabelle mit 4 Zeilen und 16 Spalten. Wenn die Eingabe aus den 6 Bits b₁, ... b₆ besteht, bestimmt die aus b₁ und b₂ gebildete Zahl (2 Bits = 4 Werte) die Tabellenzeile, die aus b₃ bis b₆ gebildete Zahl die Tabellenspalte. Die Zahl in der entsprechenden Zeile und Spalte wird ausgegeben.

Die S-Box S₁ sieht zum Beispiel so aus:

Spalte   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
Zeile
0       14   4  13   1   2  15  11   8   3  10   6  12   5   9   0   7
1        0  15   7   4  14   2  13   1  10   6  12  11   9   5   3   8
2        4   1  14   8  13   6   2  11  15  12   9   7   3  10   5   0
3       15  12   8   2   4   9   1   7   5  11   3  14  10   0   6  13

Die S-Boxen sind ebenso wie die Permutationen und LS_i Teil des Standards.

Da es schwierig ist, die S-Boxen so zu entwerfen, dass der entstehende Algorithmus kryptologisch sicher ist, hat ihre Berechnung einige Monate gedauert. Und danach hat die NSA sie dann noch überarbeitet, siehe die Geschichte von DES.

Ihre Entwurfskriterien wurden anfangs geheim gehalten und erst nach der Entdeckung der differentiellen Kryptanalyse durch durch Eli Biham und Adi Shamir ("Differential Cryptanalysis of DES-like Cryptosystems", Download als .PS.GZ) veröffentlicht. Sie sind zum Beispiel in Bruce Schneiers Buch "Applied Cryptography" nachzulesen.

In der nächsten Folge geht es noch einmal um die Unsicherheit von DES: Außer Brute-Force-Angriffen sind auch Angriffe über Kryptanalyse möglich. Außerdem werden Verbesserungen und einige Beispiele für Anwendungen des Algorithmus vorgestellt.

Carsten Eilers