AlegsaOnline.com

Feistelchiffre

Autor: Leandro Alegsa

03-11-2020

In der Kryptographie ist eine Feistel-Chiffre eine symmetrische Struktur, die bei der Konstruktion von Blockchiffren verwendet wird, benannt nach dem deutschen IBM-Kryptographen Horst Feistel; sie ist auch allgemein als Feistel-Netzwerk bekannt. Eine große Anzahl von Blockchiffrierungen verwendet dieses Schema, einschließlich des Datenverschlüsselungsstandards

Die Feistel-Struktur hat den Vorteil, dass die Ver- und Entschlüsselungsvorgänge sehr ähnlich, in einigen Fällen sogar identisch sind und nur eine Umkehrung des Schlüsselplans erfordern. Daher wird die Größe des für die Implementierung einer solchen Chiffre erforderlichen Codes oder Schaltkreises fast halbiert.

Die Feistel-Konstruktion ist iterativer Natur, was die Implementierung des Kryptosystems in Hardware erleichtert.

Feistel-Netzwerke und ähnliche Konstruktionen sind Produkt-Chiffren und kombinieren so mehrere Runden von wiederholten Operationen, wie z.B:

Bit-Mischen (oft als Permutationsboxen oder P-Boxen bezeichnet)
Einfache nicht-lineare Funktionen (oft Substitutionsboxen oder S-Boxen genannt)
Lineares Mischen (im Sinne der modularen Algebra) unter Verwendung von XOR zur Erzeugung einer Funktion mit großen Mengen dessen, was Claude Shannon als "Verwirrung und Diffusion" beschrieb.

Das Mischen der Bits erzeugt den Diffusionseffekt, während die Substitution zur Verwirrung eingesetzt wird.

Theoretische Arbeit

Viele moderne symmetrische Blockchiffrierungen verwenden Feistel-Netzwerke, und die Struktur und Eigenschaften der Feistel-Chiffren wurden von Kryptographen ausgiebig erforscht. Insbesondere Michael Luby und Charles Rackoff analysierten die Konstruktion der Feistel-Blockchiffrierung und bewiesen, dass, wenn die runde Funktion eine kryptographisch sichere pseudozufällige Funktion ist, bei der Ki als Keim verwendet wird, 3 Runden ausreichen, um die Blockchiffrierung zu einer pseudozufälligen Permutation zu machen, während 4 Runden ausreichen, um sie zu einer "starken" pseudozufälligen Permutation zu machen (was bedeutet, dass sie selbst für einen Gegner, der Zugang zu ihrer inversen Permutation erhält, pseudozufällig bleibt). Wegen dieses sehr wichtigen Ergebnisses von Luby und Rackoff werden Feistel-Chiffren manchmal als Luby-Rackoff-Blockchiffren bezeichnet. Weitere theoretische Studien verallgemeinerten die Konstruktion und definierten genauere Grenzen für die Sicherheit.

Konstruktion

Lassen Sie F {\darstellungsstil {\rm {F}}} ${\rm F}$ die Rundenfunktion sein und lassen Sie K 1 , K 2 , ... , K n {\darstellungsstil K_{1},K_{2},\ldots ,K_{n}}} $K_1,K_2,\ldots,K_{n}$ $1,2,\ldots,n$ jeweils die Unterschlüssel für die Runden 1 , 2 , ... , n {\darstellungsstil 1,2,\ldots ,n} sein.

Dann ist die Grundoperation wie folgt:

Teilen Sie den Klartextblock in zwei gleiche Teile auf, ( L 1 {\darstellungsstil L_{1}} L_1 , R 1 {\darstellungsstil R_{1}} R_1 )

Für jede Runde i = 1 , 2 , ... , n {\Darstellungsstil i=1,2,\Punkte ,n} $i =1,2,\dots,n$ , Berechnen (berechnen)

L i + 1 = R i {\Anzeigestil L_{i+1}=R_{i}\,} $L_{i+1} = R_i\,$

R i + 1 = L i ⊕ F ( R i , K i ) {\displaystyle R_{i+1}=L_{i}\oplus {\rm {\rm {F}}}(R_{i},K_{i})} $R_{i+1}= L_i \oplus {\rm F}(R_i, K_i)$ .

Dann lautet der Geheimtext ( R n + 1 , L n + 1 ) {\darstellungsstil (R_{n+1},L_{n+1})} $(R_{n+1}, L_{n+1})$ . (Üblicherweise werden die beiden Stücke R n {\darstellungsstil R_{n}} R_n und L n {\darstellungsstil L_{n}}} L_n nach der letzten Runde nicht vertauscht).

Die Entschlüsselung eines Chiffriertextes ( R n , L n ) {\darstellungsstil (R_{n},L_{n})} (R_n, L_n) erfolgt durch Berechnung für i = n , n - 1 , ... , 1 {\darstellungsstil i=n,n-1,\ldots ,1} $i=n,n-1,\ldots,1$

R i = L i + 1 {\Anzeigestil R_{i}=L_{i+1}\,} $R_{i} = L_{i+1}\,$

L i = R i + 1 ⊕ F ( L i + 1 , K i ) {\displaystyle L_{i}=R_{i+1}\oplus {\rm {\rm {F}}}(L_{i+1},K_{i})} $L_{i} = R_{i+1} \oplus {\rm F}(L_{i+1}, K_{i})$ .

Dann ( L 1 , R 1 ) {\darstellungsstil (L_{1},R_{1})} (L_1,R_1) ist wieder der Klartext.

Ein Vorteil dieses Modells ist, dass die runde Funktion F {\displaystyle {\rm {F}}} ${\rm F}$ nicht invertierbar sein muss und sehr komplex sein kann.

Das Diagramm veranschaulicht den Verschlüsselungsprozess. Bei der Entschlüsselung muss lediglich die Reihenfolge des Unterschlüssels K n , K n - 1 , ... , K 1 {\darstellungsstil K_{n},K_{n-1},\ldots ,K_{1}} $K_{n},K_{n-1},\ldots,K_1$ mit demselben Verfahren umgekehrt werden; dies ist der einzige Unterschied zwischen Verschlüsselung und Entschlüsselung:

Unausgewogene Feistel-Chiffren verwenden eine modifizierte Struktur, bei der L 1 {\darstellungsstil L_{1}} L_1 und R 1 {\darstellungsstil R_{1}} R_1 nicht gleich lang sind. Die MacGuffin-Chiffre ist ein experimentelles Beispiel für eine solche Chiffre.

Die Feistel-Konstruktion wird auch in anderen kryptographischen Algorithmen als Blockchiffrierungen verwendet. Zum Beispiel verwendet das Optimal Asymmetric Encryption Padding (OAEP) Schema ein einfaches Feistel-Netzwerk, um Chiffriertexte in bestimmten Verschlüsselungsschemata mit asymmetrischem Schlüssel zu randomisieren.

Feistel-Netzwerkbetrieb mit Blockchiffrierung, wobei P der Klartext und C der Chiffretext ist

Liste der Feistel-Chiffren

Feistel oder modifizierte Feistel: Kugelfisch, Kamelie, CAST-128, DES, FEAL, ICE, KASUMI, LOKI97, Lucifer, MARS, MAGENTA, MISTY1, RC5, TEA, Triple DES, Twofish, XTEA, GOST 28147-89

Generalisierte Feistel: CAST-256, MacGuffin, RC2, RC6, Skipjack

Fragen und Antworten

F: Was ist eine Feistel-Chiffre?

A: Eine Feistel-Chiffre ist eine symmetrische Struktur, die bei der Konstruktion von Blockchiffren verwendet wird und nach dem deutschen IBM-Kryptografen Horst Feistel benannt ist. Sie ist allgemein auch als Feistel-Netzwerk bekannt.

F: Welche Vorteile hat die Verwendung einer Feistel-Struktur?

A: Der Hauptvorteil einer Feistel-Struktur besteht darin, dass Ver- und Entschlüsselungsvorgänge sehr ähnlich, in manchen Fällen sogar identisch sind und nur eine Umkehrung des Schlüsselplans erfordern. Dies reduziert den Umfang des Codes oder der Schaltkreise, die für die Implementierung einer solchen Chiffre erforderlich sind, um fast die Hälfte. Außerdem erleichtert die iterative Natur die Implementierung des Kryptosystems in Hardware.

F: Wie beschreibt Claude Shannon "Konfusion und Diffusion"?

A: Claude Shannon beschrieb "Konfusion und Diffusion" als die Anwesenheit großer Mengen beider Elemente, um es einem Angreifer zu erschweren, eine verschlüsselte Nachricht zu entschlüsseln.

F: Welche Techniken werden verwendet, um Verwirrung und Streuung zu erzeugen?

A: Konfusion und Diffusion werden durch Bit-Mischung (oft als Permutationsboxen oder P-Boxen bezeichnet) und einfache nicht-lineare Funktionen (oft als Substitutionsboxen oder S-Boxen bezeichnet) sowie durch lineares Mischen (im Sinne der modularen Algebra) unter Verwendung von XOR erzeugt. Das Mischen von Bits erzeugt den Diffusionseffekt, während die Substitution zur Verwirrung dient.

F: Welche Art von Chiffre ist ein Feistel-Netzwerk?

A: Ein Feistel-Netzwerk ist eine Art von Produktchiffre, die mehrere Runden von wiederholten Operationen kombiniert, um Daten sicher zu verschlüsseln.

F: Wer hat diese Art der Kryptographie entwickelt?

A: Die Feistel-Struktur wurde von dem deutschen IBM-Kryptographen Horst Feistel entwickelt.

F: Basiert der Data Encryption Standard auf dieser Art von Kryptographie?

A: Ja, der Data Encryption Standard verwendet diese Art der Kryptographie, die dieselben Prinzipien wie oben beschrieben anwendet, um Verwirrung und Diffusion innerhalb einer verschlüsselten Nachricht zu erzeugen.