Rețeaua Feistel

Rețeaua lui Feistel , sau designul lui Feistel ( ing. Rețeaua Feistel, cifrul Feistel ), este una dintre metodele de construire a cifrurilor bloc . Rețeaua este formată din celule numite celule Feistel . Intrarea fiecărei celule primește date și o cheie. La ieșirea fiecărei celule, sunt primite datele modificate și cheia modificată. Toate celulele sunt de același tip și spun că rețeaua este o anumită structură repetată ( iterată ). Cheia este selectată în funcție de algoritmul de criptare/decriptare și se modifică la trecerea de la o celulă la alta. Criptarea și decriptarea efectuează aceleași operațiuni; diferă doar ordinea tastelor . Datorita simplitatii operatiunilor, reteaua Feistel este usor de implementat atat in software cat si in hardware. Un număr de cifruri bloc ( DES , RC2 , RC5 , RC6 , Blowfish , FEAL , CAST-128 , TEA , XTEA , XXTEA , etc.) folosesc ca bază rețeaua Feistel. O alternativă la rețeaua Feistel este rețeaua de permutare-permutare ( AES , etc.).

Istorie

În 1971, Horst Feistel a brevetat două dispozitive care implementau diverși algoritmi de criptare , denumiti mai târziu „ Lucifer ” ( ing. Lucifer ). Unul dintre aceste dispozitive a folosit un design numit mai târziu „rețeaua Feistel” ( în engleză Feistel cipher , Feistel network ). Apoi, Feistel a lucrat la crearea de noi criptosisteme în interiorul zidurilor IBM împreună cu Don Coppersmith . Proiectul Lucifer a fost mai degrabă experimental, dar a devenit baza algoritmului DES ( standardul de criptare a datelor de ing . ) . În 1973, revista Scientific American a publicat articolul lui Feistel „Cryptography and computer security” ( Eng. Cryptography and computer privacy ) [1] , care dezvăluia câteva aspecte importante ale criptării și descria prima versiune a proiectului Lucifer . Prima versiune a Proiectului Lucifer nu a folosit rețeaua Feistel.

Pe baza rețelei Feistel, a fost proiectat algoritmul DES. În 1977, autoritățile americane au adoptat standardul FIPS 46-3 , recunoscând DES ca metoda standard pentru criptarea datelor. DES a fost utilizat pe scară largă în sistemele criptografice de ceva timp. Structura iterativă a algoritmului a făcut posibilă crearea de implementări software și hardware simple.

Potrivit unor date [2] , în URSS , deja în anii 1970, KGB -ul a dezvoltat un cifr în bloc care folosea rețeaua Feistel și, probabil, acest cifr a fost adoptat în 1990 ca GOST 28147-89 .

În 1987, au fost dezvoltați algoritmii FEAL și RC2 . Rețelele Feistel s-au răspândit în anii 1990 - în anii apariției unor algoritmi precum Blowfish (1993), TEA (1994), RC5 (1994), CAST-128 (1996), XTEA (1997), XXTEA (1998), RC6 (1998) și alții.

La 2 ianuarie 1997, Institutul NIST a anunțat un concurs pentru a crea un nou algoritm de criptare a datelor care să înlocuiască DES . Noul cifru bloc a fost denumit AES ( un standard avansat de criptare ) și a fost aprobat la 26 mai 2002 . AES folosește o rețea de substituție-permutare în loc de o rețea Feistel .

Proiectare de criptare bloc bazată pe rețele Feistel

Descriere simplă

Criptare

Să fie necesară criptarea unor informații prezentate în formă binară (sub forma unei secvențe de zerouri și unu ) și situate în memoria unui computer sau a altui dispozitiv (de exemplu, într- un fișier ).

algoritm de criptare.

Informațiile sunt împărțite în blocuri de aceeași lungime (fixă). Blocurile rezultate se numesc input , deoarece sunt introduse în algoritm. Dacă lungimea blocului de intrare este mai mică decât dimensiunea pe care algoritmul de criptare selectat o poate cripta la un moment dat (dimensiunea blocului), atunci blocul este prelungit într-un fel. De obicei, lungimea blocului este o putere de doi, cum ar fi 64 de biți sau 128 de biți.

În plus, vom lua în considerare operațiunile care au loc cu un singur bloc, deoarece aceleași operațiuni sunt efectuate cu alte blocuri în timpul procesului de criptare.

Blocul selectat este împărțit în două subblocuri de aceeași dimensiune - „stânga” ( ) și „dreapta” ( ). $L_0$ $R_{0}$
„Subblocul din dreapta” este modificat de funcția F folosind tasta rotundă : $R_{0}$ $K_{0}$

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

Rezultatul este adăugat modulo 2 ("xor") cu "subblocul din stânga" : $L_0$

x=x\oplus L_{0}.

Rezultatul va fi folosit în runda următoare ca „subbloc dreapta” : $R_{1}$

R_{1}=x.

„Subblocul din dreapta” al rundei curente (în forma sa nemodificată la începutul rundei) va fi folosit în runda următoare ca „subblocul din stânga” : $R_{0}$ $L_{1}$

L_{1}=R_{0}.

Conform unor reguli matematice, se calculează o cheie rotundă - cheia care va fi folosită în runda următoare. $K_1$

Operațiile enumerate sunt efectuate de N-1 ori, unde N este numărul de runde din algoritmul de criptare selectat. În acest caz, între trecerile de la o rundă (etapă) la alta, tastele se schimbă: se înlocuiește cu , - cu , etc.). $K_{0}$ $K_1$ $K_1$ $K_{2}$

Decriptare

Decriptarea informațiilor are loc în același mod ca și criptarea, cu singura excepție că cheile urmează în ordine inversă, adică nu de la prima la a N -a , ci de la a N -a la prima.

Descriere algoritmică

Blocul text simplu este împărțit în două părți egale: . $(L_{0},\ R_{0})$
Fiecare rundă calculează:

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

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

Unde:

i este numărul rundei ; $i=1\ldotsN;$
N este numărul de runde din algoritmul de criptare selectat;
$f$ - o anumită funcție;
$K_{{i-1}}$ — cheia rundei i-1 (cheie rotundă).

Rezultatul rundelor este . În runda a N - a, permutarea și nu se efectuează, astfel încât este posibil să se folosească aceeași procedură pentru decriptare, pur și simplu prin inversarea ordinii de utilizare a cheilor ( în loc de ): $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}.

Cu o mică modificare, este posibil să obțineți o identitate completă a procedurilor de criptare și decriptare.

Avantaje:

reversibilitatea algoritmului indiferent de funcţia f utilizată ;
capacitatea de a alege o funcție arbitrar complexă f .

Descriere matematică

Luați în considerare un exemplu. Lăsa:

X este un bloc de date care intră în intrare (blocul de intrare);
A - o transformare involutivă (sau involuție ) - o transformare unu-la-unu care este inversă cu sine [3] , adică pentru fiecare ( ∀ ) X , expresia este adevărată:

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

Y este un bloc de date primite la ieșire (rezultat).

Aplicarea transformării A o dată la blocul de intrare X va avea ca rezultat blocul de ieșire Y :

Y=AX.

Când aplicați transformarea A la rezultatul transformării anterioare - Y , obțineți:

AY=AAX=X,\forall X.

Fie că blocul de intrare X este format din două subblocuri L și R de lungime egală:

X=(L, R).

Definim doua transformari:

$G(X,K)$ - criptarea datelor X cu cheia K :

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

$T(L,R)$ — permutarea subblocurilor L și R :

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

Să introducem notația:

aplicare unică a transformării G :

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

aplicând transformarea G de două ori :

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

Să demonstrăm involutivitatea transformării duble G ( ). $G^{2}$

Este ușor de observat că transformarea G modifică doar subblocul stâng L , lăsând neschimbat pe dreapta R :

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

{\tilde {R}}=R.

Prin urmare, în cele ce urmează, vom lua în considerare doar subblocul L . După aplicarea transformării G în L de două ori, obținem:

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

În acest fel:

G^{2}L=L;

G^{2}R=R,

prin urmare

G^{2}X=X

iar G este o involuție .

Să demonstrăm involutivitatea transformării duble T ( ). $T^{2}$

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

Luați în considerare procesul de criptare. Lăsa:

X este valoarea de intrare;
$G_{i}$ — transformarea cu cheia ; $K_{i}$
$Y_{i}$ — valoarea de ieșire, rezultatul rundei i - a .

Apoi transformarea efectuată în runda i+1 -a poate fi scrisă astfel:

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

Transformare efectuată în prima rundă:

Y_{1}=TG_{1}X.

Prin urmare, valoarea de ieșire după m runde de criptare va fi:

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

Se poate observa că în ultima etapă nu este necesară efectuarea unei permutări a lui T .

Decriptarea se realizează prin aplicarea tuturor transformărilor în ordine inversă. Datorită involutivității fiecăreia dintre transformări, ordinea inversă dă rezultatul inițial:

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.

Funcții utilizate în rețelele Feistel

În lucrarea sa „Cryptography and Computer Security” [1] , Horst Feistel descrie două blocuri de transformări (funcții ): $f(L_{{i}},\ K_{{i}})$

bloc de substituție (s-box, ing. s-box );
bloc de permutare (p-box, ing. p-box ).

Se poate arăta că orice transformare binară pe un bloc de date cu lungime fixă poate fi implementată ca s-box . Datorită complexității structurii blocului s de N -biți pentru N mari , în practică sunt utilizate construcții mai simple.

Termenul „bloc” din articolul inițial [1] este folosit în locul termenului „funcție” datorită faptului că vorbim despre un cifru bloc și s-a presupus că blocurile s- și p ar fi microcircuite digitale (digitale blocuri).

S-bloc

Blocul de substituție (s-box, ing. s-box ) este format din următoarele părți:

decodor - convertor al unui semnal binar de n biți într-un semnal de un singur bit în bază ; $2^{n}$
sistem comutator - conexiuni interne (total conexiuni posibile ); $2^{n}!$
encoder - convertor de semnal de la un-bit -ary la n-bit binary. $2^{n}$

Analiza unui bloc S de n -biți pentru n mare este extrem de dificilă, dar este foarte dificil de implementat un astfel de bloc în practică, deoarece numărul de conexiuni posibile este extrem de mare ( ). În practică, blocul de substituție este utilizat ca parte a unor sisteme mai complexe. $2^{n}$

În cazul general, un bloc s poate avea un număr diferit de intrări/ieșiri; în acest caz, în sistemul de comutare, nu poate merge strict o conexiune de la fiecare ieșire a decodorului, ci 2 sau mai multe, sau nu merge la toate. Același lucru este valabil și pentru intrările codificatorului.

În electronică, diagrama din dreapta poate fi aplicată direct. În programare, sunt generate tabele de înlocuire. Ambele abordări sunt echivalente, adică un fișier criptat pe un computer poate fi decriptat pe un dispozitiv electronic și invers.

Tabel de înlocuire pentru s-box redus de 3 biți

Combinația nr.	0	unu	2	3	patru	5	6	7
Intrare	000	001	010	011	100	101	110	111
Ieșire	011	000	001	100	110	111	010	101

P-bloc

Blocul de permutare (p-block, ing. p-box ) schimbă doar poziția numerelor și este un dispozitiv liniar. Acest bloc poate avea un număr foarte mare de intrări și ieșiri, totuși, datorită liniarității, sistemul nu poate fi considerat criptorezistent.

Criptanaliza unei chei pentru un bloc p de n biți se realizează prin furnizarea de n-1 mesaje diferite la intrare, fiecare dintre ele constând din n-1 zerouri ("0") și 1 unu ("1") (sau invers, de la unu și zero).

Schimbarea ciclică

Se poate demonstra că deplasarea ciclică este un caz special al blocului p.

În cel mai simplu caz (deplasare cu 1 bit), bitul extrem este despărțit și mutat la celălalt capăt al registrului sau magistralei. În funcție de bitul luat, dreapta sau stânga, schimbarea se numește dreapta sau stânga. Schimbările cu mai mulți biți pot fi considerate ca aplicând o schimbare de 1 de mai multe ori.

Rotiți cu m biți pentru o intrare de n biți ( m < n )

Schimbați direcția	Ordine de biți înainte de tură	Ordine de biți după schimb
Stânga	$b_{0},b_{1},b_{2},...,b_{{n-1}}$	$b_{m},b_{{m+1}},...b_{{n-1}},b_{0},b_{1},...,b_{{m-1}}$
dreapta	$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 }}$

Adăugarea modulo n

Operația „ adăugare modulo n ” se notează ca

( A + B ) mod n

și este restul împărțirii sumei A + B la n , unde A și B sunt numere.

Se poate demonstra că adăugarea a două numere modulo n este reprezentată în sistemul binar ca un bloc s, în care numărul A este alimentat la intrare și o deplasare ciclică la stânga cu B biți este utilizată ca comutare. sistemul blocului s.

În tehnologia computerelor și electronică , operația de adunare, de regulă, este implementată ca adiție modulo , unde m este un număr întreg (de obicei, m este egal cu capacitatea mașinii). Pentru a intra în binar $n = 2^m$

A + B mod

2^{m}

este suficient să adăugați numerele și apoi să aruncați cifrele începând de la m - al- lea și mai vechi.

Înmulțirea modulo n

Înmulțirea modulo n se notează ca

( A * B ) mod n

și este restul împărțirii produsului A * B la n , unde A și B sunt numere.

În calculatoarele personale de pe platforma x86 , la înmulțirea a două numere m -biți, se obține un număr cu o capacitate de 2 * m . Pentru a obține restul după împărțirea la , trebuie să eliminați cei mai importanți biți. $2^{m}$

Exemplu de implementare în limbaj C

Vedere generală a algoritmului de criptare folosind rețeaua Feistel:

/* O funcție care realizează transformarea unui subbloc, ținând cont de valoarea cheii (cu cheie). Implementarea depinde de algoritmul de cifrare bloc selectat. */ int f ( int subbloc , /* subbloc pentru conversie */ tasta int /* tasta */ ); /* valoarea returnată - bloc convertit */ /* Funcție care realizează criptarea textului simplu */ criptă goală ( int * left , /* left input subbloc */ int * right , /* right input subbloc */ int runde , /* numărul de runde */ int * key /* matrice de chei (o cheie pe rundă) */ ) { int i , temp ; pentru ( i = 0 ; i < rotunji ; i ++ ) { temp = * dreapta ^ f ( * stânga , tasta [ i ] ); * dreapta = * stânga ; * stânga = temp ; } } /* Funcție care realizează decriptarea textului */ void decripta ( int * left , /* stânga subbloc criptat */ int * dreapta , /* dreapta subbloc criptat */ int runde , /* numărul de runde */ int * key /* matrice de chei (o cheie pe rundă) */ ) { int i , temp ; pentru ( i = rotunjește - 1 ; i >= 0 ; i -- ) { temp = * stânga ^ f ( * dreapta , tasta [ i ] ); * stânga = * dreapta ; * dreapta = temp ; } }

Avantaje și dezavantaje

Avantaje:

simplitatea implementării hardware pe o bază electronică modernă;
ușurința implementării software datorită faptului că o parte semnificativă a funcțiilor sunt suportate la nivel hardware în computerele moderne (de exemplu, adăugare modulo 2 ("xor") , adăugare modulo, multiplicare modulo etc.); $2^{n}$ $2^{n}$
bună cunoaștere a algoritmilor bazați pe rețele Feistel [4] .

Defecte:

într-o rundă doar jumătate din blocul de intrare este criptat [5] .

Studii teoretice

Rețelele Feistel au fost studiate pe scară largă de criptografi datorită utilizării lor pe scară largă. În 1988, Michael Louby și Charles Rakoff au efectuat cercetări asupra rețelei Feistel și au demonstrat că, dacă funcția rotundă este pseudo-aleatoare criptografic puternică, iar cheile utilizate sunt independente în fiecare rundă, atunci 3 runde vor fi suficiente pentru ca cifra de bloc să fie permutare pseudo-aleatoare, în timp ce patru runde vor fi suficiente pentru a face o permutare pseudo-aleatoare puternică.

O „ permutare pseudo-aleatoare ” a lui Lubi și Rakoff este una care este rezistentă la un atac de alegere de text simplu adaptiv, iar o „ permutare pseudo-aleatorie puternică ” este o permutare pseudo-aleatoare care este rezistentă la un atac de text cifrat ales.

Uneori, în literatura occidentală, rețeaua Feistel este numită „cifrul bloc Luby-Rackoff” în onoarea lui Luby și Rackoff, care au făcut o mare cantitate de cercetări teoretice în acest domeniu.

Mai târziu, în 1997, Moni Naor și Omer Reingold au propus o versiune simplificată a construcției Lubi-Rakoff, constând din patru runde. Această variantă folosește două permutări independente pe perechi ca prima și ultima rundă . Cele două runde din mijloc ale construcției Naor-Reingold sunt identice cu cele din construcția Lubi-Rakoff [6] .

Cea mai mare parte a cercetării este dedicată studiului unor algoritmi specifici. Unele vulnerabilități au fost găsite în multe cifruri bloc bazate pe rețeaua Feistel, dar în unele cazuri aceste vulnerabilități sunt pur teoretice și, odată cu performanța actuală a computerelor, este imposibil să le folosești în practică pentru cracare.

Modificări ale rețelei Feistel

Cu o dimensiune mare a blocurilor de criptare (128 de biți sau mai mult), implementarea unui astfel de design Feistel pe arhitecturi pe 32 de biți poate provoca dificultăți, așa că sunt utilizate versiuni modificate ale acestui design. Rețelele cu patru ramuri sunt utilizate în mod obișnuit. Figura prezintă cele mai frecvente modificări. Există, de asemenea, scheme în care lungimile jumătăților și nu se potrivesc. Astfel de rețele sunt numite dezechilibrate . $L_0$ $R_{0}$

Modificări ale rețelei Feistel
Tipul 1
Tip 2
Tip 3

Algoritmul IDEA

Sursa [7] :

Schema unei iterații a rundei complete a algoritmului IDEA

Algoritmul IDEA folosește o rețea Feistel profund modificată. În acesta, blocurile de date de intrare pe 64 de biți (notate cu ) sunt împărțite în 4 subblocuri cu lungimea de 16 biți . Fiecare etapă folosește 6 chei pe 16 biți. În total, sunt utilizate 8 etape principale și 1 scurtată. $X_{0}$ $X_{0}=\{X^{{(0)}}X^{{(1)}}X^{{(2)}}X^{{(3)}}\}$

Formule pentru calcularea valorii subblocurilor în runda i -a (pentru rundele 1 până la 8):

calcule preliminare:

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)}};

calcule finale:

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}}),

unde este tasta j -a pe runda i -a. $K_{{i}}^{{(j)}}$

Formula de calcul a rundei a 9-a:

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)}}.

Ieșirea funcției va fi

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

Se poate observa că blocurile s și p nu sunt utilizate în forma lor pură. Principalele operațiuni sunt:

înmulțire modulo ; $2^{{16}}+1=65537$
adunare modulo . $2^{{16}}=65536$

Cifre bazate pe rețeaua Feistel

Lucifer

Din punct de vedere istoric, primul algoritm care a folosit rețeaua Feistel a fost algoritmul „ Lucifer ”, în timpul lucrării pe care Feistel a dezvoltat de fapt structura, care mai târziu a devenit cunoscută sub numele de „rețeaua Feistel”. În iunie 1971, Feistel a primit un brevet american nr. 3798359 [8] .

Prima versiune a „ Lucifer ” a folosit blocuri și chei pe 48 de biți și nu a folosit designul „rețea Feistel”. O modificare ulterioară a algoritmului a fost brevetată în numele lui John L. Smith în noiembrie 1971 (brevet SUA 3.796.830; noiembrie 1971) [ 9 ] , iar brevetul conține atât o descriere a rețelei Feistel în sine, cât și o anumită funcții de criptare. A folosit chei de 64 de biți și blocuri de 32 de biți. Și, în sfârșit, cea mai recentă versiune a fost propusă în 1973 și a funcționat cu blocuri și chei de 128 de biți. Cea mai completă descriere a algoritmului „Lucifer” a fost dată în articolul lui Arthur Sorkin ( ing. Arthur Sorkin ) „Lucifer. Cryptographic Algorithm" ("Lucifer, A Cryptographic Algorithm") în revista "Cryptology" ("Cryptologia") pentru ianuarie 1984 [10] .

Deși modificarea originală a lui „Lucifer” a făcut fără „celulele Feistel”, ea demonstrează bine cum numai utilizarea casetelor s și p poate distorsiona foarte mult textul original. Structura algoritmului „Lucifer” din eșantionul din iunie 1971 este un „sandwich” din două tipuri de straturi utilizate pe rând - așa-numitele rețele SP (sau rețele de substituție-permutare). Primul tip de strat este un bloc p de 128 de biți, urmat de un al doilea strat, care este de 32 de module, fiecare dintre ele constând din două blocuri s de patru biți , ale căror intrări corespunzătoare sunt scurtcircuitate și aceeași valoare este alimentată la acestea din ieșirea stratului anterior . Dar blocurile de substituție în sine sunt diferite (diferă în tabelele de înlocuire). Ieșirea modulului primește valori doar de la una dintre casetele s, care este determinată în mod specific de unul dintre biții din cheie, numărul cărora corespundea numărului casetei s din structură. O diagramă simplificată a algoritmului cu o adâncime de biți mai mică și un număr incomplet de runde este prezentată în figură. Folosește 16 selectoare s-box (pentru un total de 32 s-box), așa că această schemă folosește o cheie de 16 biți.

Să luăm acum în considerare modul în care textul cifrat se va schimba în algoritmul de mai sus, când se schimbă doar un bit. Pentru simplitate, luăm tabele de înlocuiri ale blocurilor s, astfel încât, dacă toate zerourile sunt introduse la intrarea unui bloc s, atunci toate zerourile vor fi de asemenea scoase. În virtutea alegerii noastre de blocuri s, dacă toate zerourile sunt introduse la intrarea dispozitivului de criptare, atunci ieșirea dispozitivului va fi toate zerourile. În sistemele reale, astfel de tabele de substituție nu sunt utilizate, deoarece simplifică foarte mult munca unui criptoanalist, dar în exemplul nostru ele ilustrează clar relația puternică între caractere atunci când se schimbă un bit al mesajului criptat. Se poate observa că, datorită primului bloc p, singura unitate se deplasează în centrul blocului, apoi următorul bloc s neliniar îl „multipește” și deja două unități își schimbă poziția datorită următorului p -bloc etc. La sfârşitul dispozitivului de criptare, datorită cuplării puternice între simboluri, biţii de ieşire au devenit o funcţie complexă a intrării şi a cheii utilizate. În medie, jumătate din biți vor fi „0” și jumătate „1” în ieșire.

În esență, rețeaua Feistel este o alternativă la rețelele SP complexe și este utilizată mult mai pe scară largă. Din punct de vedere teoretic, funcția de criptare rotundă poate fi redusă la o rețea SP, dar rețeaua Feistel este mai practică, deoarece criptarea și decriptarea pot fi efectuate de același dispozitiv, dar cu ordinea inversă a cheilor utilizate. A doua și a treia versiune a algoritmului (folosind rețeaua Feistel) au funcționat pe blocuri de 32 de biți cu o cheie de 64 de biți și blocuri de 128 de biți cu chei de 128 de biți. În cea mai recentă (a treia) versiune, funcția de criptare rotundă a fost aranjată foarte simplu - mai întâi, subblocul criptat a fost trecut printr-un strat de blocuri s de 4 biți (asemănător cu straturile din rețelele SP, doar blocul s este constant și nu depinde de cheie), apoi i s-a adăugat modulo 2 o cheie rotundă, după care rezultatul a fost trecut prin blocul p.

DES

Funcție (unde: $f(L_{i},K_{i})$

$L_i$ — bloc de intrare pe 32 de biți la i - a iterație;
$K_{i}$ - cheie pe 48 de biți la această iterație)

în algoritmul DES constă din următoarele operații:

extinderea blocului de intrare L la 48 de biți (unii biți de intrare pot fi repeți);
Adăugarea Modulului 2 cu cheie : $K_{i}$

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

împărțirea rezultatului în 8 blocuri a câte 6 biți fiecare:

{\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)}}\};

blocurile de informații primite sunt alimentate la blocuri de substituție având intrări de 6 biți și ieșiri de 4 biți; ${\tilde {L_{i}^{{(j)))))$
la ieșire, blocurile de 4 biți sunt combinate într-un bloc de 32 de biți, care este rezultatul funcției . $f(L_{i},K_{i})$

Numărul total de runde în algoritmul DES este de 16.

„Magma”

Funcția (unde și sunt numere de 32 de biți) se calculează după cum urmează: $f(L_{i},K_{i})$ $L_i$ $K_{i}$

adunați modulo : _ $L_i$ $K_{i}$ $2^{32}$

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

rezultatul este împărțit în 8 blocuri de 4 biți, care sunt alimentate în blocuri s de 4 biți (care pot fi diferite);
ieșirile s-box-urilor sunt combinate într-un număr de 32 de biți, care este apoi rotit cu 11 biți spre stânga;
rezultatul este rezultatul funcției.

Numărul de runde în algoritmul GOST 28147-89 este 32.

Lista comparativă de algoritmi

Următoarele cifruri bloc folosesc ca bază rețeaua Feistel clasică sau modificată.

Algoritm	An	Numărul de runde	Lungimea cheii	Dimensiunea blocului	Numărul de subblocuri
blowfish	1993	16	de la 32 la 448	64	2
Camelia	2000	18/24	128/192/256	128	2
CAST-128	1996	12/16	40-128	64	2
CAST-256	1998	12×4=48	128/192/256	128	2
CIFERUNICORN-A	2000	16	128/192/256	128	2
CIFERUNICORN-E	1998	16	128	64	2
CLEFIA	2007	16	128/192/256	128	16
AFACERE	1998	6 (8)	(128/192) 256	128	2
DES	1977	16	56	64	2
DFC	1998	opt	128/192/256	128	?
FEAL	1987	4-32	64	64	2
GOST 28147-89	1989 [2]	32/16	256	64	2
IDEE	1991	8+1	128	64	patru
KASUMI	1999	opt	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	patru
MAGENTA	1998	6/8	128/192/256	128	2
MARTE	1998	32	128-1248	128	2
Milă	2000	6	128	4096	?
CEȚA1	1995	4×n(8)	128	64	patru
Raiden	2006	16	128	64	2
RC2	1987	16+2	8-128	64	patru
RC5	1994	1-255(12)	0-2040 (128)	32/64/128	2
RC6	1998	douăzeci	128/192/256	128	patru
RTEA	2007	48/64	128/256	64	2
SEMINTA	1998	16	128	128	2
Sinople	2003	64	128	128	patru
lista	1998	32	80	64	patru
CEAI	1994	64	128	64	2
Triplu DES	1978	32/48	112/168	64	2
Doi pești	1998	16	128/192/256	128	patru
XTEA	1997	64	128	64	2
XTEA-3	1999	64	256	128	patru
XXTEA	1998	12-64	128	64	2

Note

↑ 1 2 3 Horst Feistel „Cryptography and computer privacy” (engleză) („Cryptography and computer security”). Traducere Arhivată 11 martie 2018 la Wayback Machine de Andrey Vinokurov.
↑ 1 2 Vinokurov A. Articol arhivat la 1 aprilie 2022 la Wayback Machine „GOST 28147-89 Encryption Algorithm, Its Use and Implementation for Intel x86 Platform Computers ”. O parte din materialele incluse în acest articol au fost publicate în numărul „# 1.5 / 1995” al revistei „Monitor”.
↑ Matematică discretă. Algoritmi. Sisteme simetrice și cifruri bloc (link inaccesibil) . Consultat la 21 noiembrie 2008. Arhivat din original pe 5 decembrie 2012. (nedefinit)
↑ Serghei Panasenko. " Algoritmi moderni de criptare arhivat la 31 ianuarie 2010 la Wayback Machine " // Byte Magazine. Numărul nr. 8 (60), august 2003.
↑ Barichev, Goncharov, Serov, 2011 .
↑ Despre construcția permutării pseudo-aleatoare: Luby-Rackoff revizuit.
↑ Menezes, Oorschot, Vanstone, 1996 , §7.6 IDEA, pp. 263.
^ Brevetul SUA 3.798.359
↑ Brevetul SUA 3.796.830
↑ Arthur Sorkin. Lucifer, un algoritm criptografic. Cryptologia, numărul 8(1), ianuarie 1984, pp. 22-41, completat în numărul 8(3), pp. 260-261

Literatură

Barichev S. G. , Goncharov V. V. , Serov R. E. Fundamentele criptografiei moderne - ed. a III-a. — M .: Dialogue-MEPhI , 2011. — 176 p. — ISBN 978-5-9912-0182-7
Menezes A. J. , Oorschot P. v. , Vanstone S. A. Handbook of Applied Cryptography (engleză) - CRC Press , 1996. - 816 p. — ( Matematică discretă și aplicațiile sale ) — ISBN 978-0-8493-8523-0

Criptosisteme simetrice
Cifruri în flux	A3 A5 A8 Decim F-FCSR Cereale HC-256 KCipher-2 MICKEY MUGI ŞTIUCĂ Phelix RC4 Iepure SIGILIU ZĂPADĂ SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Rețeaua Feistel	GOST 28147-89 (Magma) blowfish Camelia CAST-128 CAST-256 CIFERUNICORN-A CIFERUNICORN-E CLEFIA Cobra AFACERE DES DESX DFC E2 ENRUPT FEAL HPC IDEE KASUMI Khafre Khufu LOKI97 MacGuffin MARTE PLASĂ CEȚA1 NewDES NDS RC5 RC6 SEMINTA Simon Sinople lista SM4 Speck CEAI XTEA XXTEA Raiden RTEA Triplu DES Doi pești
Rețeaua SP	Lăcustă 3 căi ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Centura CRYPTON Diamant2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer prezent Curcubeu MAI SIGUR RECHIN PĂTRAT Şarpe trei pești
Alte	BROASCĂ NUSH REDOC SC2000 SHACAL CS-Cipher