Feistelio šifras

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.

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ą.