Feistel rejtjelezés

A kriptográfiában a Feistel-féle rejtjelezés egy szimmetrikus struktúra, amelyet a német IBM kriptográfusáról, Horst Feistelről neveztek el; a köznyelvben Feistel-hálózatként is ismert. A sémát számos blokkos kódoló használja, köztük a Data Encryption Standard

A Feistel-struktúra előnye, hogy a titkosítási és visszafejtési műveletek nagyon hasonlóak, sőt bizonyos esetekben azonosak, és csak a kulcsok ütemezését kell felcserélni. Ezért az ilyen rejtjelező megvalósításához szükséges kód vagy áramkör mérete majdnem a felére csökken.

A Feistel-konstrukció iteratív jellegű, ami megkönnyíti a kriptorendszer hardveres megvalósítását.

A Feistel-hálózatok és a hasonló konstrukciók termékkulcsos kódok, így több fordulóban ismétlődő műveleteket kombinálnak, például:

Bitkeverés (gyakran permutációs dobozoknak vagy P-dobozoknak nevezik)
Egyszerű nemlineáris függvények (gyakran nevezik helyettesítési dobozoknak vagy S-dobozoknak)
Lineáris keverés (a moduláris algebra értelmében) XOR segítségével, hogy egy olyan függvényt hozzon létre, amelyben nagy mennyiségben van az, amit Claude Shannon "zavar és diffúzió" néven írt le.

A bitek keverése a diffúziós hatást, míg a helyettesítés a zavaró hatást hozza létre.

Elméleti munka

Számos modern szimmetrikus blokkos titkosítás Feistel-hálózatokat használ, és a Feistel-kódok szerkezetét és tulajdonságait a kriptográfusok széles körben vizsgálták. Különösen Michael Luby és Charles Rackoff elemezte a Feistel-blokkchiffre szerkezetét, és bebizonyította, hogy ha a körfüggvény egy kriptográfiailag biztonságos pszeudorandom függvény, és K-t_i használják magként, akkor 3 kör elegendő ahhoz, hogy a blokkchiffre pszeudorandom permutáció legyen, míg 4 kör elegendő ahhoz, hogy "erős" pszeudorandom permutáció legyen (ami azt jelenti, hogy még egy olyan ellenfél számára is pszeudorandom marad, aki orákulum hozzáféréssel rendelkezik a fordított permutációhoz). Luby és Rackoff e nagyon fontos eredménye miatt a Feistel-kódokat néha Luby-Rackoff blokk-kódoknak is nevezik. További elméleti tanulmányok általánosították a konstrukciót, és pontosabb biztonsági határokat határoztak meg.

Építés

Legyen F {\displaystyle {\rm {F}}}} ${\rm F}$ a körfüggvény, és legyenek K 1 , K 2 , ... , K n {\displaystyle K_{1},K_{2},\ldots ,K_{n}}} $K_1,K_2,\ldots,K_{n}$ 1 , 2 , ... , n {\displaystyle 1,2,\ldots ,n}} $1,2,\ldots,n$ körökhöz tartozó alkulcsok.

Ezután az alapművelet a következő:

A tisztán szöveges blokkot két egyenlő darabra osztjuk ( L 1 {\displaystyle L_{1}} L_1 , R 1 {\displaystyle R_{1}} R_1 ).

Minden egyes i = 1 , 2 , ... , n fordulóban {\displaystyle i=1,2,\dots ,n} $i =1,2,\dots,n$ , számítsuk ki (kalkuláljuk)

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)$ .

Ekkor a rejtjelezett szöveg ( R n + 1 , L n + 1 ) {\displaystyle (R_{n+1},L_{n+1})} $(R_{n+1}, L_{n+1})$ . (Általában a két darab R n {\displaystyle R_{n}} R_n és L n {\displaystyle L_{n}} L_n nem cserélődik fel az utolsó kör után).

Egy rejtjelezett szöveg ( R n , L n ) {\displaystyle (R_{n},L_{n})} (R_n, L_n) visszafejtése úgy történik, hogy 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})$ .

Ekkor ( L 1 , R 1 ) {\displaystyle (L_{1},R_{1})} (L_1,R_1) ismét a nyílt szöveg.

E modell egyik előnye, hogy az F {\displaystyle {\rm {F}}} kerek függvénynek ${\rm F}$ nem kell invertálhatónak lennie, és nagyon összetett is lehet.

Az ábra a titkosítási folyamatot szemlélteti. A visszafejtéshez csak a K n , K n - 1 , ... , K 1 {\displaystyle K_{n},K_{n-1},\ldots ,K_{1}} $K_{n},K_{n-1},\ldots,K_1$ alkulcsok sorrendjét kell megfordítani ugyanezzel az eljárással; ez az egyetlen különbség a titkosítás és a visszafejtés között:

A kiegyensúlyozatlan Feistel-kódok egy módosított szerkezetet használnak, ahol L 1 {\displaystyle L_{1}} L_1 és R 1 {\displaystyle R_{1}} R_1 nem egyenlő hosszúságú. A MacGuffin rejtjelezés egy ilyen rejtjelezés kísérleti példája.

A Feistel-konstrukciót a blokkos kódoláson kívüli kriptográfiai algoritmusokban is használják. Például az Optimal Asymmetric Encryption Padding (OAEP) séma egy egyszerű Feistel-hálózatot használ a rejtjelszövegek véletlenszerűvé tételére bizonyos aszimmetrikus kulcsú titkosítási sémákban.

Feistel-hálózati művelet blokkos rejtjelezésen, ahol P az egyszerű szöveg és C a rejtjelezett szöveg.

A Feistel-kódok listája

Feistel vagy módosított Feistel: Blowfish, Camellia, CAST-128, DES, FEAL, ICE, KASUMI, LOKI97, Lucifer, MARS, MAGENTA, MISTY1, RC5, TEA, Triple DES, Twofish, XTEA, GOST 28147-89.

Általánosított Feistel: CAST-256, MacGuffin, RC2, RC6, Skipjack

Kérdések és válaszok

K: Mi az a Feistel-féle rejtjelezés?

V: A Feistel-féle rejtjelezés egy szimmetrikus struktúra, amelyet a blokkos rejtjelek építésénél használnak, és amelyet a német IBM kriptográfusáról, Horst Feistelről neveztek el. Általában Feistel-hálózatként is ismert.

K: Milyen előnyei vannak a Feistel-struktúra használatának?

V: A Feistel-struktúra használatának fő előnye, hogy a titkosítási és visszafejtési műveletek nagyon hasonlóak, sőt egyes esetekben azonosak, és csak a kulcsok ütemezésének felcserélését igénylik. Ez közel a felére csökkenti az ilyen rejtjelezés megvalósításához szükséges kód vagy áramkör méretét. Emellett az iteratív jelleg megkönnyíti a kriptorendszer hardveres megvalósítását.

K: Hogyan írja le Claude Shannon a "zavart és diffúziót"?

V: Claude Shannon a "zavar és diffúzió" fogalmát úgy írta le, hogy mindkét elem nagy mennyiségben van jelen, hogy a támadó számára megnehezítse a titkosított üzenet megfejtését.

K: Milyen technikákat használnak a zavar és a diffúzió létrehozására?

V: A zavart és a diffúziót bitkeveréssel (gyakran permutációs dobozoknak vagy P-dobozoknak nevezik) és egyszerű nemlineáris függvényekkel (gyakran helyettesítési dobozoknak vagy S-dobozoknak nevezik), valamint lineáris keveréssel (a moduláris algebra értelmében) az XOR segítségével hozzák létre. A bitkeverés a diffúziós hatást hozza létre, míg a helyettesítés a zavarás érdekében használatos.

K: Milyen típusú rejtjelező a Feistel-hálózat?

V: A Feistel-hálózat egy olyan típusú termékrejtjelező, amely az adatok biztonságos titkosítása érdekében több körös ismétlődő műveleteket kombinál.

K: Ki fejlesztette ki ezt a fajta rejtjelezést?

V: A Feistel-struktúrát a német IBM kriptográfusa, Horst Feistel fejlesztette ki.

K: A Data Encryption Standard ezen a típusú kriptográfián alapul?

V: Igen, a Data Encryption Standard ezt a fajta kriptográfiát használja, amely ugyanazokat a fentebb vázolt elveket használja a titkosított üzeneten belüli zavar és diffúzió létrehozására.