AlegsaOnline.com

Feistel-cijfer (Feistel-netwerk): structuur en gebruik in blokcijfers

Beschrijving van het Feistel-cijfer: een symmetrische bouwsteen voor blokcijfers die data in twee helften verdeelt. Werking, onderdelen, varianten en voorbeelden zoals DES worden behandeld.

Schrijver: Leandro Alegsa Aanmaakdatum: 17 december 2020 Laatste update: 21 april 2026

simple.wikipedia.org · Public domain

Overzicht

Een Feistel-cijfer, ook wel Feistel-netwerk genoemd, is een veelgebruikt ontwerpprincipe in de cryptografie voor het bouwen van veilige blokcijfers. Het schema is vernoemd naar Horst Feistel, die het concept populair maakte bij IBM. Een van de bekendste toepassingen is de Data Encryption Standard, vaak afgekort als DES, maar veel moderne en historische blokcijfers gebruiken varianten van hetzelfde idee.

Werking

De kern van een Feistel-netwerk is eenvoudig en robuust: een invoerblok wordt opgesplitst in twee helften, doorgaans L (links) en R (rechts). In elke ronde wordt een rondefunctie toegepast op één helft en gecombineerd met de andere helft, waarna de helften eventueel worden omgewisseld. Concreet geldt meestal voor ronde i: L_{i+1} = R_i en R_{i+1} = L_i ⊕ F(R_i, K_i), waarbij F de rondefunctie is en K_i de sub-sleutel voor die ronde. Deze opzet maakt dat de operatie gemakkelijk omkeerbaar is; om te ontcijferen volstaat het toepassen van dezelfde rondes in omgekeerde sleutelvolgorde. Dat is een praktisch voordeel voor implementatie van encryptie en decryptie, waarbij soms alleen het omkeren van het sleutelschema nodig is. Omdat meerdere rondes gecombineerd worden, behoort een Feistel-constructie tot de categorie van productcijfers, waarbij herhaalde eenvoudige transformaties samen sterke beveiliging opleveren.

Belangrijke onderdelen

Rondefunctie (F): een flexibele bouwsteen die niet-lineaire en lineaire bewerkingen kan combineren.
Sub-sleutels: afgeleid uit de hoofdsleutel via een sleuteluitbreidingsmechanisme; in de omgang vaak het enige verschil tussen encryptie en decryptie.
Substitutie- en permutatie-elementen: veel rondefuncties gebruiken vervangingsboxen (S-boxen) voor niet-lineariteit en permutatieboxen (P-boxen) of bit-shuffling voor bitverspreiding.
Wiskundige bewerkingen: operaties zoals bitwise XOR en aritmetische bewerkingen in een ring of modulair domein (modulaire algebra) worden vaak gecombineerd om zowel efficiëntie als cryptografische sterkte te bereiken.

Het samenspel van deze mechanismen streeft naar twee klassieke eigenschappen die Claude Shannon omschreef: verwarring en verspreiding. Verwarring verbergt de relatie tussen sleutel en ciphertext, terwijl verspreiding (diffusie) ervoor zorgt dat lokale wijzigingen in de plaintext zich over het hele ciphertext verspreiden, wat soms eenvoudigweg als verspreiding wordt aangeduid.

Voordelen, varianten en voorbeelden

Een belangrijk voordeel van de Feistel-structuur is de balans tussen eenvoud en kracht. Omdat encryptie en decryptie vaak met zeer gelijke routines kunnen worden uitgevoerd, is de implementatie compacter en eenvoudiger in hardware en software. De keuze van F en het aantal rondes bepaalt de veiligheid: eenvoudige rondefuncties kunnen veilig worden gemaakt door voldoende ronden toe te voegen.

Er bestaan meerdere varianten: het klassieke, evenwichtige Feistel-netwerk waarbij beide helften even groot zijn; ongebalanceerde of 'alternating' Feistel-ontwerpen waarbij de helften verschillende groottes hebben; en Feistel-achtige constructies die afwijken in de manier waarop halve blokken gecombineerd worden. Historische en actuele voorbeelden zijn, naast DES, verscheidene blokcijfers en blokcipher-modi die voor verschillende toepassingen zijn ontwikkeld.

Opmerkingen en notities

Ondanks zijn eenvoud blijft het Feistel-principe relevant omdat het ontwerp toelaat om met relatief eenvoudige operaties sterke cilfersystemen te construeren. De veiligheid hangt af van zorgvuldige keuze van de rondefunctie, sleuteluitbreiding en het aantal rondes. Voor theoretische garanties en praktische richtlijnen zijn er uitgebreide wetenschappelijke studies en standaarden beschikbaar die implementators helpen bij het kiezen van parameters en het evalueren van weerstand tegen bekende aanvallen.

Voor aanvullende technische referenties en voorbeelden kunt u bronnen raadplegen via gerelateerde vakliteratuur en standaarden. Zie ook de secties over cryptografie en blokcijfers voor bredere context en DES voor een klassiek voorbeeld van een Feistel-ontwerp.

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