Feistel-cijfer

Schrijver: Leandro Alegsa

17-12-2020

In de cryptografie is een Feistel-cijfer een symmetrische structuur die gebruikt wordt bij de constructie van blokcijfers, genoemd naar de Duitse IBM-cryptograaf Horst Feistel; het is ook algemeen bekend als een Feistel-netwerk. Een grote set van blokcijfers gebruikt het schema, inclusief de Data Encryptie Standaard.

De Feistel-structuur heeft het voordeel dat encryptie- en ontcijferingsoperaties zeer gelijkaardig zijn, zelfs identiek in sommige gevallen, waardoor alleen een omkering van het sleutelschema nodig is. Daarom is de grootte van de code of de schakelingen die nodig zijn om zo'n versleuteling te implementeren bijna gehalveerd.

Feistelbouw is iteratief van aard, wat de implementatie van het cryptosysteem in de hardware eenvoudiger maakt.

Feistel netwerken en soortgelijke constructies zijn productcijfers, en dus combineren meerdere rondes van herhaalde bewerkingen, zoals:

Bit-shuffling (vaak permutatieboxen of P-boxen genoemd)
Eenvoudige niet-lineaire functies (vaak vervangingsboxen of S-boxen genoemd)
Lineair mengen (in de zin van modulaire algebra) met behulp van XOR om een functie te produceren met grote hoeveelheden van wat Claude Shannon omschreef als "verwarring en verspreiding".

Bitschuiven zorgt voor het verspreidingseffect, terwijl substitutie wordt gebruikt voor verwarring.

Theoretisch werk

Veel moderne symmetrische blokcijfers maken gebruik van Feistel netwerken, en de structuur en eigenschappen van Feistel cijfers zijn uitgebreid onderzocht door cryptografen. Specifiek, Michael Luby en Charles Rackoff analyseerden de Feistel blokcodering constructie, en bewezen dat als de ronde functie is een cryptografisch veilige pseudorandom functie, met _Ki gebruikt als het zaad, dan 3 rondes is voldoende om het blokcodering een pseudorandom permutatie, terwijl 4 rondes is voldoende om het een "sterke" pseudorandom permutatie (wat betekent dat het blijft pseudorandom zelfs voor een tegenstander die krijgt orakel toegang tot zijn omgekeerde permutatie). Vanwege dit zeer belangrijke resultaat van Luby en Rackoff worden Feistel-cijfers soms Luby-Rackoff-blokcijfers genoemd. Verdere theoretische studies veralgemenen de constructie, en definiëren meer precieze grenzen voor de veiligheid.

Bouw

Laat F {\\rm {F}} de ronde functie zijn en laat ${\rm F}$ K 1 , K 2 , ... , K n {\\playstyle K_1},K_2},\ldots , K_n} $K_1,K_2,\ldots,K_{n}$ de sub-sleutels voor de rondes 1 , 2 , ... , n {\playstyle 1,2,\ldots , n} $1,2,\ldots,n$ respectievelijk.

Dan is de basisbediening als volgt:

Splits het platte tekstblok op in twee gelijke stukken, ( L 1 {displaystyle L_{1}} L_1 , R 1 {displaystyle R_1} R_1 )

Voor elke ronde i = 1 , 2 , ... , n {\\\\dstyle i=1,2,\dots,n} $i =1,2,\dots,n$ , berekenen (berekenen)

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

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

Dan is de cijfertekst ( R n + 1 , L n + 1 ) {\playstyle (R_{n+1},L_{n+1})} $(R_{n+1}, L_{n+1})$ . (Gewoonlijk worden de twee stukken R n {\\playstyle R_{n}} R_n en L n {displaystyle L_{n}} L_n niet gewisseld na de laatste ronde).

Ontcijfering van een cijfertekst ( R n , L n ) {\\playstyle (R_{n},L_{n})} (R_n, L_n) wordt bereikt door te rekenen voor i = n , n - 1 , ... , 1 {\playstyle i=n,n-1,\ldots,1} $i=n,n-1,\ldots,1$

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

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

Dan is ( L 1 , R 1 ) {\displaystyle (L_{1},R_{1})} (L_1,R_1) weer de klare tekst.

Een voordeel van dit model is dat de ronde functie F niet omkeerbaar hoeft te zijn en erg complex kan zijn.

Het diagram illustreert het encryptieproces. Voor decodering hoeft alleen de volgorde van de subsleutel K n , K n - 1 , ... , K 1 {displaystyle K_{n},K_{n-1},\ldots,K_{1}} $K_{n},K_{n-1},\ldots,K_1$ te worden omgedraaid met behulp van hetzelfde proces; dit is het enige verschil tussen encryptie en decodering:

Ongebalanceerde Feistel-cijfers gebruiken een aangepaste structuur waarbij L 1 {displaystyle L_{1} L_1 en R 1 {displaystyle R_{1}} R_1 niet even lang zijn. De MacGuffin-code is een experimenteel voorbeeld van zo'n code.

De Feistel-constructie wordt ook gebruikt in andere cryptografische algoritmen dan blokcijfers. Het Optimal Asymmetric Encryption Padding (OAEP) schema maakt bijvoorbeeld gebruik van een eenvoudig Feistel netwerk voor het randomiseren van cijferteksten in bepaalde asymmetrische-sleutel coderingsschema's.

Feistelnetwerkbediening op blokcodering, waarbij P de klaartekst is en C de coderingstekst

Lijst van Feistel-cijfers

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

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