AlegsaOnline.com

Feistel-netværk (Feistel-chiffer): Definition og anvendelse i blokchifre

Feistel-netværk: Klar gennemgang af Feistel-chifferets struktur, fordele og anvendelser i blokchifre samt hvordan det effektivt sikrer kryptering og dekryptering.

Forfatter: Leandro Alegsa

29-01-2026

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.

Hvordan en Feistel-runde virker

I et klassisk, afbalanceret Feistel-netværk opdeles et blokdata-stykke i to lige store halvdele, kaldet venstre (L) og højre (R). En enkel runde beskrives ofte som:

L_{i+1} = R_i og R_{i+1} = L_i XOR F(R_i, K_i)

Her er F en (typisk ikke-inverterbar) runde-funktion, og K_i er rundens nøgle (fra nøgleplanlægningen). Efter flere runder byttes halvdelenes roller gentagne gange. Fordi L_{i+1} kun er en kopi af R_i, og R_{i+1} kombinerer L_i og en funktion af R_i, behøver F ikke at være invertibel for at hele cifren kan dekrypteres — dekryptering udføres blot ved at køre samme konstruktionstrin i omvendt rækkefølge med rundefunktionerne anvendt i reverse nøglerækkefølge.

Varianter

Afbalanceret Feistel: Halvdelene er lige store (mest almindeligt).
Uafbalanceret Feistel: Halvdelene kan have forskellig størrelse; anvendt i nogle specialiserede cifre for at håndtere inputstørrelser, der ikke er lige.
Generaliserede Feistel-netværk: Flere end to blokke (f.eks. 4-vejs Feistel), hvor runderoterende kombinationer bruges mellem flere ord.

Sikkerhed og teoretiske resultater

Feistel-netværkets sikkerhed afhænger af rundefunktionernes kvalitet, antallet af runder og nøgleplanlægningen. Et vigtigt teoretisk resultat er Luby–Rackoff-teoremet, som viser, at under antagelsen af uafhængige tilfældige rundefunktioner kan et lille antal runder give stærke sikkerhedsegenskaber:

Med tre uafhængige tilfældige rundefunktioner får man en pseudotilfældig permutation (PRP) — dvs. opfører sig som et tilfældigt bijektivt kortlægning for en angriber uden ubegrænsede ressourcer.
Med fire runder opnås ofte stærkere sikkerhedsegenskaber (såkaldt strong PRP) mod bredere angrebstyper.

I praksis kræver sikre, konkrete design typisk flere runder end det teoretiske minimum, og man skal være opmærksom på kendte svagheder i selve rundefunktionen og i nøgleplanlægningen.

Anvendelser

Feistel-konstruktionen er brugt i mange kendte blokchifre. Den mest berømte anvendelse er Data Encryption Standard, som bruger 16 runder og en bestemt type rundefunktion baseret på S-bokse og permutationer. Andre eksempler (uden links i denne artikel) inkluderer Blowfish, CAST og 3DES (som bruger DES-kerner i en itereret struktur).

Fordele og ulemper

Fordele:
- Enkel dekryptering: samme struktur som kryptering, blot omvendt nøgleordre.
- Rundefunktionen behøver ikke at være inverterbar, hvilket giver designfrihed.
- Let at implementere effektivt både i hardware og software.
Ulemper:
- Kræver ofte mange runder for at opnå ønsket sikkerhed, hvilket kan påvirke ydeevnen.
- Fejl i rundefunktionen eller nøgleplanlægningen kan svække hele cifren.

Implementeringsnoter

Når man implementerer et Feistel-baseret chiffer, er følgende praktiske forhold vigtige:

Nøgleplanlægning: En sikker og effektiv udledning af rundekeyes er afgørende. Enkel ombytning af nøgler kan gøre dekryptering trivialt, men en dårlig nøgleplanlægning kan lække information om nøglen.
Rundefunktionens design: F bør indeholde både ikke-lineariteter (S-bokse) og spredning (permutationer / P-bokse) for at undgå statistiske svagheder.
Antal runder: Vælg et passende antal runder baseret på både teoretiske analyser og praktisk erfaring i forhold til ønsket sikkerhedsniveau.
Sidekanalangreb: Implementationsmodståelsesmekanismer (time-masking, konstante-tidsoperationer osv.) er vigtige for virkelige systemer.

Sammenfatning

Et Feistel-netværk er en fleksibel og velafprøvet metode til at bygge blokchifre. Dets hovedfordele er enkel implementering, symmetri mellem kryptering og dekryptering og muligheden for at anvende ikke-inverterbare rundefunktioner. Sikkerhed afhænger dog stærkt af rundefunktionens kvalitet, nøgleplanlægningen og antallet af runder — og derfor testes og analyseres konkrete Feistel-baserede cifre nøje før brug i kritiske systemer.

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.