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}}}{\rm F} je funkce kola a nechť K 1 , K 2 , ... , K n {\displaystyle K_{1},K_{2},\ldots ,K_{n}}K_1,K_2,\ldots,K_{n}jsou dílčí klíče pro kola 1 , 2 , ... , n {\displaystyle 1,2,\ldots ,n}}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}} L_1, R 1 {\displaystyle R_{1}} R_1).

Pro každé kolo i = 1 , 2 , ... , n {\displaystyle i=1,2,\dots ,n} i =1,2,\dots,n, vypočítejte (kalkulujte)

L i + 1 = R i {\displaystyle L_{i+1}=R_{i}\,} 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})} 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})}(R_{n+1}, L_{n+1}) . (Obvykle se po posledním kole obě části R n {\displaystyle R_{n}}R_n a L n {\displaystyle L_{n}}L_n nepřehodí.)

Dešifrování šifrového textu ( R n , L n ) {\displaystyle (R_{n},L_{n})}(R_n, L_n) se provádí výpočtem pro i = n , n - 1 , ... , 1 {\displaystyle i=n,n-1,\ldots ,1}. i=n,n-1,\ldots,1

R i = L i + 1 {\displaystyle R_{i}=L_{i+1}\,} 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})} L_{i} = R_{i+1} \oplus {\rm F}(L_{i+1}, K_{i}).

Pak ( L 1 , R 1 ) {\displaystyle (L_{1},R_{1})} (L_1,R_1)je opět otevřený text.

Jednou z výhod tohoto modelu je, že kruhová funkce F {\displaystyle {\rm {F}}} {\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}}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}} L_1a R 1 {\displaystyle R_{1}} R_1nejsou 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.Zoom
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.

Zobecněný Feistel: CAST-256, MacGuffin, RC2, RC6, Skipjack

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.

AlegsaOnline.com - 2020 / 2023 - License CC3