SP tinklas
Kriptografijoje SP tinklas arba pakeitimo ir permutacijos tinklas (SPN) yra susijusių matematinių operacijų serija, naudojama blokinių šifrų algoritmuose, pavyzdžiui, AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK ir Square.
Tokiame tinkle kaip įvestis imamas atvirojo teksto blokas ir raktas, o šifro teksto blokui gauti taikomi keli pakaitiniai "raundai" arba "sluoksniai" iš pakeitimo langelių (S-box) ir permutacijos langelių (P-box). S ir P dėžutės įvesties bitų (sub)blokus paverčia išvesties bitais. Įprasta, kad šios transformacijos yra operacijos, kurias galima efektyviai atlikti aparatinėje įrangoje, pavyzdžiui, išskirtinis arba (XOR) ir bitų pasukimas. Raktas įvedamas kiekvieno raundo metu, paprastai iš jo išvestų "raktų" pavidalu. (Kai kuriose konstrukcijose patys S-taškai priklauso nuo rakto.)
Dešifravimas atliekamas paprasčiausiai pakeičiant procesą (naudojant S ir P dėžučių inversijas ir taikant raktus atvirkštine tvarka).
S-dėžutė pakeičia nedidelį bitų bloką (S-dėžutės įvestį) kitu bitų bloku (S-dėžutės išvestimi). Šis pakeitimas turėtų būti vienas su vienu, kad būtų užtikrintas apverčiamumas (taigi ir iššifravimas). Visų pirma išėjimo ilgis turėtų būti toks pat kaip ir įėjimo ilgis (paveikslėlyje dešinėje pavaizduotos S dėžutės su 4 įėjimo ir 4 išėjimo bitais), o tai skiriasi nuo S dėžučių apskritai, kurios taip pat gali keisti ilgį, kaip, pavyzdžiui, DES (Data Encryption Standard). S-box paprastai nėra paprasta bitų permutacija. Geras S-dėžutė veikiau pasižymi savybe, kad pakeitus vieną įvesties bitą pasikeičia maždaug pusė išvesties bitų (arba lavinos efektas). Ji taip pat turės savybę, kad kiekvienas išvesties bitas priklausys nuo kiekvieno įvesties bito.
P dėžutė yra visų bitų permutacija: ji paima visų vieno raundo S dėžučių išėjimus, permituoja bitus ir perduoda juos kito raundo S dėžutėms. Geras P-box turi savybę, kad bet kurio S-box išėjimo bitai paskirstomi į kuo daugiau S-box įėjimų.
Kiekvieno raundo metu rakto raktas (gautas iš rakto atlikus tam tikras paprastas operacijas, pavyzdžiui, naudojant S ir P dėžutes) sujungiamas naudojant tam tikrą grupinę operaciją, paprastai XOR.
Vienas tipinis S-box arba vienas P-box neturi didelės kriptografinės galios: S-box galima laikyti pakeitimo šifru, o P-box - perkėlimo šifru. Tačiau gerai suprojektuotas SP tinklas su keliais pakaitiniais S ir P dėžučių raundais jau tenkina Šenono painiavos ir difuzijos savybes:
- Sklaida vyksta dėl šių priežasčių: Jei pakeičiamas vienas atvirojo teksto bitas, jis patenka į S-box, kurio išėjime pasikeičia keli bitai, tada visus šiuos pakeitimus P-box paskirsto keliems S-box, todėl visų šių S-box išėjimuose vėl pasikeičia keli bitai ir t. t. Atliekant kelis raundus, kiekvienas bitas pasikeičia kelis kartus pirmyn ir atgal, todėl pabaigoje šifro tekstas pseudorandominiu būdu visiškai pasikeičia. Visų pirma, jei atsitiktinai parinktame įvesties bloke apverčiamas i-tasis bitas, tikimybė, kad pasikeis j-tasis išvesties bitas, yra apytiksliai perpus mažesnė bet kokiems i ir j, o tai yra griežtasis lavinos kriterijus. Ir atvirkščiai, pakeitus vieną šifro teksto bitą ir pabandžius jį iššifruoti, gaunamas visiškai kitoks pranešimas nei pradinis atviras tekstas - SP šifrai nėra lengvai klastojami.
- Sumaišties priežastis yra lygiai tokia pati kaip ir difuzijos: pakeitus vieną rakto bitą, pasikeičia keli raktų raktai, o kiekvienas kiekvieno rakto rakto rakto pokytis pasklinda po visus bitus ir labai sudėtingai pakeičia šifro tekstą.
- Net jei užpuolikas kokiu nors būdu gauna vieną atvirąjį tekstą, atitinkantį vieną šifro tekstą - žinomo atvirojo teksto ataka arba, dar blogiau, pasirinkto atvirojo teksto ar pasirinkto šifro teksto ataka - dėl painiavos ir sklaidos užpuolikui sunku atkurti raktą.
Nors Feistelio tinklas, kuriame naudojami S-box'ai (pvz., DES), yra gana panašus į SP tinklus, yra tam tikrų skirtumų, dėl kurių tam tikrose situacijose labiau tinka arba tas, arba anas tinklas. Esant tam tikram sumaišties ir sklaidos kiekiui, SP tinklas turi daugiau "įgimto lygiagretumo", todėl - turint procesorių su daug vykdymo vienetų - jį galima apskaičiuoti greičiau nei Feistelio tinklą. Procesoriai, turintys nedaug vykdymo vienetų, pavyzdžiui, dauguma išmaniųjų kortelių, negali pasinaudoti šiuo būdingu lygiagretumu. Be to, SP šifrai reikalauja, kad S dėžutės būtų apverčiamos (kad būtų galima atlikti dešifravimą); Feistelio vidinėms funkcijoms toks apribojimas netaikomas ir jos gali būti konstruojamos kaip vienpusės funkcijos.
