Feistel-Netzwerke

Feistel-Netzwerke sind die Grundlage vieler moderner Blockchiffren; sie werden z.B. in DES, Blowfish, Twofish, CAST, FEAL, MARS, Khufu, Khafre, LOKI, GOST u.a. verwendet. Das Konzept wurde von dem IBM-Mitarbeiter Horst Feistel entwickelt. Das Prinzip ist sehr einfach:

Der Eingabetext wird zunächst in gleich große Verschlüsselungsblocks aufgeteilt (oft z.B. 64 Bit; in diesem Programm sind es der Übersichtlichkeit halber nur 32 Bit). Jeder Block wird dann noch einmal in zwei gleich große Hälften L und R geteilt. Die Chiffrierung erfolgt dann iterativ in mehreren Runden, indem die Ausgabe der (i+1)-ten Runde durch die der i-ten Runde bestimmt wird. Hierbei wird jeweils der rechte und linke Block getauscht; der rechte Block aus Runde (i-1) wird zum linken Block in Runde i, der linke Block aus der Runde (i-1) wird in der Runde i zum rechten Block. Der rechte Block (und nur dieser!) wird zusätzlich mit einem Wert XOR-verknüpft, der aus dem aktuellen Rundenschlüssel und der rechten Hälfte der Runde (i-1) (die nun in die linke Hälfte gewandert ist), mittels einer algorithmusspezifischen nichtlinearen Funktion f(R,K) gewonnen wird:

   Li = Ri-1
   Ri = Li-1 ⊕ f(Ri-1,Ki)
wobei ⊕ den XOR-Operator bezeichnet, f(R,K) eine beliebige (nichtlineare) Funktion ist und Ki der Rundenschlüssel der i-ten Runde ist; dieser wird vor der Verschlüsselung aus dem vorgegebenen Schlüssel berechnet.

Der große Vorteil von Feistel-Netzwerken ist, daß die Funktion f(R,K) beliebig kompliziert sein kann; sie muß (zur Dechiffrierung) nicht einmal umkehrbar sein. Man nutzt einfach die Tatsache, daß eine zweimal angewandte XOR-Verknüpfung wieder den urspünglichen Wert ergibt:

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

Für die praktische Realisierung bietet es sich an, bei der Dechiffrierung vor und nach der Operation den linken und rechten Block zu vertauschen. Dann lässt sich die Chiffrierungs-Routine auch für die Dechiffrierung benutzen, indem einfach die Reihenfolge der Rundenschlüssel invertiert wird.

In diesem Skript wird sowohl für die Rundenfunktion als auch für die Schlüsselfunktion ein Polynom 8. Grades benutzt. Die Funktionen sind willkürlich gewählt; es könnte auch eine beliebige andere Funktion benutzt werden. Bei der Rundenfunktion f(R,K) ist nur wichtig, daß sie (nicht zu schwach) nichtlinear ist, da die Sicherheit des Algorithmus durch die Wahl dieser Funktion bestimmt wird.

Es ist möglich, sich die Differenz zur letzten Ein- bzw. Ausgabe zeigen zu lassen. Die Differenz ist dabei definiert als XOR-Verknüpfung zwischen den beiden Werten; d.h., an allen Stellen, an denen sich ein Bit geändert hat, wird das Differenzbit gesetzt.

Die Eingabe kann wahlweise als Zahl oder als Bitmaske (mit den Checkboxen) erfolgen. Zur besseren Übersicht können die Eingabefelder und die Einleitung ausgeblendet werden.


Eingabe (Hex-Zahl):     
Schlüssel (Hex-Zahl):
Anzahl Runden:
Rundenfunktion:f = * (Ki*Li)8 + * (Ki*Li)6 + * (Ki*Li)4 + * (Ki*Li)2 + mod 65537
Schlüsselfunktion:Ki+1 = * Ki8 + * Ki6 + * Ki4 + * Ki2 + mod 65521

  ausführliche Ausgaben      Differenzen anzeigen      Eingabefelder ausblenden      Einführung ausblenden

Zurück zur Hauptseite


Entschlüsselung:
Bit:313029282726252423222120191817161514131211109876543210
L00000000000000000   R00000000000000000   0000:0000
L10000000000000000   R10000000000000001   0000:0001
L20000000000000001   R20000000000000101   0001:0005
L30000000000000101   R30001110100000010   0005:1D02
L40001110100000010   R40101111101000101   1D02:5F45
L50101111101000101   R51111010001111001   5F45:F479
L61111010001111001   R60110100100111010   F479:693A
L70110100100111010   R70110100001100010   693A:6862
L80110100001100010   R81111000100111110   6862:F13E
L91111000100111110   R91100001111011111   F13E:C3DF
L101100001111011111   R100101001010111101   C3DF:52BD