Dipl.-Inform. Carsten Eilers

Claude Shannon hat 1949 in seinem Artikel "Communication Theory of Secrecy Systems" (PDF) zwei Grundprinzipien der Chiffrierung beschrieben: Bei der Konfusion wird der Zusammenhang zwischen Klartext- und Geheimtextzeichen verwischt, wie zum Beispiel bei der einfachen Substitution. Bei der Diffusion werden die Informationen des Klartextes im Geheimtext verteilt.

Stromchiffren

Bei einer Stromchiffre wird ausgehend von einem Schlüssel eine "zufällige" Bitfolge generiert, die meistens über XOR mit dem Klartext verknüpft wird, also wie der Schlüssel eines One-Time-Pads verwendet wird. Die Sicherheit des Verfahrens hängt vollständig von der Generierung der Bitfolge ab. Stromchiffren sind besonders gut zur Online-Verschlüsselung von Nachrichtenkanälen geeignet.

Blockchiffren

Bei einer Blockchiffre werden Gruppen von Bits zu Blöcken zusammengefasst und gemeinsam verschlüsselt. Eine Substitution kann als Blockchiffre mit 8-Bit-Blöcken betrachtet werden, bei polyalphabetischen Substitutionen entspricht die Blocklänge der Periode.

Produktalgorithmen

Bei einem Produktalgorithmus werden mehrere einfache, kryptographisch unsichere Schritte (genannt Runden) nacheinander ausgeführt. Diese Kombination der einfachen Funktionen kann die Sicherheit stark erhöhen. Zum Vergleich nennt Reinhard Wobst in seinem Buch "Abenteuer Kryptologie" (¹) das Lösen von Gleichungen:

Lineare Gleichungen der Form "ax + b = c" sind leicht zu lösen,
für quadratische Gleichungen lernt man die Formel in der Schule, und
für kubische Gleichungen werden bereits mehrere Formeln benötigt.
Die Formeln für Gleichungen 4. Grades sind schon sehr komplex, und
für Gleichungen ab dem 5. Grad gibt es keine allgemeinen Lösungen mehr.

Feistel-Netzwerke

Feistel-Netzwerke wurden erstmals 1973 von Horst Feistel in seinem Artikel "Cryptography and Computer Privacy" (als gescannte Bilder) beschrieben. Sie dienen der Beschreibung einer Runde in einem Produktalgorithmus.

Jeder Block wird in zwei gleich große Hälften geteilt. In der i-ten Runde wird die linke Hälfte des (Klartext-)Blocks als Li-1, die rechte als Ri-1 bezeichnet. Die Verschlüsselungsfunktion f verwendet einen geheimen Schlüssel Si, um aus einem gegebenen (Klartext-)block Ki einen (Geheimtext-)block f(Si, Ki) zu erzeugen. Die eigentliche Verschlüsselung erfolgt dann, indem die beiden Halbblöcke vertauscht und Li-1 mit f(Si, Ri-1) XOR-verknüpft werden:

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

Grafisch lässt sich das ganze wie in Abbildung 1 darstellen.

Abb. 1: Verschlüsselungsrunde eines Feistel-Netzwerks (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(Si, Ri-1)

Zum Entschlüsseln werden Li und Ri 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(Si, Ri-1) ⊕ f(Si, Li) =
Li-1 ⊕  f(Si, Li)  ⊕ f(Si, Li) =: Li-1

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

Abb. 2: Eine Entschlüsselungsrunde eines Feistel-Netzwerks (Klick für großes Bild)

Das Entschlüsselungsprinzip ist unabhängig von Blocklänge und Rundenzahl. Auch die Verschlüsselungsfunktion f(Si, Ki) muss nicht mehr wie bei den klassischen Verfahren umkehrbar sein. Bisher war eine Grundbedingung der kryptographischen Verfahren, dass die Umkehrung der Verschlüsselungsfunktion f(S, K) nur bei Kenntnis des Schlüssels S möglich ist. Bei Feistel-Netzwerken reicht die Forderung, dass ohne Kenntnis des Schlüssels S keine der Funktionen f(Si, Ki) berechnet werden kann. Dies ist eine deutlich einfachere Aufgabe, da auf die Umkehrbarkeit nicht mehr geachtet werden muss.

Feistel-Netzwerke werden in vielen kryptographischen Verfahren eingesetzt, so zum Beispiel in DES oder Blowfish. Das DES-Verfahren wird in der nächsten Folge vorgestellt. Es ist das erste halbwegs aktuelle Verfahren in dieser Reihe - lange Zeit der Standard für die symmetrische Verschlüsselung, gilt es seit einigen Jahren als unsicher (und war es vielleicht schon von Anfang an).

Carsten Eilers

¹ Reinhard Wobst: Abenteuer Kryptologie. 3. Auflage. Addison-Wesley, München 2003, ISBN 3-8273-1815-7