Feistelio šifras kriptografijoje apibrėžimas ir veikimo principas

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:

1. Padalinti į bloką L0 || R0.
2. Uždaryti N raundų: kiekviename raunde atnaujinti Li ir Ri pagal aukščiau pateiktą formulę.
3. 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.

Statyba

Tegul F {\displaystyle {\rm {F}}} yra raundo funkcija ir tegul K 1 , K 2 , ... , K n {\displaystyle K_{1},K_{2},\ldots ,K_{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}} , R 1 {\displaystyle R_{1}} ).

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

L i + 1 = R i {\displaystyle 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})} .

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

Šifruoto teksto ( R n , L n ) {\displaystyle (R_{n},L_{n})} dešifravimas atliekamas apskaičiuojant i = n , n - 1 , ... , 1 {\displaystyle i=n,n-1,\ldots ,1}

R i = L i + 1 {\displaystyle 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})} .

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

Vienas iš šio modelio privalumų yra tas, kad apvalioji funkcija F {\displaystyle {\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}} 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}} ir R 1 {\displaystyle 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

Klausimai ir atsakymai

K: Kas yra Feistelio šifras?

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

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

K: Kokie metodai naudojami painiavai ir sklaidai sukurti?

Klausimas: Kokio tipo šifras yra Feistelio tinklas?

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

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

Paieška pagal raidę