AlegsaOnline.com

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

Feistelova šifra in Feistelovo omrežje razložena preprosto – definicija, delovanje in prednosti v kriptografiji, blokovne šifre kot DES, krogi z P- in S-polji, XOR, šifriranje in dešifriranje

Avtor: Leandro Alegsa Datum ustvarjanja: 07. november 2021 Zadnja posodobitev: 25. avgust 2025

simple.wikipedia.org · Public domain

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.

Teoretično delo

Številne sodobne simetrične blokovne šifre uporabljajo Feistelove mreže, kriptografi pa so podrobno raziskali strukturo in lastnosti Feistelovih šifer. Michael Luby in Charles Rackoff sta analizirala konstrukcijo Feistelove blokovne šifre in dokazala, da če je krožna funkcija kriptografsko varna psevdorandomna funkcija, pri čemer se kot seme uporabi K_i, potem zadostujejo trije krogi, da je blokovna šifra psevdorandomna permutacija, štirje krogi pa zadostujejo, da je to "močna" psevdorandomna permutacija (kar pomeni, da je psevdorandomna tudi za nasprotnika, ki ima dostop do njene obratne permutacije). Zaradi tega zelo pomembnega rezultata Lubyja in Rackoffa se Feistelove šifre včasih imenujejo Luby-Rackoffove blokovne šifre. Nadaljnje teoretične študije so konstrukcijo posplošile in določile natančnejše meje varnosti.

Gradnja

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

Osnovna operacija je naslednja:

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

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

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

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

Dešifriranje šifriranega besedila ( R n , L n ) {\displaystyle (R_{n},L_{n})} (R_n, L_n) opravimo tako, da za i = n , n - 1 , ... , 1 {\displaystyle i=n,n-1,\ldots ,1} izračunamo $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})$ .

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

Ena od prednosti tega modela je, da okrogli funkciji F {\displaystyle {\rm {F}}} ${\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}} $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}} L_1 in R 1 {\displaystyle R_{1}} 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

Seznam Feistelovih šifer

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

Splošni Feistel: CAST-256, MacGuffin, RC2, RC6, Skipjack

Vprašanja in odgovori

V: Kaj je Feistelova šifra?

O: Feistelova šifra je simetrična struktura, ki se uporablja pri gradnji blokovnih šifer in se imenuje po nemškem IBM-ovem kriptografu Horstu Feistelu. Splošno je znana tudi kot Feistelovo omrežje.

V: Katere so prednosti uporabe Feistelove strukture?

O: Glavna prednost uporabe Feistelove strukture je, da sta operaciji šifriranja in dešifriranja zelo podobni, v nekaterih primerih celo enaki, saj je potrebna le zamenjava razporeda ključev. To zmanjša velikost kode ali vezja, potrebnega za izvedbo take šifre, za skoraj polovico. Poleg tega je zaradi iterativne narave šifrirnega sistema njegovo izvajanje v strojni opremi lažje.

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

O: Claude Shannon je "zmedo in difuzijo" opisal kot prisotnost velikih količin obeh elementov, da bi napadalec težko dešifriral šifrirano sporočilo.

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

O: Zmeda in razpršitev se ustvarjata s premešanjem bitov (pogosto imenovanim permutacijska polja ali P-polja) in preprostimi nelinearnimi funkcijami (pogosto imenovanimi substitucijska polja ali S-polja) ter linearnim mešanjem (v smislu modularne algebre) z uporabo XOR. Premešanje bitov ustvari učinek razpršitve, medtem ko se zamenjava uporablja za zmedo.

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

O: Feistelovo omrežje je vrsta produktne šifre, ki združuje več krogov ponavljajočih se operacij za varno šifriranje podatkov.

V: Kdo je razvil to vrsto kriptografije?

O: Feistelovo strukturo je razvil nemški IBM-ov kriptograf Horst Feistel.

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

O: Da, standard Data Encryption Standard uporablja to vrsto kriptografije, ki uporablja ista načela, opisana zgoraj, za ustvarjanje zmede in razpršitve znotraj šifriranega sporočila.