Feistelova šifra

Teoretická práca

Mnohé moderné symetrické blokové šifry využívajú Feistelove siete a kryptografi podrobne skúmali štruktúru a vlastnosti Feistelových šifier. Konkrétne Michael Luby a Charles Rackoff analyzovali konštrukciu Feistelovej blokovej šifry a dokázali, že ak je kruhová funkcia kryptograficky bezpečnou pseudonáhodnou funkciou, pričom ako semeno sa používa K_i, potom stačia 3 kolá na to, aby bloková šifra bola pseudonáhodnou permutáciou, zatiaľ čo 4 kolá stačia na to, aby bola "silnou" pseudonáhodnou permutáciou (čo znamená, že zostáva pseudonáhodnou aj pre protivníka, ktorý získa prístup k jej inverznej permutácii). Kvôli tomuto veľmi dôležitému výsledku Lubyho a Rackoffa sa Feistelove šifry niekedy nazývajú Luby-Rackoffove blokové šifry. Ďalšie teoretické štúdie zovšeobecnili túto konštrukciu a definovali presnejšie limity bezpečnosti.

Konštrukcia

Nech F {\displaystyle {\rm {F}}} je kruhová funkcia a nech K 1 , K 2 , ... , K n {\displaystyle K_{1},K_{2},\ldots ,K_{n}}sú podkľúče pre kolá 1 , 2 , ... , n {\displaystyle 1,2,\ldots ,n}}.

Základná operácia je potom nasledovná:

Rozdeľte blok otvoreného textu na dve rovnaké časti ( L 1 {\displaystyle L_{1}} , R 1 {\displaystyle R_{1}} )

Pre každé kolo i = 1 , 2 , ... , n {\displaystyle i=1,2,\dots ,n} , vypočítajte (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})} .

Potom je šifrový text ( R n + 1 , L n + 1 ) {\displayystyle (R_{n+1},L_{n+1})} . (Bežne sa po poslednom kole dve časti R n {\displaystyle R_{n}} a L n {\displaystyle L_{n}} neprehodia.)

Dešifrovanie šifrového textu ( R n , L n ) {\displaystyle (R_{n},L_{n})} sa vykoná výpočtom pre 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})} .

Potom ( L 1 , R 1 ) {\displaystyle (L_{1},R_{1})} je opäť otvorený text.

Jednou z výhod tohto modelu je, že kruhová funkcia F {\displaystyle {\rm {F}}} nemusí byť invertovateľná a môže byť veľmi zložitá.

Schéma znázorňuje proces šifrovania. Dešifrovanie si vyžaduje len zmenu poradia podkľúčov K n , K n - 1 , ... , K 1 {\displayystyle K_{n},K_{n-1},\ldots ,K_{1}} rovnakým postupom; to je jediný rozdiel medzi šifrovaním a dešifrovaním:

Nevyvážené Feistelove šifry používajú modifikovanú štruktúru, kde L 1 {\displaystyle L_{1}} a R 1 {\displaystyle R_{1}} nie sú rovnako dlhé. Šifra MacGuffin je experimentálnym príkladom takejto šifry.

Feistelova konštrukcia sa používa aj v iných kryptografických algoritmoch ako blokové šifry. Napríklad schéma Optimal Asymmetric Encryption Padding (OAEP) využíva jednoduchú Feistelovu sieť na náhodnú zmenu šifrových textov v niektorých schémach šifrovania s asymetrickým kľúčom.

Feistelova sieťová operácia na blokovej šifre, kde P je otvorený text a C je šifrový text

Zoznam Feistelových šifier

Feistel alebo modifikovaný Feistel: Blowfish, Camellia, CAST-128, DES, FEAL, ICE, KASUMI, LOKI97, Lucifer, MARS, MAGENTA, MISTY1, RC5, TEA, Triple DES, Twofish, XTEA, GOST 28147-89

Zovšeobecnený Feistel: CAST-256, MacGuffin, RC2, RC6, Skipjack