AlegsaOnline.com

Feistelio šifras kriptografijoje apibrėžimas ir veikimo principas

Feistelio šifras kriptografijoje, aiškus apibrėžimas ir veikimo principas, Feistelio tinklas, raundai, S ir P dėžutės, šifravimo ir dešifravimo ypatumai, praktiniai pavyzdžiai

Autorius: Leandro Alegsa Sukūrimo data: 2021 m. lapkričio 7 d. Paskutinis atnaujinimas: 2025 m. rugpjūčio 24 d.

simple.wikipedia.org · Public domain

Kriptografijoje Feistelio šifras yra simetrinė struktūra, naudojama blokiniams šiframs kurti, pavadinta vokiečių IBM kriptografo Horsto Feistelio vardu; jis taip pat paprastai vadinamas Feistelio tinklu. Šią schemą naudoja daug blokinių šifrų, įskaitant duomenų šifravimo standartą.

Feistelio struktūros privalumas tas, kad šifravimo ir dešifravimo operacijos yra labai panašios, o kai kuriais atvejais net identiškos, todėl reikia tik pakeisti rakto tvarkaraštį. Todėl tokiam šifrui įgyvendinti reikalingo kodo ar grandinės dydis sumažėja beveik perpus.

Feistelio konstrukcija yra iteracinio pobūdžio, todėl kriptosistemą lengviau įgyvendinti aparatinėje įrangoje.

Feistelio tinklai ir panašios konstrukcijos yra produktų šifrai, todėl jie sujungia kelis pasikartojančių operacijų raundus, pvz:

Bitų perstumdymas (dažnai vadinamas permutacijų dėžutėmis arba P-dėžutėmis)
Paprastos netiesinės funkcijos (dažnai vadinamos pakaitų dėžutėmis arba S-dėžutėmis)
Linijinis maišymas (modulinės algebros prasme) naudojant XOR, kad būtų sukurta funkcija su dideliu kiekiu to, ką Claude'as Shannonas apibūdino kaip "painiavą ir difuziją".

Bitų permaišymas sukuria sklaidos efektą, o pakeitimu sukuriama painiava.

Feistelio tinklo pagrindinė struktūra

Feistelio šifre blokas padalijamas į dvi lygias dalis: kairę (L) ir dešinę (R). Kiekviename raunde taikoma funkcija F, kuri naudoja raundo raktą Ki ir vieną bloko pusę, o rezultatas kombinuojamas su kita puse per XOR operaciją. Standartinė vieno raundo transformacija (i-tas raundas) yra:

Li = R{i-1} Ri = L{i-1} XOR F(R{i-1}, Ki)

Tokia konstrukcija užtikrina, kad visas tinklas yra invertuojamas net jei pati funkcija F nėra invertuojama — invertavimui tereikia taikyti raundus atvirkštine tvarka su atitinkamais raktais.

Šifravimo ir dešifravimo žingsniai

Tipinis Feistelio šifravimo algoritmas:

Padalinti į bloką L0 || R0.
Uždaryti N raundų: kiekviename raunde atnaujinti Li ir Ri pagal aukščiau pateiktą formulę.
Gauti išeigos bloką LN || RN (kai kuriose implementacijose gale atliekama papildoma permutacija arba swap).

Dešifravimas atliekamas ta pačia schema, tačiau raktų tvarka atvirkštinė (K_N, K_{N-1}, ..., K_1). Dėl Feistelio savybių nereikia invertuoti funkcijos F — pakanka taikyti raundus atvirkščiai.

Pavyzdžiai ir variacijos

DES (Data Encryption Standard) — klasikinis 64 bitų bloko, 56 bitų rakto, 16 raundų Feistelio šifras.
Blowfish — Feistelio tipo šifras su kintamu raundų skaičiumi ir sudėtingu rakto planu.
Twofish — naudoja Feistelio principus kartu su pažangesnėmis S-dėžutėmis ir maišymo etapais.
Yra variantų: balanced (lygios pusės), unbalanced (skirtingo dydžio pusės) ir Generalized Feistel Network (GFN), kur bloko dalys gali būti daugiau nei dvi.

Funkcijos F, S-dėžutės ir P-dėžutės

Raundo funkcija F dažnai susideda iš kelių žingsnių: rakto sumaišymo, S-dėžutės (pakaitos) taikymo netiesinumio suteikimui ir P-dėžutės (permutacijos) sklaidai. Gerai suprojektuotos S-dėžutės turi mažą struktūrinį ryšį su įvestimi, kad būtų atsparios diferencinei ir linijinei kriptanalizei.

Saugumo aspektai

Feistelio tinklo saugumas priklauso nuo:

rau ndo funkcijų F dizaino (netiesiškumo, S-dėžučių savybių),
raundų skaičiaus — per mažai raundų leidžia kriptanalizei išnaudoti struktūrinius modelius,
rakto tvarkaraščio (key schedule) — silpnas rakto generavimas gali sukelti rakto atskleidimą ar reikšmingas simetrijas.

Matematiniai rezultatai, pvz., Luby–Rackoff teorema, rodo, kad su idealiais atsitiktiniais raundo funkcijų pasirinkimais ribinis raundų skaičius (pvz., 3 ar 4) gali užtikrinti tam tikras pseudorandom permutacijų savybes. Praktikoje dizaineriai dažnai naudoja daug raundų (pvz., 16), kad suteiktų atsparumą realioms atakoms (diferencinei, linijinei ir kitoms modernioms atakoms).

Privalumai ir trūkumai

Privalumai:

Šifravimo ir dešifravimo logika labai panaši — paprasta implementacija ir mažesnis kodas/aparatinė grandinė.
Funkcija F gali būti sudėtinga arba net invertuotina nereikalaujanti, todėl įmanoma plačiai keisti dizainą be dešifravimo sudėtingumo padidėjimo.
Lengva pritaikyti variantus (GFN, nevienalyčiai blokai) ir optimizuoti aparatūrai.

Trūkumai:

Feistelio saugumas stipriai priklauso nuo F ir rakto plano — netinkamai suprojektuotos S-dėžutės ar per mažai raundų gali lemti pažeidžiamumą.
Kai kurie modernūs konstrukcijų tipai (pvz., SPN — substitution–permutation network) leidžia kitokias optimizacijas ir kartais geresnį paralelizavimą.

Trumpa santrauka

Feistelio šifras yra patikima ir lanksčią architektūrą turinti blokinių šifrų paradigma: ji suteikia efektyvų būdą sukurti invertuojimą be būtinybės, kad raundo funkcija būtų invertuojama. Daug žinomų šifrų, įskaitant DES ir kitus, naudoja Feistelio principus, o tinkamas raundų funkcijų, S-dėžučių ir rakto planavimo projektavimas yra esminis saugai užtikrinti.

Teorinis darbas

Daugelyje šiuolaikinių simetrinių blokinių šifrų naudojami Feistelio tinklai, o kriptografai daug tyrinėjo Feistelio šifrų struktūrą ir savybes. Konkrečiai Michael Luby ir Charles Rackoff išanalizavo Feistelio blokinio šifro konstrukciją ir įrodė, kad jei raundo funkcija yra kriptografiškai saugi pseudorandominė funkcija, o K_i naudojamas kaip sėkla, tai pakanka 3 raundų, kad blokinis šifras taptų pseudorandomine permutacija, o 4 raundų pakanka, kad jis taptų "stipria" pseudorandomine permutacija (tai reiškia, kad jis išlieka pseudorandominis net ir priešininkui, kuris gauna orakulo prieigą prie jo atvirkštinės permutacijos). Dėl šio labai svarbaus Luby ir Rackoffo rezultato Feistelio šifrai kartais vadinami Luby-Rackoffo blokiniais šifrais. Tolesniuose teoriniuose tyrimuose ši konstrukcija buvo apibendrinta ir nustatytos tikslesnės saugumo ribos.

Statyba

Tegul F {\displaystyle {\rm {F}}} ${\rm F}$ yra raundo funkcija ir tegul K 1 , K 2 , ... , K n {\displaystyle K_{1},K_{2},\ldots ,K_{n}} $K_1,K_2,\ldots,K_{n}$ $1,2,\ldots,n$ atitinkamai yra raundų 1 , 2 , ... , n {\displaystyle 1,2,\ldots ,n}} daliniai raktai.

Tada pagrindinė operacija yra tokia:

Padalykite atvirojo teksto bloką į dvi lygias dalis ( L 1 {\displaystyle L_{1}} L_1 , R 1 {\displaystyle R_{1}} R_1 ).

Kiekvienam raundui i = 1 , 2 , ... , n {\displaystyle i=1,2,\dots ,n} $i =1,2,\dots,n$ apskaičiuokite (apskaičiuoti)

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}\oplius {\rm {F}}}(R_{i},K_{i})} $R_{i+1}= L_i \oplus {\rm F}(R_i, K_i)$ .

Tada šifro tekstas yra ( R n + 1 , L n + 1 ) {\displaystyle (R_{n+1},L_{n+1})} $(R_{n+1}, L_{n+1})$ . (Paprastai dvi dalys R n {\displaystyle R_{n}} R_n ir L n {\displaystyle L_{n}} L_n po paskutinio raundo nėra sukeičiamos vietomis).

Šifruoto teksto ( R n , L n ) {\displaystyle (R_{n},L_{n})} (R_n, L_n) dešifravimas atliekamas apskaičiuojant 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})$ .

Tada ( L 1 , R 1 ) {\displaystyle (L_{1},R_{1})} vėl (L_1,R_1) yra atvirasis tekstas.

Vienas iš šio modelio privalumų yra tas, kad apvalioji funkcija F {\displaystyle {\rm {F}}} ${\rm F}$ neprivalo būti apverčiama ir gali būti labai sudėtinga.

Schemoje pavaizduotas šifravimo procesas. Dešifravimui reikia tik pakeisti dalinių raktų K n , K n - 1 , ... , K 1 {\displaystyle K_{n},K_{n-1},K_{n-1},\ldots ,K_{1}} $K_{n},K_{n-1},\ldots,K_1$ tvarką naudojant tą patį procesą; tai vienintelis šifravimo ir dešifravimo skirtumas:

Nesubalansuotuose Feistelio šifruose naudojama modifikuota struktūra, kurioje L 1 {\displaystyle L_{1}} L_1 ir R 1 {\displaystyle R_{1}} R_1 nėra vienodo ilgio. Tokio šifro eksperimentinis pavyzdys yra MacGuffin šifras.

Feistelio konstrukcija naudojama ir kituose kriptografiniuose algoritmuose, ne blokiniuose šifruose. Pavyzdžiui, Optimal Asymmetric Encryption Padding (OAEP) schemoje tam tikrose asimetrinio rakto šifravimo schemose šifrogramoms atsitiktinai nustatyti naudojamas paprastas Feistelio tinklas.

Feistelio tinklo operacija su blokiniu šifru, kai P yra atviras tekstas, o C - šifruotas tekstas

Feistelio šifrų sąrašas

Feistelis arba modifikuotas Feistelis: Blowfish, Camellia, CAST-128, DES, FEAL, ICE, KASUMI, LOKI97, Lucifer, MARS, MAGENTA, MISTY1, RC5, TEA, Triple DES, Twofish, XTEA, GOST 28147-89.

Apibendrintas Feistelis: CAST-256, MacGuffin, RC2, RC6, Skipjack

Klausimai ir atsakymai

K: Kas yra Feistelio šifras?

A: Feistelio šifras yra simetrinė struktūra, naudojama blokiniams šiframs kurti, pavadinta vokiečių IBM kriptografo Horsto Feistelio vardu. Jis taip pat paprastai vadinamas Feistelio tinklu.

K: Kokie yra kai kurie Feistelio struktūros naudojimo privalumai?

A: Pagrindinis Feistelio struktūros naudojimo privalumas yra tas, kad šifravimo ir dešifravimo operacijos yra labai panašios, kai kuriais atvejais net identiškos, todėl reikia tik pakeisti raktų tvarkaraštį. Tai beveik perpus sumažina kodų ar grandynų, reikalingų tokiam šifrui įgyvendinti, dydį. Be to, dėl iteracinio pobūdžio lengviau įgyvendinti šifravimo sistemą aparatinėje įrangoje.

K: Kaip Klodas Šenonas apibūdina "painiavą ir sklaidą"?

A: Klodas Šenonas (Claude Shannon) apibūdino "painiavą ir difuziją" kaip didelį abiejų elementų kiekį, kad užpuolikui būtų sunku iššifruoti užšifruotą pranešimą.

K: Kokie metodai naudojami painiavai ir sklaidai sukurti?

A.: Sumaištis ir sklaida sukuriama naudojant bitų permaišymą (dažnai vadinamą permutacijų dėžutėmis arba P dėžutėmis) ir paprastas netiesines funkcijas (dažnai vadinamas pakeitimo dėžutėmis arba S dėžutėmis), taip pat tiesinį maišymą (modulinės algebros prasme) naudojant XOR. Bitų maišymas sukuria difuzijos efektą, o pakaitinimas naudojamas supainiojimui.

Klausimas: Kokio tipo šifras yra Feistelio tinklas?

A: Feistelio tinklas yra produkto šifro tipas, kuriame derinami keli pasikartojančių operacijų raundai, siekiant saugiai užšifruoti duomenis.

K: Kas sukūrė šį kriptografijos tipą?

A: Feistelio struktūrą sukūrė vokiečių IBM kriptografas Horstas Feistelis.

K: Ar duomenų šifravimo standartas pagrįstas šio tipo kriptografija?

A: Taip, "Data Encryption Standard" naudoja šio tipo kriptografiją, kurioje naudojami tie patys pirmiau aprašyti principai, kaip užšifruotame pranešime sukelti painiavą ir sklaidą.