Feistel hálózat

A Feistel hálózata vagy a Feistel terve ( angol. Feistel hálózat, Feistel titkosítás ) a blokk titkosítások létrehozásának egyik módszere . A hálózat Feistel cellákból áll . Minden cella bemenete adatokat és kulcsot kap. Az egyes cellák kimenetén a megváltozott adatok és a megváltozott kulcs fogadása történik. Minden cella azonos típusú, és azt mondják, hogy a hálózat egy bizonyos ismétlődő ( iterált ) struktúra. A kulcsot a titkosítási / visszafejtési algoritmustól függően választják ki, és az egyik cellából a másikba való áthelyezéskor megváltozik. A titkosítás és a visszafejtés ugyanazokat a műveleteket hajtja végre; csak a sorrend máskulcsok . A műveletek egyszerűsége miatt a Feistel hálózat szoftveresen és hardveresen is könnyen megvalósítható. Számos blokk titkosítás ( DES , RC2 , RC5 , RC6 , Blowfish , FEAL , CAST-128 , TEA , XTEA , XXTEA stb.) a Feistel hálózatot használja alapul. A Feistel hálózat alternatívája a permutációs-permutációs hálózat ( AES stb.).

Történelem

1971 -ben Horst Feistel szabadalmaztatott két különböző titkosítási algoritmusokat megvalósító eszközt, amelyeket később " Lucifer "-nek ( Eng. Lucifer ) neveztek el. Az egyik ilyen eszköz a később "Feistel-hálózatnak" ( angol Feistel cipher , Feistel network ) elnevezett kialakítást használt. Ezután Feistel Don Coppersmith -tel közösen új kriptorendszerek létrehozásán dolgozott az IBM falai között . A Lucifer-projekt meglehetősen kísérleti jellegű volt, de a DES algoritmus ( eng. d ata e ncryption s tandard ) alapja lett. 1973- ban a Scientific American magazin megjelentette Feistel "Cryptography and computer security" ( Eng. Cryptography and computer privacy ) [1] című cikkét, amely feltárta a titkosítás néhány fontos vonatkozását, és leírta a Lucifer - projekt első változatát. A Project Lucifer első verziója nem használta a Feistel hálózatot.

A Feistel hálózat alapján készült a DES algoritmus. 1977 -ben az Egyesült Államok hatóságai elfogadták a FIPS 46-3 szabványt , és a DES-t ismerték el az adattitkosítás szabványos módszereként. A DES-t már egy ideje széles körben használják kriptográfiai rendszerekben. Az algoritmus iteratív felépítése lehetővé tette egyszerű szoftveres és hardveres implementációk létrehozását.

Egyes adatok szerint [2] a Szovjetunióban már az 1970-es években a KGB kifejlesztett egy blokk-rejtjelet , amely a Feistel hálózatot használta, és valószínűleg ezt a titkosítást fogadták el 1990 -ben GOST 28147-89 néven .

1987 - ben kifejlesztették a FEAL és az RC2 algoritmusokat . A Feistel hálózatok az 1990 -es években terjedtek el – az olyan algoritmusok megjelenésének éveiben, mint a Blowfish (1993), TEA (1994), RC5 (1994), CAST-128 (1996), XTEA (1997), XXTEA (1998), RC6 (1998) és mások.

1997. január 2- án a NIST Institute versenyt hirdetett egy új adattitkosítási algoritmus létrehozására a DES helyettesítésére . Az új blokkrejtjelet AES -nek ( a fejlett e ncryption s tandard ) nevezték el, és 2002. május 26-án hagyták jóvá . Az AES helyettesítő-permutációs hálózatot használ a Feistel hálózat helyett .

Blokktitkos tervezés Feistel hálózatokon

Egyszerű leírás

Titkosítás

Legyen megkövetelhető néhány információ titkosítása , amely bináris formában jelenik meg ( nullák és egyesek sorozata formájában ), és amely egy számítógép vagy más eszköz memóriájában található (például egy fájlban ).

titkosítási algoritmus.

Az információ azonos (fix) hosszúságú blokkra van osztva. Az így kapott blokkokat inputnak nevezzük , mivel az algoritmus bemenetei. Ha a bemeneti blokk hossza kisebb, mint az a méret, amelyet a kiválasztott titkosító algoritmus egyszerre képes titkosítani (blokkméret), akkor a blokk valamilyen módon meghosszabbodik. A blokk hossza általában kettő hatványa , például 64 bit vagy 128 bit.

Továbbá figyelembe vesszük azokat a műveleteket is, amelyek csak egy blokkal fordulnak elő, mivel ugyanazokat a műveleteket más blokkokkal hajtják végre a titkosítási folyamat során.

A kiválasztott blokk két azonos méretű alblokkra van felosztva – „balra” ( ) és „jobbra” ( ). $L_0$ $R_{0}$
A "jobb oldali alblokkot" az F függvény módosítja a kerek gomb segítségével : $R_{0}$ $K_{0}$

x=F(R_{0},K_{0}).

Az eredmény hozzáadódik a modulo 2-höz ("xor") a "bal oldali alblokkkal" : $L_0$

x=x\oplus L_{0}.

Az eredményt a következő körben "jobboldali részblokkként" használjuk : $R_{1}$

R_{1}=x.

Az aktuális kör „jobb oldali alblokkja” (a kör elején változatlan formában) a következő körben „bal oldali alblokkként” lesz használva : $R_{0}$ $L_{1}$

L_{1}=R_{0}.

Egyes matematikai szabályok szerint egy kerek kulcs kerül kiszámításra - a következő körben használt kulcs. $K_1$

A felsorolt műveletek N-1 alkalommal kerülnek végrehajtásra, ahol N a kiválasztott titkosítási algoritmus köreinek száma . Ebben az esetben az egyik fordulóból (szakaszból) a másikba való átmenetek között a billentyűk megváltoznak: helyette , - a stb.). $K_{0}$ $K_1$ $K_1$ $K_{2}$

Dekódolás

Az információ visszafejtése ugyanúgy történik, mint a titkosítás, azzal az egyetlen kivétellel, hogy a kulcsok fordított sorrendben következnek, vagyis nem az elsőtől az N -ig, hanem az N- ediktől az elsőig .

Algoritmikus leírás

Az egyszerű szöveges blokk két egyenlő részre oszlik: . $(L_{0},\ R_{0})$
Minden kör a következőket számolja:

L_{i}\ =\ R_{{i-1}}\oplus f(L_{{i-1}},K_{{i-1}});

R_{i}\ =\ L_{{i-1}},

ahol:

i a kör száma ; $i=1\ldotsN;$
N a körök száma a kiválasztott titkosítási algoritmusban;
$f$ - valamilyen funkció;
$K_{{i-1}}$ — az i-1 . kör kulcsa (körkulcs).

A fordulók eredménye . Az N - edik körben a és permutáció nem kerül végrehajtásra, így ugyanazt az eljárást lehet használni a visszafejtéshez, egyszerűen a kulcsok használati sorrendjének megfordításával ( helyett ): $N$ $(L_{N},\ R_{N})$ $L_{N}$ $R_{N}$ $K_{N},K_{{N-1}},\ldots ,K_{0}$ $K_{0},K_{1},\ldots ,K_{N}$

L_{{i-1}}\ =\ R_{{i}}\oplus f(L_{{i}},\ K_{{i-1}})

R_{{i-1}}\ =\ L_{i}.

Egy kis változtatással elérhető a titkosítási és visszafejtési eljárások teljes azonossága.

Előnyök:

az algoritmus megfordíthatósága a használt f függvénytől függetlenül ;
tetszőlegesen összetett f függvény kiválasztásának képessége .

Matematikai leírás

Vegyünk egy példát. Legyen:

X a bemenetre belépő adatblokk (bemeneti blokk);
A - valamilyen involúciós transzformáció (vagy involúció ) - egy az egyhez transzformáció, amely önmagára nézve inverz [3] , vagyis minden ( ∀ ) X esetén igaz a kifejezés:

AAX=A^{2}X=X,\forall X;

Y a kimeneten kapott adatblokk (eredmény).

Az A transzformáció egyszeri alkalmazása az X bemeneti blokkra az Y kimeneti blokkot eredményezi :

Y=AX.

Ha az A transzformációt alkalmazza az előző - Y transzformáció eredményére, akkor a következőt kapja:

AY=AAX=X,\forall X.

Legyen az X bemeneti blokk két egyenlő hosszúságú L és R részblokkból :

X=(L, R).

Két transzformációt határozunk meg:

$G(X,K)$ - X adattitkosítás K kulccsal :

G(X,K)=G((L,R),K)=(L\oplus F(K,R),R);

$T(L,R)$ — az L és R részblokkok permutációja :

T(L,R)=(R,L).

Bemutatjuk a jelölést:

a G transzformáció egyetlen alkalmazása :

{\tilde {X}}=({\tilde {L)),{\tilde {R)))=GX;

kétszer alkalmazva a G transzformációt :

{\tilde {{\tilde {X}}}}=({\tilde {{\tilde {L}}}},{\tilde {{\tilde {R}}}})=G^{2}X .

Bizonyítsuk be a G ( ) kettős transzformáció involutivitását . $G^{2}$

Könnyen belátható, hogy a G transzformáció csak a bal L alblokkot változtatja meg , a jobb R változatlan marad:

{\tilde {L}}=L\oplus F(K,R);

{\tilde {R}}=R.

Ezért a következőkben csak az L részblokkot fogjuk figyelembe venni . Miután kétszer alkalmaztuk a G transzformációt L - re , a következőt kapjuk:

{\tilde {{\tilde {L))))={\tilde {L}}\oplus F(K,{\tilde {R)))={\tilde {L}}\oplus F(K,R )=L\oplus F(K,R)\oplus F(K,R)=L.

Ilyen módon:

G^{2}L=L;

G^{2}R=R,

Következésképpen

G^{2}X=X

és G involúció . _

Bizonyítsuk be a T ( ) kettős transzformáció involutivitását . $T^{2}$

T^{2}X=T^{2}(L,R)=T(R,L)=(L,R)=X.

Fontolja meg a titkosítási folyamatot. Legyen:

X a bemeneti érték;
$GI}$ — átalakítás a kulccsal ; $K_{i}$
$Y_{i}$ — kimeneti érték, az i - edik kör eredménye .

Ekkor az i+1 -edik körben végrehajtott transzformáció a következőképpen írható fel:

Y_{{i+1}}=TG_{i}Y_{i}

Az 1. fordulóban végrehajtott átalakítás:

Y_{1}=TG_{1}X.

Ezért a kimeneti érték m titkosítási kör után a következő lesz:

Y_{m}=TG_{m}Y_{{m-1}}=TG_{m}TG_{{m-1}}\lpontok TG_{1}X.

Látható, hogy az utolsó szakaszban nem szükséges T permutációt végrehajtani .

A visszafejtés az összes transzformáció fordított sorrendben történő alkalmazásával történik. Az egyes transzformációk involutivitása miatt a fordított sorrend adja az eredeti eredményt:

X=G_{1}TG_{2}T\lpontok G_{{m-1}}TG_{m}T(Y_{m})=G_{1}TG_{2}T\lpontok G_{{m-1 }}T(Y_{{m-1}})=\ldots =G_{1}T(Y_{1})=X.

A Feistel hálózatokban használt funkciók

Horst Feistel "Cryptography and Computer Security" [1] című munkájában az átalakítások (függvények ) két blokkját írja le: $f(L_{{i}},\ K_{{i}})$

helyettesítő blokk (s-box, eng. s-box );
permutációs blokk (p-box, eng. p-box ).

Megmutatható, hogy bármilyen bináris transzformáció egy fix hosszúságú adatblokkon keresztül megvalósítható s-boxként . A nagy N N bites s-blokk szerkezetének összetettsége miatt a gyakorlatban egyszerűbb konstrukciókat alkalmaznak.

Az eredeti cikkben [1] a "blokk" kifejezést használjuk a "funkció" kifejezés helyett, mivel blokk titkosításról beszélünk, és feltételezték, hogy az s- és p-blokkok digitális mikroáramkörök (digitális blokkok).

S-blokk

A helyettesítő blokk (s-box, angol s-box ) a következő részekből áll:

dekódoló - n bites bináris jel átalakítója egybites jellé bázisban ; $2^{n}$
kapcsolórendszer - belső csatlakozások (összes lehetséges csatlakozás ); $2^{n}!$
kódoló - jelátalakító egybites -árisról n bites binárisra. $2^{n}$

Egy n bites S-blokk elemzése nagy n esetén rendkívül nehéz, de nagyon nehéz egy ilyen blokkot a gyakorlatban megvalósítani, mivel a lehetséges kapcsolatok száma rendkívül nagy ( ). A gyakorlatban a helyettesítési blokkot összetettebb rendszerek részeként használják. $2^{n}$

Általános esetben egy s-blokk eltérő számú be-/kimenettel rendelkezhet, ebben az esetben a kapcsolórendszerben nem szigorúan egy kapcsolat mehet a dekóder minden kimenetéről, hanem 2 vagy több, vagy nem. összes. Ugyanez igaz a kódoló bemeneteire is.

Az elektronikában a jobb oldali diagram közvetlenül alkalmazható. A programozás során helyettesítő táblákat állítanak elő. Mindkét megközelítés egyenértékű, azaz a számítógépen titkosított fájl visszafejthető elektronikus eszközön és fordítva.

Csere táblázat a csökkentett 3 bites s-boxhoz

számú kombináció	0	egy	2	3	négy	5	6	7
Bejárat	000	001	010	011	100	101	110	111
Kijárat	011	000	001	100	110	111	010	101

P-blokk

A permutációs blokk (p-block, eng. p-box ) csak megváltoztatja a számok helyzetét, és egy lineáris eszköz. Ennek a blokknak nagyon sok be- és kimenete lehet, azonban a linearitás miatt a rendszer nem tekinthető kriptorezisztensnek.

Egy n bites p-blokk kulcsának kriptoanalízise n-1 különböző üzenet bemenetére való eljuttatásával történik, amelyek mindegyike n-1 nullából ("0") és 1 egyesből ("1") áll (vagy fordítva, egyesektől és nullától ).

Ciklikus váltás

Megmutatható, hogy a ciklikus eltolás a p-blokk speciális esete.

A legegyszerűbb esetben (1 bites eltolás) a szélső bitet leválasztjuk, és áthelyezzük a regiszter vagy busz másik végére. Attól függően, hogy melyik bitet veszik fel, jobbra vagy balra, az eltolást jobbra vagy balra hívják. A több bittel történő eltolás úgy is felfogható, hogy többszöri 1-gyel történik.

Forgatás m bittel n bites bemenethez ( m < n )

Irányváltás	Bitrendelés műszak előtt	Bitsorrend műszak után
Bal	$b_{0},b_{1},b_{2},...,b_{{n-1}}$	$b_{m},b_{{m+1}},...b_{{n-1}},b_{0},b_{1},...,b_{{m-1}}$
jobb	$b_{0},b_{1},b_{2},...,b_{{n-1}}$	$b_{{nm}},b_{{n-m+1}},...b_{{n-1}},b_{0},b_{1},...,b_{{nm-1 }}$

Kiegészítés modulo n

Az " add modulo n " műveletet a következőképpen jelöljük

( A + B ) mod n

és az A + B összeg n -nel való osztásának maradéka , ahol A és B számok.

Megmutatható, hogy két modulo n szám összeadása a bináris rendszerben s-blokkként van ábrázolva, amelyben az A szám a bemenetre kerül, és a kapcsolásként egy B bites ciklikus balra eltolást használunk. s-blokk rendszere.

A számítástechnikában és az elektronikában az összeadási műveletet általában modulo összeadásként valósítják meg , ahol m egy egész szám (általában m egyenlő a gép kapacitásával). Binárisba kerülni $n = 2^m$

A + B mod

2^{m}

elég összeadni a számokat, majd eldobni az m -től kezdődő számjegyeket és az idősebbeket.

Szorzás modulo n

A modulo n szorzást így jelöljük

( A * B ) mod n

és az A * B szorzat n -nel való osztásának maradéka , ahol A és B számok.

Az x86 platformon lévő személyi számítógépekben két m bites szám szorzásakor 2 * m kapacitású számot kapunk . Ahhoz, hogy a maradékot megkapja a -val való osztás után , el kell dobnia az m legjelentősebb bitet. $2^{m}$

Példa megvalósítás C nyelven

A Feistel hálózatot használó titkosítási algoritmus általános képe:

/* Egy részblokk transzformációját végrehajtó függvény, figyelembe véve a kulcs értékét (kulcsonként). A megvalósítás a kiválasztott blokk titkosítási algoritmustól függ. */ int f ( int alblokk , /* alblokk konvertálásához */ int kulcs /* gomb */ ); /* visszatérési érték - konvertált blokk */ /* Egyszerű szöveges titkosítást végrehajtó függvény */ üres kripta ( int * bal , /* bal beviteli alblokk */ int * jobb , /* jobb beviteli alblokk */ int rounds , /* körök száma */ int * kulcs /* billentyűtömb (körönként egy billentyű) */ ) { int i , temp ; for ( i = 0 ; i < kör ; i ++ ) { hőmérséklet = * jobb ^ f ( * bal , gomb [ i ] ); * jobb = * bal ; * bal = hőmérséklet ; } } /* Szöveg visszafejtését végző függvény */ érvénytelen visszafejtés ( int * balra , /* balra titkosított alblokk */ int * jobb , /* jobb oldali titkosított alblokk */ int rounds , /* körök száma */ int * kulcs /* billentyűtömb (körönként egy billentyű) */ ) { int i , temp ; for ( i = kör - 1 ; i >= 0 ; i -- ) { hőmérséklet = * bal ^ f ( * jobb , gomb [ i ] ); * bal = * jobb ; * jobb = hőmérséklet ; } }

Előnyök és hátrányok

Előnyök:

a hardveres megvalósítás egyszerűsége modern elektronikus bázison;
szoftveres implementáció egyszerűsége annak köszönhetően, hogy a funkciók jelentős része hardver szinten támogatott a modern számítógépeken (például modulo 2 összeadás ("xor") , modulo addíció, modulo szorzás stb.); $2^{n}$ $2^{n}$
Feistel hálózatokon alapuló algoritmusok jó ismerete [4] .

Hibák:

egy körben csak a bemeneti blokk fele titkosítva [5] .

Elméleti tanulmányok

A Feistel hálózatokat széles körben tanulmányozták a kriptográfusok széleskörű használatuk miatt. 1988- ban Michael Louby és Charles Rakoff kutatást végzett a Feistel hálózaton, és bebizonyította, hogy ha a körfüggvény kriptográfiailag erős pszeudo-véletlenszerű, és a használt kulcsok minden körben függetlenek, akkor 3 kör is elegendő lesz. hogy a blokk titkosítás pszeudo-véletlen permutáció legyen, míg négy kör elég lesz egy erős pszeudo-véletlen permutációhoz.

Lubi és Rakoff „ ál- véletlenszerű permutációja ” olyan, amely ellenáll az adaptív nyílt szöveges választási támadásnak, az „ erős pszeudo-véletlenszerű permutáció ” pedig egy pszeudo-véletlen permutáció, amely ellenáll a választott titkosított szöveges támadásnak.

A nyugati irodalomban néha a Feistel hálózatot "Luby-Rackoff blokk titkosításnak" nevezik Luby és Rackoff tiszteletére, akik nagy mennyiségű elméleti kutatást végeztek ezen a területen.

Később, 1997-ben Moni Naor és Omer Reingold javasolta a Lubi-Rakoff konstrukció egyszerűsített változatát, amely négy körből áll. Ez a változat két páronkénti független permutációt használ első és utolsó körként . A Naor-Reingold konstrukció két középső köre megegyezik a Lubi-Rakoff konstrukció köreivel [6] .

A legtöbb kutatás konkrét algoritmusok tanulmányozására irányul. A Feistel hálózaton alapuló számos blokk-titkosítóban találtak néhány sebezhetőséget, de egyes esetekben ezek pusztán elméleti jellegűek, és a számítógépek jelenlegi teljesítménye mellett a gyakorlatban lehetetlen feltörni őket.

A Feistel hálózat módosításai

Nagy méretű (128 bites vagy több) titkosítási blokkok esetén az ilyen Feistel-terv 32 bites architektúrákon való megvalósítása nehézségeket okozhat, ezért ennek a kialakításnak a módosított változatait használják. Általában négy ágú hálózatokat használnak. Az ábra a leggyakoribb módosításokat mutatja. Vannak olyan rendszerek is, amelyekben a felek és a hossza nem egyezik. Az ilyen hálózatokat kiegyensúlyozatlannak nevezzük . $L_0$ $R_{0}$

Feistel hálózati módosítások
1. típus
2. típus
3. típus

IDEA algoritmus

Forrás [7] :

Az IDEA algoritmus teljes körének egy iterációjának sémája

Az IDEA algoritmus egy mélyen módosított Feistel hálózatot használ. Ebben a 64 bites bemeneti adatblokkok (jelölése ) 4, 16 bites alblokkra vannak osztva . Mindegyik szakasz 6 darab 16 bites kulcsot használ. Összesen 8 fő szakaszt és 1 rövidített szakaszt használnak. $X_{0}$ $X_{0}=\{X^{{(0)}}X^{{(1)}}X^{{(2)}}X^{{(3)}}\}$

Képletek a részblokkok értékének kiszámításához az i - edik körben (1-8. körhöz):

előzetes számítások:

A_{{i}}=((X_{{i-1}}^{{(0)}}*K_{{i}}^{{(1)}})\oplus (X_{{i-1 }}^{{(2)}}+K_{{i}}^{{(3)}}))*K_{{i}}^{{(5)}};

B_{{i}}=(((X_{{i-1}}^{{(1)}}+K_{{i}}^{{(2)}})\oplus (X_{{i- 1}}^{{(3)}}*K_{{i}}^{{(4)}})+A_{{i}})*K_{{i}}^{{(6)}} );

C_{{i}}=((X_{{i-1}}^{{(1)}}+K_{{i}}^{{(2)}})\oplus (X_{{i-1 }}^{{(3)}}*K_{{i}}^{{(4)}})+((X_{{i-1}}^{{(0)}}*K_{{i }}^{{(1)}})\oplus (X_{{i-1}}^{{(2)}}+K_{{i}}^{{(3)}}))*K_{ {i}}^{{(5)}})*K_{{i}}^{{(6)}};

végső számítások:

X_{{i}}^{{(0)}}\ =\ (X_{{i-1}}^{{(0)}}*K_{{i}}^{{(1)}}) \oplus B_{{i}};

X_{{i}}^{{(1)}}\ =\ (X_{{i-1}}^{{(2)}}+K_{{i}}^{{(3)}}) \oplus B_{{i}};

X_{{i}}^{{(2)}}\ =\ (X_{{i-1}}^{{(1)}}+K_{{i}}^{{(2)}}) \oplus (A_{{i}}+C_{{i}});

X_{{i}}^{{(3)}}\ =\ (X_{{i-1}}^{{(3)}}*K_{{i}}^{{(4)}}) \oplus (A_{{i}}+C_{{i}}),

hol van a j -edik billentyű az i -edik körön. $K_{{i}}^{{(j)}}$

A 9. forduló kiszámításának képlete:

X_{{9}}^{{(0)}}\ =\ X_{{8}}^{{(0)}}*K_{{9}}^{{(1)}};

X_{{9}}^{{(1)}}\ =\ X_{{8}}^{{(2)}}+K_{{9}}^{{(2)}};

X_{{9}}^{{(2)}}\ =\ X_{{8}}^{{(1)}}+K_{{9}}^{{(3)}};

X_{{9}}^{{(3)}}\ =\ X_{{8}}^{{(3)}}*K_{{9}}^{{(4)}}.

A függvény kimenete az lesz

Y=\{X_{{9}}^{{(0)}}X_{{9}}^{{(1)}}X_{{9}}^{{(2)}}X_{{9 }}^{{(3)}}\}.

Látható, hogy az s- és p-blokkokat nem tiszta formában használják. A fő műveletek a következők:

modulo szorzás ; $2^{{16}}+1=65537$
modulo kiegészítés . $2^{{16}}=65536$

A Feistel hálózaton alapuló titkosítások

Lucifer

Történelmileg az első Feistel-hálózatot használó algoritmus a „ Lucifer ” algoritmus volt, a munka során, amelyen Feistel ténylegesen kidolgozta a struktúrát, amely később „Feistel-hálózat” néven vált ismertté. 1971 júniusában a Feistel megkapta a 3798359. számú amerikai szabadalmat [8] .

A " Lucifer " első verziója 48 bites blokkokat és kulcsokat használt, és nem a "Feistel hálózat" kialakítását. Az algoritmus egy későbbi módosítását John L. Smith nevére szabadalmaztatták 1971 novemberében (3 796 830 amerikai egyesült államokbeli szabadalom; 1971. november) [ 9 ] , és a szabadalom magában foglalja a Feistel hálózat leírását és egy speciális titkosítási funkciót is. 64 bites kulcsokat és 32 bites blokkokat használt. Végül pedig a legújabb verziót 1973-ban javasolták, és 128 bites blokkokkal és kulcsokkal működött. A "Lucifer" algoritmus legteljesebb leírását Arthur Sorkin ( eng. Arthur Sorkin ) "Lucifer. Cryptographic Algorithm" ("Lucifer, A Cryptographic Algorithm") a "Cryptology" ("Cryptologia") folyóiratban 1984 januárjában [10] .

Bár a "Lucifer" eredeti módosítása nélkülözte a "Feistel-sejteket", jól mutatja, hogy csak az s- és p-dobozok használata nagymértékben torzíthatja az eredeti szöveget. Az 1971. júniusi minta „Lucifer” algoritmusának felépítése kétféle réteg „szendvicse” egymás után – az úgynevezett SP-hálózatok (vagy helyettesítési-permutációs hálózatok). Az első rétegtípus egy 128 bites p-blokk, amelyet egy második réteg követ, amely 32 modulból áll, amelyek mindegyike két négybites s-blokkból áll , amelyek megfelelő bemenetei rövidre vannak zárva, és ugyanazt az értéket táplálják azokat az előző réteg kimenetéből . De maguk a helyettesítési blokkok különböznek egymástól (a helyettesítési táblázatokban különböznek). A modul kimenete csak az egyik s-boxból kap értékeket, melyeket konkrétan a kulcs egyik bitje határozza meg, aminek a száma megegyezett a szerkezetben lévő s-box számával. Az algoritmus egyszerűsített diagramja kisebb bitmélységgel és nem teljes körszámmal az ábrán látható. 16 s-box szelektort használ (összesen 32 s-boxot), tehát ez a séma 16 bites kulcsot használ.

Vizsgáljuk meg most, hogyan változik a rejtjelezett szöveg a fenti algoritmusban, ha csak egy bit változik. Az egyszerűség kedvéért az s-blokk cseréinek táblázatait vesszük úgy, hogy ha az összes nullát betápláljuk egy s-blokk bemenetére, akkor az összes nulla is megjelenik. Az általunk választott s-blokkok alapján, ha minden nulla a titkosító eszköz bemenetére kerül, akkor az eszköz kimenete csupa nulla lesz. Valós rendszerekben nem használnak ilyen helyettesítési táblákat, mivel nagymértékben leegyszerűsítik a kriptoanalitikus munkáját, de példánkban jól szemléltetik az erős karakterek közötti kapcsolatot a titkosított üzenet egy bitjének megváltoztatásakor. Látható, hogy az első p-blokk miatt az egyetlen egység a blokk közepére kerül, majd a következő nemlineáris s-blokk "megsokszorozza", és már két egység megváltoztatja pozícióját a következő p miatt. -blokk, stb. A titkosító eszköz végén az erős szimbólumok közötti csatolás miatt a kimeneti bitek a bemenet és a használt kulcs komplex funkcióivá váltak. Átlagosan a bitek fele "0" és fele "1" lesz a kimenetben.

Lényegében a Feistel hálózat alternatívája az összetett SP-hálózatoknak, és sokkal szélesebb körben használják. Elméleti szempontból a kerek titkosítási funkció SP hálózatra redukálható, de a Feistel hálózat praktikusabb, mivel a titkosítást és a visszafejtést ugyanaz az eszköz végezheti, de a használt kulcsok fordított sorrendjében. Az algoritmus második és harmadik verziója (a Feistel hálózatot használva) 32 bites blokkon működött 64 bites kulccsal és 128 bites blokkokkal 128 bites kulccsal. A legújabb (harmadik) verzióban a kerek titkosítási funkciót nagyon egyszerűen rendezték el - először a titkosított alblokkot egy 4 bites s-blokk rétegen vezették át (hasonlóan az SP hálózatok rétegeihez, csak az s-blokk állandó és nem függ a kulcstól), majd a modulo 2-hez egy kerek kulcsot adtak hozzá, ami után az eredmény átkerült a p-blokkon.

DES

Funkció (ahol: $f(L_{i},K_{i})$

$L_i$ — 32 bites bemeneti blokk az i - edik iterációnál;
$K_{i}$ - 48 bites kulcs ennél az iterációnál)

A DES algoritmus a következő műveletekből áll:

az L bemeneti blokk kiterjesztése 48 bitre (néhány bemeneti bit megismétlődhet);
Modulo 2 kiegészítés kulccsal : $K_{i}$

{\tilde {L_{i}}}=L_{i}\oplus K_{i};

az eredményt 8, egyenként 6 bites blokkra osztva:

{\tilde {L_{i))}=\{{\tilde {L_{i))}^{{(0)}}{\tilde {L_{i))}^{{(1))){ \tilde {L_{i}}}^{{(2)}}{\tilde {L_{i}}}^{{(3))){\tilde {L_{i}}}^{{(4 )}}{\tilde {L_{i}}}^{{(5)}}{\tilde {L_{i}}}^{{(6))){\tilde {L_{i}}}^ {{(7)}}\};

a vett információblokkokat 6 bites bemenettel és 4 bites kimenettel rendelkező helyettesítő blokkokhoz táplálják ; ${\tilde {L_{i}^{{(j)))))$
a kimeneten a 4 bites blokkokat 32 bites blokkká egyesítik, ami a függvény eredménye . $f(L_{i},K_{i})$

A DES algoritmusban a körök száma összesen 16.

"Magma"

A függvény (ahol és 32 bites számok) a következőképpen kerül kiszámításra: $f(L_{i},K_{i})$ $L_i$ $K_{i}$

add össze a modult : $L_i$ $K_{i}$ $2^{32}$

{\tilde {L_{i))}=(L_{i}+K_{i})\ {\bmod \ }2^{{32}};

az eredményt 8 darab 4 bites blokkra osztjuk, amelyeket 4 bites s-blokkokba táplálunk (amelyek eltérőek lehetnek);
az s-boxok kimeneteit egy 32 bites számmá egyesítik, amelyet ezután 11 bittel balra forgatnak;
az eredmény a függvény kimenete.

A GOST 28147-89 algoritmusban a fordulók száma 32.

Algoritmusok összehasonlító listája

A következő blokk titkosítások a klasszikus vagy módosított Feistel hálózatot használják alapként.

Algoritmus	Év	A körök száma	Kulcs hossza	Blokkméret	Alblokkok száma
blowfish	1993	16	32-től 448-ig	64	2
Kamélia	2000	18/24	128/192/256	128	2
CAST-128	1996	12/16	40-128	64	2
CAST-256	1998	12×4=48	128/192/256	128	2
CIPHERUNICORN-A	2000	16	128/192/256	128	2
CIPHERUNICORN-E	1998	16	128	64	2
CLEFIA	2007	16	128/192/256	128	16
ÜZLET	1998	6 (8)	(128/192) 256	128	2
DES	1977	16	56	64	2
DFC	1998	nyolc	128/192/256	128	?
FEAL	1987	4-32	64	64	2
GOST 28147-89	1989 [2]	32/16	256	64	2
ÖTLET	1991	8+1	128	64	négy
KASUMI	1999	nyolc	128	64	2
Khufu	1990	16-32/64	512	64	2
LOKI97	1997	16	128/192/256	128	2
Lucifer	1971	16	48/64/128	48/32/128	2
MacGuffin	1994	32	128	64	négy
BÍBORVÖRÖS	1998	6/8	128/192/256	128	2
MARS	1998	32	128-1248	128	2
Kegyelem	2000	6	128	4096	?
MISTY1	1995	4×n(8)	128	64	négy
Raiden	2006	16	128	64	2
RC2	1987	16+2	8-128	64	négy
RC5	1994	1-255 (12)	0-2040 (128)	32/64/128	2
RC6	1998	húsz	128/192/256	128	négy
RTEA	2007	48/64	128/256	64	2
MAG	1998	16	128	128	2
Sinopoli	2003	64	128	128	négy
skipjack	1998	32	80	64	négy
TEA	1994	64	128	64	2
Tripla DES	1978	32/48	112/168	64	2
Kéthal	1998	16	128/192/256	128	négy
XTEA	1997	64	128	64	2
XTEA-3	1999	64	256	128	négy
XXTEA	1998	12-64	128	64	2

Jegyzetek

↑ 1 2 3 Horst Feistel "Cryptography and computer privacy" (angolul) ("Cryptography and computer security"). Fordítás archiválva : 2018. március 11. a Wayback Machine -nél, Andrej Vinokurov.
↑ 1 2 Vinokurov A. Cikk archiválva 2022. április 1-én a Wayback Machine -nél „GOST 28147-89 titkosítási algoritmus, annak használata és megvalósítása Intel x86 platformszámítógépekhez ”. A cikkben szereplő anyagok egy része a „Monitor” magazin „# 1.5 / 1995” számában jelent meg.
↑ Diszkrét matematika. Algoritmusok. Szimmetrikus rendszerek és blokk titkosítások (elérhetetlen link) . Letöltve: 2008. november 21. Az eredetiből archiválva : 2012. december 5.. (határozatlan)
↑ Szergej Panasenko. " Modern titkosítási algoritmusok archiválva 2010. január 31-én a Wayback Machine -nél " // Byte Magazine. 8. szám (60), 2003. augusztus.
↑ Baricsev, Goncsarov, Szerov, 2011 .
↑ A pszeudo-véletlen permutáció felépítéséről: Luby-Rackoff újra megvizsgálta.
↑ Menezes, Oorschot, Vanstone, 1996 , 7.6 IDEA, pp. 263.
↑ 3 798 359 számú amerikai egyesült államokbeli szabadalom
↑ 3 796 830 számú amerikai egyesült államokbeli szabadalom
↑ Arthur Sorkin. Lucifer, A kriptográfiai algoritmus. Cryptologia, 8. szám (1), 1984. január, 22-41., kiegészítve a 8. szám (3) 260-261.

Irodalom

Barichev S. G. , Goncharov V. V. , Serov R. E. A modern kriptográfia alapjai - 3. kiadás. — M .: Dialógus-MEPhI , 2011. — 176 p. — ISBN 978-5-9912-0182-7
Menezes A. J. , Oorschot P. v. , Vanstone S. A. Handbook of Applied Cryptography (angol) - CRC Press , 1996. - 816 p. — ( Diszkrét matematika és alkalmazásai ) — ISBN 978-0-8493-8523-0

Szimmetrikus titkosítási rendszerek
Rejtjelfolyam adatfolyam	A3 A5 A8 Decim F-FCSR Gabona HC-256 KCipher-2 MICKEY MUGI CSUKA Phelix RC4 Nyúl FÓKA HÓ SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Feistel hálózat	GOST 28147-89 (Magma) blowfish Kamélia CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra ÜZLET DES DESX DFC E2 EnRUPT FEAL HPC ÖTLET KASUMI Khafre Khufu LOKI97 MacGuffin MARS HÁLÓ MISTY1 NewDES NDS RC5 RC6 MAG Simon Sinopoli skipjack SM4 Folt TEA XTEA XXTEA Raiden RTEA Tripla DES Kéthal
SP hálózat	Szöcske 3 út ABC ÁRIA AES (Rijndael) Akelarre Anubis BaseKing Bass Omatic Öv CRYPTON Gyémánt2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer jelenlegi Szivárvány BIZTONSÁGOSBAN CÁPA NÉGYZET Kígyó háromhal
Egyéb	BÉKA NUSH REDOC SC2000 SHACAL CS-Cipher