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í.
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í.
Galéria obrázkov
1 Obrázok
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 Ki, 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}}}
je kruhová funkcia a nech K 1 , K 2 , ... , K n {\displaystyle K_{1},K_{2},\ldots ,K_{n}}
sú podkľúče pre kolá 1 , 2 , ... , n {\displaystyle 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}} 
, R 1 {\displaystyle R_{1}} 
)
Pre každé kolo i = 1 , 2 , ... , n {\displaystyle i=1,2,\dots ,n} 
, vypočítajte (kalkulujte)
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})} 
.
Potom je šifrový text ( R n + 1 , L n + 1 ) {\displayystyle (R_{n+1},L_{n+1})} 
. (Bežne sa po poslednom kole dve časti R n {\displaystyle R_{n}} 
a L n {\displaystyle L_{n}} 
neprehodia.)
Dešifrovanie šifrového textu ( R n , L n ) {\displaystyle (R_{n},L_{n})}
sa vykoná výpočtom pre i = n , n - 1 , ... , 1 {\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})} 
.
Potom ( L 1 , R 1 ) {\displaystyle (L_{1},R_{1})} 
je opäť otvorený text.
Jednou z výhod tohto modelu je, že kruhová funkcia F {\displaystyle {\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}}
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}} a R 1 {\displaystyle 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.
Zoznam Feistelových šifier
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.
Súvisiace články
Autor
AlegsaOnline.com Feistelova sieť: Definícia blokovej šifry v kryptografii Leandro Alegsa
URL: https://sk.alegsaonline.com/art/33900