Feistelova síť: princip, konstrukce a využití v blokových šifrách
Feistelova síť: přehled principu, konstrukce a praktického využití v blokových šifrách — jak funguje, výhody, implementace a bezpečnostní aspekty.
Feistelova šifra je v kryptografii symetrická struktura používaná při konstrukci blokových šifer, pojmenovaná po německém kryptografovi IBM Horstu Feistelovi; běžně se také nazývá Feistelova síť. Toto schéma používá velká řada blokových šifer, včetně standardu Data Encryption Standard. Feistelova síť poskytuje jednoduchý a flexibilní rámec pro navrhování šifer s dobrými vlastnostmi zmatení a rozptýlení, při relativně malé implementační složitosti.
Feistelova struktura má tu výhodu, že operace šifrování a dešifrování jsou velmi podobné, v některých případech dokonce totožné, a vyžadují pouze změnu rozvrhu klíčů. Proto se velikost kódu nebo obvodů potřebných k implementaci takové šifry sníží téměř o polovinu. Díky iterativní povaze je konstrukce také výhodná pro implementaci v hardwaru i softwaru (pipeline, opakované použití stejné logiky, bit-slicing).
Galerie obrázků
1 Obrázek
Princip fungování
V nejjednodušším (vyváženém) Feistelově schématu se vstupní blok bitů rozdělí na dvě stejně dlouhé poloviny L0 a R0. Pro každé kolo i se použije nelineární tzv. kolová funkce F a podklíč Ki takto:
- Li = Ri−1
- Ri = Li−1 ⊕ F(Ri−1, Ki)
Po posledního kola (u některých variant se provede ještě záměna nebo ne) se poloviny spojí a získá se šifrovaný blok. Dešifrování se provádí přesně opačným pořadím klíčů: stejná kolová funkce F se používá, ale klíče se aplikují v opačném sledu, takže není nutné navrhovat inverzní funkci F. Tento princip vysvětluje, proč Feistelova konstrukce umožňuje jednoduchou dešifrovací logiku i pro kolové funkce, které samy nejsou vratné.
Konstrukce a varianty
- Bit-shuffling (často nazývaný permutační pole nebo P-box)
- Jednoduché nelineární funkce (často nazývané substituční pole nebo S-box)
- Lineární míchání (ve smyslu modulární algebry) pomocí XOR k vytvoření funkce s velkým množstvím toho, co Claude Shannon popsal jako "zmatení a rozptýlení".
Přehazování bitů vytváří difuzní efekt, zatímco záměna se používá pro zmatení.
Kromě klasického (vyváženého) Feistela existují i varianty:
- Nevyvážená Feistelova síť – poloviny nejsou stejné délky, užitečná pro specifické velikosti bloků.
- Obecná (Generalized) Feistelova síť – blok se rozdělí na více než dvě části a kolové funkce kombinují více větví; použitá v některých moderních návrzích pro lepší paralelizaci.
- Feistel se vstupními/multiplikativními modifikacemi – do kola se přidávají další lineární/ne-lineární operace (např. modular addition) pro zvýšení odolnosti.
Bezpečnost a kryptanalýza
Bezpečnost Feistelovy sítě závisí hlavně na kvalitě kolové funkce F, na rozvrhu klíčů a na počtu kol. Teoretické výsledky (např. věty Luby–Rackoff) ukazují, že s náhodnými kolovými funkcemi může několik kol (typicky 3 až 4) poskytnout silné formy pseudonáhodnosti; v praxi se však používá větší počet kol kvůli reálným implementacím funkcí a známým útokům.
Mezi nejčastější typy útoků patří:
- Diferenciální kryptanalýza – sleduje, jak se rozdíly ve vstupu šíří přes kola; návrh S-boxů a dostatečný počet kol tento útok snižují.
- Lineární kryptanalýza – hledá lineární aproximace mezi bitovými proměnnými vstupu a výstupu; silné nelineární složky a náhodný rozvrh klíčů pomáhají.
- Slide útoky – využívají opakování stejné struktury a slabého rozvrhu klíčů; odolávat lze propracovaným rozvrhem klíčů a variantami kol.
Praktické použití a příklady
Feistelova konstrukce byla základem mnoha reálných šifer. Nejznámějším příkladem je Data Encryption Standard (DES), který využívá 16 kol Feistelovy sítě s definovanými S-boxy a permutacemi. Mezi další šifry založené na Feistelově konstrukci patří Blowfish, CAST-128, Twofish nebo Camellia (u každé z nich se liší detaily kolové funkce, počet kol a rozvrh klíčů).
Výhody pro implementaci
- Šifrování a dešifrování mohou sdílet stejnou hardwarovou/softwarovou logiku — stačí reverzní pořadí klíčů.
- Iterativní provedení umožňuje snadné škálování, pipeline a opakované použití komponent.
- Kolová funkce může být navržena nezávisle a nemusí být vratná, což rozšiřuje designérské možnosti.
Doporučení pro návrháře a implementátory
- Pečlivě navrhněte kolovou funkci F (silné S-boxy, vhodné lineární operace) tak, aby odolávala diferenciální a lineární analýze.
- Zajistěte robustní rozvrh klíčů, aby se zabránilo útokům vyžadujícím opakování nebo symetrii kol.
- Použijte dostatečný počet kol podle současných bezpečnostních doporučení a odhadů útočných nákladů.
- Při implementaci dbejte na odolnost proti útokům zaměřeným na postranní kanály (timing, cache, power), zejména v embedded prostředích.
Feistelovy sítě zůstávají díky své flexibilitě, jednoduchosti a dobrým bezpečnostním vlastnostem základním stavebním kamenem v návrhu blokových šifer. Při dodržení osvědčených návrhových zásad a pečlivé analýze kolové funkce poskytují robustní řešení pro symetrické šifrování dat.
Teoretická práce
Mnoho moderních symetrických blokových šifer využívá Feistelovy sítě a struktura a vlastnosti Feistelových šifer byly kryptografy hojně zkoumány. Konkrétně Michael Luby a Charles Rackoff analyzovali konstrukci Feistelovy blokové šifry a dokázali, že pokud je kruhová funkce kryptograficky bezpečnou pseudonáhodnou funkcí, přičemž jako semeno se používá Ki, pak stačí 3 kola, aby bloková šifra byla pseudonáhodnou permutací, zatímco 4 kola stačí, aby byla "silnou" pseudonáhodnou permutací (což znamená, že zůstane pseudonáhodnou i pro protivníka, který získá přístup k její inverzní permutaci). Kvůli tomuto velmi důležitému výsledku Lubyho a Rackoffa se Feistelovy šifry někdy nazývají Lubyho-Rackoffovy blokové šifry. Další teoretické studie tuto konstrukci zobecnily a definovaly přesnější limity bezpečnosti.
Konstrukce
Nechť F {\displaystyle {\rm {F}}}
je funkce kola a nechť K 1 , K 2 , ... , K n {\displaystyle K_{1},K_{2},\ldots ,K_{n}}
jsou dílčí klíče pro kola 1 , 2 , ... , n {\displaystyle 1,2,\ldots ,n}}
.
Základní operace pak vypadá následovně:
Rozdělte blok otevřeného textu na dvě stejné části ( L 1 {\displaystyle L_{1}} 
, R 1 {\displaystyle R_{1}} 
).
Pro každé kolo i = 1 , 2 , ... , n {\displaystyle i=1,2,\dots ,n} 
, vypočítejte (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})} 
.
Pak je šifrový text ( R n + 1 , L n + 1 ) {\displayystyle (R_{n+1},L_{n+1})}
. (Obvykle se po posledním kole obě části R n {\displaystyle R_{n}}
a L n {\displaystyle L_{n}}
nepřehodí.)
Dešifrování šifrového textu ( R n , L n ) {\displaystyle (R_{n},L_{n})}
se provádí výpočtem pro 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})} 
.
Pak ( L 1 , R 1 ) {\displaystyle (L_{1},R_{1})} 
je opět otevřený text.
Jednou z výhod tohoto modelu je, že kruhová funkce F {\displaystyle {\rm {F}}} nemusí být inverzní a může být velmi složitá.
Schéma znázorňuje proces šifrování. Dešifrování vyžaduje pouze obrácení pořadí dílčích klíčů K n , K n - 1 , ... , K 1 {\displayystyle K_{n},K_{n-1},\ldots ,K_{1}}
stejným postupem; to je jediný rozdíl mezi šifrováním a dešifrováním:
Nevyvážené Feistelovy šifry používají modifikovanou strukturu, kde L 1 {\displaystyle L_{1}} a R 1 {\displaystyle R_{1}} nejsou stejně dlouhé. Experimentálním příkladem takové šifry je šifra MacGuffin.
Feistelova konstrukce se používá i v jiných kryptografických algoritmech než blokových šifrách. Například schéma OAEP (Optimal Asymmetric Encryption Padding) používá jednoduchou Feistelovu síť k randomizaci šifrových textů v některých schématech šifrování s asymetrickým klíčem.
Seznam Feistelových šifer
Otázky a odpovědi
Otázka: Co je to Feistelova šifra?
Odpověď: Feistelova šifra je symetrická struktura používaná při konstrukci blokových šifer, pojmenovaná podle německého kryptografa IBM Horsta Feistela. Běžně je také známá jako Feistelova síť.
Otázka: Jaké jsou výhody použití Feistelovy struktury?
Odpověď: Hlavní výhodou použití Feistelovy struktury je, že operace šifrování a dešifrování jsou velmi podobné, v některých případech dokonce totožné, a vyžadují pouze změnu rozvrhu klíčů. To snižuje velikost kódu nebo obvodů potřebných k implementaci takové šifry téměř o polovinu. Její iterativní povaha navíc usnadňuje implementaci kryptosystému v hardwaru.
Otázka: Jak Claude Shannon popisuje "zmatení a rozptýlení"?
Odpověď: Claude Shannon popsal "zmatení a rozptýlení" jako přítomnost velkého množství obou prvků, aby bylo pro útočníka obtížné dešifrovat zašifrovanou zprávu.
Otázka: Jaké techniky se používají k vytvoření zmatení a rozptýlení?
Odpověď: Zmatek a difúze se vytvářejí pomocí míchání bitů (často nazývaného permutační pole nebo P-boxy) a jednoduchých nelineárních funkcí (často nazývaných substituční pole nebo S-boxy), jakož i lineárního míchání (ve smyslu modulární algebry) pomocí XOR. Bitové míchání vytváří difuzní efekt, zatímco substituce slouží k záměně.
Otázka: Jakým typem šifry je Feistelova síť?
Odpověď: Feistelova síť je typ součinové šifry, která kombinuje více kol opakovaných operací za účelem bezpečného zašifrování dat.
Otázka: Kdo vyvinul tento typ kryptografie?
Odpověď: Feistelovu strukturu vyvinul německý kryptograf IBM Horst Feistel.
Otázka: Je standard Data Encryption Standard založen na tomto typu kryptografie?
Odpověď: Ano, standard Data Encryption Standard využívá tento typ kryptografie, který využívá stejné principy popsané výše pro vytváření zmatku a rozptylu uvnitř šifrované zprávy.
Související články
Autor
AlegsaOnline.com Feistelova síť: princip, konstrukce a využití v blokových šifrách Leandro Alegsa
URL: https://cs.alegsaonline.com/art/33900