Grundlagen der Kryptographie, Teil 6: Feistel-Netzwerke
Ab dieser Folge lernen Sie aktuell eingesetzte kryptographische Verfahren kennen. Während bisher mit Ausnahme der bitweisen Vigenère-Verschlüsselung zeichenorientierte Verfahren behandelt wurden, wird in den nun folgenden Verfahren in der Regel bitweise gearbeitet. Bevor es aber richtig los gehen kann müssen erst wieder einige Grundbegriffe erklärt werden:
Konfusion und Diffusion
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" (1) 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).
1 Reinhard Wobst: Abenteuer Kryptologie. 3. Auflage. Addison-Wesley, München 2003, ISBN 3-8273-1815-7
Trackbacks
Dipl.-Inform. Carsten Eilers am : Kryptographie - Ein Überblick
Vorschau anzeigen