SP-omrežje
V kriptografiji je omrežje SP ali omrežje substitucije in permutacije (SPN) niz povezanih matematičnih operacij, ki se uporabljajo v algoritmih blokovnih šifer, kot so AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK in Square.
Takšno omrežje vzame blok odprtega besedila in ključ kot vhoda ter uporabi več izmeničnih "krogov" ali "slojev" substitucijskih polj (S-box) in permutacijskih polj (P-box), da dobi blok šifriranega besedila. S-boxi in P-boxi preoblikujejo (pod)bloke vhodnih bitov v izhodne bite. Običajno so te pretvorbe operacije, ki jih je mogoče učinkovito izvajati v strojni opremi, kot sta ekskluzivna ali (XOR) in bitna rotacija. Ključ se uvede v vsakem krogu, običajno v obliki "krožnih ključev", ki so izpeljani iz njega. (V nekaterih izvedbah so od ključa odvisna tudi sama polja S.)
Dešifriranje se izvede s preprosto obrnjenim postopkom (z uporabo inverzij polj S in P ter uporabo okroglih ključev v obrnjenem vrstnem redu).
S-box zamenja majhen blok bitov (vhod S-boxa) z drugim blokom bitov (izhod S-boxa). Ta zamenjava mora biti ena proti ena, da se zagotovi invertibilnost (torej dešifriranje). Zlasti dolžina izhoda mora biti enaka dolžini vhoda (na sliki na desni so S-boxi s 4 vhodnimi in 4 izhodnimi biti), kar se razlikuje od S-boxov na splošno, ki lahko spreminjajo tudi dolžino, kot na primer v DES (Data Encryption Standard). Polje S običajno ni preprosto permutacija bitov. Dober S-box ima prej lastnost, da sprememba enega vhodnega bita spremeni približno polovico izhodnih bitov (ali lavinski učinek). Ima tudi lastnost, da je vsak izhodni bit odvisen od vsakega vhodnega bita.
P-box je permutacija vseh bitov: vzame izhode vseh S-boxov enega kroga, permutacijo bitov in jih pošlje v S-boxe naslednjega kroga. Dober P-box ima lastnost, da so izhodni biti kateregakoli S-boxa porazdeljeni na čim več vhodov S-boxa.
V vsakem krogu se krožni ključ (pridobljen iz ključa z nekaterimi preprostimi operacijami, na primer z uporabo S-boxov in P-boxov) združi z neko skupinsko operacijo, običajno XOR.
Samo en tipičen S-box ali en sam P-box nima velike kriptografske moči: na S-box lahko gledamo kot na substitucijsko šifro, na P-box pa kot na transpozicijsko šifro. Vendar pa dobro zasnovano omrežje SP z več izmeničnimi krogi S- in P-boxov že izpolnjuje Shannonovi lastnosti zamenjave in razpršitve:
- Razlog za difuzijo je naslednji: Če spremenimo en bit odprtega besedila, se ta bit vnese v polje S, katerega izhod se spremeni za več bitov, nato vse te spremembe polje P razdeli med več polj S, zato se izhodi vseh teh polj S spet spremenijo za več bitov in tako naprej. V več krogih se vsak bit večkrat spremeni sem in tja, zato se na koncu šifrirano besedilo popolnoma spremeni na psevdorandomni način. Če za naključno izbran vhodni blok obrnemo i-ti bit, je verjetnost, da se bo spremenil j-ti izhodni bit, za vsak i in j približno polovična, kar je strogo lavinsko merilo. In obratno, če spremenimo en bit šifriranega besedila in ga nato poskušamo dešifrirati, je rezultat sporočilo, ki je popolnoma drugačno od prvotnega odprtega besedila - šifre SP niso zlahka prilagodljive.
- Razlog za zmedo je popolnoma enak kot pri difuziji: sprememba enega bita ključa spremeni več krožnih ključev in vsaka sprememba vsakega krožnega ključa se razširi na vse bite, kar zelo kompleksno spremeni šifrirano besedilo.
- Tudi če napadalec nekako pridobi eno navadno besedilo, ki ustreza enemu šifrirnemu besedilu - napad z znanim navadnim besedilom ali, še huje, napad z izbranim navadnim besedilom ali izbranim šifrirnim besedilom -, mu zmeda in razpršitev otežita obnovitev ključa.
Čeprav je Feistelovo omrežje, ki uporablja škatle S (kot je DES), precej podobno omrežjem SP, obstajajo nekatere razlike, zaradi katerih je v določenih primerih bolj uporabno to ali ono. Pri dani količini zmede in razpršitve ima omrežje SP več "inherentnega paralelizma", zato ga je mogoče - ob upoštevanju procesorja z veliko izvedbenimi enotami - izračunati hitreje kot omrežje Feistel. Procesorji z malo izvedbenimi enotami - kot je večina pametnih kartic - tega inherentnega paralelizma ne morejo izkoristiti. Šifre SP zahtevajo tudi, da so polja S invertibilna (za izvedbo dešifriranja); Feistelove notranje funkcije nimajo take omejitve in jih je mogoče konstruirati kot enosmerne funkcije.
