Feistelkrypto

Inom kryptografin är ett Feistel-chiffer en symmetrisk struktur som används vid konstruktion av blockchiffer, uppkallad efter den tyske IBM-kryptografen Horst Feistel. Ett stort antal blockchiffer använder systemet, bland annat Data Encryption Standard.

Feistel-strukturen har fördelen att krypterings- och dekrypteringsoperationer är mycket lika, till och med identiska i vissa fall, och att det bara krävs en omvänd nyckelplanering. Därför är storleken på den kod eller krets som krävs för att genomföra ett sådant chiffer nästan halverad.

Feistelkonstruktionen är iterativ till sin natur, vilket gör det lättare att implementera kryptosystemet i hårdvara.

Feistel-nätverk och liknande konstruktioner är produktchiffrer och kombinerar därför flera omgångar av upprepade operationer, t.ex:

Bit-shuffling (ofta kallad permutationsboxar eller P-boxar).
Enkla icke-linjära funktioner (ofta kallade substitutionsrutor eller S-rutor).
Linjär blandning (i betydelsen modulär algebra) med hjälp av XOR för att producera en funktion med stora mängder av det som Claude Shannon beskrev som "förvirring och spridning".

Bit-shuffling skapar spridningseffekten, medan substitution används för att skapa förvirring.

Teoretiskt arbete

Många moderna symmetriska blockchiffrar använder Feistel-nätverk, och kryptografer har utförligt undersökt strukturen och egenskaperna hos Feistel-chiffrar. Michael Luby och Charles Rackoff analyserade Feistels blockchifferkonstruktion och bevisade att om rundfunktionen är en kryptografiskt säker pseudorandomfunktion, med K_i som frö, räcker det med tre rundor för att göra blockchiffret till en pseudorandompermutation, medan fyra rundor räcker för att göra det till en "stark" pseudorandompermutation (vilket innebär att den förblir pseudorandom även för en motståndare som får tillgång till den inversa permutationen i oraklet). På grund av detta mycket viktiga resultat av Luby och Rackoff kallas Feistelkrypter ibland Luby-Rackoff-blockkrypter. Ytterligare teoretiska studier generaliserade konstruktionen och definierade mer exakta gränser för säkerheten.

Konstruktion

Låt F {\displaystyle {\rm {F}}}} ${\rm F}$ vara rundfunktionen och låt K 1 , K 2 , ... , K n {\displaystyle K_{1},K_{2},\ldots ,K_{n}}} $K_1,K_2,\ldots,K_{n}$ vara undernycklarna för rundorna 1 , 2 , ... , n {\displaystyle 1,2,\ldots ,n} $1,2,\ldots,n$ respektive.

Den grundläggande operationen är då följande:

Dela upp klartextblocket i två lika stora delar ( L 1 {\displaystyle L_{1}} L_1 , R 1 {\displaystyle R_{1}} R_1 ).

För varje omgång i = 1 , 2 , ... , n {\displaystyle i=1,2,\dots ,n} $i =1,2,\dots,n$ , beräkna (beräkna)

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)$ .

Då är chiffertexten ( R n + 1 , L n + 1 ) {\displaystyle (R_{n+1},L_{n+1})} $(R_{n+1}, L_{n+1})$ . (Vanligtvis byts inte de två delarna R n {\displaystyle R_{n}} R_n och L n {\displaystyle L_{n}}} L_n ut efter den sista omgången.

Dekryptering av en chiffertext ( R n , L n ) {\displaystyle (R_{n},L_{n})} (R_n, L_n) sker genom att för 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})$ .

Då (L_1,R_1) är ( L 1 , R 1 ) {\displaystyle (L_{1},R_{1})} återigen den klara texten.

En fördel med denna modell är att den runda funktionen F {\displaystyle {\rm {F}}} ${\rm F}$ inte behöver vara inverterbar och kan vara mycket komplex.

Diagrammet illustrerar krypteringsprocessen. För dekryptering krävs endast att ordningen på undernyckeln K n , K n - 1 , ... , K 1 {\displaystyle K_{n},K_{n-1},\ldots ,K_{1}}} $K_{n},K_{n-1},\ldots,K_1$ vänds om på samma sätt; detta är den enda skillnaden mellan kryptering och dekryptering:

Obalanserade Feistel-chiffer använder en modifierad struktur där L 1 {\displaystyle L_{1}}} L_1 och R 1 {\displaystyle R_{1}}} R_1 inte är lika långa. MacGuffin-chiffret är ett experimentellt exempel på ett sådant chiffer.

Feistelkonstruktionen används även i andra kryptografiska algoritmer än blockchiffer. I OAEP (Optimal Asymmetric Encryption Padding) används till exempel ett enkelt Feistel-nätverk för att randomisera chiffertexter i vissa krypteringssystem med asymmetriska nycklar.

Feistel-nätverksoperation på blockchiffer, där P är den klara texten och C är chiffertexten.

Förteckning över Feistel-chiffer

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

Generaliserad Feistel: CAST-256, MacGuffin, RC2, RC6, Skipjack.

Frågor och svar

F: Vad är ett Feistel-chiffer?

S: Ett Feistelchiffer är en symmetrisk struktur som används vid konstruktion av blockchiffer, uppkallad efter den tyske IBM-kryptografen Horst Feistel. Den är också allmänt känd som ett Feistel-nätverk.

F: Vilka är fördelarna med att använda en Feistel-struktur?

S: Den största fördelen med att använda en Feistel-struktur är att krypterings- och dekrypteringsoperationer är mycket likartade, till och med identiska i vissa fall, och att det bara krävs en omvänd nyckelplanering. Detta minskar storleken på den kod eller krets som krävs för att genomföra ett sådant chiffer med nästan hälften. Dessutom gör dess iterativa karaktär det lättare att genomföra kryptosystemet i hårdvara.

F: Hur beskriver Claude Shannon "förvirring och spridning"?

S: Claude Shannon beskrev "förvirring och spridning" som att det krävs stora mängder av båda elementen för att göra det svårt för en angripare att dechiffrera ett krypterat meddelande.

F: Vilka tekniker används för att skapa förvirring och spridning?

S: Förvirring och spridning skapas genom bitblandning (ofta kallad permutationsboxar eller P-boxar) och enkla icke-linjära funktioner (ofta kallad substitutionsboxar eller S-boxar), samt linjär blandning (i betydelsen modulär algebra) med hjälp av XOR. Bit-shuffling skapar spridningseffekten, medan substitution används för förvirring.

F: Vilken typ av chiffer är ett Feistel-nätverk?

S: Ett Feistel-nätverk är en typ av produktchiffer som kombinerar flera omgångar av upprepade operationer för att kryptera data på ett säkert sätt.

F: Vem utvecklade denna typ av kryptografi?

S: Feistelstrukturen utvecklades av den tyske IBM-kryptografen Horst Feistel.

F: Är Data Encryption Standard baserad på denna typ av kryptografi?

Svar: Ja, Data Encryption Standard använder denna typ av kryptografi som använder samma principer som beskrivs ovan för att skapa förvirring och spridning i ett krypterat meddelande.