Feistel cipher

Inden for kryptografi er en Feistel-chiffer en symmetrisk struktur, der anvendes til konstruktion af blokchiffer, opkaldt efter den tyske IBM-kryptograf Horst Feistel; den er også almindeligvis kendt som et Feistel-netværk. En lang række blokchiffrer anvender dette skema, herunder Data Encryption Standard

Feistel-strukturen har den fordel, at krypterings- og dekrypteringsoperationer er meget ens, i nogle tilfælde endog identiske, og at det kun kræver en omvendt nøgleplanlægning. Derfor er størrelsen af den kode eller det kredsløb, der kræves for at implementere en sådan kryptering, næsten halveret.

Feistel-konstruktionen er iterativ i sin natur, hvilket gør det lettere at implementere kryptosystemet i hardware.

Feistel-netværk og lignende konstruktioner er produktchiffrer og kombinerer derfor flere runder af gentagne operationer, f.eks:

Bit-shuffling (ofte kaldet permutationsbokse eller P-bokse)
Simple ikke-lineære funktioner (ofte kaldet substitutionsbokse eller S-bokse)
Lineær blanding (i modulalgebraens forstand) ved hjælp af XOR for at frembringe en funktion med store mængder af det, som Claude Shannon beskrev som "forvirring og spredning".

Bit shuffling skaber diffusionseffekten, mens substitution bruges til at skabe forvirring.

Teoretisk arbejde

Mange moderne symmetriske blokchiffrer anvender Feistel-netværk, og kryptografer har udforsket strukturen og egenskaberne ved Feistel-chiffrer i stor udstrækning. Michael Luby og Charles Rackoff har analyseret Feistel-blokchifferkonstruktionen og bevist, at hvis rundfunktionen er en kryptografisk sikker pseudorandomfunktion med K_i som frø, er 3 runder tilstrækkeligt til at gøre blokchiffret til en pseudorandom permutation, mens 4 runder er tilstrækkeligt til at gøre det til en "stærk" pseudorandom permutation (hvilket betyder, at det forbliver pseudorandom, selv for en modstander, der får orakeladgang til dets inverse permutation). På grund af dette meget vigtige resultat af Luby og Rackoff kaldes Feistel-chifre undertiden Luby-Rackoff-blokchifre. Yderligere teoretiske undersøgelser generaliserede konstruktionen og definerede mere præcise grænser for sikkerheden.

Byggeri

Lad F {\displaystyle {\rm {F}}}} ${\rm F}$ være rundens funktion, og lad K 1 , K 2 , ... , K n {\displaystyle K_{1},K_{2},\ldots ,K_{n}}} $K_1,K_2,\ldots,K_{n}$ være undernøglerne for $1,2,\ldots,n$ henholdsvis runde 1 , 2 , ... , n {\displaystyle 1,2,\ldots ,n}}.

Den grundlæggende operation er så som følger:

Opdel den klare tekstblok i to lige store stykker ( L 1 {\displaystyle L_{1}}} L_1 , R 1 {\displaystyle R_{1}}} R_1 )

For hver runde i = 1 , 2 , ... , n {\displaystyle i=1,2,\dots ,n} $i =1,2,\dots,n$ , beregne (beregne)

L i + 1 = R i {\displaystyle 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 {F}}}(R_{i},K_{i})} $R_{i+1}= L_i \oplus {\rm F}(R_i, K_i)$ .

Så er den krypterede tekst ( R n + 1 , L n + 1 ) {\displaystyle (R_{n+1},L_{n+1})} $(R_{n+1}, L_{n+1})$ . (Almindeligvis byttes de to dele R n {\displaystyle R_{n}}} R_n og L n {\displaystyle L_{n}}} L_n ikke om efter den sidste runde).

Dekryptering af en krypteringstekst ( R n , L n ) {\displaystyle (R_{n},L_{n})} (R_n, L_n) opnås ved at beregne for i = n , n - 1 , ... , 1 {\displaystyle i=n,n-1,\ldots ,1} $i=n,n-1,\ldots,1$

R i = L i + 1 {\displaystyle 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 {F}}}(L_{i+1},K_{i})} $L_{i} = R_{i+1} \oplus {\rm F}(L_{i+1}, K_{i})$ .

Så er ( L 1 , R 1 ) {\displaystyle (L_{1},R_{1})} (L_1,R_1) igen den klare tekst.

En fordel ved denne model er, at den runde funktion F {\displaystyle {\rm {F}}}} ${\rm F}$ ikke behøver at være invertibel og kan være meget kompleks.

Diagrammet illustrerer krypteringsprocessen. Dekryptering kræver blot, at rækkefølgen af undernøglen K n , K n - 1 , ... , K 1 {\displaystyle K_{n},K_{n-1},\ldots ,K_{1}}} $K_{n},K_{n-1},\ldots,K_1$ omvendes ved hjælp af den samme proces; dette er den eneste forskel mellem kryptering og dekryptering:

Ubalancerede Feistel-krypteringer anvender en modificeret struktur, hvor L 1 {\displaystyle L_{1}}} L_1 og R 1 {\displaystyle R_{1}}} R_1 ikke er lige lange. MacGuffin-chifferet er et eksperimentelt eksempel på en sådan chiffer.

Feistel-konstruktionen anvendes også i andre kryptografiske algoritmer end blokchiffrer. F.eks. bruger OAEP-ordningen (Optimal Asymmetric Encryption Padding) et simpelt Feistel-netværk til at randomisere ciphertexter i visse asymmetriske krypteringsordninger.

Feistel-netværksoperation på blokcifring, hvor P er klarteksten og C er cifferteksten

Liste over Feistel-krypteringer

Feistel eller modificeret Feistel: Blowfish, Camellia, CAST-128, DES, FEAL, ICE, KASUMI, LOKI97, Lucifer, MARS, MAGENTA, MISTY1, RC5, TEA, Triple DES, Twofish, XTEA, GOST 28147-89

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

Spørgsmål og svar

Spørgsmål: Hvad er en Feistel-ciffer?

A: En Feistel-chiffer er en symmetrisk struktur, der anvendes til konstruktion af blokchifre, opkaldt efter den tyske IBM-kryptograf Horst Feistel. Den er også almindeligvis kendt som et Feistel-netværk.

Sp: Hvilke fordele er der ved at bruge en Feistel-struktur?

A: Den største fordel ved at anvende en Feistel-struktur er, at krypterings- og dekrypteringsoperationer er meget ens, i nogle tilfælde endog identiske, og at det kun er nødvendigt at vende om på nøgleplanen. Dette reducerer størrelsen af den kode eller det kredsløb, der kræves for at implementere en sådan kryptering, med næsten halvdelen. Desuden gør den iterative karakter det lettere at implementere kryptosystemet i hardware.

Spørgsmål: Hvordan beskriver Claude Shannon "forvirring og spredning"?

Svar: Claude Shannon beskrev "forvirring og spredning" som værende en stor mængde af begge elementer for at gøre det vanskeligt for en angriber at dechifrere en krypteret meddelelse.

Spørgsmål: Hvilke teknikker anvendes til at skabe forvirring og spredning?

Svar: Forvirring og spredning skabes ved hjælp af bitblanding (ofte kaldet permutationsbokse eller P-bokse) og enkle ikke-lineære funktioner (ofte kaldet substitutionsbokse eller S-bokse) samt lineær blanding (i betydningen modulær algebra) ved hjælp af XOR. Bit shuffling skaber diffusionseffekten, mens substitution anvendes til forvirring.

Spørgsmål: Hvilken type kryptering er et Feistel-netværk?

A: Et Feistel-netværk er en type produktchiffer, som kombinerer flere runder af gentagne operationer for at kryptere data sikkert.

Spørgsmål: Hvem har udviklet denne type kryptografi?

A: Feistel-strukturen blev udviklet af den tyske IBM-kryptograf Horst Feistel.

Spørgsmål: Er Data Encryption Standard baseret på denne type kryptografi?

Svar: Ja, Data Encryption Standard anvender denne type kryptografi, som benytter de samme principper som dem, der er beskrevet ovenfor, til at skabe forvirring og spredning i en krypteret meddelelse.