Feistel cipher

Krüptograafias on Feistel-krüptograafia sümmeetriline struktuur, mida kasutatakse plokk-krüptograafide ehitamisel ja mis on nimetatud Saksa IBM-i krüptograafi Horst Feisteli järgi; seda tuntakse ka Feistel-võrguna. Suur hulk plokkšifreid kasutavad seda skeemi, sealhulgas Data Encryption Standard

Feisteli struktuuri eeliseks on see, et krüpteerimis- ja dekrüpteerimisoperatsioonid on väga sarnased, mõnel juhul isegi identsed, nõudes ainult võtme ajakava ümberpööramist. Seetõttu väheneb sellise šifri rakendamiseks vajaliku koodi või vooluahela suurus peaaegu poole võrra.

Feisteli konstruktsioon on oma olemuselt iteratiivne, mis muudab krüptosüsteemi rakendamise riistvaras lihtsamaks.

Feisteli võrgud ja sarnased konstruktsioonid on tootesümbolid ja kombineerivad seega mitmeid korduvaid operatsioone, näiteks:

Bittide segamine (sageli nimetatakse permutatsioonikastideks või P-kastideks)
Lihtsad mittelineaarsed funktsioonid (mida sageli nimetatakse asenduskastideks või S-kastideks)
Lineaarne segamine (modulaaralgebra tähenduses), kasutades XOR-i, et tekitada funktsioon, milles on suures koguses seda, mida Claude Shannon kirjeldas kui "segadust ja hajutamist".

Bittide segamine tekitab difusiooni efekti, samas kui asendamist kasutatakse segaduse tekitamiseks.

Teoreetiline töö

Paljud kaasaegsed sümmeetrilised plokkšifrid kasutavad Feisteli võrke ning krüptograafid on Feisteli šifrite struktuuri ja omadusi põhjalikult uurinud. Nimelt analüüsisid Michael Luby ja Charles Rackoff Feisteli plokkšifri ehitust ja tõestasid, et kui ringfunktsioon on krüptograafiliselt turvaline pseudorandomfunktsioon, mille seemneks on K_i, siis piisab 3 voorust, et plokkšifrile saaks pseudorandomne permutatsioon, samas kui 4 voorust piisab, et saada "tugev" pseudorandomne permutatsioon (mis tähendab, et see jääb pseudorandomne isegi vastase jaoks, kes saab oraakli juurdepääsu selle pöördpermutatsioonile). Selle Luby ja Rackoffi väga olulise tulemuse tõttu nimetatakse Feisteli šifreid mõnikord Luby-Rackoffi plokkšifriteks. Edasised teoreetilised uurimused üldistasid seda konstruktsiooni ja määratlesid täpsemad turvalisuse piirid.

Ehitus

Olgu F {\displaystyle {\rm {F}}} ${\rm F}$ ringfunktsioon ja olgu 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$ vastavalt ringide 1 , 2 , ... , n {\displaystyle 1,2,\ldots ,n}} alamvõtmed.

Siis on põhitoiming järgmine:

Jagatakse lihtkirjablokk kaheks võrdseks tükiks ( L 1 {\displaystyle L_{1}} L_1 , R 1 {\displaystyle R_{1}} R_1 ).

Iga vooru i = 1 , 2 , ... , n puhul {\displaystyle i=1,2,\dots ,n} $i =1,2,\dots,n$ arvutatakse (arvutatakse)

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

Siis on salatekst ( R n + 1 , L n + 1 ) {\displaystyle (R_{n+1},L_{n+1})} $(R_{n+1}, L_{n+1})$ . (Tavaliselt ei vahetata pärast viimast vooru kahte tükki R n {\displaystyle R_{n}} R_n ja L n {\displaystyle L_{n}} L_n ).

Krüptograafilise teksti ( R n , L n ) {\displaystyle (R_{n},L_{n})} (R_n, L_n) dekrüpteerimiseks arvutatakse i = n , n - 1 , ... , 1 jaoks {\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})$ .

Siis (L_1,R_1) on ( L 1 , R 1 ) {\displaystyle (L_{1},R_{1})} jälle selgeks tekstiks.

Selle mudeli üks eelis on see, et ümmargune funktsioon F {\displaystyle {\rm {F}} ${\rm F}$ ei pea olema inverteeritav ja võib olla väga keeruline.

Joonis illustreerib krüpteerimisprotsessi. Dekrüpteerimine nõuab ainult alamvõtmete K n , K n - 1 , ... , K 1 {\displaystyle K_{n},K_{n-1},\ldots ,K_{1}} $K_{n},K_{n-1},\ldots,K_1$ järjekorra ümberpööramist, kasutades sama protsessi; see on ainus erinevus krüpteerimise ja dekrüpteerimise vahel:

Tasakaalustamata Feistel-kodeeringud kasutavad muudetud struktuuri, kus L 1 {\displaystyle L_{1}} L_1 ja R 1 {\displaystyle R_{1}} R_1 ei ole võrdse pikkusega. MacGuffin'i šiffer on sellise šifri eksperimentaalne näide.

Feisteli konstruktsiooni kasutatakse ka muudes krüptograafilistes algoritmides kui plokkšifrites. Näiteks optimaalne asümmeetriline krüpteerimisskeem (Optimal Asymmetric Encryption Padding, OAEP) kasutab lihtsat Feisteli võrku, et juhuslikuks muuta salatekstid teatavates asümmeetrilise võtmega krüpteerimisskeemides.

Feisteli võrguoperatsioon plokkšifriga, kus P on lihttekst ja C on salatekst.

Feistel-koodide nimekiri

Feistel või modifitseeritud Feistel: Blowfish, Camellia, CAST-128, DES, FEAL, ICE, KASUMI, LOKI97, Lucifer, MARS, MAGENTA, MISTY1, RC5, TEA, Triple DES, Twofish, XTEA, GOST 28147-89.

Üldistatud Feistel: CAST-256, MacGuffin, RC2, RC6, Skipjack.

Küsimused ja vastused

K: Mis on Feisteli šifreering?

V: Feistel-krüptograaf on sümmeetriline struktuur, mida kasutatakse plokk-krüptograafide ehitamisel ja mis on nimetatud Saksa IBMi krüptograafi Horst Feisteli järgi. See on üldtuntud ka kui Feisteli võrk.

K: Millised on Feisteli struktuuri kasutamise eelised?

V: Peamine Feisteli struktuuri kasutamise eelis on see, et krüpteerimis- ja dekrüpteerimisoperatsioonid on väga sarnased, mõnel juhul isegi identsed, nõudes ainult võtme ajakava ümberpööramist. See vähendab sellise šifri rakendamiseks vajaliku koodi või vooluahela suurust peaaegu poole võrra. Lisaks muudab selle iteratiivne olemus krüptosüsteemi riistvaralise rakendamise lihtsamaks.

K: Kuidas kirjeldab Claude Shannon "segadust ja hajutamist"?

V: Claude Shannon kirjeldas "segadust ja difusiooni" kui mõlema elemendi suurt hulka, et ründajal oleks raske krüpteeritud sõnumit dešifreerida.

K: Milliseid meetodeid kasutatakse segaduse ja hajuvuse tekitamiseks?

V: Segadust ja hajuvust tekitatakse bittide segamise (mida sageli nimetatakse permutatsioonikastideks või P-kastideks) ja lihtsate mittelineaarsete funktsioonide (mida sageli nimetatakse asenduskastideks või S-kastideks), samuti lineaarse segamise (moodulalgebra tähenduses) abil, kasutades XOR-i. Bittide segamine tekitab difusiooniefekti, samas kui asendamist kasutatakse segaduse tekitamiseks.

Küsimus: Mis tüüpi šiffer on Feisteli võrk?

V: Feisteli võrk on teatud tüüpi tootesalvesti, mis kombineerib andmete turvaliseks krüpteerimiseks mitu ringi korduvaid operatsioone.

K: Kes töötas selle krüptograafia tüübi välja?

V: Feisteli struktuuri töötas välja Saksa IBMi krüptograaf Horst Feistel.

K: Kas Data Encryption Standard põhineb seda tüüpi krüptograafial?

V: Jah, Data Encryption Standard kasutab seda tüüpi krüptograafiat, mis kasutab eespool kirjeldatud põhimõtteid segaduse ja hajuvuse tekitamiseks krüpteeritud sõnumi sees.