Feistelchiffre


aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Feistelchiffre, auch als Feistelnetzwerk bezeichnet, ist eine allgemeine Struktur, mit der Blockchiffren realisiert werden können. Ein Mitarbeiter von IBM, Horst Feistel, gilt als der Erfinder dieser Chiffre. Er arbeitete in den 1970er Jahren mit anderen am sog. Projekt „Lucifer“, dessen Ziel es war, eine effiziente Verschlüsselungstechnologie zu entwickeln. Die Feistelchiffre war später dann die Grundlage für den DES-Algorithmus.

Viele moderne symmetrische Verschlüsselungsalgorithmen basieren auf Feistelnetzwerken. Dies rührt daher, dass Blockverschlüsselungen, welche auf Feistelnetzwerken basieren, garantiert umkehrbar (bijektiv) sind. Damit ist die notwendige Grundbedingung für Blockchiffren erfüllt, dass es bei der Abbildung von Chiffreblöcken auf Klartextblöcke bei der Entschlüsselung zu keinen Mehrdeutigkeiten kommen darf. Weiterhin wurde diese Struktur von sehr vielen Kryptografen analysiert und für gut befunden.

Arbeitsweise

Datei:Feistel.png
Struktur einer Feistelchiffre

Wie es der Name „Blockchiffre“ schon nahelegt, operiert die Chiffre auf einem Klartextblock. Die Größe eines Blocks hängt vom jeweiligen Verschlüsselungsverfahren ab, oft ist sie ein Vielfaches von 64 Bit. Ein Block wird zuerst in zwei (meist gleich große) Teile (<math>L_1</math> und <math>R_1</math>) geteilt und in <math>n</math> Runden verarbeitet. In jeder Runde wird auf den einen Teil die Ausgabe einer vom Rundenschlüssel abhängigen Rundenfunktion des anderen Teils addiert. Innerhalb der <math>i</math>-ten Runde (<math>i</math> läuft von 1 bis <math>n</math>) wird folgende Formel angewendet:

<math>L_{i+1} \!\, = R_i</math>
<math>R_{i+1} \!\, = L_i \oplus F(R_i, K_i)</math>

Dabei bildet <math>F</math> die sog. Runden- oder Transformationsfunktion und <math>K_1</math> bis <math>K_n</math> sind die Rundenschlüssel. <math>\oplus</math> steht für das bitweise XOR, das mit seiner Umkehrung identisch ist. Der verschlüsselte Text am Ende der Runden ist die Zusammenführung <math>C = \left(L_{n+1},R_{n+1}\right).</math>

Feistelnetzwerke ermöglichen eine Entschlüsselung, ohne dass die Umkehrfunktion von <math>F</math> benötigt wird. Will man einen Geheimtext dechiffrieren, wendet man die Umkehrung der obigen Formel an, wobei man <math>i</math> von <math>n</math> bis 1 laufen lässt:

<math>R_i \!\, = L_{i+1}</math>
<math>L_i \!\, = R_{i+1} \oplus F(L_{i+1}, K_i)</math>

Variante

Manche Verfahren verknüpfen auch die Rundenschlüssel direkt mit den Textteilen, und die Rundenfunktion <math>F</math> ist dann (meist) nicht vom Schlüssel abhängig:

<math>L_{i+1} \!\, = R_i \circ K_i</math>
<math>R_{i+1} \!\, = L_i \oplus F(L_{i+1})</math>

<math>\oplus</math> und <math>\circ</math> stehen wiederum für (nicht unbedingt verschiedene) einfach invertierbare Verknüpfungen.

Interner Zustand

Ein balanciertes Feistelnetzwerk (BFN) liegt dann vor, wenn die beiden Hälften, die in die Rundenfunktion eingehen, gleich groß sind. Von einem unbalancierten (nicht-balancierten) Feistelnetzwerk (UFN) spricht man, wenn entweder die beiden Hälften nicht gleich groß sind oder aus einem Block für die Rundenfunktion mehr als zwei Teile gebildet werden.

Anwendungen

Feistelnetzwerke kommen u. a. in folgenden Chiffren zum Tragen:

Weblinks

Literatur