Feistelova šifra in Feistelovo omrežje – definicija in delovanje v kriptografiji

V kriptografiji je Feistelova šifra simetrična struktura, ki se uporablja pri gradnji blokovnih šifer in je poimenovana po nemškem kriptografu IBM Horstu Feistelu; pogosto je znana tudi kot Feistelovo omrežje. To shemo uporablja velik nabor blokovnih šifer, vključno s standardom šifriranja podatkov (Data Encryption Standard)

Prednost Feistelove strukture je, da sta šifriranje in dešifriranje zelo podobna, v nekaterih primerih celo enaka, saj je potrebna le zamenjava urnika ključev. Zato se velikost kode ali vezja, potrebnega za izvedbo take šifre, skoraj prepolovi.

Feistelova konstrukcija je iterativne narave, kar olajša implementacijo kriptosistema v strojni opremi.

Kako deluje Feistelovo omrežje

Feistelova šifra obdeluje podatke v blokih fiksne dolžine. Vsak vhodni blok dolžine n bitov se razdeli na levo in desno polovico, označeni kot L in R (vsaka po n/2 bitov). V vsakem krogu se izvede enaka zaporedna operacija z različnim podključem iz urnika ključev:

• Za krog i vzemi trenutni par (Li, Ri).
• Izračunaj Li+1 = Ri.
• Izračunaj Ri+1 = Li XOR F(Ri, Ki), kjer je F krožna (Feistelova) funkcija, Ki pa podključ kroga.
• Postopek ponovi za določen števil krogov (npr. 8, 16, 32).

Ključna lastnost je, da pri dešifriranju ni treba obrniti funkcije F. Zadostuje uporaba istih korakov v obratnem vrstnem redu s podključi v obratnem zaporedju. To poenostavi implementacijo in je razlog, da sta šifriranje in dešifriranje skoraj povsem simetrična.

Kaj počne krožna funkcija F

F prejme desno polovico bloka in podključ ter vrne izhod enake dolžine kot ena polovica bloka. Zasnovana je tako, da vnese nelinearnost, premešanje in mešanje bitov, kar ustvarja zmedo (confusion) in razpršitev (diffusion) – pojma, ki ju je opredelil Claude Shannon.

Feistelova omrežja in podobne konstrukcije so produktne šifre, zato združujejo več krogov ponavljajočih se operacij, kot so:

• Premešanje bitov (pogosto imenovano permutacijska polja ali P-polja)
• Enostavne nelinearne funkcije (pogosto imenovane nadomestna polja ali S-polja)
• Linearno mešanje (v smislu modularne algebre) z uporabo funkcije XOR za ustvarjanje funkcije z veliko količino tega, kar je Claude Shannon opisal kot "zmedo in razpršitev".

Premešanje bitov ustvari učinek razpršitve, zamenjava pa se uporablja za zmedo.

Koraki šifriranja in dešifriranja na kratko

• Priprava: razdeli blok na L0 in R0; iz glavnega ključa izpelji zaporedje podključev.
• Krogi: večkrat uporabi pravilo Li+1 = Ri in Ri+1 = Li XOR F(Ri, Ki).
• Zaključek: po zadnjem krogu se polovici pogosto še enkrat zamenjata (odvisno od implementacije), nato dobimo šifrogram.
• Dešifriranje: izvede iste korake v obratnem vrstnem redu podključev; funkcije F ni treba invertirati.

Parametri zasnove in praktični vidiki

• Število krogov: več krogov poveča varnost (npr. DES ima 16 krogov). Premalo krogov je ranljivih na analize vzorcev.
• Velikost bloka: določa, koliko podatkov se obdeluje naenkrat (npr. 64 ali 128 bitov). Večji bloki običajno bolje razpršijo vzorce.
• Velikost ključa: vpliva na odpornost proti napadom s surovo silo.
• Oblikovanje F: kakovostna S- in P-polja, linearno mešanje in dobro zasnovan urnik ključev so ključni za varnost.
• Whitening (pred- in po-krožni XOR z delom ključa) se pogosto uporablja za dodatno zaščito.
• Uravnotežene in neuravnotežene različice: v uravnoteženih omrežjih sta polovici enako veliki; neuravnotežene različice uporabljajo različne velikosti za posebne potrebe.

Varnostne lastnosti in napadi

• Razpršitev in zmeda zagotovita, da majhna sprememba v vhodu ali ključu povzroči velike spremembe v izhodu (učinek plazu).
• Diferencialna in linearna kriptoanaliza sta standardni metodi napada na Feistelove šifre; število krogov in zasnova S-polij morata zagotoviti dovolj rezerve.
• Teoretične garancije: rezultati tipa Luby–Rackoff kažejo, da nekaj krogov s primerno psevdo-naključno F daje varno permutacijo celotnega bloka.

Primeri Feistelovih šifer

• DES: klasičen primer s 64-bitnimi bloki in 16 krogi; danes se šteje za zastarelega zaradi prekratkega ključa.
• Blowfish: spremenljiva dolžina ključa (do 448 bitov), učinkovita programska izvedba.
• Twofish in Camellia: sodobnejše šifre, ki uporabljajo Feistelu podoben pristop z močnimi krožnimi funkcijami.
• GOST 28147-89: nacionalni standard s 64-bitnimi bloki in 32 krogi.

Prednosti in slabosti

• Prednosti: enoten mehanizem za šifriranje in dešifriranje, preprosta strojna implementacija, prilagodljivost pri izbiri F in parametrov.
• Slabosti: učinkovitost v programski opremi je lahko nižja od nekaterih drugih konstrukcij; slabo zasnovana F ali urnik ključev vodita v ranljivosti.

Feistel proti substitucijsko-permutacijskim omrežjem

Feistelova struktura je ogrodje za gradnjo blokovnih šifer, v katerem polovica bloka ostane nespremenjena in se samo zamenja med krogi. Alternativa so substitucijsko-permutacijska omrežja (SPN), kjer se na celoten blok zaporedno uporabljajo sloji S-polij in permutacij (primer je AES). Obe zasnovi lahko dosežeta visoko varnost; izbira je pogosto kompromis med varnostjo, učinkovitostjo in enostavnostjo implementacije.

Uporaba v praksi

• Feistelove šifre se uporabljajo kot osnovni gradniki; za šifriranje sporočil poljubne dolžine uporabljamo načine delovanja (npr. CBC, CTR), ki pa so ločeni od same notranje strukture.
• Pri implementaciji je pomembno paziti na časovne napade in druge stranske kanale; operacije naj bodo konstantnočasovne, kjer je to mogoče.

Gradnja

Naj bo F {\displaystyle {\rm {F}}} funkcija kroga in naj bodo K 1 , K 2 , ... , K n {\displaystyle K_{1},K_{2},\ldots ,K_{n}}podključi za kroge 1 , 2 , ... , n {\displaystyle 1,2,\ldots ,n}}.

Osnovna operacija je naslednja:

Blok čistega besedila razdelite na dva enaka dela ( L 1 {\displaystyle L_{1}} , R 1 {\displaystyle R_{1}} )

Za vsak krog i = 1 , 2 , ... , n {\displaystyle i=1,2,\dots ,n} , izračunajte (izračunajte)

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}\oplus {\rm {F}}}(R_{i},K_{i})} .

Potem je šifrirano besedilo ( R n + 1 , L n + 1 ) {\displaystyle (R_{n+1},L_{n+1})} . (Običajno se deli R n {\displaystyle R_{n}} in L n {\displaystyle L_{n}} po zadnjem krogu ne zamenjajo.)

Dešifriranje šifriranega besedila ( R n , L n ) {\displaystyle (R_{n},L_{n})} opravimo tako, da za i = n , n - 1 , ... , 1 {\displaystyle i=n,n-1,\ldots ,1} izračunamo

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

Potem je ( L 1 , R 1 ) {\displaystyle (L_{1},R_{1})} spet odprto besedilo.

Ena od prednosti tega modela je, da okrogli funkciji F {\displaystyle {\rm {F}}} ni treba biti invertibilna in je lahko zelo zapletena.

Slika prikazuje postopek šifriranja. Za dešifriranje je treba z uporabo istega postopka le obrniti vrstni red podključev K n , K n - 1 , ... , K 1 {\displaystyle K_{n},K_{n-1},\ldots ,K_{1}}; to je edina razlika med šifriranjem in dešifriranjem:

Neuravnotežene Feistelove šifre uporabljajo spremenjeno strukturo, kjer L 1 {\displaystyle L_{1}} in R 1 {\displaystyle R_{1}} nista enako dolga. Šifra MacGuffin je eksperimentalni primer take šifre.

Feistelova konstrukcija se uporablja tudi v drugih kriptografskih algoritmih, ne le v blokovnih šifrah. Na primer, shema OAEP (Optimal Asymmetric Encryption Padding) uporablja preprosto Feistelovo mrežo za naključno šifriranje šifrantov v nekaterih shemah šifriranja z asimetričnim ključem.

Feistelova omrežna operacija na blokovni šifri, kjer je P odprto besedilo, C pa šifrirano besedilo

Vprašanja in odgovori

V: Kaj je Feistelova šifra?

V: Katere so prednosti uporabe Feistelove strukture?

V: Kako je Claude Shannon opisal "zmedo in širjenje"?

V: Katere tehnike se uporabljajo za ustvarjanje zmede in razpršitve?

V: Katera vrsta šifre je Feistelovo omrežje?

V: Kdo je razvil to vrsto kriptografije?

V: Ali standard šifriranja podatkov temelji na tej vrsti kriptografije?

Išči po črki