SP-võrk

Krüptograafias on SP-võrk ehk substitutsioonipermutatsioonivõrk (SPN) rida omavahel seotud matemaatilisi operatsioone, mida kasutatakse sellistes plokkšifreeringutes nagu AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK ja Square.

Selline võrk võtab sisendiks lihtteksti ploki ja võtme ning kasutab salateksti ploki saamiseks mitmeid vaheldumisi "ringe" või "kihte", mis koosnevad asenduskastidest (S-kastid) ja permutatsioonikastidest (P-kastid). S- ja P-kastid muudavad sisendbittide (alam)plokid väljundbittideks. Tavaliselt on need teisendused sellised operatsioonid, mida on riistvaras tõhus teostada, näiteks eksklusiivne või (XOR) ja bittide pööramine. Võti võetakse kasutusele igas voorus, tavaliselt sellest tuletatud "vooru võtmete" kujul. (Mõnes konstruktsioonis sõltuvad S-kastid ise võtmest).

Dekrüpteerimine toimub lihtsalt protsessi ümberpööramise teel (kasutades S- ja P-kastide inversioone ja rakendades ringvõtmeid vastupidises järjekorras).

S-box asendab väikese bittide ploki (S-boxi sisend) teise bittide plokiga (S-boxi väljund). See asendamine peaks olema üks-ühele, et tagada inverteeritavus (seega ka dekrüpteerimine). Eelkõige peaks väljundi pikkus olema sama, mis sisendi pikkus (paremal oleval pildil on S-kastid 4 sisend- ja 4 väljundbitiga), mis erineb S-kastidest üldiselt, mis võivad ka pikkust muuta, nagu näiteks DESis (Data Encryption Standard). S-box ei ole tavaliselt lihtsalt bittide permutatsioon. Pigem on heal S-boxil selline omadus, et ühe sisendbiti muutmine muudab umbes pool väljundbittidest (ehk laviini efekt). Samuti on tal omadus, et iga väljundbit sõltub igast sisendbitist.

P-kast on kõigi bittide permutatsioon: see võtab ühe vooru kõikide S-kastide väljundid, muudab bittide arvu ja sisestab need järgmise vooru S-kastidesse. Heal P-kastil on omadus, et iga S-kasti väljundbitid jaotatakse võimalikult paljudele S-kasti sisenditele.

Igas voorus kombineeritakse vooru võti (mis saadakse võtmest mõne lihtsa operatsiooniga, näiteks S- ja P-kastide abil), kasutades mõnda grupioperatsiooni, tavaliselt XOR.

Üksik tüüpiline S-kast või üksik P-kast üksi ei ole eriti tugev krüptograafiliselt: S-kasti võib pidada asendussalakirjaks, P-kasti aga transpositsioonisalakirjaks. Hästi kavandatud SP-võrk, kus S- ja P-kastid vahelduvad mitmes voorus, vastab aga juba Shannoni segaduse ja hajuvuse omadustele:

• Hajutamise põhjus on järgmine: Kui üks bitt muudetakse lihtkirjas, siis sisestatakse see S-boksi, mille väljund muutub mitmes bitis, seejärel jaotab P-boks kõik need muudatused mitme S-boksi vahel, seega kõigi nende S-bokside väljundid muutuvad jälle mitmes bitis jne. Mitu ringi tehes muutub iga bitt mitu korda edasi-tagasi, seega on salatekst lõpuks täielikult muutunud, pseudorandomaalselt. Kui juhuslikult valitud sisendploki puhul pööratakse i-ndat bitti, siis on tõenäosus, et j-ndat väljundbitti muudetakse umbes poole võrra, mis tahes i ja j puhul, mis on rangeks Avalanche-kriteeriumiks (Strict Avalanche Criterion). Vastupidiselt, kui muuta üks bit salakirjas ja seejärel püüda seda dekrüpteerida, on tulemuseks algsest selgeks tekstist täiesti erinev sõnum - SP-kodeeringud ei ole kergesti muudetavad.
• Segaduse põhjus on täpselt sama, mis difusiooni puhul: võtme ühe biti muutmine muudab mitmeid ringvõtmeid ja iga muutus igas ringvõtmes levib üle kõigi bittide, muutes salakirjateksti väga keerulisel viisil.
• Isegi kui ründaja saab kuidagi kätte ühe salatekstile vastava lihtteksti - tuntud lihtteksti rünnak või, mis veelgi hullem, valitud lihtteksti või valitud salateksti rünnak -, on ründajal tänu segadusele ja levikule raske võtit taastada.

Kuigi Feisteli võrk, mis kasutab S-karpe (nagu DES), on üsna sarnane SP-võrkudega, on mõningaid erinevusi, mis muudavad kas selle või teise võrgu teatud olukordades paremini kohaldatavaks. SP-võrgul on antud segaduse ja hajutamise korral rohkem "loomupärast paralleelsust" ja seega - arvestades paljude täitmisüksustega protsessorit - saab seda arvutada kiiremini kui Feisteli võrku. Väheste täitmisüksustega protsessorid - nagu enamik kiipkaarte - ei saa seda loomupärast paralleelsust ära kasutada. Samuti nõuavad SP-kodeeringud, et S-kastid oleksid inverteeritavad (et teha dekrüpteerimist); Feisteli sisemistel funktsioonidel ei ole sellist piirangut ja neid saab konstrueerida ühesuunaliste funktsioonidena.

Otsing