Síť Feistel

Feistelova síť neboli Feistelův návrh ( angl. Feistel network, Feistel cipher ), je jednou z metod konstrukce blokových šifer . Síť je tvořena buňkami nazývanými Feistelovy buňky . Vstup každé buňky přijímá data a klíč. Na výstupu každé buňky jsou přijata změněná data a změněný klíč. Všechny buňky jsou stejného typu a říkají, že síť je určitá opakovaně opakovaná ( iterovaná ) struktura. Klíč se vybírá v závislosti na šifrovacím / dešifrovacím algoritmu a mění se při přechodu z jedné buňky do druhé. Šifrování a dešifrování provádějí stejné operace; liší se pouze pořadí kláves . Díky jednoduchosti ovládání je síť Feistel snadno softwarově i hardwarově implementovatelná. Řada blokových šifer ( DES , RC2 , RC5 , RC6 , Blowfish , FEAL , CAST-128 , TEA , XTEA , XXTEA atd.) využívá jako základ síť Feistel. Alternativou k síti Feistel je permutačně-permutační síť ( AES atd.).

Historie

V roce 1971 si Horst Feistel patentoval dvě zařízení, která implementovala různé šifrovací algoritmy , později nazvané „ Lucifer “ ( eng. Lucifer ). Jedno z těchto zařízení používalo konstrukci později nazvanou „Feistelova síť“ ( anglicky Feistelova šifra , Feistelova síť ). Poté Feistel pracoval na vytvoření nových kryptosystémů ve zdech IBM spolu s Donem Coppersmithem . Projekt Lucifer byl spíše experimentální, ale stal se základem pro algoritmus DES ( angl. d ata e ncryption s standard ). V roce 1973 časopis Scientific American publikoval Feistelův článek „Cryptography and computer security“ ( Eng. Cryptography and computer privacy ) [1] , který odhalil některé důležité aspekty šifrování a popsal první verzi projektu Lucifer . První verze projektu Lucifer nepoužívala síť Feistel.

Na základě sítě Feistel byl navržen algoritmus DES. V roce 1977 americké úřady přijaly standard FIPS 46-3 , který uznal DES jako standardní metodu pro šifrování dat. DES je již nějakou dobu široce používán v kryptografických systémech. Iterativní struktura algoritmu umožnila vytvářet jednoduché softwarové i hardwarové implementace.

Podle některých údajů [2] v SSSR již v 70. letech KGB vyvinula blokovou šifru , která používala Feistelovu síť, a pravděpodobně to byla právě tato šifra , která byla v roce 1990 přijata jako GOST 28147-89 .

V roce 1987 byly vyvinuty algoritmy FEAL a RC2 . Sítě Feistel se rozšířily v 90. letech - během let vzniku takových algoritmů jako Blowfish (1993), TEA (1994), RC5 (1994), CAST-128 (1996), XTEA (1997), XXTEA (1998), RC6 (1998) a další.

2. ledna 1997 vyhlásil institut NIST soutěž na vytvoření nového algoritmu šifrování dat, který nahradí DES . Nová bloková šifra dostala název AES ( standard pokročilého šifrování ) a byla schválena 26. května 2002 . AES používá substituční permutační síť namísto Feistelovy sítě .

Návrh blokové šifry založený na sítích Feistel

Jednoduchý popis

Šifrování

Nechť je požadováno šifrování některých informací prezentovaných v binární podobě (ve formě sekvence nul a jedniček ) a umístěných v paměti počítače nebo jiného zařízení (například v souboru ).

šifrovací algoritmus.

Informace jsou rozděleny do bloků stejné (pevné) délky. Výsledné bloky se nazývají vstup , protože jsou vstupem do algoritmu. Pokud je délka vstupního bloku menší než velikost, kterou je vybraný šifrovací algoritmus schopen najednou zašifrovat (velikost bloku), pak se blok nějakým způsobem prodlouží. Typicky je délka bloku mocnina dvou, například 64 bitů nebo 128 bitů.

Dále budeme uvažovat operace, které se vyskytují pouze s jedním blokem, protože stejné operace se provádějí s jinými bloky během procesu šifrování.

Vybraný blok je rozdělen na dva podbloky stejné velikosti — „levý“ ( ) a „pravý“ ( ). $L_0$ $R_{0}$
"Pravý podblok" je upraven funkcí F pomocí kulaté klávesy : $R_{0}$ $K_{0}$

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

Výsledkem je přidání modulo 2 ("xor") s "levým podblokem" : $L_0$

x=x\oplus L_{0}.

Výsledek bude použit v dalším kole jako „pravý podblok“ : $R_{1}$

R_{1}=x.

„Pravý dílčí blok“ aktuálního kola (v jeho nezměněné podobě na začátku kola) bude v dalším kole použit jako „levý dílčí blok“ : $R_{0}$ $L_{1}$

L_{1}=R_{0}.

Podle nějakého matematického pravidla se vypočítá kulatý klíč – klíč, který bude použit v dalším kole. $K_1$

Uvedené operace jsou provedeny N-1 krát, kde N je počet kol ve zvoleném šifrovacím algoritmu. V tomto případě se mezi přechody z jednoho kola (stage) do druhého mění klávesy: je nahrazeno , - , atd.). $K_{0}$ $K_1$ $K_1$ $K_{2}$

Dešifrování

Dešifrování informací probíhá stejným způsobem jako šifrování, s jedinou výjimkou, že klíče následují v obráceném pořadí, tedy nikoli od prvního k N -tému , ale od N -tého k prvnímu.

Algoritmický popis

Blok otevřeného textu je rozdělen na dvě stejné části: . $(L_{0},\ R_{0})$
Každé kolo počítá:

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

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

kde:

i je číslo kola ; $i=1\ldotsN;$
N je počet kol ve vybraném šifrovacím algoritmu;
$F$ - nějaká funkce;
$K_{{i-1}}$ — klíč i-1 . kola (kulatý klíč).

Výsledek kol je . V N - tém kole se permutace a neprovádí, takže je možné použít stejný postup pro dešifrování, jednoduše obrácením pořadí použití klíčů ( místo ): $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}.

S malou změnou je možné dosáhnout úplné identity šifrovacích a dešifrovacích procedur.

výhody:

vratnost algoritmu bez ohledu na použitou funkci f ;
schopnost volit libovolně složitou funkci f .

Matematický popis

Zvažte příklad. Nechat:

X je blok dat vstupujících na vstup (vstupní blok);
A - nějaká involutivní transformace (nebo involuce ) - transformace jedna ku jedné, která je inverzní sama k sobě [3] , to znamená, že pro každé ( ∀ ) X platí výraz:

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

Y je blok dat přijatých na výstupu (výsledek).

Jednorázové použití transformace A na vstupní blok X bude mít za následek výstupní blok Y :

Y=AX.

Když aplikujete transformaci A na výsledek předchozí transformace - Y , získáte:

AY=AAX=X,\forall X.

Vstupní blok X nechť sestává ze dvou podbloků L a R stejné délky:

X = (L, R).

Definujeme dvě transformace:

$G(X,K)$ - šifrování dat X pomocí klíče K :

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

$T(L,R)$ — permutace podbloků L a R :

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

Představme si notaci:

jediná aplikace transformace G :

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

dvakrát použít transformaci G :

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

Dokažme involutivitu dvojí transformace G ( ). $G^{2}$

Je snadné vidět, že transformace G změní pouze levý podblok L a pravý R ponechá beze změny:

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

{\tilde {R}}=R.

Proto v následujícím budeme uvažovat pouze podblok L . Po dvojnásobném použití transformace G na L dostaneme:

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

Takto:

G^{2}L=L;

G^{2}R=R,

tudíž

G^{2}X=X

a G je involuce .

Dokažme involutivitu dvojí transformace T ( ). $T^{2}$

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

Zvažte proces šifrování. Nechat:

X je vstupní hodnota;
$G_{i}$ — transformace pomocí klíče ; $K_{i}$
$Y_{i}$ — výstupní hodnota, výsledek i - tého kola .

Pak lze transformaci provedenou v i+1 -tém kole zapsat jako:

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

Transformace provedená v 1. kole:

Y_{1}=TG_{1}X.

Proto výstupní hodnota po m šifrovacích kolech bude:

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

Je vidět, že v poslední fázi není nutné provádět permutaci T .

Dešifrování se provádí aplikací všech transformací v opačném pořadí. Vzhledem k involutivity každé z transformací dává obrácené pořadí původní výsledek:

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

Funkce používané v sítích Feistel

Horst Feistel ve své práci „Cryptography and Computer Security“ [1] popisuje dva bloky transformací (funkcí ): $f(L_{{i}},\ K_{{i}})$

substituční blok (s-box, angl. s-box );
permutační blok (p-box, angl. p-box ).

Lze ukázat, že jakákoli binární transformace přes datový blok pevné délky může být implementována jako s-box . Vzhledem ke složitosti struktury N -bitového s-bloku pro velké N se v praxi používají jednodušší konstrukce.

Pojem "blok" v původním článku [1] je použit místo pojmu "funkce" z důvodu, že mluvíme o blokové šifře a předpokládalo se, že s- a p-bloky budou digitální mikroobvody (digitální bloky).

S-blok

Náhradní blok (s-box, angl. s-box ) se skládá z následujících částí:

dekodér - převodník n - bitového binárního signálu na jednobitový signál v bázi ; $2^{n}$
systém spínačů - vnitřní připojení (celkový počet možných připojení ); $2^{n}!$
kodér - převodník signálu z jednobitové -ary na n bitovou binární. $2^{n}$

Analýza n -bitového S-bloku pro velké n je extrémně obtížná, ale je velmi obtížné implementovat takový blok v praxi, protože počet možných spojení je extrémně velký ( ). V praxi se substituční blok používá jako součást složitějších systémů. $2^{n}$

V obecném případě může mít s-blok různý počet vstupů/výstupů; v tomto případě v přepínacím systému nemůže jít striktně jedno připojení z každého výstupu dekodéru, ale 2 nebo více, nebo nejde Všechno. Totéž platí pro vstupy kodéru.

V elektronice lze přímo použít schéma vpravo. Při programování se generují náhradní tabulky. Oba tyto přístupy jsou ekvivalentní, tj. soubor zašifrovaný na počítači lze dešifrovat na elektronickém zařízení a naopak.

Náhradní tabulka pro zmenšený 3bitový s-box

Kombinace č.	0	jeden	2	3	čtyři	5	6	7
Vchod	000	001	010	011	100	101	110	111
Výstup	011	000	001	100	110	111	010	101

P-blok

Permutační blok (p-blok, angl. p-box ) pouze mění polohu čísel a je lineárním zařízením. Tento blok může mít velmi velké množství vstupů a výstupů, nicméně vzhledem k linearitě nelze systém považovat za kryptoodolný.

Kryptoanalýza klíče pro n -bitový p-blok se provádí dodáním n-1 různých zpráv na vstup, z nichž každá se skládá z n-1 nul ("0") a 1 jedniček ("1") (nebo naopak od jedniček a nuly).

Cyklický posun

Lze ukázat, že cyklický posun je speciální případ p-bloku.

V nejjednodušším případě (posun o 1 bit) se krajní bit oddělí a přesune na druhý konec registru nebo sběrnice. V závislosti na tom, který bit se bere, doprava nebo doleva, se posun nazývá doprava nebo doleva. Posuny o více bitů lze považovat za použití posunu o 1 vícekrát.

Otočit o m bitů pro n -bitový vstup ( m < n )

Směr posunu	Pořadí bitů před směnou	Pořadí bitů po směně
Vlevo, odjet	$b_{0},b_{1},b_{2},...,b_{{n-1}}$	$b_{m},b_{{m+1}},...b_{{n-1}},b_{0},b_{1},...,b_{{m-1}}$
že jo	$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 }}$

Přídavek modulo n

Operace " sčítání modulo n " je označena jako

( A + B ) mod n

a je zbytek po dělení součtu A + B n , kde A a B jsou čísla.

Lze ukázat, že sčítání dvou čísel modulo n je v binární soustavě reprezentováno jako s-blok, ve kterém je na vstup přivedeno číslo A a jako přepínání se používá cyklický posun doleva o B bitů. systém s-bloku.

Ve výpočetní technice a elektronice se operace sčítání zpravidla realizuje jako sčítání modulo , kde m je celé číslo (obvykle m je rovno kapacitě stroje). Chcete-li se dostat do binárního kódu $n = 2^m$

A + B mod

2^{m}

stačí sečíst čísla a pak číslice od m - té a starší vyhodit.

Násobení modulo n

Násobení modulo n je označeno jako

( A * B ) mod n

a je zbytek po dělení součinu A * B n , kde A a B jsou čísla.

V osobních počítačích na platformě x86 se při vynásobení dvou m -bitových čísel získá číslo s kapacitou 2 * m . Chcete-li získat zbytek po dělení , musíte zahodit m nejvýznamnějších bitů. $2^{m}$

Příklad implementace v jazyce C

Celkový pohled na šifrovací algoritmus pomocí sítě Feistel:

/* Funkce, která provádí transformaci podbloku s přihlédnutím k hodnotě klíče (podle klíče). Implementace závisí na zvoleném algoritmu blokové šifry. */ int f ( int podblok , /* podblok pro převod */ klíč int /* klíč */ ); /* návratová hodnota - převedený blok */ /* Funkce, která provádí šifrování prostého textu */ prázdná krypta ( int * left , /* left input subblok */ int * vpravo , /* pravý vstupní podblok */ int rounds , /* počet kol */ int * klíč /* pole klíčů (jeden klíč na kolo) */ ) { int i , teplota ; pro ( i = 0 ; i < zaokrouhlí ; i ++ ) { temp = * vpravo ^ f ( * vlevo , klávesa [ i ] ); * vpravo = * vlevo ; * vlevo = teplota ; } } /* Funkce, která provádí dešifrování textu */ void dešifrovat ( int * vlevo , /* vlevo zašifrovaný podblok */ int * right , /* right zašifrovaný podblok */ int rounds , /* počet kol */ int * klíč /* pole klíčů (jeden klíč na kolo) */ ) { int i , teplota ; pro ( i = kola - 1 ; i >= 0 ; i -- ) { temp = * left ^ f ( * right , key [ i ] ); * vlevo = * vpravo ; * vpravo = teplota ; } }

Výhody a nevýhody

výhody:

jednoduchost hardwarové implementace na moderní elektronické bázi;
snadnost softwarové implementace díky skutečnosti, že značná část funkcí je v moderních počítačích podporována na hardwarové úrovni (například sčítání modulo 2 („xor“) , sčítání modulo, násobení modulo atd.); $2^{n}$ $2^{n}$
dobrá znalost algoritmů založených na Feistelových sítích [4] .

nedostatky:

v jednom kole je zašifrována pouze polovina vstupního bloku [5] .

Teoretické studie

Sítě Feistel byly široce studovány kryptografy kvůli jejich širokému použití. V roce 1988 provedli Michael Louby a Charles Rakoff výzkum na síti Feistel a dokázali, že pokud je kruhová funkce kryptograficky silná pseudonáhodná a použité klíče jsou v každém kole nezávislé, budou stačit 3 kola. aby bloková šifra byla pseudonáhodnou permutací, zatímco čtyři kola budou stačit k vytvoření silné pseudonáhodné permutace.

" Pseudonáhodná permutace " od Lubiho a Rakoffa je ta, která je odolná vůči adaptivnímu útoku s volbou otevřeného textu, a " silná pseudonáhodná permutace " je pseudonáhodná permutace, která je odolná vůči zvolenému útoku šifrovaného textu.

Někdy se v západní literatuře Feistelova síť nazývá „Luby-Rackoffova bloková šifra“ na počest Lubyho a Rackoffa, kteří v této oblasti provedli velké množství teoretických výzkumů.

Později, v roce 1997, Moni Naor a Omer Reingold navrhli zjednodušenou verzi konstrukce Lubi-Rakoff, sestávající ze čtyř nábojů. Tato varianta používá dvě párové nezávislé permutace jako první a poslední kolo . Dva střední náboje konstrukce Naor-Reingold jsou totožné s náboji v konstrukci Lubi-Rakoff [6] .

Většina výzkumu je věnována studiu konkrétních algoritmů. Některé zranitelnosti byly nalezeny v mnoha blokových šifrách založených na síti Feistel, ale v některých případech jsou tyto zranitelnosti čistě teoretické a při současném výkonu počítačů je prakticky nelze použít k prolomení.

Úpravy sítě Feistel

Při velké velikosti šifrovacích bloků (128 bitů nebo více) může implementace takového návrhu Feistel na 32bitových architekturách způsobit potíže, proto se používají upravené verze tohoto návrhu. Běžně se používají sítě se čtyřmi větvemi. Obrázek ukazuje nejběžnější úpravy. Existují také schémata, ve kterých se délky polovin a neshodují. Takové sítě se nazývají nevyvážené . $L_0$ $R_{0}$

Úpravy sítě Feistel
Typ 1
Typ 2
Typ 3

Algoritmus IDEA

Zdroj [7] :

Schéma jedné iterace celého kola algoritmu IDEA

Algoritmus IDEA využívá hluboce upravenou síť Feistel. V něm jsou 64bitové vstupní datové bloky (označené ) rozděleny do 4 podbloků o délce 16 bitů . Každá fáze používá 6 16bitových klíčů. Celkem je použito 8 hlavních stupňů a 1 zkrácený. $X_{0}$ $X_{0}=\{X^{{(0)}}X^{{(1)}}X^{{(2)}}X^{{(3)}}\}$

Vzorce pro výpočet hodnoty dílčích bloků v i -tém kole (pro kola 1 až 8):

předběžné kalkulace:

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)}};

konečné výpočty:

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}}),

kde je j -tá klávesa v i -tém kole. $K_{{i}}^{{(j)}}$

Vzorec pro výpočet 9. kola:

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

Výstupem funkce bude

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

Je vidět, že s- a p-bloky se nepoužívají v čisté formě. Hlavní operace jsou:

modulo násobení ; $2^{{16}}+1=65537$
modulo přidání . $2^{{16}}=65536$

Šifry založené na síti Feistel

Lucifer

Historicky prvním algoritmem využívajícím Feistelovu síť byl algoritmus „ Lucifer “, během práce na kterém Feistel skutečně vyvinul strukturu, která se později stala známou jako „Feistelova síť“. V červnu 1971 obdržel Feistel americký patent č. 3798359 [8] .

První verze „ Lucifer “ používala 48bitové bloky a klíče a nepoužívala design „Feistel network“. Následná modifikace algoritmu byla patentována jménem Johna L. Smithe v listopadu 1971 (US Patent 3 796 830; listopad 1971) [ 9 ] a patent obsahuje jak popis samotné sítě Feistel, tak specifické šifrovací funkce. Používal 64bitové klíče a 32bitové bloky. A konečně, poslední verze byla navržena v roce 1973 a fungovala se 128bitovými bloky a klíči. Nejúplnější popis algoritmu "Lucifer" byl uveden v článku Arthura Sorkina ( angl. Arthur Sorkin ) "Lucifer. Cryptographic Algorithm" ("Lucifer, A Cryptographic Algorithm") v časopise "Cryptology" ("Cryptologia") za leden 1984 [10] .

Původní modifikace „Lucifer“ se sice obešla bez „Feistelových buněk“, ale dobře demonstruje, jak pouze použití s- a p-boxů může značně zkreslit původní text. Struktura „Luciferova“ algoritmu vzorku z června 1971 je „sendvič“ dvou typů vrstev používaných postupně – tzv. SP-sítě (neboli substituční-permutační sítě). Prvním typem vrstvy je 128bitový p-blok, následovaný druhou vrstvou, což je 32 modulů, z nichž každý se skládá ze dvou čtyřbitových s-bloků , jejichž odpovídající vstupy jsou zkratovány a stejná hodnota je přiváděna do je z výstupu předchozí vrstvy . Samotné substituční bloky jsou ale jiné (liší se v substitučních tabulkách). Výstup modulu přijímá hodnoty pouze z jednoho s-boxu, který je konkrétně určen jedním z bitů v klíči, jehož počet odpovídal číslu s-boxu ve struktuře. Zjednodušené schéma algoritmu s menší bitovou hloubkou a neúplným počtem kol je na obrázku. Používá 16 selektorů s-box (celkem 32 s-boxů), takže toto schéma používá 16bitový klíč.

Uvažujme nyní, jak se změní šifrový text ve výše uvedeném algoritmu, když se změní pouze jeden bit. Pro jednoduchost vezmeme tabulky nahrazení s-bloku tak, že pokud jsou všechny nuly přivedeny na vstup s-bloku, pak všechny nuly budou také na výstupu. Na základě našeho výběru s-bloků, pokud jsou všechny nuly přiváděny na vstup šifrovacího zařízení, pak na výstupu zařízení budou samé nuly. V reálných systémech se takové substituční tabulky nepoužívají, protože značně zjednodušují práci kryptoanalytika, ale v našem příkladu jasně ilustrují silný vztah mezi znaky při změně jednoho bitu zašifrované zprávy. Je vidět, že díky prvnímu p-bloku se jediná jednotka přesune do středu kvádru, následně ji další nelineární s-blok „znásobí“ a již dvě jednotky změní svou polohu díky dalšímu p -blok atd. Na konci šifrovacího zařízení se díky silné mezisymbolové vazbě výstupní bity staly komplexní funkcí vstupu a použitého klíče. V průměru bude polovina bitů na výstupu „0“ a polovina „1“.

Síť Feistel je ve svém jádru alternativou ke komplexním sítím SP a je využívána mnohem šířeji. Z teoretického hlediska lze funkci kruhového šifrování redukovat na síť SP, ale praktičtější je síť Feistel, protože šifrování a dešifrování lze provádět stejným zařízením, ale s opačným pořadím použitých klíčů. Druhá a třetí verze algoritmu (s využitím sítě Feistel) pracovaly na 32bitových blocích s 64bitovým klíčem a 128bitových blocích se 128bitovými klíči. V nejnovější (třetí) verzi byla funkce kulatého šifrování uspořádána velmi jednoduše - nejprve se šifrovaný podblok prošel vrstvou 4bitových s-bloků (podobně jako vrstvy v sítích SP, pouze s-blok je konstantní a nezávisí na klíči), pak k němu modulo 2 byl přidán kulatý klíč, po kterém byl výsledek předán přes p-blok.

DES

Funkce (kde: $f(L_{i},K_{i})$

$L_i$ — 32bitový vstupní blok v i - té iteraci;
$K_{i}$ - 48bitový klíč v této iteraci)

v algoritmu DES se skládá z následujících operací:

rozšíření vstupního bloku L na 48 bitů (některé vstupní bity se mohou opakovat);
Přidání Modulo 2 s klíčem : $K_{i}$

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

rozdělení výsledku do 8 bloků po 6 bitech:

{\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)}}\};

přijaté bloky informací jsou přiváděny do substitučních bloků majících 6bitové vstupy a 4bitové výstupy; ${\tilde {L_{i}^{{(j)))))$
na výstupu jsou 4bitové bloky sloučeny do 32bitového bloku, který je výsledkem funkce . $f(L_{i},K_{i})$

Celkový počet kol v algoritmu DES je 16.

"Magma"

Funkce (kde a jsou 32bitová čísla) se vypočítá takto: $f(L_{i},K_{i})$ $L_i$ $K_{i}$

sečíst modulo : _ $L_i$ $K_{i}$ $2^{32}$

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

výsledek je rozdělen do 8 4bitových bloků, které jsou přiváděny do 4bitových s-bloků (které mohou být různé);
výstupy s-boxů jsou spojeny do 32bitového čísla, které je následně otočeno o 11 bitů doleva;
výsledkem je výstup funkce.

Počet nábojů v algoritmu GOST 28147-89 je 32.

Srovnávací seznam algoritmů

Následující blokové šifry využívají jako základ klasickou nebo upravenou Feistelovu síť.

Algoritmus	Rok	Počet kol	Délka klíče	Velikost bloku	Počet dílčích bloků
blowfish	1993	16	od 32 do 448	64	2
Kamélie	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
OBCHOD	1998	6 (8)	(128/192) 256	128	2
DES	1977	16	56	64	2
DFC	1998	osm	128/192/256	128	?
FEAL	1987	4-32	64	64	2
GOST 28147-89	1989 [2]	32/16	256	64	2
IDEA	1991	8+1	128	64	čtyři
KASUMI	1999	osm	128	64	2
Chufu	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	čtyři
PURPUROVÁ	1998	6/8	128/192/256	128	2
MARS	1998	32	128-1248	128	2
Soucit	2000	6	128	4096	?
MISTY1	1995	4×n(8)	128	64	čtyři
Raiden	2006	16	128	64	2
RC2	1987	16+2	8-128	64	čtyři
RC5	1994	1-255(12)	0-2040(128)	32/64/128	2
RC6	1998	dvacet	128/192/256	128	čtyři
RTEA	2007	48/64	128/256	64	2
SEMÍNKO	1998	16	128	128	2
Sinople	2003	64	128	128	čtyři
skipjack	1998	32	80	64	čtyři
ČAJ	1994	64	128	64	2
Trojitý DES	1978	32/48	112/168	64	2
Dvě ryby	1998	16	128/192/256	128	čtyři
XTEA	1997	64	128	64	2
XTEA-3	1999	64	256	128	čtyři
XXTEA	1998	12-64	128	64	2

Poznámky

↑ 1 2 3 Horst Feistel "Cryptography and computer privacy" (anglicky) ("Cryptography and computer security"). Překlad archivován 11. března 2018 na Wayback Machine od Andrey Vinokurova.
↑ 1 2 Vinokurov A. Článek archivován 1. dubna 2022 na Wayback Machine „GOST 28147-89 Encryption Algorithm, its Use and Implementation for Intel x86 Platform Computers “. Část materiálů obsažených v tomto článku byla publikována v čísle "# 1.5 / 1995" časopisu "Monitor".
↑ Diskrétní matematika. Algoritmy. Symetrické systémy a blokové šifry (nepřístupný odkaz) . Získáno 21. listopadu 2008. Archivováno z originálu 5. prosince 2012. (neurčitý)
↑ Sergej Panasenko. " Moderní šifrovací algoritmy archivovány 31. ledna 2010 na Wayback Machine " // Byte Magazine. Vydání č. 8 (60), srpen 2003.
↑ Barichev, Goncharov, Serov, 2011 .
↑ Ke konstrukci pseudonáhodné permutace: Luby-Rackoff znovu.
↑ Menezes, Oorschot, Vanstone, 1996 , §7.6 IDEA, str. 263.
↑ Americký patent 3,798,359
↑ Americký patent 3,796,830
↑ Arthur Sorkin. Lucifer, Kryptografický algoritmus. Cryptologia, číslo 8(1), leden 1984, s. 22-41, doplněno v čísle 8(3), s. 260-261

Literatura

Barichev S. G. , Goncharov V. V. , Serov R. E. Základy moderní kryptografie - 3. vydání. — M .: Dialogue-MEPhI , 2011. — 176 s. — ISBN 978-5-9912-0182-7
Menezes A. J. , Oorschot P. v. , Vanstone S. A. Handbook of Applied Cryptography (anglicky) - CRC Press , 1996. - 816 s. — ( Diskrétní matematika a její aplikace ) — ISBN 978-0-8493-8523-0

Symetrické kryptosystémy
Streamové šifry	A3 A5 A8 Decim F-FCSR Obilí HC-256 KCipher-2 MICKEY MUGI ŠTIKA Phelix RC4 Králičí TĚSNĚNÍ SNÍH SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Síť Feistel	GOST 28147-89 (Magma) blowfish Kamélie CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra OBCHOD DES DESX DFC E2 EnRUPT FEAL HPC IDEA KASUMI Khafre Chufu LOKI97 MacGuffin MARS PLETIVO MISTY1 NewDES NDS RC5 RC6 SEMÍNKO Simone Sinople skipjack SM4 Smítko ČAJ XTEA XXTEA Raiden RTEA Trojitý DES Dvě ryby
Síť SP	Saranče 3 způsob ABC ÁRIE AES (Rijndael) Akelarre Anubis BaseKing Bass Omatic Pás KRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer současnost, dárek Duha BEZPEČNĚJŠÍ ŽRALOK NÁMĚSTÍ Had tři ryby
jiný	ŽÁBA NUSH REDOC SC2000 SHACAL CS-Cipher