SP-verkko (substituutio–permutaatioverkko): määritelmä ja lohkosalausten periaate
SP-verkko (substituutio–permutaatioverkko): selkeä ja syvä selitys lohkosalauksen periaatteista, S- ja P-laatikoista, AES-yhteyksistä ja turvallisuusominaisuuksista.
SP-verkko eli substitution–permutaatioverkko (engl. substitution–permutation network, SPN) on lohkosalausalgoritmien rakenne, jossa syöte muunnetaan salaukseksi vuorottelevilla korvaus- ja permutaatiovaiheilla. Tunnettuja SP-verkkoihin perustuvia algoritmeja ovat esimerkiksi AES (Rijndael), 3‑Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK ja Square.
Malli ja periaate
SP-verkko käsittelee selkotekstilohkon ja avaimen ja suorittaa useita kierroksia. Jokaisella kierroksella on tyypillisesti kaksi päävaihetta:
- substituutio (S‑laatikot) — pienet, ei-lineaariset korvausfunktiot, ja
- permutaatiovaihe (P‑laatikko) — bittien tai tavualueiden järjestyksen sekoitus ja jakelu seuraaviin S‑laatikkoihin.
Kierrosavaimet (yleensä kierroksista johdetut alkiot pääavaimesta) yhdistetään dataan typillisesti XOR‑operaatiolla ennen tai jälkeen S‑ ja P‑vaiheiden. Salaus puretaan kääntämällä prosessin vaiheet ja käyttämällä S‑laatikkojen sekä P‑laatikon käänteisfunktioita sekä soveltamalla kierrosavaimia käänteisessä järjestyksessä.
S-laatikko (substituutio)
S-laatikko korvaa pienen bittijoukon (esim. 4 tai 8 bittiä) toisella bittijoukolla. Käänteistettävyyden varmistamiseksi korvaus halutaan yleensä yksi‑yhteen (bijektio), jolloin pureminen on mahdollista. Monet SP‑verkot käyttävät S‑laatikkoja, joiden sisääntulo- ja ulostulopituus on sama (esim. AES:n 8→8 S‑laatikko).
Hyvä S‑laatikko on ei‑lineaarinen ja täyttää ominaisuuksia, jotka vaikeuttavat matemaattisia hyökkäyksiä:
- korkea ei‑lineaarisuus (vähentää lineaarikryptanalyysin tehokkuutta),
- alhainen differentiaalinen yhtenäisyys (vähentää differentiaali‑kryptanalyysin hyötyä), ja
- avalanche‑ominaisuus (pieni syötteen muutos vaikuttaa noin puoleen lähtöbineistä).
P-laatikko (permutaatio)
P-laatikko on lineaarinen vaihe, joka permutoi kierroksen kaikkien S‑laatikkojen ulostulobitit ja jakaa ne seuraavien S‑laatikkojen syötteiksi. Tavoitteena on levittää yhden S‑laatikon vaikutus mahdollisimman laajalle seuraavissa kierroksissa, eli parantaa diffuusiota. Hyvin suunnitellulla P‑laatikolla minkä tahansa S‑laatikon ulostulobitit päätyvät eri S‑laatikkojen syötteisiin seuraavalla kierroksella.
Kierrosavaimet ja avaimenlevitys
Jokaisella kierroksella käytettävä kierroksen avain johdetaan pääavaimesta avainlaajennusalgoritmilla (key schedule). Avainlaajennuksen suunnittelulla on suuri merkitys; huonosti suunniteltu avainlaajennus voi heikentää koko salausalgoritmin turvallisuutta esimerkiksi tekemällä siitä alttiimman tunnetuille selkoteksti‑hyökkäyksille tai palauttamattomuusvirheille.
Shannonin sekaannus- ja diffuusio‑ominaisuudet
Hyvin suunniteltu SP‑verkko täyttää Claude Shannonin määrittelemät sekaannus (confusion) ja diffuusio (diffusion) -vaatimukset:
- Diffuusio: P‑laatikko levittää pienten muutosten vaikutuksen useisiin S‑laatikkoihin, ja toistuvat S‑ ja P‑vaiheet varmistavat, että yksittäinen syötebitin muutos vaikuttaa lopulliseen salatekstiin laajasti. Tämä synnyttää lumivyörytunnuksen (avalanche), missä yhden syötebitin muuttaminen muuttaa noin puolet lähtöbineistä usean kierroksen jälkeen.
- Sekaannus: S‑laatikot tuottavat ei‑lineaarisuutta siten, että avaimen ja salatun tekstin välinen riippuvuus on monimutkainen ja epälineaarinen. P‑laatikon kanssa tämä piilottaa avaimen rakenteen tehokkaasti.
Turvallisuus ja käytännön suunnittelu
SP‑verkkojen turvallisuus riippuu S‑laatikkojen ominaisuuksista, kierrosten määrästä sekä avainlaajennuksesta. Useita hyökkäystyyppejä arvioidaan suunnitteluvaiheessa, esimerkiksi differentiaali‑ ja lineaarikryptanalyysi sekä avainhyökkäykset. Käytännössä suunnittelijat valitsevat riittävän määrän kierroksia siten, että mahdolliset hyökkäysmenetelmät eivät saavuta tarvittavaa tilastollista etua.
Suunnittelussa huomioidaan myös suorituskyky ja toteutusympäristö: SP‑verkot tarjoavat usein luonnostaan rinnakkaistettavissa olevia operaatioita (monta S‑laatikkoa samaan aikaan), mikä hyödyttää laitteistoa ja laajaa SIMD/ASIMD‑suorituskykyä. Toisaalta esimerkiksi älykorteissa, joissa rinnakkaisuutta on vähän, Feistel‑rakenteet voivat olla kilpailukykyisiä.
Resistanssi hyökkäyksiä vastaan
Hyvin suunnitellut S‑laatikot ja riittävä kierrosmäärä tekevät SP‑verkoista vastustuskykyisiä differentiaali‑ ja lineaarikryptanalyysille. Lisäksi avainlaajennuksen ominaisuudet (esimerkiksi hyvä sekoittuminen ja eri kierrosten avainten monimutkainen riippuvuus pääavaimesta) estävät avaimen helpon rekonstruoinnin tunnetuista selkoteksti–salateksti‑pareista.
Vertailu Feistel‑verkkoihin
Feistel‑rakenteet (kuten DES) ja SP‑verkot jakavat periaatteessa samaa ideaa: sekoitus ja diffuusio vuorottelevat. Erona on, että Feistel‑verkossa kierroksen sisäinen funktio ei tarvitse olla käänteinen, koska kokonaissalaus käännetään vaihtamalla puolikkaat ja käyttämällä kierrosfunktioiden tuloksia oikeassa järjestyksessä. SP‑verkossa S‑laatikkojen ja P‑laatikon yhdistelmän on yleensä oltava käännettävissä, joten yksittäiset S‑laatikot ovat usein bijektioita. SP‑verkot voivat hyödyntää rinnakkaisuutta tehokkaammin, joten ne voivat olla nopeampia laitteissa ja prosessoreissa, joissa on useita suoritusyksiköitä, kun taas Feistel‑rakenteet sopivat hyvin ympäristöihin, joissa rinnakkaisuutta on vähän.
Käytännön esimerkkejä
AES on käytännön esimerkki SP‑tyyppisestä arkkitehtuurista: sen kierroksiin kuuluvat SubBytes (S‑laatikko), ShiftRows ja MixColumns (lineaarinen diffuusiovaihe, joka täyttää saman roolin kuin P‑laatikko) sekä AddRoundKey. Pienemmät, kevyet lohkosalaimet kuten PRESENT käyttävät hyvin pieniä S‑laatikkoja ja bititason permutaatioita soveltuen laitteistoihin ja sulautettuihin järjestelmiin.
Yhteenvetona: SP‑verkko on joustava ja tehokas rakenne lohkosalaussuunnittelussa. Sen turvallisuus perustuu huolella valittuihin S‑laatikkoihin, tehokkaaseen P‑laatikkoon, riittävään kierrosmäärään ja turvalliseen avainlaajennukseen.
Etsiä