Feistel-salaus symmetrinen lohkosalakirjoitus ja rakenne

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-rakenne on perusrakenteena monille tunnetuille salausalgoritmeille, koska se tarjoaa helposti toteutettavan tavan rakentaa käännettävä (invertible) lohkokirjoitus käyttäen ei-välttämättä käännettäviä osafunktioita.

Mikä on Feistel-rakenne?

Feistel-verkko on iteroitu lohkokirjoitusrakenne, jossa selväteksti jaetaan tyypillisesti kahteen yhtä suureen osaan: vasempaan (L) ja oikeaan (R) puolikkaaseen. Rakenteessa toistetaan useita kierroksia (round), ja jokainen kierros muuntaa osia käyttäen alifunktiota (kierrosfunktio) ja alavaimia (subkeys) avaimen aikataulusta. Rakenteen yksi keskeinen ominaisuus on, että salaus voidaan kumota samalla rakenteella ja samoilla alifunktioilla, kun alavaimojen järjestys vain käännetään — tästä seuraa tehokas implementaatio sekä ohjelmisto- että laitteistotasolla.

Kuinka Feistel-verkko toimii (yksittäinen kierros)

Yksinkertaistetusti yhden kierroksen operaatiot ovat:

Syötteenä L_{i-1} ja R_{i-1} (edellisen kierroksen tulokset).
L_i = R_{i-1}.
R_i = L_{i-1} XOR F(R_{i-1}, K_i), jossa F on kierrosfunktio ja K_i on kierroksen alavain.

Tämä rakenne takaa, että koko kierros on käännettävissä, koska XOR-operaatio on kääntyvä ja vasemman ja oikean puolikkaan vaihto on helposti peruutettavissa, kun alavaimat käytetään käänteisessä järjestyksessä purussa.

Kierrosfunktio ja komponentit

Feistel-verkot käyttävät usein 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. Kierrosfunktio F voi sisältää esimerkiksi S-laatikoita, permutaatioita, modulaarisia yhteenlaskuja tai muita epälineaarisia operaatioita. Tärkeää on, että F tuo epälineaarisuutta, koska ilman sitä verkko olisi alttiimpi analyyseille, kuten lineaariselle tai differentiaaliselle kryptanalyysille.

Ominaisuudet ja edut

Invertoitavuus ilman käänteisiä osafunktioita: Feistel-rakenne mahdollistaa sen, että koko lohkokirjoitus on käännettävissä vaikka kierrosfunktio F ei itsessään olisi käännettävissä.
Yhtenäinen toteutus: Salaus- ja purkuoperaatiot ovat rakenteellisesti lähellä toisiaan; purku saadaan käyttämällä samoja kierrosfunktioita mutta kääntämällä alavaimojen järjestys.
Hyvä diffuusio ja sekoittuminen: Yhdistämällä P-laatikoita, S-laatikoita ja XOR-operaatioita saavutetaan Shannonin kuvailema sekaannus ja hajanaisuus, mikä tekee salatusta tekstistä vaikeasti ennustettavaa.
Skaalautuvuus: Kierrosten määrää voi lisätä tai vähentää halutun turvallisuustason mukaan; tyypillisiä toteutuksia käyttävät esimerkiksi 8–32 tai enemmän kierroksia riippuen algoritmista.
Helppo laitteistototeutus: Iteratiivinen rakenne sopii hyvin piirirakenteisiin ja pipelinettyihin toteutuksiin.

Käyttöesimerkkejä

Feistel-rakennetta käyttävät monet tunnetut algoritmit. Esimerkkiarkkitehtuureja ovat muun muassa DES, Blowfish, CAST- ja monet muut vanhemmat sekä joistain tapauksista johdetut lohkosalausalgoritmit. Eri algoritmit eroavat käytettyjen S-laatikoiden, permutaatioiden, kierrosfunktion monimutkaisuuden ja alavaimojen generointitavan (avaimen aikataulu) osalta.

Turvallisuus ja suunnittelu

Feistel-verkkojen turvallisuus riippuu ensisijaisesti kierrosfunktion laadusta, S-laatikoiden epälineaarisuudesta, alavaimojen riippumattomuudesta sekä kierrosten määrästä. Hyvin suunnitellut S-laatikot ja riittävä määrä kierroksia auttavat vastustamaan differential- ja linear-kryptanalyysiä. Avaimen aikataulun (key schedule) heikkoudet voivat johtaa heikkoihin tai ristikkäisiin avaimiin, joten sen suunnittelu on olennainen osa turvallisuutta — tästä syystä joidenkin algoritmien turvallisuus heikkenee, jos avaimen aikataulu on liian heikko tai altis symmetrialle.

Variantiot ja laajennukset

Perinteisen (tasapainotetun) Feistel-verkon lisäksi on olemassa myös epätasapainotettuja Feistel-verkkoja, joissa L- ja R-osiot eivät ole yhtä suuria, sekä ristiin-sekoittavia (generalized) Feistel-rakenteita, joissa kierrosfunktiot ja vaihdot voidaan toteuttaa moninaisemmin. Joissain moderneissa rakenteissa käytetään hybridimuotoja, jotka yhdistävät Feistelin ja substituutio-permutaatioverkkojen (SPN) elementtejä.

Yhteenveto

Feistel-salaus on monikäyttöinen ja tehokas tapa rakentaa käännettävä lohkokirjoitus. Sen etuina ovat helppo toteutus, selkeä purkuprosessi (alavaimojen käännöllä) ja mahdollisuus käyttää monimutkaisia, epälineaarisia kierrosfunktioita ilman, että itse funktioiden tarvitsee olla käännettäviä. Kuitenkin turvallisuus perustuu aina huolelliseen suunnitteluun: riittävään määrä kierroksia, hyvin valittuihin S-laatikkoihin, ja vahvaan avaimen aikatauluun.

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ä.