AlegsaOnline.com

Feistel-hálózat: szimmetrikus blokkrejtjelezés, elv és példák

Ismerje meg a Feistel-hálózat elvét, előnyeit és példáit (pl. DES): könnyen implementálható szimmetrikus blokkrejtjelezés, zavar és diffúzió szemléletes magyarázata.

Szerző: Leandro Alegsa

13-02-2026

A kriptográfiában a Feistel-féle rejtjelezés egy szimmetrikus struktúra, amelyet a német IBM kriptográfusáról, Horst Feistelről neveztek el; a köznyelvben Feistel-hálózatként is ismert. A sémát számos blokkos kódoló használja, köztük a Data Encryption Standard

A Feistel-struktúra előnye, hogy a titkosítási és visszafejtési műveletek nagyon hasonlóak, sőt bizonyos esetekben azonosak, és csak a kulcsok ütemezését kell felcserélni. Ezért az ilyen rejtjelező megvalósításához szükséges kód vagy áramkör mérete majdnem a felére csökken.

A Feistel-konstrukció iteratív jellegű, ami megkönnyíti a kriptorendszer hardveres megvalósítását.

A Feistel-hálózatok és a hasonló konstrukciók termékkulcsos kódok, így több fordulóban ismétlődő műveleteket kombinálnak, például:

Bitkeverés (gyakran permutációs dobozoknak vagy P-dobozoknak nevezik)
Egyszerű nemlineáris függvények (gyakran nevezik helyettesítési dobozoknak vagy S-dobozoknak)
Lineáris keverés (a moduláris algebra értelmében) XOR segítségével, hogy egy olyan függvényt hozzon létre, amelyben nagy mennyiségben van az, amit Claude Shannon "zavar és diffúzió" néven írt le.

A bitek keverése a diffúziós hatást, míg a helyettesítés a zavaró hatást hozza létre.

Alapelvek és működés

A Feistel-hálózat tipikus felépítése: a bemeneti blokkot két egyenlő részre osztjuk, bal (L0) és jobb (R0) felére. Minden fordulóban egy körfüggvény (round function, F) dolgozik a jobb feletten és a fordulóhoz tartozó részleges kulccsal (Ki), majd a kimenetet XOR-oljuk a bal felével. Egy forduló formálisan:

L_i = R_{i-1}, R_i = L_{i-1} XOR F(R_{i-1}, K_i)

Ez az iteráció több fordulón keresztül ismétlődik. Az eredményként kapott páros (L_n, R_n) gyakran felcserélve kerül kiadáshoz, a konvenciónak megfelelően (egyes implementációk egy végső swap-ot alkalmaznak, másoknál ezt a swap-ot a round-számból adódóan kezelik).

Miért fordítható a konstrukció függetlenül az F-től?

A Feistel-séma fő előnye, hogy a teljes permutáció visszafordítható (visszafejthető) még akkor is, ha maga a körfüggvény F nem invertálható. A visszafejtés ugyanazokat a lépéseket használja, mint a titkosítás, csak a kulcsok sorrendjét fordítva (K_n, K_{n-1}, …, K_1). Ez egyszerűsíti a megvalósítást, mert ugyanaz a hardver vagy programkönyvtár használható mindkét irányban.

Tulajdonságok és elméleti eredmények

Invertálhatóság: már említettük — a Feistel-konstrukció garantálja a visszafordíthatóságot kulcssorrend megfordításával.
Luby–Rackoff tétel: elméletileg igazolt, hogy ha a körfüggvények idealizált véletlenszerű függvények (vagy megfelelően jó PRF-ek), akkor három forduló elegendő ahhoz, hogy a konstrukció pszeudovilágos permutációnak (pseudorandom permutation) tekinthető, és négy forduló erősebb bizonyosságot ad (strong PRP). Ez az eredmény elméleti alapot ad a Feistel-hálózat biztonságosságának megítéléséhez.
Kiegyensúlyozottság: a szabványos Feistel-hálózatoknál a blokk két felét általában egyenlő méretűre választják (balanced Feistel). Vannak unbalanced és generalized Feistel-változatok is, ahol a részek mérete vagy a keverés módja eltér.

Példák és gyakorlati alkalmazások

Több ismert blokkrejtjelező Feistel-szerkezetre épül vagy annak változata:

DES (Data Encryption Standard) — klasszikus példa, 16 fordulóval.
Triple DES (3DES) — DES ismétlése háromszor különböző kulcsokkal a biztonság növelésére.
Blowfish — változtatható kulcsmérettel és Feistel-szerkezeten alapul.
CAST-128 (CAST5), TEA (Tiny Encryption Algorithm), Camellia és mások — mind tartalmaznak Feistel-jellegű konstrukciókat vagy azok variánsait.

Változatok és kiterjesztések

Az alkalmazott variánsok különböző céloknak felelnek meg: általánosított Feistel-hálózatok (generalized Feistel networks, GFN) több blokkra bontják az adatot és különböző módon kombinálják a részeket; unbalanced Feistelnél a bal és jobb rész mérete eltér; egyes konstrukciók elő- és utó-belana (whitening) lépéseket illesztenek be a biztonság növelésére; mások FL/FLINV rétegeket vagy speciális kulcselőállítást használnak (például Camellia).

Biztonság és kriptoanalízis

A Feistel-hálózat biztonsága nagymértékben függ a körfüggvény (F) és a kulcselőállítás (key schedule) minőségétől, valamint a fordulók számától. Néhány fontos megfontolás:

Differenciális és lineáris kriptoanalízis: ezek gyakori támadási módszerek blokk-kódolók ellen; megfelelően tervezett S-dobozokkal és elegendő fordulóval mérsékelhetők a kockázatok.
Fordulószám: túl kevés forduló gyenge védelmet eredményez; a gyakorlati algoritmusokban ezért tipikusan sok (10–32 vagy több) fordulót alkalmaznak az erős biztonság érdekében.
Többszörös titkosítás: például a 3DES alkalmaz több DES-hívást, hogy kompenzálja a DES kis kulcshosszának problémáit; azonban ez más sebezhetőségeket (pl. meet-in-the-middle) is hozhat magával.

Gyakorlati megfontolások

Implementációkor figyelembe kell venni a következőket:

Hatékonyság hardveres és szoftveres környezetben (Feistel jól párhuzamosítható és egyszerű logikát igényel).
Időzítési és oldalsó csatorna-védelem (side-channel attacks) — a biztonság nem csupán a matematikai konstrukción múlik.
Kulcselőállítás és véletlenszerűség minősége — gyenge kulcsgenerálás könnyen megtörhető rendszert eredményez.

Összefoglalás

A Feistel-hálózat egyszerű, de hatékony séma a szimmetrikus blokk-rejtjelezésben: invertálhatósága, iteratív felépítése és a kriptorendszerekben bevált elvei miatt számos ismert algoritmus (például a Data Encryption Standard) alapját képezi. A biztonság a körfüggvény, a kulcselosztás és a fordulók számának megfelelő megválasztásán múlik; elméleti eredmények (például a Luby–Rackoff tétel) és gyakorlati kriptoanalízis egyaránt ad útmutatást a tervezéshez.

Elméleti munka

Számos modern szimmetrikus blokkos titkosítás Feistel-hálózatokat használ, és a Feistel-kódok szerkezetét és tulajdonságait a kriptográfusok széles körben vizsgálták. Különösen Michael Luby és Charles Rackoff elemezte a Feistel-blokkchiffre szerkezetét, és bebizonyította, hogy ha a körfüggvény egy kriptográfiailag biztonságos pszeudorandom függvény, és K-t_i használják magként, akkor 3 kör elegendő ahhoz, hogy a blokkchiffre pszeudorandom permutáció legyen, míg 4 kör elegendő ahhoz, hogy "erős" pszeudorandom permutáció legyen (ami azt jelenti, hogy még egy olyan ellenfél számára is pszeudorandom marad, aki orákulum hozzáféréssel rendelkezik a fordított permutációhoz). Luby és Rackoff e nagyon fontos eredménye miatt a Feistel-kódokat néha Luby-Rackoff blokk-kódoknak is nevezik. További elméleti tanulmányok általánosították a konstrukciót, és pontosabb biztonsági határokat határoztak meg.

Építés

Legyen F {\displaystyle {\rm {F}}}} ${\rm F}$ a körfüggvény, és legyenek K 1 , K 2 , ... , K n {\displaystyle K_{1},K_{2},\ldots ,K_{n}}} $K_1,K_2,\ldots,K_{n}$ 1 , 2 , ... , n {\displaystyle 1,2,\ldots ,n}} $1,2,\ldots,n$ körökhöz tartozó alkulcsok.

Ezután az alapművelet a következő:

A tisztán szöveges blokkot két egyenlő darabra osztjuk ( L 1 {\displaystyle L_{1}} L_1 , R 1 {\displaystyle R_{1}} R_1 ).

Minden egyes i = 1 , 2 , ... , n fordulóban {\displaystyle i=1,2,\dots ,n} $i =1,2,\dots,n$ , számítsuk ki (kalkuláljuk)

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

Ekkor a rejtjelezett szöveg ( R n + 1 , L n + 1 ) {\displaystyle (R_{n+1},L_{n+1})} $(R_{n+1}, L_{n+1})$ . (Általában a két darab R n {\displaystyle R_{n}} R_n és L n {\displaystyle L_{n}} L_n nem cserélődik fel az utolsó kör után).

Egy rejtjelezett szöveg ( R n , L n ) {\displaystyle (R_{n},L_{n})} (R_n, L_n) visszafejtése úgy történik, hogy i = n , n - 1 , ... , 1 {\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})$ .

Ekkor ( L 1 , R 1 ) {\displaystyle (L_{1},R_{1})} (L_1,R_1) ismét a nyílt szöveg.

E modell egyik előnye, hogy az F {\displaystyle {\rm {F}}} kerek függvénynek ${\rm F}$ nem kell invertálhatónak lennie, és nagyon összetett is lehet.

Az ábra a titkosítási folyamatot szemlélteti. A visszafejtéshez csak a K n , K n - 1 , ... , K 1 {\displaystyle K_{n},K_{n-1},\ldots ,K_{1}} $K_{n},K_{n-1},\ldots,K_1$ alkulcsok sorrendjét kell megfordítani ugyanezzel az eljárással; ez az egyetlen különbség a titkosítás és a visszafejtés között:

A kiegyensúlyozatlan Feistel-kódok egy módosított szerkezetet használnak, ahol L 1 {\displaystyle L_{1}} L_1 és R 1 {\displaystyle R_{1}} R_1 nem egyenlő hosszúságú. A MacGuffin rejtjelezés egy ilyen rejtjelezés kísérleti példája.

A Feistel-konstrukciót a blokkos kódoláson kívüli kriptográfiai algoritmusokban is használják. Például az Optimal Asymmetric Encryption Padding (OAEP) séma egy egyszerű Feistel-hálózatot használ a rejtjelszövegek véletlenszerűvé tételére bizonyos aszimmetrikus kulcsú titkosítási sémákban.

Feistel-hálózati művelet blokkos rejtjelezésen, ahol P az egyszerű szöveg és C a rejtjelezett szöveg.

A Feistel-kódok listája

Feistel vagy módosított Feistel: Blowfish, Camellia, CAST-128, DES, FEAL, ICE, KASUMI, LOKI97, Lucifer, MARS, MAGENTA, MISTY1, RC5, TEA, Triple DES, Twofish, XTEA, GOST 28147-89.

Általánosított Feistel: CAST-256, MacGuffin, RC2, RC6, Skipjack

Kérdések és válaszok

K: Mi az a Feistel-féle rejtjelezés?

V: A Feistel-féle rejtjelezés egy szimmetrikus struktúra, amelyet a blokkos rejtjelek építésénél használnak, és amelyet a német IBM kriptográfusáról, Horst Feistelről neveztek el. Általában Feistel-hálózatként is ismert.

K: Milyen előnyei vannak a Feistel-struktúra használatának?

V: A Feistel-struktúra használatának fő előnye, hogy a titkosítási és visszafejtési műveletek nagyon hasonlóak, sőt egyes esetekben azonosak, és csak a kulcsok ütemezésének felcserélését igénylik. Ez közel a felére csökkenti az ilyen rejtjelezés megvalósításához szükséges kód vagy áramkör méretét. Emellett az iteratív jelleg megkönnyíti a kriptorendszer hardveres megvalósítását.

K: Hogyan írja le Claude Shannon a "zavart és diffúziót"?

V: Claude Shannon a "zavar és diffúzió" fogalmát úgy írta le, hogy mindkét elem nagy mennyiségben van jelen, hogy a támadó számára megnehezítse a titkosított üzenet megfejtését.

K: Milyen technikákat használnak a zavar és a diffúzió létrehozására?

V: A zavart és a diffúziót bitkeveréssel (gyakran permutációs dobozoknak vagy P-dobozoknak nevezik) és egyszerű nemlineáris függvényekkel (gyakran helyettesítési dobozoknak vagy S-dobozoknak nevezik), valamint lineáris keveréssel (a moduláris algebra értelmében) az XOR segítségével hozzák létre. A bitkeverés a diffúziós hatást hozza létre, míg a helyettesítés a zavarás érdekében használatos.

K: Milyen típusú rejtjelező a Feistel-hálózat?

V: A Feistel-hálózat egy olyan típusú termékrejtjelező, amely az adatok biztonságos titkosítása érdekében több körös ismétlődő műveleteket kombinál.

K: Ki fejlesztette ki ezt a fajta rejtjelezést?

V: A Feistel-struktúrát a német IBM kriptográfusa, Horst Feistel fejlesztette ki.

K: A Data Encryption Standard ezen a típusú kriptográfián alapul?

V: Igen, a Data Encryption Standard ezt a fajta kriptográfiát használja, amely ugyanazokat a fentebb vázolt elveket használja a titkosított üzeneten belüli zavar és diffúzió létrehozására.