Feistel netværk

Feistels netværk , eller Feistels design ( Eng. Feistel netværk, Feistel cipher ), er en af metoderne til at konstruere blokcifre . Netværket består af celler kaldet Feistel-celler . Indtastningen af hver celle modtager data og en nøgle. Ved udgangen af hver celle modtages de ændrede data og den ændrede nøgle. Alle celler er af samme type, og de siger, at netværket er en bestemt gentagne gange gentaget ( itereret ) struktur. Nøglen vælges afhængigt af krypterings-/dekrypteringsalgoritmen og ændres ved flytning fra en celle til en anden. Kryptering og dekryptering udfører de samme operationer; kun rækkefølgen er anderledesnøgler . På grund af betjeningens enkelhed er Feistel-netværket nemt at implementere både i software og hardware. En række blokcifre ( DES , RC2 , RC5 , RC6 , Blowfish , FEAL , CAST-128 , TEA , XTEA , XXTEA osv.) bruger Feistel-netværket som grundlag. Et alternativ til Feistel-netværket er permutation-permutation-netværket ( AES , etc.).

Historie

I 1971 patenterede Horst Feistel to enheder, der implementerede forskellige krypteringsalgoritmer , senere kaldet " Lucifer " ( eng. Lucifer ). En af disse enheder brugte et design, der senere blev kaldt "Feistel-netværket" ( engelsk Feistel-chiffer , Feistel-netværk ). Derefter arbejdede Feistel på skabelsen af nye kryptosystemer inden for IBMs mure sammen med Don Coppersmith . Lucifer-projektet var ret eksperimentelt, men blev grundlaget for DES-algoritmen ( eng. d ata e ncryption s tandard ). I 1973 offentliggjorde magasinet Scientific American Feistels artikel "Cryptography and computer security" ( Eng. Cryptography and computer privacy ) [1] , som afslørede nogle vigtige aspekter af kryptering og beskrev den første version af Lucifer- projektet. Den første version af Project Lucifer brugte ikke Feistel-netværket.

Baseret på Feistel-netværket blev DES-algoritmen designet. I 1977 vedtog de amerikanske myndigheder FIPS 46-3 standarden , der anerkendte DES som standardmetoden til datakryptering. DES har været meget brugt i kryptografiske systemer i nogen tid. Algoritmens iterative struktur gjorde det muligt at skabe simple software- og hardwareimplementeringer.

Ifølge nogle data [2] udviklede KGB allerede i 1970'erne i USSR en blokchiffer , der brugte Feistel-netværket, og sandsynligvis var det denne ciffer , der blev vedtaget i 1990 som GOST 28147-89 .

I 1987 blev FEAL- og RC2 - algoritmerne udviklet . Feistel-netværk blev udbredt i 1990'erne - i årene med fremkomsten af sådanne algoritmer som Blowfish (1993), TEA (1994), RC5 (1994), CAST-128 (1996), XTEA (1997), XXTEA (1998), RC6 (1998) og andre.

Den 2. januar 1997 annoncerede NIST Institute en konkurrence om at skabe en ny datakrypteringsalgoritme til at erstatte DES . Den nye blokchiffer fik navnet AES ( en avanceret krypteringsstandard ) og blev godkendt den 26. maj 2002 . AES bruger et substitutions-permutationsnetværk i stedet for et Feistel-netværk .

Blokkrypteringsdesign baseret på Feistel-netværk

Enkel beskrivelse

Kryptering

Lad det være påkrævet at kryptere nogle oplysninger , der præsenteres i binær form (i form af en sekvens af nuller og enere ) og placeret i hukommelsen på en computer eller anden enhed (for eksempel i en fil ).

krypteringsalgoritme.

Information er opdelt i blokke af samme (faste) længde. De resulterende blokke kaldes input , da de er input til algoritmen. Hvis længden af inputblokken er mindre end den størrelse, som den valgte krypteringsalgoritme er i stand til at kryptere ad gangen (blokstørrelse), så forlænges blokken på en eller anden måde. Typisk er bloklængden en potens på to, såsom 64 bit eller 128 bit.

Yderligere vil vi overveje operationer, der kun forekommer med én blok, da de samme operationer udføres med andre blokke under krypteringsprocessen.

Den valgte blok er opdelt i to underblokke af samme størrelse — "venstre" ( ) og "højre" ( ). $L_0$ $R_{0}$
Den "højre underblok" ændres af F- funktionen ved hjælp af den runde tast : $R_{0}$ $K_{0}$

x=F(R_{0},K_{0}).

Resultatet tilføjes modulo 2 ("xor") med "venstre underblok" : $L_0$

x=x\oplus L_{0}.

Resultatet vil blive brugt i næste runde som en "højre underblok" : $R_{1}$

R_{1}=x.

Den "højre underblok" i den nuværende runde (i dens uændrede form ved starten af runden) vil blive brugt i den næste runde som "venstre underblok" : $R_{0}$ $L_{1}$

L_{1}=R_{0}.

Ifølge en eller anden matematisk regel beregnes en rundnøgle - den nøgle , der skal bruges i næste runde. $K_1$

De anførte operationer udføres N-1 gange, hvor N er antallet af runder i den valgte krypteringsalgoritme. I dette tilfælde, mellem overgangene fra en runde (stadie) til en anden, ændres nøglerne: den erstattes af , - af , osv.). $K_{0}$ $K_1$ $K_1$ $K_{2}$

Dekryptering

Dekryptering af information sker på samme måde som kryptering, med den eneste undtagelse, at nøglerne følger i omvendt rækkefølge, det vil sige ikke fra den første til den Nte , men fra den N. til den første.

Algoritmisk beskrivelse

Klartekstblokken er opdelt i to lige store dele: . $(L_{0},\ R_{0})$
Hver runde beregner:

L_{i}\ =\ R_{{i-1}}\oplus f(L_{{i-1}},K_{{i-1}});

R_{i}\ =\ L_{{i-1}},

hvor:

i er rundens nummer ; $i=1\ldotsN;$
N er antallet af runder i den valgte krypteringsalgoritme;
$f$ - en eller anden funktion;
$K_{{i-1}}$ — nøglen til i-1 . runde (rundnøgle).

Resultatet af runderne er . I den N - te runde udføres permutationen og ikke, så det er muligt at bruge den samme procedure til dekryptering, blot ved at invertere rækkefølgen af at bruge nøglerne ( i stedet for ): $N$ $(L_{N},\ R_{N})$ $L_{N}$ $R_{N}$ $K_{N},K_{{N-1}},\ldots ,K_{0}$ $K_{0},K_{1},\ldots ,K_{N}$

L_{{i-1}}\ =\ R_{{i}}\oplus f(L_{{i}},\ K_{{i-1}})

R_{{i-1}}\ =\ L_{i}.

Med en lille ændring er det muligt at opnå fuldstændig identitet af krypterings- og dekrypteringsprocedurerne.

Fordele:

reversibilitet af algoritmen uanset den anvendte funktion f ;
evnen til at vælge en vilkårligt kompleks funktion f .

Matematisk beskrivelse

Overvej et eksempel. Lade:

X er en blok af data, der kommer ind i input (input blok);
A - en eller anden involutiv transformation (eller involution ) - en en-til-en transformation, der er omvendt i forhold til sig selv [3] , det vil sige, for hver ( ∀ ) X er udtrykket sandt:

AAX=A^{2}X=X,\foralt X;

Y er en blok af data modtaget ved udgangen (resultat).

Anvendelse af transformationen A én gang på inputblokken X vil resultere i outputblokken Y :

Y=AX.

Når du anvender transformation A på resultatet af den tidligere transformation - Y , får du:

AY=AAX=X,\foralt X.

Lad inputblokken X bestå af to underblokke L og R af samme længde:

X = (L, R).

Vi definerer to transformationer:

$G(X,K)$ - datakryptering X med nøgle K :

G(X,K)=G((L,R),K)=(L\plus F(K,R),R);

$T(L,R)$ — permutation af underblokke L og R :

T(L,R)=(R,L).

Lad os introducere notationen:

enkelt anvendelse af transformation G :

{\tilde {X}}=({\tilde {L)),{\tilde {R)))=GX;

ved at anvende transformationen G to gange :

{\tilde {{\tilde {X}}}}=({\tilde {{\tilde {L}}}},{\tilde {{\tilde {R}}}})=G^{2}X .

Lad os bevise involutiviteten af den dobbelte transformation G ( ). $G^{2}$

Det er let at se, at transformationen G kun ændrer den venstre underblok L , og efterlader den højre R uændret:

{\tilde {L}}=L\oplus F(K,R);

{\tilde {R}}=R.

Derfor vil vi i det følgende kun betragte underblokken L . Efter at have anvendt transformationen G til L to gange, får vi:

{\tilde {{\tilde {L))))={\tilde {L}}\oplus F(K,{\tilde {R)))={\tilde {L}}\oplus F(K,R )=L\plus F(K,R)\plus F(K,R)=L.

På denne måde:

G^{2}L=L;

G^{2}R=R,

følgelig

G^{2}X=X

og G er en involution .

Lad os bevise involutiviteten af den dobbelte transformation T ( ). $T^{2}$

T^{2}X=T^{2}(L,R)=T(R,L)=(L,R)=X.

Overvej krypteringsprocessen. Lade:

X er inputværdien;
$G_{i}$ — transformation med nøglen ; $K_{i}$
$Y_{i}$ — udgangsværdi, resultatet af den i - te runde .

Derefter kan transformationen udført på i+1 -te runde skrives som:

Y_{{i+1}}=TG_{i}Y_{i}

Transformation udført i 1. runde:

Y_{1}=TG_{1}X.

Derfor vil outputværdien efter m krypteringsrunder være:

Y_{m}=TG_{m}Y_{{m-1}}=TG_{m}TG_{{m-1}}\ldots TG_{1}X.

Det kan ses, at det på sidste trin ikke er nødvendigt at udføre en permutation af T .

Dekryptering udføres ved at anvende alle transformationerne i omvendt rækkefølge. På grund af involutiviteten af hver af transformationerne giver den omvendte rækkefølge det oprindelige resultat:

X=G_{1}TG_{2}T\ldots G_{{m-1}}TG_{m}T(Y_{m})=G_{1}TG_{2}T\ldots G_{{m-1 }}T(Y_{{m-1}})=\ldots =G_{1}T(Y_{1})=X.

Funktioner brugt i Feistel-netværk

I sit værk "Cryptography and Computer Security" [1] beskriver Horst Feistel to blokke af transformationer (funktioner ): $f(L_{{i}},\ K_{{i}})$

substitutionsblok (s-box, eng. s-box );
permutationsblok (p-boks, eng. p-boks ).

Det kan vises, at enhver binær transformation over en datablok med fast længde kan implementeres som en s-boks . På grund af kompleksiteten af strukturen af N -bit s-blokken for store N , anvendes enklere konstruktioner i praksis.

Udtrykket "blok" i den originale artikel [1] bruges i stedet for udtrykket "funktion" på grund af det faktum, at vi taler om en blokchiffer, og det blev antaget, at s- og p-blokke ville være digitale mikrokredsløb (digitale). blokke).

S-blok

Substitutionsblokken (s-box, eng. s-box ) består af følgende dele:

dekoder - konverter af et n - bit binært signal til et enkelt-bit signal i base ; $2^{n}$
switch system - interne forbindelser (samlet mulige forbindelser ); $2^{n}!$
encoder - signalkonverter fra single-bit -ær til n-bit binær. $2^{n}$

Analyse af en n -bit S-blok for stor n er ekstremt vanskelig, men det er meget vanskeligt at implementere en sådan blok i praksis, da antallet af mulige forbindelser er ekstremt stort ( ). I praksis bruges substitutionsblokken som en del af mere komplekse systemer. $2^{n}$

I det generelle tilfælde kan en s-blok have et forskelligt antal indgange/udgange; i dette tilfælde kan der i koblingssystemet ikke strengt taget én forbindelse gå fra hver udgang på dekoderen, men 2 eller flere, eller ikke gå kl. alle. Det samme gælder for encoder-indgangene.

I elektronik kan diagrammet til højre anvendes direkte. Ved programmering genereres erstatningstabeller. Begge disse tilgange er ækvivalente, dvs. en fil krypteret på en computer kan dekrypteres på en elektronisk enhed og omvendt.

Udskiftningsbord til den reducerede 3-bit s-boks

Kombinationsnr.	0	en	2	3	fire	5	6	7
Indgang	000	001	010	011	100	101	110	111
Afslut	011	000	001	100	110	111	010	101

P-blok

Permutationsblokken (p-blok, eng. p-boks ) ændrer blot positionen af tallene og er en lineær enhed. Denne blok kan have et meget stort antal input og output, men på grund af lineariteten kan systemet ikke betragtes som krypto-resistent.

Krypteringsanalyse af en nøgle for en n -bit p-blok udføres ved at levere n-1 forskellige meddelelser til input, som hver består af n-1 nuller ("0") og 1 enere ("1") (eller omvendt, fra etaller og nul).

Cyklisk skift

Det kan påvises, at det cykliske skift er et specialtilfælde af p-blokken.

I det enkleste tilfælde (skift med 1 bit) spaltes den ekstreme bit og flyttes til den anden ende af registeret eller bussen. Afhængigt af hvilken bit der tages, højre eller venstre, kaldes skiftet højre eller venstre. Forskydninger med flere bit kan opfattes som at anvende et skift med 1 flere gange.

Roter med m bit for en n -bit input ( m < n )

Skift retning	Bitrækkefølge før skift	Bitrækkefølge efter skift
Venstre	$b_{0},b_{1},b_{2},...,b_{{n-1}}$	$b_{m},b_{{m+1}},...b_{{n-1}},b_{0},b_{1},...,b_{{m-1}}$
ret	$b_{0},b_{1},b_{2},...,b_{{n-1}}$	$b_{{nm}},b_{{n-m+1}},...b_{{n-1}},b_{0},b_{1},...,b_{{nm-1 }}$

Tilføjelse modulo n

Operationen " addition modulo n " betegnes som

( A + B ) mod n

og er resten af at dividere summen A + B med n , hvor A og B er tal.

Det kan vises, at tilføjelsen af to tal modulo n er repræsenteret i det binære system som en s-blok, hvor tallet A føres til input , og et cyklisk skift til venstre med B bit bruges som omskiftning s-blokkens system.

I computerteknologi og elektronik er additionsoperationen som regel implementeret som modulo addition , hvor m er et heltal (normalt er m lig med maskinens kapacitet). For at komme i binær $n = 2^m$

A + B mod

2^{m}

det er nok at tilføje tallene og derefter kassere cifrene fra m - th og ældre.

Multiplikation modulo n

Multiplikation modulo n betegnes som

( A * B ) mod n

og er resten af at dividere produktet A * B med n , hvor A og B er tal.

I personlige computere på x86 -platformen opnås et tal med en kapacitet på 2 * m , når to m -bit tal multipliceres . For at få resten efter at have divideret med , skal du kassere de m mest signifikante bits. $2^{m}$

Eksempel på implementering i C -sprog

Generel visning af krypteringsalgoritmen ved hjælp af Feistel-netværket:

/* En funktion, der udfører transformationen af en underblok under hensyntagen til nøglens værdi (efter nøgle). Implementeringen afhænger af den valgte blokchifferalgoritme. */ int f ( int underblok , /* underblok for at konvertere */ int- tast /*-tast */ ); /* returværdi - konverteret blok */ /* Funktion, der udfører almindelig tekstkryptering */ ugyldig krypt ( int * venstre , /* venstre input underblok */ int * højre , /* højre input underblok */ int runder , /* antal runder */ int * nøgle /* række af nøgler (en nøgle pr. runde) */ ) { int i , temp ; for ( i = 0 ; i < runder ; i ++ ) { temp = * højre ^ f ( * venstre , tast [ i ] ); * højre = * venstre ; * venstre = temp ; } } /* Funktion, der udfører tekstdekryptering */ void dekrypter ( int * venstre , /* venstre krypteret underblok */ int * højre , /* højrekrypteret underblok */ int runder , /* antal runder */ int * nøgle /* række af nøgler (en nøgle pr. runde) */ ) { int i , temp ; for ( i = runder - 1 ; i >= 0 ; i - ) { temp = * venstre ^ f ( * højre , tast [ i ] ); * venstre = * højre ; * højre = temp ; } }

Fordele og ulemper

Fordele:

enkelhed af hardwareimplementering på en moderne elektronisk base;
let softwareimplementering på grund af det faktum, at en betydelig del af funktionerne understøttes på hardwareniveau i moderne computere (for eksempel modulo 2 addition ("xor") , modulo addition, modulo multiplikation osv.); $2^{n}$ $2^{n}$
godt kendskab til algoritmer baseret på Feistel netværk [4] .

Fejl:

i en runde er kun halvdelen af inputblokken krypteret [5] .

Teoretiske studier

Feistel-netværk er blevet bredt undersøgt af kryptografer på grund af deres udbredte brug. I 1988 foretog Michael Louby og Charles Rakoff forskning på Feistel-netværket og beviste, at hvis rundfunktionen er kryptografisk stærk pseudo-tilfældig, og de anvendte nøgler er uafhængige i hver runde, så vil 3 runder være nok for at blokchifferet er pseudo-tilfældig permutation, mens fire runder vil være nok til at lave en stærk pseudo-tilfældig permutation.

En " pseudo- tilfældig permutation " af Lubi og Rakoff er en, der er modstandsdygtig over for et adaptivt klartekstvalgsangreb, og en " stærk pseudo-tilfældig permutation " er en pseudo-tilfældig permutation, der er modstandsdygtig over for et valgt chiffertekstangreb.

Nogle gange i vestlig litteratur kaldes Feistel-netværket "Luby-Rackoff blokchifferet" til ære for Luby og Rackoff, som har lavet en stor mængde teoretisk forskning på dette område.

Senere, i 1997, foreslog Moni Naor og Omer Reingold en forenklet version af Lubi-Rakoff-konstruktionen, bestående af fire runder. Denne variant bruger to parvise uafhængige permutationer som første og sidste runde . De to midterste runder af Naor-Reingold-konstruktionen er identiske med runderne i Lubi-Rakoff-konstruktionen [6] .

Det meste af forskningen er afsat til studiet af specifikke algoritmer. Nogle sårbarheder er fundet i mange blokcifre baseret på Feistel-netværket, men i nogle tilfælde er disse sårbarheder rent teoretiske, og med den nuværende ydeevne på computere er det umuligt at bruge dem i praksis til cracking.

Ændringer af Feistel-netværket

Med en stor størrelse af krypteringsblokke (128 bit eller mere), kan implementeringen af et sådant Feistel-design på 32-bit arkitekturer forårsage vanskeligheder, så modificerede versioner af dette design bruges. Netværk med fire grene er almindeligt anvendt. Figuren viser de mest almindelige modifikationer. Der er også ordninger, hvor længderne af halvdelene og ikke matcher. Sådanne netværk kaldes ubalancerede . $L_0$ $R_{0}$

Feistel netværksændringer
Type 1
Type 2
Type 3

IDEA-algoritme

Kilde [7] :

Skema med én iteration af den fulde runde af IDEA- algoritmen

IDEA - algoritmen bruger et dybt modificeret Feistel-netværk. I den er 64-bit input-datablokke (betegnet med ) opdelt i 4 underblokke 16 bit lange . Hvert trin bruger 6 16-bit nøgler. I alt anvendes 8 hovedtrin og 1 forkortet. $X_{0}$ $X_{0}=\{X^{{(0)}}X^{{(1)}}X^{{(2)}}X^{{(3)}}\}$

Formler til beregning af værdien af underblokke i den i -te runde (for runde 1 til 8):

foreløbige beregninger:

A_{{i}}=((X_{{i-1}}^{{(0)}}*K_{{i}}^{{(1)}})\oplus (X_{{i-1 }}^{{(2)}}+K_{{i}}^{{(3)}}))*K_{{i}}^{{(5)}};

B_{{i}}=(((X_{{i-1}}^{{(1)}}+K_{{i}}^{{(2)}})\oplus (X_{{i- 1}}^{{(3)}}*K_{{i}}^{{(4)}})+A_{{i}})*K_{{i}}^{{(6)}} );

C_{{i}}=((X_{{i-1}}^{{(1)}}+K_{{i}}^{{(2)}})\oplus (X_{{i-1 }}^{{(3)}}*K_{{i}}^{{(4)}})+((X_{{i-1}}^{{(0)}}*K_{{i }}^{{(1)}})\oplus (X_{{i-1}}^{{(2)}}+K_{{i}}^{{(3)}}))*K_{ {i}}^{{(5)}})*K_{{i}}^{{(6)}};

endelige beregninger:

X_{{i}}^{{(0)}}\ =\ (X_{{i-1}}^{{(0)}}*K_{{i}}^{{(1)}}) \oplus B_{{i}};

X_{{i}}^{{(1)}}\ =\ (X_{{i-1}}^{{(2)}}+K_{{i}}^{{(3)}}) \oplus B_{{i}};

X_{{i}}^{{(2)}}\ =\ (X_{{i-1}}^{{(1)}}+K_{{i}}^{{(2)}}) \oplus (A_{{i}}+C_{{i}});

X_{{i}}^{{(3)}}\ =\ (X_{{i-1}}^{{(3)}}*K_{{i}}^{{(4)}}) \oplus (A_{{i}}+C_{{i}}),

hvor er den j -te nøgle på den i -te runde. $K_{{i}}^{{(j)}}$

Formel til beregning af 9. runde:

X_{{9}}^{{(0)}}\ =\ X_{{8}}^{{(0)}}*K_{{9}}^{{(1)}};

X_{{9}}^{{(1)}}\ =\ X_{{8}}^{{(2)}}+K_{{9}}^{{(2)}};

X_{{9}}^{{(2)}}\ =\ X_{{8}}^{{(1)}}+K_{{9}}^{{(3)}};

X_{{9}}^{{(3)}}\ =\ X_{{8}}^{{(3)}}*K_{{9}}^{{(4)}}.

Funktionens output vil være

Y=\{X_{{9}}^{{(0)}}X_{{9}}^{{(1)}}X_{{9}}^{{(2)}}X_{{9 }}^{{(3)}}\}.

Det ses, at s- og p-blokke ikke anvendes i deres rene form. De vigtigste operationer er:

modulo multiplikation ; $2^{{16}}+1=65537$
modulo tilføjelse . $2^{{16}}=65536$

Ciphere baseret på Feistel-netværket

Lucifer

Historisk set var den første algoritme, der brugte Feistel-netværket, " Lucifer "-algoritmen, under det arbejde, hvor Feistel faktisk udviklede strukturen, som senere blev kendt som "Feistel-netværket". I juni 1971 modtog Feistel et amerikansk patent nr. 3798359 [8] .

Den første version af " Lucifer " brugte 48-bit blokke og nøgler og brugte ikke "Feistel-netværket"-designet. En efterfølgende modifikation af algoritmen blev patenteret i John L. Smiths navn i november 1971 (US Patent 3.796.830; Nov 1971) [ 9 ] , og patentet indeholder både en beskrivelse af selve Feistel-netværket og en specifik krypteringsfunktion. Den brugte 64-bit nøgler og 32-bit blokke. Og endelig blev den seneste version foreslået i 1973 og drevet med 128-bit blokke og nøgler. Den mest komplette beskrivelse af "Lucifer"-algoritmen blev givet i artiklen af Arthur Sorkin ( eng. Arthur Sorkin ) "Lucifer. Cryptographic Algorithm" ("Lucifer, A Cryptographic Algorithm") i tidsskriftet "Cryptology" ("Cryptologia") for januar 1984 [10] .

Selvom den oprindelige modifikation af "Lucifer" klarede sig uden "Feistel-cellerne", demonstrerer den godt, hvordan kun brugen af s- og p-bokse i høj grad kan fordreje den originale tekst. Strukturen af "Lucifer"-algoritmen i prøven fra juni 1971 er en "sandwich" af to typer lag, der bruges på skift - de såkaldte SP-netværk (eller substitutions-permutationsnetværk). Den første type lag er en 128-bit p-blok, efterfulgt af et andet lag, som er 32 moduler, som hver består af to fire-bit s-blokke , hvis tilsvarende indgange er kortsluttede og den samme værdi føres til dem fra outputtet af det forrige lag. Men selve substitutionsblokkene er forskellige (de adskiller sig i substitutionstabeller). Udgangen af modulet modtager værdier fra kun én af s-boksene, hvilken en specifikt er bestemt af en af bits i nøglen, hvis nummer svarede til nummeret på s-boksen i strukturen. Et forenklet diagram over algoritmen med en mindre bitdybde og et ufuldstændigt antal runder er vist i figuren. Den bruger 16 s-boks-vælgere (til i alt 32 s-bokse), så denne ordning bruger en 16-bit nøgle.

Lad os nu overveje, hvordan chifferteksten vil ændre sig i ovenstående algoritme, når kun en bit ændres. For nemheds skyld tager vi tabeller over s-blok- erstatninger , således at hvis alle nuller føres til input af en s-blok, så vil alle nuller også blive outputtet. I kraft af vores valg af s-blokke, hvis alle nuller føres til indgangen på krypteringsenheden, så vil udgangen af enheden være alle nuller. I rigtige systemer bruges sådanne substitutionstabeller ikke, da de i høj grad forenkler arbejdet for en kryptoanalytiker, men i vores eksempel illustrerer de tydeligt det stærke inter-karakter-forhold, når man ændrer en bit af den krypterede meddelelse. Det kan ses, at på grund af den første p-blok, flytter den eneste enhed til midten af blokken, derefter "multiplicerer" den næste ikke-lineære s-blok den, og allerede to enheder ændrer deres position på grund af den næste p -blok osv. I slutningen af krypteringsenheden, på grund af den stærke inter-symbol kobling, blev udgangsbittene en kompleks funktion af inputtet og den anvendte nøgle. I gennemsnit vil halvdelen af bits være "0" og halvdelen "1" i outputtet.

I sin kerne er Feistel-netværket et alternativ til komplekse SP-netværk og bruges meget mere udbredt. Fra et teoretisk synspunkt kan den runde krypteringsfunktion reduceres til et SP-netværk, men Feistel-netværket er mere praktisk, da kryptering og dekryptering kan udføres af samme enhed, men i omvendt rækkefølge af de anvendte nøgler. Den anden og tredje version af algoritmen (ved hjælp af Feistel-netværket) fungerede på 32-bit blokke med en 64-bit nøgle og 128-bit blokke med 128-bit nøgler. I den seneste (tredje) version var den runde krypteringsfunktion arrangeret meget enkelt - først blev den krypterede underblok sendt gennem et lag af 4-bit s-blokke (svarende til lag i SP-netværk, kun s-blokken er konstant og afhænger ikke af tonearten), så til den modulo 2 blev der tilføjet en rund nøgle, hvorefter resultatet blev ført gennem p-blokken.

DES

Funktion (hvor: $f(L_{i},K_{i})$

$L_i$ — 32-bit inputblok ved den i - te iteration;
$K_{i}$ - 48-bit nøgle ved denne iteration)

i DES-algoritmen består af følgende operationer:

udvidelse af inputblokken L til 48 bit (nogle inputbit kan gentages);
Modulo 2 tilføjelse med nøgle : $K_{i}$

{\tilde {L_{i}}}=L_{i}\oplus K_{i};

opdeling af resultatet i 8 blokke af 6 bit hver:

{\tilde {L_{i))}=\{{\tilde {L_{i))}^{{(0)}}{\tilde {L_{i))}^{{(1))){ \tilde {L_{i}}}^{{(2)}}{\tilde {L_{i}}}^{{(3))){\tilde {L_{i}}}^{{(4 )}}{\tilde {L_{i}}}^{{(5)}}{\tilde {L_{i}}}^{{(6))){\tilde {L_{i}}}^ {{(7)}}\};

de modtagne informationsblokke føres til substitutionsblokke med 6-bit input og 4-bit output; ${\tilde {L_{i}^{{(j)))))$
ved udgangen kombineres 4-bit blokke til en 32-bit blok, som er resultatet af funktionen . $f(L_{i},K_{i})$

Det samlede antal runder i DES-algoritmen er 16.

"Magma"

Funktionen (hvor og er 32-bit tal) beregnes som følger: $f(L_{i},K_{i})$ $L_i$ $K_{i}$

tilføje modulo : _ $L_i$ $K_{i}$ $2^{32}$

{\tilde {L_{i))}=(L_{i}+K_{i})\ {\bmod \ }2^{{32}};

resultatet opdeles i 8 4-bit blokke, som føres ind i 4-bit s-blokke (som kan være forskellige);
udgangene fra s-boksene kombineres til et 32-bit tal, som derefter roteres 11 bit til venstre;
resultatet er resultatet af funktionen.

Antallet af runder i GOST 28147-89-algoritmen er 32.

Sammenlignende liste over algoritmer

Følgende blokcifre bruger det klassiske eller modificerede Feistel-netværk som grundlag.

Algoritme	År	Antal runder	Nøglens længde	Blokstørrelse	Antal underblokke
blæsefisk	1993	16	fra 32 til 448	64	2
Camellia	2000	18/24	128/192/256	128	2
CAST-128	1996	16/12	40-128	64	2
CAST-256	1998	12×4=48	128/192/256	128	2
CIFERUNIKORN-A	2000	16	128/192/256	128	2
CIFERUNIKORN-E	1998	16	128	64	2
CLEFIA	2007	16	128/192/256	128	16
DEL	1998	6 (8)	(128/192) 256	128	2
DES	1977	16	56	64	2
DFC	1998	otte	128/192/256	128	?
FEAL	1987	4-32	64	64	2
GOST 28147-89	1989 [2]	32/16	256	64	2
IDE	1991	8+1	128	64	fire
KASUMI	1999	otte	128	64	2
Khufu	1990	16-32/64	512	64	2
LOKI97	1997	16	128/192/256	128	2
Lucifer	1971	16	48/64/128	48/32/128	2
MacGuffin	1994	32	128	64	fire
MAGENTA	1998	6/8	128/192/256	128	2
MARS	1998	32	128-1248	128	2
Barmhjertighed	2000	6	128	4096	?
MISTY1	1995	4×n(8)	128	64	fire
Raiden	2006	16	128	64	2
RC2	1987	16+2	8-128	64	fire
RC5	1994	1-255(12)	0-2040(128)	32/64/128	2
RC6	1998	tyve	128/192/256	128	fire
RTEA	2007	48/64	128/256	64	2
FRØ	1998	16	128	128	2
Sinople	2003	64	128	128	fire
skipjack	1998	32	80	64	fire
TE	1994	64	128	64	2
Triple DES	1978	32/48	112/168	64	2
To fisk	1998	16	128/192/256	128	fire
XTEA	1997	64	128	64	2
XTEA-3	1999	64	256	128	fire
XXTEA	1998	12-64	128	64	2

Noter

↑ 1 2 3 Horst Feistel "Kryptografi og computerbeskyttelse" (engelsk) ("Kryptografi og computersikkerhed"). Oversættelse Arkiveret 11. marts 2018 på Wayback Machine af Andrey Vinokurov.
↑ 1 2 Vinokurov A. Artikel Arkiveret 1. april 2022 på Wayback-maskinen "GOST 28147-89 Encryption Algorithm, Its Use and Implementation for Intel x86 Platform Computers ". En del af materialerne inkluderet i denne artikel blev offentliggjort i nummeret "# 1.5 / 1995" af magasinet "Monitor".
↑ Diskret matematik. Algoritmer. Symmetriske systemer og blokcifre (utilgængeligt link) . Hentet 21. november 2008. Arkiveret fra originalen 5. december 2012. (ubestemt)
↑ Sergey Panasenko. " Moderne krypteringsalgoritmer arkiveret 31. januar 2010 på Wayback Machine " // Byte Magazine. Udgave nr. 8 (60), august 2003.
↑ Barichev, Goncharov, Serov, 2011 .
↑ Om konstruktionen af pseudo-tilfældig permutation: Luby-Rackoff revisited.
↑ Menezes, Oorschot, Vanstone, 1996 , §7.6 IDEA, s. 263.
↑ US patent 3.798.359
↑ US patent 3.796.830
↑ Arthur Sorkin. Lucifer, en kryptografisk algoritme. Cryptologia, udgave 8(1), januar 1984, s. 22-41, suppleret i nummer 8(3), s. 260-261

Litteratur

Barichev S. G. , Goncharov V. V. , Serov R. E. Fundamentals of modern cryptography - 3. udg. — M .: Dialogue-MEPhI , 2011. — 176 s. — ISBN 978-5-9912-0182-7
Menezes A. J. , Oorschot P. v. , Vanstone S. A. Handbook of Applied Cryptography (engelsk) - CRC Press , 1996. - 816 s. — ( Diskret matematik og dens anvendelser ) — ISBN 978-0-8493-8523-0

Symmetriske kryptosystemer
Stream-cifre	A3 A5 A8 Decim F-FCSR Korn HC-256 KCipher-2 MICKEY MUGI GEDD Phelix RC4 Kanin FORSEGLE SNE SOSEMANUK Salsa 20 STRUMOK Trivium VMPC
Feistel netværk	GOST 28147-89 (Magma) blæsefisk Camellia CAST-128 CAST-256 CIFERUNIKORN-A CIFERUNIKORN-E CLEFIA Cobra DEL DES DESX DFC E2 ENRUPT FEAL HPC IDE KASUMI Khafre Khufu LOKI97 MacGuffin MARS MESH MISTY1 NyDES NDS RC5 RC6 FRØ Simon Sinople skipjack SM4 Speck TE XTEA XXTEA Raiden RTEA Triple DES To fisk
SP netværk	Græshoppe 3 vejs ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Bælte CRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer til stede Regnbue SIKRERE HAJ FIRKANT Slange tre fisk
Andet	FRØ NUSH REDOC SC2000 SHACAL CS-Cipher