AlegsaOnline.com

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.

Autor: Leandro Alegsa

03-11-2025

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.

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.