Feistelova šifra
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 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.
Feistelova konstrukce je iterativní povahy, což usnadňuje implementaci kryptosystému v hardwaru.
Feistelovy sítě a podobné konstrukce jsou součinové šifry, takže kombinují více kol opakovaných operací, jako např.:
- 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í.
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.
Feistelova síťová operace na blokové šifře, kde P je otevřený text a C je šifrový text.
Seznam Feistelových šifer
Feistel nebo modifikovaný Feistel: Blowfish, Camellia, CAST-128, DES, FEAL, ICE, KASUMI, LOKI97, Lucifer, MARS, MAGENTA, MISTY1, RC5, TEA, Triple DES, Twofish, XTEA, GOST 28147-89.
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.
