Feistelchiffre - LinkFang.de





Feistelchiffre


Feistelchiffre nennt man eine Blockverschlüsselung, die in Form eines Feistelnetzwerks aufgebaut ist. Dieses ist eine allgemeine Struktur, mit der Blockverschlüsselungen realisiert werden können. Ein Mitarbeiter von IBM, Horst Feistel, gilt als der Erfinder dieser Struktur. Er arbeitete in den 1970er Jahren mit anderen am sog. Projekt „Lucifer“, dessen Ziel es war, eine effiziente Verschlüsselungstechnologie zu entwickeln. Lucifer und der daraus abgeleitete DES-Algorithmus stellen ein Feistelnetzwerk dar.

Viele moderne symmetrische Verschlüsselungen basieren auf Feistelnetzwerken, weil man damit leicht die Umkehrbarkeit (Bijektivität) der Verschlüsselung sicherstellen kann. 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 kommt. Weiterhin wurde die Feistel-Struktur von sehr vielen Kryptografen analysiert und für gut befunden.

Arbeitsweise

Wie es der Name „Blockchiffre“ schon nahelegt, wird der Klartext in Blöcke zerlegt, die jeweils für sich verschlüsselt werden. Die Größe der Blöcke 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 einer dieser Teile mit der Ausgabe einer Rundenfunktion verknüpft. Die Rundenfunktion erhält den anderen Teilblock und einen Rundenschlüssel als Eingabe. 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 eine einfach umkehrbare Verknüpfung. Oft verwendet man 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, führt man die Schritte der obigen Formel in umgekehrter Reihenfolge aus, 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} \ominus F(L_{i+1}, K_i)[/math]

[math]\ominus[/math] steht für die Umkehrung von [math]\oplus[/math]. Zum Beispiel kann [math]\oplus[/math] die Addition modulo [math]2^b[/math] sein, mit [math]b[/math] als Länge eines Teilblocks in Bit, und [math]\ominus[/math] ist dann die Subtraktion modulo [math]2^b[/math]. Beide können auf den meisten Digitalrechnern einfach berechnet werden, denn die Modulo-Division ergibt sich von selbst durch das Abschneiden eines eventuellen Überlaufbits. Beispiel: XTEA.

Die Verknüpfung kann auch komplexer ausfallen und z. B. auch Bitrotationen enthalten. Beispiele: RC5, RC6.

Variante

Manche Verfahren verknüpfen auch die Rundenschlüssel direkt mit den Teilblöcken, 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. Beispiele: RC5, RC6, Blowfish.

Aufteilung in Teilblöcke

Ein balanciertes Feistelnetzwerk (BFN) liegt dann vor, wenn die beiden Teile, die in die Rundenfunktion eingehen, gleich groß sind. Von einem unbalancierten (nicht-balancierten) Feistelnetzwerk (UFN) spricht man, wenn entweder die beiden Teile nicht gleich groß sind oder aus einem Block mehr als zwei Teile gebildet werden. Beispiel: die Kompressionsfunktionen der Hashalgorithmen MD4 und MD5, wo ein Block in vier Wörter von je 32 Bit zerlegt wird. Drei dieser Wörter werden in der Rundenfunktion verrechnet und das Ergebnis mit dem vierten Wort verknüpft.

Anwendungen

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

Weblinks

Literatur


Kategorien: Blockverschlüsselung

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Feistelchiffre (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.