Feistelova šifra

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

Konstrukce Feistelovy šifry

Feistelova šifra 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).[1]

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[editovat | editovat zdroj]

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.[1]

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[2]).

Šifry, kde se používá[editovat | editovat zdroj]

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

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

Reference[editovat | editovat zdroj]

  1. a b c B. Schneier and J. Kelsey: Unbalanced Feistel Networks and Block Cipher Design. Fast Software Encryption, Third International Workshop Proceedings (February 1996), Springer-Verlag, 1996, pp. 121-144.
  2. a b Orr Dunkelman, Nathan Keller a Adi Shamir: A Practical-Time Attack on the A5/3 Cryptosystem Used in Third Generation GSM Telephony, Cryptology ePrint Archive: Report 2010/013
  3. M. Matsui, J. Nakajima, S. Moriai: A Description of the Camellia Encryption Algorithm, RFC 3713, April 2004