Feistelova šifra
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.
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.
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 Ki, 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}}}
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
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
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.
