Feistelova šifra

Jako Feistelova šifra či Feistelova síť se v kryptografii označuje základní struktura použitá v mnoha blokových šifrách včetně DES. Její výhodou je, že šifrování a dešifrování fungují prakticky stejně, což zjednodušuje a zlevňuje implementaci.

Nazývá se podle Horsta Feistela, který tuto konstrukci použil v šifře Lucifer.

Popis

Konstrukce Feistelovy šifry

Feistelova šifra je konstrukce blokových šifer, která spočívá v tom, že se otevřený text šifrovaného bloku nejprve rozdělí na dvě poloviny $(L_{0},R_{0})$ (předpokládá se tedy jeho sudá délka) a následně se opakuje několik rund (kol, anglicky round), při kterých se vždy provede stejná operace:

$L_{i+1}=R_{i}$,

$R_{i+1}=L_{i}\oplus f(R_{i},K_{i})$,

kde $f$ je rundová funkce, $K_{i}$ je subklíč pro $i$. rundu (odvozený z klíče celé šifry), $\oplus$ je operace XOR. Výsledným šifrovým textem pak je výstup poslední rundy, avšak v opačném pořadí: $(R_{k},L_{k})$.

Základní výhodou Feistelovy šifry je fakt, že funkce rundy nemusí být invertibilní: pro dešifrování se používá naprosto identická struktura se stejnou rundovou funkcí, pouze se otočí plán klíčů – subklíče se používají v opačném pořadí. Díky struktuře šifry a vlastnostem funkce XOR to funguje pro libovolnou rundovou funkci (volba funkce však má zásadní vliv na bezpečnost šifry). Na Feistelovu síť se tedy dá hledět jako na způsob, jak libovolnou funkci převést na permutaci (bijekci).

Konkrétní šifry založené na Feistelově síti se pak od sebe liší počtem rund, definicí rundové funkce a postupem, jakým se z klíče odvozují jednotlivé subklíče.

Modifikace

Bruce Schneier a John Kelsey navrhli zobecnění Feistelovy sítě, ve kterém se nepracuje se dvěma stejně velkými polovinami bloku, ale s nestejně velkými částmi; dále navrhli možnost nehomogenní Feistelovy sítě, ve které rundová funkce není ve všech rundách stejná; načež dospěli ke zcela zobecněné Feistelově síti, která zachovává jen základní strukturu.

Existují také šifry, kde se Feistelova síť používá jako jedna z komponent (dokonce i některé Feistelovy šifry uvnitř rundové funkce používají další Feistelovu síť, např. MISTY).

Šifry, kde se používá

Feistelovou šifrou je mnoho blokových šifer, jmenovitě například: Lucifer, DES (a 3DES), GOST, FEAL, Khufu a Khafre, LOKI, CAST, Blowfish, RC5, Camellia, MISTY, KASUMI.

Další šifry používají Feistelovu síť v modifikované podobě, jen částečně, případně jsou jí inspirovány.