AlegsaOnline.com

Feistelova sieť: Definícia blokovej šifry v kryptografii

Feistelova sieť: prehľad blokovej šifry v kryptografii — princíp, výhody, bezpečná implementácia a praktické použitie Feistelových konštrukcií.

Autor: Leandro Alegsa

23-03-2026

Feistelova šifra je v kryptografii symetrická štruktúra používaná pri konštrukcii blokových šifier, pomenovaná podľa nemeckého kryptografa IBM Horsta Feistela; bežne sa nazýva aj Feistelova sieť. Túto schému využíva veľký súbor blokových šifier vrátane Data Encryption Standard (DES) a mnohé ďalšie moderné návrhy ako napr. Blowfish alebo rôzne varianty generalized Feistel sietí.

Ako Feistelova sieť funguje

Feistelova konštrukcia rozdeľuje vstupný blok na dve časti (zvyčajne rovnaké veľkosti): ľavú časť L a pravú časť R. Šifrovanie sa vykonáva cez niekoľko opakovaných kôl (rounds). Jedno kolo s kľúčom Ki typicky vykonáva tieto operácie:

Li = R{i-1}
Ri = L{i-1} XOR F(R{i-1}, Ki)

kde F je tzv. round function – nelineárna funkcia, ktorá prijíma polovicu bloku a podkľúč a vracia výstup rovnakého bitového rozmeru. Po poslednom kole sa (ak je potrebné) časti možno prehodiť, aby vznikol výsledný šifrový text.

Dešifrovanie v Feistelovej sieti používa rovnakú štruktúru ako šifrovanie s tým rozdielom, že sa aplikuje rovnaká funkcia F s kľúčmi v opačnom poradí (zmena rozvrhu kľúčov). Preto nie je potrebné mať explicitne invertibilnú funkciu F — invertibilita celej konštrukcie je daná samotnou Feistelovou štruktúrou.

Kľúčové komponenty a typické operácie

Feistelove siete a podobné konštrukcie sú súčinové šifry, a preto kombinujú viacero kôl opakovaných operácií, ako napríklad:

Bit-shuffling (často nazývaný permutačné boxy alebo P-boxy)
Jednoduché nelineárne funkcie (často nazývané substitučné polia alebo S-polia)
Lineárne miešanie (v zmysle modulárnej algebry) pomocou XOR na vytvorenie funkcie s veľkým množstvom toho, čo Claude Shannon opísal ako "zmätok a difúziu".

Premiešavanie bitov vytvára efekt difúzie, zatiaľ čo substitúcia sa používa na zámenu (zmätok). Kombinácia týchto operácií v dostatočnom počte kôl vedie k dobre rozptýlenému a nelineárnemu výstupu.

Výhody Feistelovej konštrukcie

Jednoduché dešifrovanie: dešifrovací proces je veľmi podobný šifrovaciemu a často vyžaduje len zmenu poradia kľúčov, čo znižuje objem kódu alebo obvodov potrebných na implementáciu.
Možnosť použiť neinvertibilné F: funkcia F nemusí byť invertibilná, čo uľahčuje návrh zložitých nelineárnych komponentov bez nutnosti konštrukcie ich inverzie.
Iteratívna implementácia: vhodné pre hardvér aj softvér vďaka opakovanému použitiu rovnakých komponentov.
Flexibilita: jednoduché rozšírenie počtu kôl, rôzne veľkosti polovíc (balanced vs. unbalanced) a varianty ako generalized Feistel network (GFN).

Nevýhody a bezpečnostné aspekty

Potenciálna zraniteľnosť pri slabých komponentoch: ak sú S-boxy, funkcia F alebo rozvrh kľúčov nesprávne navrhnuté, šifra môže byť citlivá na diferentálnu alebo lineárnu kryptanalýzu.
Pečeť pevného velikosti bloku: bloková šifra má pevný rozmer bloku, čo môže byť obmedzením pre určité aplikácie (existujú však techniky, ako napr. režimy prevádzky alebo format-preserving encryption).
Počet kôl: bezpečnosť závisí od dostatočného počtu kôl a kvality F; je potrebné starostlivo zvoliť počet a návrh funkcií.

Varianty a príklady

Medzi známe implementácie Feistelovej konštrukcie patria:

DES — klasická 16-kolová Feistelova šifra s 64-bitovým blokom (efektívne 56-bitovým kľúčom).
Blowfish — Feistelova sieť s variabilnou dĺžkou kľúča a 16 kolami.
CAST, GOST (v niektorých verziách) a mnohé ďalšie návrhy používajú Feistelovu alebo rozšírené Feistelove schémy.

Moderné alternatívy k Feistelovým sieťam sú napríklad substitučné-permutačné siete (SPN) ako AES (Rijndael), ktoré používajú invertibilné S-boxy a operácie na celej stavebnici namiesto rozdelenia na polovice. Oba prístupy majú svoje výhody a sú bezpečné pri správnom návrhu.

Bezpečnostné poznámky a teoretické výsledky

Feistelova konštrukcia má silnú teoretickú podporu: známe výsledky v kombinatorickej kryptografii (napr. práce Lubyho a Rackoffa) ukazujú, že Feistelove siete s dostatočným počtom kôl a náhodnými (alebo kryptograficky silnými) funkciami F môžu dosiahnuť vlastnosti pseudonáhodnej permutácie. V praxi to znamená, že pri správnom návrhu S-boxov, rozvrhu kľúčov a počtu kôl môže byť Feistelova šifra odolná voči bežným kryptanalytickým útokom.

Praktické odporúčania

Pri návrhu použiť overené komponenty (silné S-boxy, dobre navrhnutý rozvrh kľúčov).
Zvoliť dostatočný počet kôl podľa požadanej bezpečnosti a analýz konkrétnej konštrukcie.
Pri implementácii dbať na ochranu proti bočným kanálom (timing, power analysis) a na správne spracovanie režimov šifrovania.

Feistelova sieť zostáva dôležitým a praktickým stavebným kameňom v návrhu blokových šifier vďaka svojej jednoduchej invertibilite, flexibilite a efektívnosti implementácie.

Teoretická práca

Mnohé moderné symetrické blokové šifry využívajú Feistelove siete a kryptografi podrobne skúmali štruktúru a vlastnosti Feistelových šifier. Konkrétne Michael Luby a Charles Rackoff analyzovali konštrukciu Feistelovej blokovej šifry a dokázali, že ak je kruhová funkcia kryptograficky bezpečnou pseudonáhodnou funkciou, pričom ako semeno sa používa K_i, potom stačia 3 kolá na to, aby bloková šifra bola pseudonáhodnou permutáciou, zatiaľ čo 4 kolá stačia na to, aby bola "silnou" pseudonáhodnou permutáciou (čo znamená, že zostáva pseudonáhodnou aj pre protivníka, ktorý získa prístup k jej inverznej permutácii). Kvôli tomuto veľmi dôležitému výsledku Lubyho a Rackoffa sa Feistelove šifry niekedy nazývajú Luby-Rackoffove blokové šifry. Ďalšie teoretické štúdie zovšeobecnili túto konštrukciu a definovali presnejšie limity bezpečnosti.

Konštrukcia

Nech F {\displaystyle {\rm {F}}} ${\rm F}$ je kruhová funkcia a nech K 1 , K 2 , ... , K n {\displaystyle K_{1},K_{2},\ldots ,K_{n}} $K_1,K_2,\ldots,K_{n}$ sú podkľúče pre kolá 1 , 2 , ... , n {\displaystyle 1,2,\ldots ,n}} $1,2,\ldots,n$ .

Základná operácia je potom nasledovná:

Rozdeľte blok otvoreného textu na dve rovnaké časti ( L 1 {\displaystyle L_{1}} L_1 , R 1 {\displaystyle R_{1}} R_1 )

Pre každé kolo i = 1 , 2 , ... , n {\displaystyle i=1,2,\dots ,n} $i =1,2,\dots,n$ , vypočítajte (kalkulujte)

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

Potom je šifrový text ( R n + 1 , L n + 1 ) {\displayystyle (R_{n+1},L_{n+1})} $(R_{n+1}, L_{n+1})$ . (Bežne sa po poslednom kole dve časti R n {\displaystyle R_{n}} R_n a L n {\displaystyle L_{n}} L_n neprehodia.)

Dešifrovanie šifrového textu ( R n , L n ) {\displaystyle (R_{n},L_{n})} (R_n, L_n) sa vykoná výpočtom pre 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})$ .

Potom ( L 1 , R 1 ) {\displaystyle (L_{1},R_{1})} (L_1,R_1) je opäť otvorený text.

Jednou z výhod tohto modelu je, že kruhová funkcia F {\displaystyle {\rm {F}}} ${\rm F}$ nemusí byť invertovateľná a môže byť veľmi zložitá.

Schéma znázorňuje proces šifrovania. Dešifrovanie si vyžaduje len zmenu poradia podkľúčov K n , K n - 1 , ... , K 1 {\displayystyle K_{n},K_{n-1},\ldots ,K_{1}} $K_{n},K_{n-1},\ldots,K_1$ rovnakým postupom; to je jediný rozdiel medzi šifrovaním a dešifrovaním:

Nevyvážené Feistelove šifry používajú modifikovanú štruktúru, kde L 1 {\displaystyle L_{1}} L_1 a R 1 {\displaystyle R_{1}} R_1 nie sú rovnako dlhé. Šifra MacGuffin je experimentálnym príkladom takejto šifry.

Feistelova konštrukcia sa používa aj v iných kryptografických algoritmoch ako blokové šifry. Napríklad schéma Optimal Asymmetric Encryption Padding (OAEP) využíva jednoduchú Feistelovu sieť na náhodnú zmenu šifrových textov v niektorých schémach šifrovania s asymetrickým kľúčom.

Feistelova sieťová operácia na blokovej šifre, kde P je otvorený text a C je šifrový text

Zoznam Feistelových šifier

Feistel alebo modifikovaný Feistel: Blowfish, Camellia, CAST-128, DES, FEAL, ICE, KASUMI, LOKI97, Lucifer, MARS, MAGENTA, MISTY1, RC5, TEA, Triple DES, Twofish, XTEA, GOST 28147-89

Zovšeobecnený Feistel: CAST-256, MacGuffin, RC2, RC6, Skipjack

Otázky a odpovede

Otázka: Čo je to Feistelova šifra?

Odpoveď: Feistelova šifra je symetrická štruktúra používaná pri konštrukcii blokových šifier, pomenovaná podľa nemeckého kryptografa IBM Horsta Feistela. Bežne je známa aj ako Feistelova sieť.

Otázka: Aké sú niektoré výhody používania Feistelovej štruktúry?

Odpoveď: Hlavnou výhodou použitia Feistelovej štruktúry je, že šifrovacie a dešifrovacie operácie sú veľmi podobné, v niektorých prípadoch dokonca identické a vyžadujú si len zmenu rozvrhu kľúčov. To znižuje veľkosť kódu alebo obvodov potrebných na implementáciu takejto šifry takmer o polovicu. Okrem toho jej iteratívna povaha uľahčuje implementáciu kryptosystému v hardvéri.

Otázka: Ako Claude Shannon opisuje "zmätok a difúziu"?

Odpoveď: Claude Shannon opísal "zmätok a difúziu" ako prítomnosť veľkého množstva oboch prvkov s cieľom sťažiť útočníkovi dešifrovanie zašifrovanej správy.

Otázka: Aké techniky sa používajú na vytvorenie zmätku a difúzie?

Odpoveď: Zmätok a difúzia sa vytvárajú pomocou miešania bitov (často nazývaného permutačné polia alebo P-boxy) a jednoduchých nelineárnych funkcií (často nazývaných substitučné polia alebo S-boxy), ako aj lineárneho miešania (v zmysle modulárnej algebry) pomocou XOR. Premiešavanie bitov vytvára difúzny efekt, zatiaľ čo substitúcia sa používa na zmätenie.

Otázka: Aký typ šifry je Feistelova sieť?

Odpoveď: Feistelova sieť je typ súčinovej šifry, ktorá kombinuje viacero kôl opakovaných operácií s cieľom bezpečne zašifrovať údaje.

Otázka: Kto vyvinul tento typ kryptografie?

Odpoveď: Feistelovu štruktúru vyvinul nemecký kryptograf IBM Horst Feistel.

Otázka: Je Data Encryption Standard založený na tomto type kryptografie?

Odpoveď: Áno, Data Encryption Standard využíva tento typ kryptografie, ktorý využíva rovnaké princípy uvedené vyššie na vytvorenie zmätku a rozptýlenia v šifrovanej správe.