Feisteli võrk — plokkšifrite konstruktsioon ja tööpõhimõte

Süvitsi Feisteli võrgus: plokkšifrite konstruktsioon, tööpõhimõte, eelised ja rakendused — selge juhend krüptograafia põhimõtetest ja turvalisusest.

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 ning mitmed teised tuntud algoritmid (nt Blowfish, CAST-pered ja mitmed vanemad šifrid).

Konstruktsioon — põhimõtteline skeem

Feistel-võrk töötleb fikseeritud pikkusega plokke, mis jagatakse kaheks poolmaks — vasakuks (L) ja paremaks (R). Iga ümberkäigu (round) jooksul rakendatakse paremale poolele nn ümarfunktsiooni F koos rundivõtmega Ki ning seejärel kombineeritakse tulemus vasaku poolega tavaliselt XOR-operatsiooniga. Üldine kordusreegel ühe ümberkäigu kohta on:

• Li = R(i−1)
• Ri = L(i−1) XOR F(R(i−1), Ki)

Pärast mitut ümberkäiku võib lõpuks olla veel vasak- ja parempoolte vahetus, sõltuvalt konkreetse šifri disainist. Tähtis omadus on see, et funktsioon F ei pea olema pööratav — tänu Feisteli skeemile on kogu permutatsioon ikkagi pööratav ning seetõttu dekrüpteerimine on võimalik.

Dekrüpteerimine ja võtme ajakava

Feistel-struktuuri peamine praktiline eelis on see, et dekodeerimisoperatsioon on väga sarnane krüpteerimisele: sama ümberkäikude mehhanismi saab kasutada, kuid rundivõtmete järjekord pööratakse ümber (või vajadusel rakendatakse võtme ajakava vastupidises suunas). Seetõttu on rakenduse kood või riistvaraline loogika lihtne ja kompaktne — sama ploki ümberkäigufunktsioon F ja samad operatsioonid toimivad mõlemas suunas.

Rundifunktsioon F ja võtme ajakava

Rundifunktsioon F on tavaliselt kombinatsioonist:

• permutatsioonikastidest (P-kastid) — bitide ümberpaigutus (lineaarne samm)
• asenduskastidest (S-kastid) — mittelineaarsed asendustabelid, mis annavad segaduse (confusion)
• võtme segamisest (XOR, lisamine või muu lineaarne/mitteilineaarne kombineerimine) — võti on funktsiooni F parameeter

Lisaks kasutatakse sageli modulaaralgebra tähenduses lineaarseid operatsioone (nt XOR, rotatsioonid, liitmine), et saavutada soovitud hajutatuse (diffusion) ja segaduse (confusion) omadused. Nagu tekstis mainitud, on selle eesmärk tekitada süsteemis seda, mida Claude Shannon nimetas "segaduseks ja hajutamiseks".

Difusioon ja segadus

Bittide segamine (permutatsioonid ja lineaaroperatsioonid) tekitab difusiooni efekti — ühe sisendbiti mõju levib kiirelt üle kogu ploki. Asenduskastid (S-kastid) annavad mittelineaarsuse ehk segaduse, mis muudab suhet võtme ja väljundi vahel keerukaks. Mõlema tüüpi operatsioonide kordamine paljude ümberkäikude jooksul tagab tugevama turvalisuse.

Variatsioonid ja teoreetiline turvalisus

On olemas mitmeid Feistel-põhiseid variante:

• Tasakaalustatud Feistel (balanced) — kahe poole pikkus on võrdne.
• Ebatasakaalustatud (unbalanced) Feistel — pooled on erineva pikkusega, kasutatakse mõnes spetsiifilises konstruktsioonis.
• Generaliseeritud Feistel — mitu alamplokki ja keerukamad ümberjaotused ümarfunktsiooni sisendis/väljundis.

Teoreetiliselt on Luby–Rackoffi tulemused näidanud, et Feistel-konstruktsioon võib, kui kasutatakse piisavalt hästi valitud (pseudojuhuslikke) rindefunktsioone, tuua kaasa pseudojuhusliku permutatsiooni; konkreetsemalt annavad Luby ja Rackoff tingimused, mille alusel mõne ümberkäiguarvu korral saab tõestada turvalisuseomadusi (näiteks mitu ümberkäiku on vajalik, et saavutada teatud indistinguishability omadused).

Eelised ja puudused

• Eelised: lihtne pööratavus (F ei pea olema pööratav), vähene eraldi loogika dekrüpteerimiseks, hea sobivus riist- ja tarkvaralise implementatsiooni jaoks, modulaarne disain (S-kastid, P-kastid, võtme ajakava).
• Puudused: turvalisus sõltub tugevalt rundifunktsioonide ja võtme ajakava korralikkusest; nõuetekohase S-kastide ja võtmeajaskema kujundus on kriitiline. Samuti võib suure arvuga ümberkäike kaasa tuua jõudlusmõjusid.

Kasutusnäited

Praktilised Feistel-põhised šifrid hõlmavad lisaks DES-ile ka selliseid algoritme nagu Blowfish, CAST-pered ja mitmed muud plokkšifrid, kus on kasutatud Feistel-ideed ümberkäikude (rounds) ja S-/P-kastide kombinatsioonist.

Feistel-võrk on tänu oma lihtsusele, pööratavusele ja modulaarsele loogikale olnud üks võtmetehnikaid plokkšifrite konstruktsioonis. Õigesti kujundatud rundifunktsioonide ja võtme ajakava korral annab see tugeva aluse krüptograafiliselt turvalistele šifritele.

Ehitus

Olgu F {\displaystyle {\rm {F}}} ringfunktsioon ja olgu K 1 , K 2 , ... , K n {\displaystyle K_{1},K_{2},\ldots ,K_{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}} , R 1 {\displaystyle R_{1}} ).

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

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

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

Krüptograafilise teksti ( R n , L n ) {\displaystyle (R_{n},L_{n})} dekrüpteerimiseks arvutatakse i = n , n - 1 , ... , 1 jaoks {\displaystyle i=n,n-1,\ldots ,1}

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

Siis 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}} 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}} 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}} ja R 1 {\displaystyle 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.

Küsimused ja vastused

K: Mis on Feisteli šifreering?

K: Millised on Feisteli struktuuri kasutamise eelised?

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

K: Milliseid meetodeid kasutatakse segaduse ja hajuvuse tekitamiseks?

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

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

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

Otsing