Feistelin verkko

Feistelin verkko eli Feistelin suunnittelu ( eng. Feistel network, Feistel cipher ) on yksi lohkosalausten rakentamismenetelmistä . Verkko koostuu Feistel-soluista . Jokaisen solun syöttö vastaanottaa dataa ja avaimen. Jokaisen solun lähdössä vastaanotetaan muutettu data ja muutettu avain. Kaikki solut ovat samantyyppisiä ja sanovat, että verkko on tietty toistuvasti toistuva ( iteroitu ) rakenne. Avain valitaan salaus-/salauksenpurkualgoritmin mukaan ja muuttuu siirryttäessä solusta toiseen. Salaus ja salauksen purku suorittavat samat toiminnot; vain järjestys on erilainenavaimet . Toiminnan yksinkertaisuuden ansiosta Feistel-verkko on helppo toteuttaa sekä ohjelmistollisesti että laitteistollisesti. Useat lohkosalaukset ( DES , RC2 , RC5 , RC6 , Blowfish , FEAL , CAST-128 , TEA , XTEA , XXTEA jne.) käyttävät Feistelin verkkoa perustana. Vaihtoehto Feistelin verkolle on permutaatio-permutaatioverkko ( AES jne.).

Historia

Vuonna 1971 Horst Feistel patentoi kaksi laitetta, jotka toteuttivat erilaisia salausalgoritmeja , myöhemmin nimeltään " Lucifer " ( eng. Lucifer ). Yhdessä näistä laitteista käytettiin suunnittelua, jota myöhemmin kutsuttiin "Feistel-verkoksi" ( englanniksi Feistel -salaus , Feistel-verkko ). Sitten Feistel työskenteli uusien salausjärjestelmien luomisessa IBM :n seinien sisällä yhdessä Don Coppersmithin kanssa . Lucifer-projekti oli melko kokeellinen, mutta siitä tuli DES-algoritmin ( eng. d ata e ncryption s tandard ) perusta. Vuonna 1973 Scientific American -lehti julkaisi Feistelin artikkelin "Cryptography and computer security" ( Eng. Cryptography and computer privacy ) [1] , jossa paljastettiin joitain tärkeitä salauksen näkökohtia ja kuvattiin Lucifer - projektin ensimmäinen versio . Project Luciferin ensimmäinen versio ei käyttänyt Feistel-verkkoa.

DES-algoritmi suunniteltiin Feistelin verkkoon perustuen. Vuonna 1977 Yhdysvaltain viranomaiset ottivat käyttöön FIPS 46-3 -standardin ja tunnustivat DES:n tietojen salauksen vakiomenetelmäksi. DES on ollut laajalti käytössä kryptografisissa järjestelmissä jo jonkin aikaa. Algoritmin iteratiivinen rakenne mahdollisti yksinkertaisten ohjelmisto- ja laitteistototeutusten luomisen.

Joidenkin tietojen mukaan [2] Neuvostoliitossa KGB kehitti jo 1970-luvulla lohkosalauksen , joka käytti Feistel -verkkoa, ja luultavasti juuri tämä salaus otettiin käyttöön vuonna 1990 nimellä GOST 28147-89 .

Vuonna 1987 kehitettiin FEAL- ja RC2 -algoritmit . Feistel-verkot yleistyivät 1990-luvulla - sellaisten algoritmien ilmaantumisen vuosina kuin Blowfish (1993), TEA (1994), RC5 (1994), CAST-128 (1996), XTEA (1997), XXTEA (1998), RC6 (1998) ja muut.

2. tammikuuta 1997 NIST - instituutti julkaisi kilpailun uuden datan salausalgoritmin luomiseksi DES :n korvaamiseksi . Uusi lohkosalaus nimettiin AES ( advanced encryption s tandard ) ja se hyväksyttiin 26. toukokuuta 2002 . AES käyttää korvauspermutaatioverkkoa Feistel-verkon sijaan .

Lohkosalauksen suunnittelu perustuu Feistelin verkkoihin

Yksinkertainen kuvaus

Salaus

Vaaditaanko salaamaan joitakin tietoja , jotka esitetään binäärimuodossa ( nolla- ja ykkösjonon muodossa ) ja jotka sijaitsevat tietokoneen tai muun laitteen muistissa (esimerkiksi tiedostossa ).

salausalgoritmi.

Tiedot on jaettu samanpituisiin (kiinteään) lohkoihin. Tuloksena olevia lohkoja kutsutaan inputiksi , koska ne syötetään algoritmiin. Jos syöttölohkon pituus on pienempi kuin koko, jonka valittu salausalgoritmi pystyy salaamaan kerrallaan (lohkokoko), lohkoa pidennetään jollakin tavalla. Tyypillisesti lohkon pituus on kahden potenssi , kuten 64 bittiä tai 128 bittiä.

Lisäksi tarkastelemme operaatioita, jotka tapahtuvat vain yhdellä lohkolla, koska samat toiminnot suoritetaan muiden lohkojen kanssa salausprosessin aikana.

Valittu lohko on jaettu kahteen samankokoiseen alilohkoon - "vasemmalle" ( ) ja "oikealle" ( ). $L_0$ $R_{0}$
"Oikea alilohko" muutetaan F -toiminnolla käyttämällä pyöreää näppäintä : $R_{0}$ $K_{0}$

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

Tulokseen lisätään modulo 2 ("xor") "vasemmalla alilohkolla" : $L_0$

x=x\oplus L_{0}.

Tulosta käytetään seuraavalla kierroksella "oikeana osalohkona" : $R_{1}$

R_{1}=x.

Nykyisen kierroksen "oikeaa alilohkoa" (muutamattomassa muodossaan kierroksen alussa) käytetään seuraavalla kierroksella "vasempana alilohkona" : $R_{0}$ $L_{1}$

L_{1}=R_{0}.

Jonkin matemaattisen säännön mukaan lasketaan pyöreä avain - se avain, jota käytetään seuraavalla kierroksella. $K_1$

Listatut toiminnot suoritetaan N-1 kertaa, missä N on valitun salausalgoritmin kierrosten lukumäärä. Tässä tapauksessa siirtymien välillä kierroksesta (vaiheesta) toiselle näppäimet vaihtuvat: se korvataan , - merkillä jne.). $K_{0}$ $K_1$ $K_1$ $K_{2}$

Salauksen purku

Tietojen salauksen purku tapahtuu samalla tavalla kuin salaus, sillä ainoalla poikkeuksella, että avaimet seuraavat käänteisessä järjestyksessä, eli ei ensimmäisestä N: nneen , vaan N :nnestä ensimmäiseen.

Algoritminen kuvaus

Selkotekstilohko on jaettu kahteen yhtä suureen osaan : . $(L_{0},\ R_{0})$
Jokainen kierros laskee:

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

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

missä:

i on kierroksen numero ; $i=1\ldotsN;$
N on valitun salausalgoritmin kierrosten lukumäärä;
$f$ - jokin toiminto;
$K_{{i-1}}$ — i-1 . kierroksen avain (kierrosavain) .

Kierrosten tulos on . N - kierroksella permutaatiota ja ei suoriteta, joten on mahdollista käyttää samaa menettelyä salauksen purkamiseen yksinkertaisesti kääntämällä avainten käyttöjärjestys ( sijaan ) : $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}.

Pienellä muutoksella on mahdollista saavuttaa salaus- ja salauksenpurkumenettelyjen täydellinen identiteetti.

Edut:

algoritmin palautuvuus käytetystä funktiosta f riippumatta ;
kyky valita mielivaltaisesti monimutkainen funktio f .

Matemaattinen kuvaus

Harkitse esimerkkiä. Päästää:

X on tietolohko, joka tulee syötteeseen (syöttölohko);
A - jokin involuutiivinen muunnos (tai involuutio ) - yksi yhteen muunnos, joka on käänteinen itselleen [3] eli jokaiselle ( ∀ ) X :lle lauseke on tosi:

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

Y on lähdössä vastaanotettu datalohko (tulos).

Kun muunnos A käytetään kerran sisääntulolohkoon X , tuloksena on lähtölohko Y :

Y=AX.

Kun käytät muunnosa A edellisen muunnoksen - Y tulokseen, saat:

AY=AAX=X,\kaikki X.

Olkoon syöttölohko X kahdesta samanpituisesta alilohkosta L ja R :

X = (L, R).

Määrittelemme kaksi muutosta:

$G(X,K)$ - tietojen salaus X avaimella K :

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

$T(L,R)$ — alilohkojen L ja R permutaatio :

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

Esitellään merkintä:

muunnoksen G yksittäinen sovellus :

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

soveltamalla muunnos G kahdesti :

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

Todistetaan kaksoismuunnoksen G ( ) involuutio . $G^{2}$

On helppo nähdä, että muunnos G muuttaa vain vasemman alilohkon L jättäen oikean R :n ennalleen:

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

{\tilde {R}}=R.

Siksi seuraavassa tarkastelemme vain alilohkoa L. Kun muunnos G :stä L :ään on sovellettu kahdesti, saadaan:

{\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.

Tällä tavalla:

G^{2}L=L;

G^{2}R=R,

Näin ollen

G^{2}X=X

ja G on involuutio .

Todistetaan kaksoismuunnoksen T ( ) involuutio . $T^{2}$

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

Harkitse salausprosessia. Päästää:

X on syöttöarvo;
$G_{i}$ — muunnos avaimella ; $K_{i}$
$Y_{i}$ — lähtöarvo, i . kierroksen tulos .

Sitten i+1 -kierroksella suoritettu muunnos voidaan kirjoittaa seuraavasti:

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

1. kierroksella suoritettu muunnos:

Y_{1}=TG_{1}X.

Siksi lähtöarvo m salauskierroksen jälkeen on:

Y_{m}=TG_{m}Y_{{m-1}}=TG_{m}TG_{{m-1}}\lpisteitä TG_{1}X.

Voidaan nähdä, että viimeisessä vaiheessa ei ole tarpeen suorittaa T :n permutaatiota .

Salauksen purku suoritetaan käyttämällä kaikkia muunnoksia käänteisessä järjestyksessä. Johtuen kunkin muunnoksen involutiivisuudesta, käänteinen järjestys antaa alkuperäisen tuloksen:

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

Feistelin verkoissa käytetyt toiminnot

Teoksessaan "Cryptography and Computer Security" [1] Horst Feistel kuvaa kaksi muunnoslohkoa (funktioita ): $f(L_{{i}},\ K_{{i}})$

korvauslohko (s-box, eng. s-box );
permutaatiolohko (p-box, eng. p-box ).

Voidaan osoittaa, että mikä tahansa binäärimuunnos kiinteän pituisen datalohkon yli voidaan toteuttaa s-boxina . Suuren N :n N -bitin s-lohkon rakenteen monimutkaisuuden vuoksi käytetään käytännössä yksinkertaisempia rakenteita.

Alkuperäisen artikkelin [1] termiä "lohko" käytetään termin "funktio" sijaan, koska puhumme lohkosalauksesta ja oletettiin, että s- ja p-lohkot olisivat digitaalisia mikropiirejä (digitaalisia lohkot).

S-lohko

Korvauslohko (s-box, eng. s-box ) koostuu seuraavista osista:

dekooderi - n - bittisen binaarisen signaalin muuntaja yksibittiseksi signaaliksi kannassa ; $2^{n}$
kytkinjärjestelmä - sisäiset liitännät (mahdolliset liitännät yhteensä ); $2^{n}!$
enkooderi - signaalinmuunnin yksibittisestä -arisesta n-bittiseksi binääriksi. $2^{n}$

N -bittisen S-lohkon analysointi suurelle n:lle on erittäin vaikeaa, mutta sellaisen lohkon toteuttaminen käytännössä on erittäin vaikeaa, koska mahdollisten yhteyksien määrä on erittäin suuri ( ). Käytännössä korvauslohkoa käytetään osana monimutkaisempia järjestelmiä. $2^{n}$

Yleisessä tapauksessa s-lohkolla voi olla eri määrä tuloja/lähtöjä; tässä tapauksessa kytkentäjärjestelmässä ei saa mennä tiukasti yksi yhteys dekooderin jokaisesta lähdöstä, vaan 2 tai useampi tai ei mennä kaikki. Sama pätee kooderin tuloihin.

Elektroniikassa oikealla olevaa kaaviota voidaan soveltaa suoraan. Ohjelmoinnissa luodaan korvaavat taulukot. Molemmat lähestymistavat ovat samanarvoisia, eli tietokoneella salatun tiedoston salaus voidaan purkaa elektronisella laitteella ja päinvastoin.

Korvaava taulukko supistetulle 3-bittiselle s-boxille

Yhdistelmä nro	0	yksi	2	3	neljä	5	6	7
Sisäänkäynti	000	001	010	011	100	101	110	111
Poistu	011	000	001	100	110	111	010	101

P-lohko

Permutaatiolohko (p-block, eng. p-box ) vain muuttaa numeroiden sijaintia ja on lineaarinen laite. Tällä lohkolla voi olla erittäin suuri määrä tuloja ja lähtöjä, mutta lineaarisuuden vuoksi järjestelmää ei voida pitää kryptonkestävänä.

N -bittisen p-lohkon avaimen krypta -analyysi suoritetaan syöttämällä sisääntuloon n-1 erilaista viestiä, joista jokainen koostuu n-1 nollasta ("0") ja 1 ykkösestä ("1") (tai päinvastoin, ykkösistä ja nollasta ).

Syklinen vaihto

Voidaan osoittaa, että syklinen siirto on p-lohkon erikoistapaus.

Yksinkertaisimmassa tapauksessa (siirto 1 bitillä) äärimmäinen bitti jaetaan ja siirretään rekisterin tai väylän toiseen päähän. Riippuen siitä, mikä bitti otetaan, oikealle tai vasemmalle, siirtoa kutsutaan oikealle tai vasemmalle. Muutoksia useammalla bitillä voidaan ajatella käyttämällä siirtoa 1:llä useita kertoja.

Kierrä m bittiä n -bittiselle tulolle ( m < n )

Muuta suuntaa	Bittijärjestys ennen vuoroa	Bittijärjestys työvuoron jälkeen
Vasen	$b_{0},b_{1},b_{2},...,b_{{n-1}}$	$b_{m},b_{{m+1}},...b_{{n-1}},b_{0},b_{1},...,b_{{m-1}}$
oikein	$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 }}$

Lisäys modulo n

Operaatio " lisäys modulo n " on merkitty nimellä

( A + B ) mod n

ja on jäännös summan A + B jakamisesta n: llä , missä A ja B ovat lukuja.

Voidaan osoittaa, että kahden luvun modulo n yhteenlasku esitetään binäärijärjestelmässä s-lohkona, jossa syötetään luku A ja kytkentänä käytetään B -bitin syklistä siirtoa vasemmalle. s-lohkon järjestelmä.

Tietotekniikassa ja elektroniikassa summausoperaatio toteutetaan pääsääntöisesti modulo - lisäyksenä , jossa m on kokonaisluku (yleensä m on yhtä suuri kuin koneen kapasiteetti). Päästä binääriin $n = 2^m$

A + B mod

2^{m}

riittää, kun lisäät numerot ja hylkäät sitten numerot alkaen m - th ja vanhemmat.

Kertominen modulo n

Kertolasku modulo n on merkitty

( A * B ) mod n

ja on jakojäännös tulon A * B jakamisesta n: llä , missä A ja B ovat lukuja.

Henkilökohtaisissa tietokoneissa x86 -alustalla, kun kerrotaan kaksi m - bittistä numeroa, saadaan luku, jonka kapasiteetti on 2 * m . Saadaksesi loppuosan :lla jakamisen jälkeen , sinun on hylättävä m merkittävintä bittiä. $2^{m}$

Esimerkki toteutuksesta C -kielellä

Yleisnäkymä Feistel-verkkoa käyttävästä salausalgoritmista:

/* Funktio, joka suorittaa alilohkon muunnoksen ottaen huomioon avaimen arvon (avaimella). Toteutus riippuu valitusta lohkosalausalgoritmista. */ int f ( int alilohko , /* alilohko muuntaa */ int avain /* avain */ ); /* paluuarvo - muunnettu lohko */ /* Pelkän tekstin salauksen suorittava toiminto */ tyhjä krypta ( int * vasen , /* vasen syötteen alilohko */ int * oikea , /* oikea tulon alilohko */ int kierrokset , /* kierrosten lukumäärä */ int * avain /* näppäinjoukko (yksi avain per kierros) */ ) { int i , temp ; for ( i = 0 ; i < kierrosta ; i ++ ) { lämpötila = * oikea ^ f ( * vasen , näppäin [ i ] ); * oikea = * vasen ; * vasen = lämpötila ; } } /* Toiminto, joka purkaa tekstin salauksen */ void purkaa ( int * vasen , /* vasen salattu alilohko */ int * oikea , /* oikea salattu alilohko */ int kierrokset , /* kierrosten lukumäärä */ int * avain /* näppäinjoukko (yksi avain per kierros) */ ) { int i , temp ; for ( i = kierrokset - 1 ; i > = 0 ; i -- ) { lämpötila = * vasen ^ f ( * oikea , näppäin [ i ] ); * vasen = * oikea ; * oikea = lämpötila ; } }

Edut ja haitat

Edut:

laitteiston toteutuksen yksinkertaisuus nykyaikaisella sähköisellä pohjalla;
ohjelmiston toteutuksen helppous johtuen siitä, että merkittävää osaa toiminnoista tuetaan laitteistotasolla nykyaikaisissa tietokoneissa (esimerkiksi modulo 2 -lisäys ("xor") , modulo-lisäys, modulo kertominen jne.); $2^{n}$ $2^{n}$
hyvä Feistel-verkkoihin perustuvien algoritmien tuntemus [4] .

Virheet:

yhdellä kierroksella vain puolet syöttölohkosta salataan [5] .

Teoreettiset opinnot

Salaustutkijat ovat tutkineet Feistel-verkkoja laajalti niiden laajan käytön vuoksi. Vuonna 1988 Michael Louby ja Charles Rakoff tekivät tutkimusta Feistel-verkosta ja osoittivat, että jos kierrosfunktio on kryptografisesti vahva pseudosatunnainen ja käytetyt avaimet ovat riippumattomia kullakin kierroksella, niin 3 kierrosta riittää. jotta lohkosalaus olisi näennäissatunnainen permutaatio, kun taas neljä kierrosta riittää vahvan näennäissatunnaisen permutaatioon.

Lubin ja Rakoffin " pseudosatunnainen permutaatio " on sellainen, joka kestää adaptiivisen selkotekstin valinnan hyökkäyksen, ja " vahva pseudosatunnainen permutaatio " on näennäissatunnainen permutaatio, joka kestää valittua salatekstihyökkäystä.

Joskus länsimaisessa kirjallisuudessa Feistel-verkkoa kutsutaan "Luby-Rackoffin lohkosalaukseksi" Lubyn ja Rackoffin kunniaksi, jotka ovat tehneet suuren määrän teoreettista tutkimusta tällä alalla.

Myöhemmin, vuonna 1997, Moni Naor ja Omer Reingold ehdottivat yksinkertaistettua versiota Lubi-Rakoff-rakenteesta, joka koostuu neljästä kierroksesta. Tämä variantti käyttää kahta parittaista riippumatonta permutaatiota ensimmäisenä ja viimeisenä kierroksena . Naor-Reingold-konstruktion kaksi keskimmäistä kierrosta ovat identtisiä Lubi-Rakoff-konstruktion kierrosten kanssa [6] .

Suurin osa tutkimuksesta on omistettu tiettyjen algoritmien tutkimiseen. Useista Feistel-verkkoon perustuvista lohkosalauksista on löydetty joitakin haavoittuvuuksia, mutta joissain tapauksissa nämä haavoittuvuudet ovat puhtaasti teoreettisia ja tietokoneiden nykyisellä suorituskyvyllä on mahdotonta käyttää niitä käytännössä murtamiseen.

Muutokset Feistel-verkostoon

Suurikokoisilla salauslohkoilla (vähintään 128 bittiä) tällaisen Feistel-suunnittelun toteuttaminen 32-bittisissä arkkitehtuureissa voi aiheuttaa vaikeuksia, joten tämän suunnittelun muunneltuja versioita käytetään. Yleisesti käytetään neljän haaran verkkoja. Kuvassa on yleisimmät muutokset. On myös järjestelmiä, joissa puoliskojen ja pituudet eivät täsmää. Tällaisia verkkoja kutsutaan epätasapainoisiksi . $L_0$ $R_{0}$

Feistelin verkkomuutokset
Tyyppi 1
Tyyppi 2
Tyyppi 3

IDEA-algoritmi

Lähde [7] :

Idea -algoritmin koko kierroksen yhden iteroinnin kaavio

IDEA - algoritmi käyttää syvästi muokattua Feistel-verkkoa. Siinä 64-bittiset syöttödatalohkot (merkitty ) on jaettu neljään 16 bitin pituiseen alilohkoon . Jokainen vaihe käyttää 6 16-bittistä avainta. Yhteensä käytetään 8 päävaihetta ja 1 lyhennetty. $X_{0}$ $X_{0}=\{X^{{(0)}}X^{{(1)}}X^{{(2)}}X^{{(3)}}\}$

Kaavat alilohkojen arvon laskemiseksi i :nnellä kierroksella (kierroksille 1-8):

alustavat laskelmat:

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

lopulliset laskelmat:

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

missä on i -kierroksen j -näppäin . $K_{{i}}^{{(j)}}$

Kaava 9. kierroksen laskemiseksi:

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

Toiminnon tulos on

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

Voidaan nähdä, että s- ja p-lohkoja ei käytetä puhtaassa muodossaan. Päätoiminnot ovat:

modulo kertolasku ; $2^{{16}}+1=65537$
modulo lisäys . $2^{{16}}=65536$

Feistel-verkkoon perustuvat salakirjoitukset

Lucifer

Historiallisesti ensimmäinen Feistel-verkkoa käyttävä algoritmi oli " Lucifer "-algoritmi, jonka aikana Feistel itse asiassa kehitti rakenteen, joka myöhemmin tunnettiin nimellä "Feistel-verkko". Kesäkuussa 1971 Feistel sai amerikkalaisen patentin nro 3798359 [8] .

" Luciferin " ensimmäinen versio käytti 48-bittisiä lohkoja ja avaimia, eikä siinä käytetty "Feistel-verkkoa". Algoritmin myöhempi muunnos patentoitiin John L. Smithin nimiin marraskuussa 1971 (US-patentti 3 796 830; marraskuu 1971) [ 9 ] , ja patentti sisältää sekä kuvauksen itse Feistelin verkosta että tietyt salaustoiminnot. Se käytti 64-bittisiä avaimia ja 32-bittisiä lohkoja. Ja lopuksi, viimeisin versio ehdotettiin vuonna 1973, ja se toimi 128-bittisillä lohkoilla ja avaimilla. Täydellisin kuvaus "Lucifer"-algoritmista on Arthur Sorkinin ( eng. Arthur Sorkin ) artikkelissa "Lucifer. Cryptographic Algorithm" ("Lucifer, A Cryptographic Algorithm") lehdessä "Cryptology" ("Cryptologia") tammikuussa 1984 [10] .

Vaikka "Luciferin" alkuperäinen muunnos selvisi ilman "Feistel-soluja", se osoittaa hyvin, kuinka vain s- ja p-laatikoiden käyttö voi vääristää alkuperäistä tekstiä suuresti. Kesäkuun 1971 näytteen "Lucifer"-algoritmin rakenne on "sandwich" kahdesta vuorotellen käytetystä kerroksesta - ns. SP-verkoista (tai substituutio-permutaatioverkoista). Ensimmäinen kerrostyyppi on 128-bittinen p-lohko, jota seuraa toinen kerros, joka koostuu 32 moduulista, joista jokainen koostuu kahdesta nelibittisestä s-lohkosta , joiden vastaavat tulot on oikosuljettu ja sama arvo syötetään ne edellisen kerroksen lähdöstä . Mutta itse korvauslohkot ovat erilaisia (ne eroavat korvaustaulukoista). Moduulin ulostulo vastaanottaa arvoja vain yhdestä s-laatikosta, jonka nimenomaan määrittää yksi avaimen bitti, jonka numero vastasi rakenteen s-laatikon numeroa. Kuvassa on esitetty algoritmin yksinkertaistettu kaavio pienemmällä bittisyvyydellä ja epätäydellisellä määrällä kierroksia. Se käyttää 16 s-box-valitsinta (yhteensä 32 s-laatikkoa), joten tämä menetelmä käyttää 16-bittistä avainta.

Tarkastellaan nyt kuinka salateksti muuttuu yllä olevassa algoritmissa, kun vain yksi bitti muuttuu. Yksinkertaisuuden vuoksi otamme taulukoita s-lohkon korvauksista siten, että jos kaikki nollat syötetään s-lohkon tuloon, myös kaikki nollat tulostetaan. Valitsemamme s-lohkojen perusteella, jos kaikki nollat syötetään salauslaitteen tuloon, laitteen ulostulo on kaikki nollia. Todellisissa järjestelmissä tällaisia substituutiotaulukoita ei käytetä, koska ne yksinkertaistavat suuresti kryptanalyytikon työtä, mutta esimerkissämme ne havainnollistavat selkeästi vahvaa merkkien välistä suhdetta vaihdettaessa yhtä bittiä salatusta viestistä. Voidaan nähdä, että ensimmäisestä p-lohkosta johtuen ainoa yksikkö siirtyy lohkon keskelle, sitten seuraava epälineaarinen s-lohko "kertoo" sen, ja jo kaksi yksikköä muuttaa sijaintiaan seuraavan p:n takia. -lohko jne. Salauslaitteen lopussa vahvan symbolien välisen kytkennän ansiosta lähtöbiteistä tuli monimutkainen syötteen ja käytetyn avaimen funktio. Keskimäärin puolet biteistä on "0" ja puolet "1" lähdössä.

Feistel-verkko on ytimenään vaihtoehto monimutkaisille SP-verkoille ja sitä käytetään paljon laajemmin. Teoreettisesta näkökulmasta pyöreä salaustoiminto voidaan pelkistää SP-verkkoon, mutta Feistel-verkko on käytännöllisempi, koska salaus ja salauksen purku voidaan suorittaa samalla laitteella, mutta käänteisessä avainten järjestyksessä. Algoritmin toinen ja kolmas versio (käyttivät Feistel-verkkoa) toimivat 32-bittisillä lohkoilla 64-bittisellä avaimella ja 128-bittisillä lohkoilla 128-bittisillä avaimilla. Viimeisimmässä (kolmannessa) versiossa pyöreä salaustoiminto oli järjestetty hyvin yksinkertaisesti - ensin salattu alilohko kuljetettiin 4-bittisten s-lohkojen kerroksen läpi (samanlainen kuin kerrokset SP-verkoissa, vain s-lohko on vakio ja ei riipu avaimesta), sitten siihen modulo 2 lisättiin pyöreä avain, jonka jälkeen tulos kuljetettiin p-lohkon läpi.

DES

Toiminto (missä: $f(L_{i},K_{i})$

$L_i$ — 32-bittinen syöttölohko i :nnessä iteraatiossa;
$K_{i}$ - 48-bittinen avain tässä iteraatiossa)

DES-algoritmissa koostuu seuraavista toiminnoista:

syöttölohkon L laajentaminen 48 bittiin (jotkut tulobitit voivat toistua);
Modulo 2 lisäys avaimella : $K_{i}$

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

jakamalla tuloksen 8 lohkoon, joissa kussakin on 6 bittiä:

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

vastaanotetut informaatiolohkot syötetään korvauslohkoihin, joissa on 6-bittiset tulot ja 4-bittiset lähdöt; ${\tilde {L_{i}^{{(j)))))$
lähdössä 4-bittiset lohkot yhdistetään 32-bittiseksi lohkoksi, joka on funktion tulos . $f(L_{i},K_{i})$

DES-algoritmin kierrosten kokonaismäärä on 16.

"Magma"

Funktio (jossa ja ovat 32-bittisiä lukuja) lasketaan seuraavasti: $f(L_{i},K_{i})$ $L_i$ $K_{i}$

lisää modulo : _ $L_i$ $K_{i}$ $2^{32}$

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

tulos jaetaan 8 4-bittiseen lohkoon, jotka syötetään 4-bittisiksi s-lohkoiksi (jotka voivat olla erilaisia);
s-laatikoiden lähdöt yhdistetään 32-bittiseksi luvuksi, jota sitten kierretään 11 bittiä vasemmalle;
tulos on funktion tulos.

GOST 28147-89 -algoritmin kierrosten määrä on 32.

Vertaileva algoritmien luettelo

Seuraavat lohkosalaukset käyttävät perustanaan klassista tai modifioitua Feistel-verkkoa.

Algoritmi	vuosi	Kierrosten lukumäärä	Avaimen pituus	Lohkon koko	Alilohkojen lukumäärä
blowfish	1993	16	32-448	64	2
Camellia	2000	18/24	128/192/256	128	2
CAST-128	1996	16.12	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
SOPIMUS	1998	6 (8)	(128/192) 256	128	2
DES	1977	16	56	64	2
DFC	1998	kahdeksan	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	neljä
KASUMI	1999	kahdeksan	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	neljä
MAGENTA	1998	6/8	128/192/256	128	2
MARS	1998	32	128-1248	128	2
Armo	2000	6	128	4096	?
MISTY1	1995	4×n(8)	128	64	neljä
Raiden	2006	16	128	64	2
RC2	1987	16+2	8-128	64	neljä
RC5	1994	1-255(12)	0-2040 (128)	32/64/128	2
RC6	1998	kaksikymmentä	128/192/256	128	neljä
RTEA	2007	48/64	128/256	64	2
SIEMEN	1998	16	128	128	2
Sinopoli	2003	64	128	128	neljä
jätkä	1998	32	80	64	neljä
TEE	1994	64	128	64	2
Kolminkertainen DES	1978	32/48	112/168	64	2
Kaksi kalaa	1998	16	128/192/256	128	neljä
XTEA	1997	64	128	64	2
XTEA-3	1999	64	256	128	neljä
XXTEA	1998	12-64	128	64	2

Muistiinpanot

↑ 1 2 3 Horst Feistel "Cryptography and computer privacy" (englanniksi) ("Salaus ja tietoturva"). Käännös arkistoitu 11. maaliskuuta 2018 Wayback Machinessa , kirjoittanut Andrey Vinokurov.
↑ 1 2 Vinokurov A. Artikkeli arkistoitu 1. huhtikuuta 2022 Wayback Machinessa "GOST 28147-89 -salausalgoritmi, sen käyttö ja toteutus Intel x86 -alustatietokoneille ". Osa tähän artikkeliin sisältyvistä materiaaleista julkaistiin "Monitor" -lehden numerossa "# 1.5 / 1995".
↑ Diskreetti matematiikka. Algoritmit. Symmetriset järjestelmät ja lohkosalaukset (linkki ei saavutettavissa) . Haettu 21. marraskuuta 2008. Arkistoitu alkuperäisestä 5. joulukuuta 2012. (määrätön)
↑ Sergei Panasenko. " Modern Encryption Algorithms Arkistoitu 31. tammikuuta 2010 Wayback Machinessa " // Byte Magazine. Numero 8 (60), elokuu 2003.
↑ Barichev, Goncharov, Serov, 2011 .
↑ Näennäissatunnaisen permutoinnin rakentamisesta: Luby-Rackoff vieraili uudelleen.
↑ Menezes, Oorschot, Vanstone, 1996 , §7.6 IDEA, s. 263.
↑ US-patentti 3 798 359
↑ US-patentti 3 796 830
↑ Arthur Sorkin. Lucifer, salausalgoritmi. Cryptologia, Issue 8(1), tammikuu 1984, s. 22-41, täydennetty numerossa 8(3), s. 260-261

Kirjallisuus

Barichev S. G. , Goncharov V. V. , Serov R. E. Modernin kryptografian perusteet - 3. painos. — 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 (englanti) - CRC Press , 1996. - 816 s. — ( Diskreetti matematiikka ja sen sovellukset ) — ISBN 978-0-8493-8523-0

Symmetriset salausjärjestelmät
Suoratoista salauksia	A3 A5 A8 Desim F-FCSR Vilja HC-256 KCipher-2 MIKKI MUGI HAUKI Phelix RC4 Kani TIIVISTE LUMI SOSEMANUK Salsa 20 STRUMOK Trivium VMPC
Feistelin verkko	GOST 28147-89 (Magma) blowfish Camellia CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra SOPIMUS DES DESX DFC E2 enRUPT FEAL HPC IDEA KASUMI Khafre Khufu LOKI97 MacGuffin MARS MESH MISTY1 UusiDES NDS RC5 RC6 SIEMEN Simon Sinopoli jätkä SM4 Speck TEE XTEA XXTEA Raiden RTEA Kolminkertainen DES Kaksi kalaa
SP verkko	Heinäsirkka 3 tapaa ABC AARIA AES (Rijndael) Akelarre Anubis BaseKing Basso Omatic Vyö CRYPTON Timantti 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer esittää Sateenkaari TURVALLISTA HAI NELIÖ Käärme kolme kalaa
muu	SAMMAKKO NUSH REDOC SC2000 SHACAL CS-Cipher