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-ti 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}}}} a körfüggvény, és legyenek K 1 , K 2 , ... , K n {\displaystyle K_{1},K_{2},\ldots ,K_{n}}}1 , 2 , ... , n {\displaystyle 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}} , R 1 {\displaystyle R_{1}} ).
Minden egyes i = 1 , 2 , ... , n fordulóban {\displaystyle i=1,2,\dots ,n} , számítsuk ki (kalkuláljuk)
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})} .
Ekkor a rejtjelezett szöveg ( R n + 1 , L n + 1 ) {\displaystyle (R_{n+1},L_{n+1})} . (Általában a két darab R n {\displaystyle R_{n}} és L n {\displaystyle 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})} visszafejtése úgy történik, hogy 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})} .
Ekkor ( L 1 , R 1 ) {\displaystyle (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 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}} 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}} és R 1 {\displaystyle 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.