Cifra Feistel

În criptografie, un cifru Feistel este o structură simetrică utilizată în construcția cifrului bloc, denumită astfel după criptograful german Horst Feistel de la IBM; este, de asemenea, cunoscută sub numele de rețea Feistel. Un set mare de blocuri de cifrare utilizează această schemă, inclusiv Data Encryption Standard

Structura Feistel are avantajul că operațiunile de criptare și de decriptare sunt foarte asemănătoare, chiar identice în unele cazuri, necesitând doar o inversare a programului de chei. Prin urmare, dimensiunea codului sau a circuitelor necesare pentru implementarea unui astfel de cifru este aproape înjumătățită.

Construcția Feistel este de natură iterativă, ceea ce face mai ușoară implementarea criptosistemului în hardware.

Rețelele Feistel și construcțiile similare sunt cifrări de produs și, prin urmare, combină mai multe runde de operații repetate, cum ar fi:

Bit-shuffling (adesea numite cutii de permutare sau cutii P)
Funcții neliniare simple (adesea numite cutii de substituție sau cutii S)
Amestecul liniar (în sensul algebrei modulare) folosind XOR pentru a produce o funcție cu cantități mari de ceea ce Claude Shannon a descris ca fiind "confuzie și difuzie".

Amestecul de biți creează efectul de difuzie, în timp ce substituția este utilizată pentru confuzie.

Lucrări teoretice

Numeroase coduri de bloc simetrice moderne utilizează rețele Feistel, iar structura și proprietățile codurilor Feistel au fost explorate pe larg de criptografi. Mai exact, Michael Luby și Charles Rackoff au analizat construcția cifrului bloc Feistel și au demonstrat că, dacă funcția de rundă este o funcție pseudorandom sigură din punct de vedere criptografic, cu K_i folosit ca sămânță, atunci 3 runde sunt suficiente pentru ca cifrul bloc să fie o permutare pseudorandomică, în timp ce 4 runde sunt suficiente pentru ca acesta să fie o permutare pseudorandomică "puternică" (ceea ce înseamnă că rămâne pseudorandom chiar și pentru un adversar care are acces în oracol la permutarea sa inversă). Datorită acestui rezultat foarte important al lui Luby și Rackoff, cifrele Feistel sunt uneori numite cifre în bloc Luby-Rackoff. Studii teoretice ulterioare au generalizat construcția și au definit limite mai precise pentru securitate.

Construcție

Fie F {\displaystyle {\rm {F}}}} ${\rm F}$ funcția de rundă și fie K 1 , K 2 , ... , K n {\displaystyle K_{1},K_{2},\ldots ,K_{n}} $K_1,K_2,\ldots,K_{n}$ sunt subcheile pentru rundele 1 , 2 , ... , n {\displaystyle 1,2,\ldots ,n} $1,2,\ldots,n$ respectiv.

Apoi, operațiunea de bază este următoarea:

Se împarte blocul de text în două bucăți egale, ( L 1 {\displaystyle L_{1}} L_1 , R 1 {\displaystyle R_{1}} R_1 )

Pentru fiecare rundă i = 1 , 2 , ... , n {\displaystyle i=1,2,\dots ,n} $i =1,2,\dots,n$ , compute (calculate)

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

Atunci textul cifrat este ( R n + 1 , L n + 1 ) {\displaystyle (R_{n+1},L_{n+1})} $(R_{n+1}, L_{n+1})$ . (În mod obișnuit, cele două bucăți R n {\displaystyle R_{n}} R_n și L n {\displaystyle L_{n}} L_n nu sunt schimbate după ultima rundă).

Decriptarea unui text cifrat ( R n , L n ) {\displaystyle (R_{n},L_{n})} (R_n, L_n) se realizează prin calcularea pentru 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})$ .

Atunci ( L 1 , R 1 ) {\displaystyle (L_{1},R_{1})} (L_1,R_1) este din nou textul în clar.

Un avantaj al acestui model este că funcția rotundă F {\displaystyle {\rm {F}} ${\rm F}$ nu trebuie să fie inversabilă și poate fi foarte complexă.

Diagrama ilustrează procesul de criptare. Decriptarea necesită doar inversarea ordinii subcheie K n , K n - 1 , ... , K 1 {\displaystyle K_{n},K_{n-1},\ldots ,K_{1}} $K_{n},K_{n-1},\ldots,K_1$ folosind același proces; aceasta este singura diferență între criptare și decriptare:

Cifrele Feistel dezechilibrate utilizează o structură modificată în care L 1 {\displaystyle L_{1}} L_1 și R 1 {\displaystyle R_{1}} R_1 nu sunt de lungimi egale. Cifrul MacGuffin este un exemplu experimental al unui astfel de cifru.

Construcția Feistel este utilizată și în alți algoritmi criptografici decât cele de cifrare în bloc. De exemplu, schema OAEP (Optimal Asymmetric Encryption Padding) utilizează o rețea Feistel simplă pentru a randomiza textele cifrate în anumite scheme de criptare cu cheie asimetrică.

Operația de rețea Feistel pe cifru în bloc, unde P este textul în clar și C este textul cifrat

Lista cifrelor Feistel

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

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

Întrebări și răspunsuri

Î: Ce este un cifru Feistel?

R: Un cifru Feistel este o structură simetrică utilizată în construcția de blocuri de cifrare, denumită astfel după criptograful german Horst Feistel de la IBM. Este, de asemenea, cunoscută în mod obișnuit sub denumirea de rețea Feistel.

Î: Care sunt unele dintre avantajele utilizării unei structuri Feistel?

R: Principalul avantaj al utilizării unei structuri Feistel este că operațiunile de criptare și de decriptare sunt foarte asemănătoare, chiar identice în unele cazuri, necesitând doar o inversare a programului de chei. Acest lucru reduce aproape la jumătate dimensiunea codului sau a circuitelor necesare pentru implementarea unui astfel de cifru. În plus, natura sa iterativă face ca implementarea criptosistemului în hardware să fie mai ușoară.

Î: Cum descrie Claude Shannon "confuzia și difuzarea"?

R: Claude Shannon a descris "confuzia și difuzarea" ca fiind o cantitate mare de ambele elemente prezente pentru a face dificilă descifrarea unui mesaj criptat de către un atacator.

Î: Ce tehnici sunt utilizate pentru a crea confuzie și difuzie?

R: Confuzia și difuzarea sunt create prin amestecarea biților (adesea numite cutii de permutare sau cutii P) și funcții neliniare simple (adesea numite cutii de substituție sau cutii S), precum și prin amestecare liniară (în sensul algebrei modulare) folosind XOR. Amestecul de biți creează efectul de difuzie, în timp ce substituția este utilizată pentru confuzie.

Î: Ce tip de cifru este o rețea Feistel?

R: O rețea Feistel este un tip de cifru de produs care combină mai multe runde de operații repetate pentru a cripta datele în siguranță.

Î: Cine a dezvoltat acest tip de criptografie?

R: Structura Feistel a fost dezvoltată de criptograful german Horst Feistel de la IBM.

Î: Data Encryption Standard se bazează pe acest tip de criptografie?

R: Da, Data Encryption Standard folosește acest tip de criptografie care utilizează aceleași principii descrise mai sus pentru a crea confuzie și difuzie în cadrul unui mesaj criptat.