SP tinklas (SPN): pakeitimo ir permutacijų tinklo apibrėžimas

SP tinklas: išsamus pakeitimo ir permutacijų tinklo (SPN) apibrėžimas, veikimo principai, S‑box/P‑box ypatybės ir taikymas blokiniuose šifruose (AES, Kalyna).

Autorius: Leandro Alegsa

14-01-2026 15:16

Kriptografijoje SP tinklas arba pakeitimo ir permutacijos tinklas (SPN) yra struktūra, sudaryta iš susijusių matematinių operacijų, plačiai naudojama blokinėse šifravimo schemose. SP tinklo idėja panaudota daugelyje žinomų algoritmų, pavyzdžiui, AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK ir Square.

Kaip veikia SP tinklas

Tokiame tinkle įvestis yra atvirojo teksto blokas ir raktas; šifro teksto blokui gauti taikoma kelios iteracijos — „raundai“ arba „sluoksniai“. Kiekviename raunde paprastai būna trys pagrindiniai žingsniai:

pakeitimas (S-dėžutės, angl. S-box),
difuzija arba permutacija (P-dėžutės, angl. P-box arba linijinė sklaidos funkcija),
raktų įtraukimas (key mixing), dažniausiai XOR operacija su subraktu).

Šios transformacijos derinamos per kelis raundus taip, kad išgautas rezultatas taptų kriptografiškai saugus. Raktas gali būti įvedamas kiekviename raunde kaip iš pradinio rakto išvesti „subraktai“ (key schedule). Kai kuriuose dizainuose netgi S-dėžutės gali priklausyti nuo rakto.

S-dėžutė (S-box)

S-dėžutė pakeičia nedidelį bitų bloką (įvestį) kitu bitų bloku (išvestimi). Praktikoje S-dėžutė dažniausiai yra bijekcija (vienas su vienu), kad būtų užtikrintas apverčiamumas ir galimybė iššifruoti. Dažnai S-dėžutės įvesties ir išvesties ilgiai sutampa (pvz., 4→4 arba 8→8 bitų), nors kai kuriuose šifruose gali būti kitoks dydis (pvz., DES S-dėžutės keičia ilgį).

Geros S-dėžutės savybės:

aukšta nelinijiškumas (sunku aproksimuoti linijinėmis funkcijomis),
mažas diferencialinis vienodumas (differential uniformity),
didelis algebraic degree (sudėtinga algebraiškiems prieštaravimams),
lavinos (avalanche) efektas — pakeitus vieną įvesties bitą, pasikeičia apytiksliai pusė išvesties bitų,
kiekvienas išvesties bitas priklauso nuo daugumos (geriausia — visų) įvesties bitų.

S-dėžutės įgyvendinamos įvairiai: kaip tiesioginės lentelės (lookup tables), arba optimizuotos skaitmeninės logikos ar sudarytos iš mažesnių funkcijų (composite field implementacijos) tam, kad sumažinti atminties poreikį arba pažeidžiamumą priekanalinių atakų (side-channel).

P-dėžutė ir linijinė difuzija

P-dėžutė paprastai atlieka bitų permutaciją arba platesnę linijinę transformaciją: ji paima visų vieno raundo S-dėžučių išėjimus, permutuoja arba sumaišo bitus ir perduoda juos kito raundo S-dėžutėms. Tikslas — paskirstyti informacijos ir klaidų poveikį per kuo daugiau S-dėžučių kitame raunde.

Šiuolaikiniai SP tinklai dažnai naudoja ne vien paprastą bitų permutaciją, bet ir matricas ar MDS (Maximum Distance Separable) transformacijas (pvz., AES MixColumns), kurios užtikrina gerą difuziją tarp baitų ar blokų. Geras P-layer užtikrina, kad bet kurio S-box išėjimo bitai būtų paskirstyti į kuo daugiau skirtingų S-box įėjimų.

Raktų įterpimas ir raktų tvarkaraštis (key schedule)

Kiekviename raunde atliekamas raktų sujungimas (dažniausiai XOR) su įvestimi arba su tarpiniu bloku. Efektyvus ir saugus raktų tvarkaraštis yra svarbi SP tinklo dalis: jis turi užtikrinti, kad subraktai nebūtų lengvai tarpusavyje susiję arba nuspėjami, kad būtų atsparu sumažintoms ar susijusių raktų atakoms (related-key attacks).

Šenono „sumaištis“ ir „sklaida“

Gerai suprojektuotas SP tinklas vykdo dviejų pagrindinių kriptografinių principų, kuriuos apibrėžė Claude Shannon, realizaciją:

Difuzija (sklaida): vieno įvesties bito pakeitimas dėl S-dėžutės ir P-dėžutės veikimo pasklinda per daugelį bitų po kelių raundų — tai lemia lavinos efektą. Kitaip tariant, pakeitus vieną atvirojo teksto bitą, galutinio šifro teksto bitai pasikeičia pseudorandominiu būdu, o tikimybė, kad koks nors konkretus išvesties bitas pasikeis, yra apie 1/2.
Sumaištis (konfuzija): raktų poveikis į šifro tekstą yra sudėtingas ir netiesinis — pakeitus vieną raktinio žodžio bitą, dėl S-dėžučių ir raktų tvarkaraščio pasikeitimų būtina daug raiškių pokyčių, kad pasikeistų šifro tekstas. Tai apsunkina ryšio tarp rakto ir šifro teksto atsekimą.

Dėl šių savybių, net jei užpuolikas turi žinomų atvirųjų tekstų ir atitinkamų šifro tekstų (known-plaintext) arba gali pasirinkti atvirą tekstą (chosen-plaintext), jam vis tiek sunku atkurti pradinį raktą.

Saugumas ir kriptanalizė

SP tinklai, kaip ir kiti blokiniai šifrai, turi būti projektuojami atspariai pagrindinėms kriptanalizės atakoms:

skirtumui pagrįsta kriptanalizė (differential cryptanalysis) — analizuoja, kaip skirtumai įvestyje lemia skirtumus išvestyje per raundus;
linijinė kriptanalizė (linear cryptanalysis) — ieško linijinių aproksimacijų tarp įvesties, išvesties ir rakto bitų;
kitos technikos: algebraiškos atakos, integral attack, boomerang ir kt.

Dizaino metodai, tokie kaip wide-trail strategy (naudota kuriant AES), padeda įvertinti, kiek raundų reikia, kad būtų įveiktos šios atakos. S-dėžučių nelinijiškumas ir P-dėžučių difuzijos laipsnis yra esminiai elementai.

Implementacija ir praktiniai aspektai

SP šifrai turi kelias praktines ypatybes:

Lygiagretumas: daug S-dėžučių ir P-dėžutės operacijų galima vykdyti lygiagrečiai, todėl SP tinklai gerai pritaikomi aparatūrinėms ir daugiaičiaškoms architektūroms. Dėl to, turint daug vykdymo vienetų, SP tinklai dažnai skaičiuojami greičiau nei Feistelio tinklai.
Atminties ir greičio kompromisas: S-dėžutės gali būti įgyvendintos per look-up lenteles (greita, bet reikalauja atminties) arba per loginių elementų tinklus (mažesnė atminties sąnauda, bet galbūt lėčiau).
Dešifravimas: kadangi SP tinklas yra apverčiamas transformacijų seka, dešifravimas reikalauja inversinių S-dėžučių ir inversinių P-dėžučių (arba inversinės linijinės funkcijos). Tai gali sudaryti papildomą reikalavimą dizainui ir įgyvendinimui.
Įrenginiai su ribotu vykdymu: mažos įvesties/vykdymo galios įrenginiai (pvz., išmaniosios kortelės) negali pilnai pasinaudoti SP tinklų lygiagrečiu dizainu ir turi kitus optimizavimo reikalavimus.
Priekanalinės atakos (side-channel): SP tinklų implementacijos turi būti saugios nuo laiko, energijos ar elektromagnetinio išsiskyrimo stebėjimo, ypač kai S-dėžutės naudojamos kaip lentelės.

Pavyzdžiai ir variantai

Konkrečiuose algoritmuose SP konceptas realizuojamas skirtingai:

AES (Rijndael) naudoja baitinę S-dėžutę (8→8) ir linijinį sluoksnį, sudarytą iš ShiftRows + MixColumns, užtikrinantį aukštą difuziją. Raundų skaičius priklauso nuo rakto ilgio.
PRESENT — lengvas SP tinklas skirtas mažai atminčiai ir energijai jautrioms sistemoms; naudoja mažas 4-bit S-dėžutes ir griežtą bitų permutaciją.
Kuznyechik, Kalyna ir kai kurie kiti standartai taip pat remiasi SP principu, tačiau pritaiko S/P sluoksnius atsižvelgdami į bloko ir rakto dydžius bei nacionalinius reikalavimus.

SP tinklas prieš Feistelio tinklą

Nors Feistelio tinklas (naudojamas pvz., DES) ir SP tinklas naudoja S-dėžutes, jie skiriasi architektūra ir specifika:

Feistelio tinklas leidžia naudoti neapverčiamas vidines funkcijas (t. y. S-dėžutės nereikia būti invertuojamos), todėl konstrukcija yra lankstesnė tam tikrose srityse.
SP tinklas reikalauja, kad visos transformacijos būtų invertuojamos dešifravimo atlikimui (išimtys — kai dešifravimo procesas pakeičiamas specialiomis inversijomis), bet dažnai siūlo daugiau įgimto lygiagrečio vykdymo, tad aparatūroje jis gali būti našesnis.
Praktikoje pasirinkimas priklauso nuo reikalavimų: efektyvumo, įgyvendinimo sąlygų, saugumo kriterijų ir dizaino patogumo.

Dizaino gairės ir geros praktikos

naudoti S-dėžutes su aukštu nelinijiškumu ir žemu diferencialiniu vienodumu;
užtikrinti, kad linijinis sluoksnis (P-layer arba Mix) būtų gerai difuzinis (pvz., turėtų aukštą branch number arba MDS savybes);
parinkti pakankamai raundų, kad būtų užblokuotos diferencinės ir linijinės atakos;
kuriant raktų tvarkaraštį, vengti silpnų arba lengvai susijusių subraktų;
implementacijoje apsvarstyti apsaugas nuo priekanalinių atakų ir klaidų atakų (fault injection).

Apibendrinant, SP tinklas yra aiški ir efektyvi blokinių šifrų struktūra: paprasti vietiniai pakeitimai (S-box) plėtojami per keletą raundų su permutacijų arba linijinių sluoksnių (P-box), kartu su raktų įtraukimu, suteikia stiprią sumaištį ir sklaidą. Tinkamai suprojektuotas SP tinklas yra atsparus daugeliui klasikinių kriptanalizės metodų ir gali būti optimizuotas tiek programiškai, tiek aparatūriškai.

Ieškoti