Feistel-salakirjoitus

Kryptografiassa Feistel-salaus on symmetrinen rakenne, jota käytetään lohkosalakirjoitusten rakentamisessa ja joka on nimetty saksalaisen IBM:n salakirjoittajan Horst Feistelin mukaan; se tunnetaan yleisesti myös nimellä Feistel-verkko. Suuri joukko lohkosalakirjoituksia käyttää tätä järjestelmää, mukaan lukien Data Encryption Standard -standardi.

Feistel-rakenteen etuna on, että salaus- ja purkuoperaatiot ovat hyvin samankaltaisia, joissakin tapauksissa jopa identtisiä, ja ne vaativat vain avaimen aikataulun vaihtamisen. Näin ollen tällaisen salakirjoituksen toteuttamiseen tarvittavan koodin tai piirin koko lähes puolittuu.

Feistel-rakenne on luonteeltaan iteratiivinen, mikä helpottaa salausjärjestelmän toteuttamista laitteistossa.

Feistel-verkot ja vastaavat rakenteet ovat tuotesalakirjoituksia, joten ne yhdistävät useita toistuvia operaatiokierroksia, kuten:

Bittien sekoittaminen (usein kutsutaan permutaatiolaatikoiksi tai P-laatikoiksi).
Yksinkertaiset epälineaariset funktiot (joita kutsutaan usein korvauslaatikoiksi tai S-laatikoiksi).
Lineaarinen sekoittaminen (modulaarialgebran merkityksessä) XOR:n avulla tuottaa funktion, jossa on suuria määriä sitä, mitä Claude Shannon kuvaili "sekaannukseksi ja hajanaisuudeksi".

Bittien sekoittaminen luo diffuusiovaikutuksen, kun taas substituutiota käytetään sekoittamiseen.

Teoreettinen työ

Monet nykyaikaiset symmetriset lohkosalakirjoitukset käyttävät Feistel-verkkoja, ja salakirjoittajat ovat tutkineet laajasti Feistel-salakirjoitusten rakennetta ja ominaisuuksia. Erityisesti Michael Luby ja Charles Rackoff analysoivat Feistel-lohkosalakirjoituksen rakennetta ja osoittivat, että jos kierrosfunktio on kryptografisesti turvallinen pseudosatunnaisfunktio, jonka siemenenä käytetään K:ta_i, kolme kierrosta riittää tekemään lohkosalakirjoituksesta pseudosatunnaisen permutaation, kun taas neljä kierrosta riittää tekemään siitä "vahvan" pseudosatunnaisen permutaation (mikä tarkoittaa, että se säilyy pseudosatunnaisena jopa sellaiselle vastustajalle, joka saa oraakkelin kautta pääsyn käänteiseen permutaatioonsa). Tämän Lubyn ja Rackoffin erittäin tärkeän tuloksen vuoksi Feistel-salakirjoituksia kutsutaan joskus Luby-Rackoff-lohkosalakirjoituksiksi. Myöhemmissä teoreettisissa tutkimuksissa rakennetta yleistettiin ja määritettiin turvallisuudelle tarkemmat rajat.

Rakentaminen

Olkoon F {\displaystyle {\rm {F}}} ${\rm F}$ kierrosfunktio ja olkoon K 1 , K 2 , ... , K n {\displaystyle K_{1},K_{2},\ldots ,K_{n}}} $K_1,K_2,\ldots,K_{n}$ kierrosten 1 , 2 , ... , n {\displaystyle 1,2,\ldots ,n}} $1,2,\ldots,n$ aliavaimet.

Tällöin perustoiminto on seuraava:

Jaetaan selkotekstilohko kahteen yhtä suureen osaan ( L 1 {\displaystyle L_{1}} L_1 , R 1 {\displaystyle R_{1}} R_1 ).

Jokaisella kierroksella i = 1 , 2 , ... , n {\displaystyle i=1,2,\dots ,n} $i =1,2,\dots,n$ , laske (calcul)

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

Tällöin salateksti on ( R n + 1 , L n + 1 ) {\displaystyle (R_{n+1},L_{n+1})} $(R_{n+1}, L_{n+1})$ . (Yleensä kahta kappaletta R n {\displaystyle R_{n}} R_n ja L n {\displaystyle L_{n}} L_n ei vaihdeta viimeisen kierroksen jälkeen).

Salakirjoitustekstin ( R n , L n ) {\displaystyle (R_{n},L_{n})} (R_n, L_n) salauksen purku suoritetaan laskemalla 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})$ .

Sitten ( L 1 , R 1 ) {\displaystyle (L_{1},R_{1})} (L_1,R_1) on jälleen selvä teksti.

Yksi tämän mallin eduista on, että pyöreän funktion F {\displaystyle {\rm {F}}} ${\rm F}$ ei tarvitse olla käänteismuunnettavissa, ja se voi olla hyvin monimutkainen.

Kaavio havainnollistaa salausprosessia. Salakirjoituksen purkaminen edellyttää vain aliavaimien K n , K n - 1 , ... , K 1 {\displaystyle K_{n},K_{n-1},\ldots ,K_{1}} $K_{n},K_{n-1},\ldots,K_1$ järjestyksen kääntämistä saman prosessin avulla; tämä on ainoa ero salauksen ja salauksen purkamisen välillä:

Epätasapainoisissa Feistel-salauksissa käytetään muunnettua rakennetta, jossa L 1 {\displaystyle L_{1}} L_1 ja R 1 {\displaystyle R_{1}} R_1 eivät ole yhtä pitkiä. MacGuffin-salaus on kokeellinen esimerkki tällaisesta salakirjoituksesta.

Feistelin rakennetta käytetään myös muissa salausalgoritmeissa kuin lohkosalauksissa. Esimerkiksi Optimal Asymmetric Encryption Padding (OAEP) -järjestelmässä käytetään yksinkertaista Feistel-verkkoa salaustekstien satunnaistamiseen tietyissä epäsymmetristen avainten salausjärjestelmissä.

Feistel-verkko-operaatio lohkosalakirjoitukselle, jossa P on selkoteksti ja C on salateksti.

Luettelo Feistelin salakirjoituksista

Feistel tai muunnettu Feistel: Blowfish, Camellia, CAST-128, DES, FEAL, ICE, KASUMI, LOKI97, Lucifer, MARS, MAGENTA, MISTY1, RC5, TEA, Triple DES, Twofish, XTEA, GOST 28147-89.

Yleistetty Feistel: CAST-256, MacGuffin, RC2, RC6, Skipjack.

Kysymyksiä ja vastauksia

K: Mikä on Feistelin salakirjoitus?

A: Feistel-salaus on lohkosalakirjoitusten rakentamisessa käytetty symmetrinen rakenne, joka on nimetty saksalaisen IBM:n salakirjoittajan Horst Feistelin mukaan. Se tunnetaan yleisesti myös nimellä Feistel-verkko.

K: Mitä etuja Feistel-rakenteen käytöstä on?

V: Feistel-rakenteen käytön tärkein etu on se, että salaus- ja purkuoperaatiot ovat hyvin samankaltaisia, joissakin tapauksissa jopa identtisiä, ja ne vaativat vain avaimen aikataulun vaihtamisen. Tämä pienentää tällaisen salakirjoituksen toteuttamiseen tarvittavan koodin tai piirin kokoa lähes puoleen. Lisäksi sen iteratiivinen luonne helpottaa salausjärjestelmän toteuttamista laitteistossa.

Kysymys: Miten Claude Shannon kuvailee "sekaannusta ja diffuusiota"?

V: Claude Shannon kuvasi "hämmennystä ja diffuusiota" siten, että molempia elementtejä on paljon, jotta hyökkääjän on vaikea purkaa salattua viestiä.

K: Mitä tekniikoita käytetään hämmennyksen ja hajonnan aikaansaamiseksi?

V: Hämmennystä ja diffuusiota luodaan bittien sekoittamisella (jota kutsutaan usein permutaatiolaatikoiksi tai P-laatikoiksi) ja yksinkertaisilla epälineaarisilla funktioilla (joita kutsutaan usein substituutiolaatikoiksi tai S-laatikoiksi) sekä lineaarisella sekoittamisella (modulaarialgebran merkityksessä) XOR:n avulla. Bittien sekoittaminen luo diffuusiovaikutuksen, kun taas substituutiota käytetään sekoittamiseen.

Kysymys: Minkä tyyppinen salaus on Feistel-verkko?

V: Feistel-verkko on eräänlainen tuotesalakirjoitus, jossa yhdistetään useita toistuvia operaatiokierroksia tietojen salaamiseksi turvallisesti.

K: Kuka kehitti tämän tyyppisen salakirjoituksen?

V: Feistel-rakenteen kehitti saksalainen IBM:n salakirjoittaja Horst Feistel.

K: Perustuuko Data Encryption Standard tähän salaustyyppiin?

V: Kyllä, Data Encryption Standard käyttää tätä salausmenetelmää, jossa käytetään samoja periaatteita kuin edellä on esitetty sekaannuksen ja hajanaisuuden luomiseksi salatun viestin sisällä.