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