AlegsaOnline.com

Feistelkrypto: struktur i många blockchiffer

Feistelkrypto är en symmetrisk konstruktion för blockchiffer som delar data i halvor och upprepar rundor med nyckelstyrda funktioner.

Författare: Leandro Alegsa Skapandedatum: 7 november 2021 Senast uppdaterad: 23 april 2026

simple.wikipedia.org · Public domain

Feistelkrypto, eller Feistel-struktur i kryptografi, är ett sätt att konstruera blockchiffer. Metoden delar ett textblock i två halvor och låter dem genomgå flera rundor där en nyckelstyrd funktion påverkar den ena halvan medan den andra förs vidare till nästa steg. Konstruktionen är uppkallad efter Horst Feistel och blev viktig i utvecklingen av moderna digitala chiffer.

I en typisk runda beräknas en funktion av den ena halvan och en rundnyckel. Resultatet kombineras sedan ofta med den andra halvan med hjälp av XOR, varefter halvorna byter plats. Det gör att samma grundidé kan användas för både kryptering och dekryptering: vid avkodning kör man i praktiken rundorna baklänges med omvänd nyckelplanering. Den egenskapen har gjort Feistelstrukturen attraktiv eftersom den kan implementeras relativt enkelt i både programvara och hårdvara.

Historik och exempel

Feistelidén fick stort genomslag genom Data Encryption Standard, ett av de mest kända historiska blockchiffren. Sedan dess har många andra konstruktioner använt samma princip eller nära besläktade varianter. Feistelkrypto är därför bättre att se som en byggmodell än som ett enda specifikt chiffer. Det är också viktigt att skilja den från andra blockchifferarkitekturer, till exempel sådana som bygger på andra typer av rundor och datastrukturer.

Hur konstruktionen är uppbyggd

Feistelnätverk räknas till produktchiffer, alltså system där flera enkla steg kombineras för att skapa starkare skydd. I varje runda kan olika komponenter förekomma: P-boxar för permutation, S-rutor för icke-linjär substitution och blandning av data med hjälp av modulär algebra och XOR. Tillsammans hjälper dessa delar till att bygga upp det Claude Shannon beskrev som förvirring och spridning.

Permutationer flyttar runt bitar och bidrar till att information sprids över blocket.
Substitutioner skapar icke-linjära samband som gör mönster svårare att utnyttja.
Flera rundor förstärker både förvirring och spridning i hela chiffret.

Bitomkastning och andra permutationssteg bidrar särskilt till spridningseffekten, medan substitutionen står för förvirringen. Det är kombinationen av dessa egenskaper som gör att små förändringar i klartext eller nyckel kan ge stora utslag i den krypterade texten efter flera rundor.

Feistelkrypto har därför fått en bestående plats i kryptografins historia. Metoden visar hur en relativt enkel och elegant struktur kan ligga till grund för effektiva och välstuderade blockchiffer. Säkerheten beror dock inte på Feistelidén ensam, utan på hur stark rundfunktionen är, hur många rundor som används och hur nycklarna hanteras.

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.