SP-nätverk (Substitution–Permutation): Definition och funktion i blockchiffer
Lär dig om SP-nätverk (Substitution–Permutation): hur S-boxar, P-boxar och rundnycklar bygger säkra blockchiffer som AES — funktion, designprinciper och säkerhetsaspekter.
Inom kryptografi är ett SP-nätverk, eller substitution–permutationsnätverk (SPN), en standardkonstruktion för blockchiffer. Ett SP-nätverk består av flera upprepade lager (rundor) som växlar mellan icke‑linära substitutioner (S‑boxar) och linjära permutationer eller diffusioner (P‑boxar eller mixningslager). Många moderna blockchiffer använder denna struktur, till exempel AES (Rijndael), 3‑Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK och Square.
Grundläggande princip
Ett SP‑nätverk tar ett block av klartext och en nyckel som indata och applicerar flera omgångar av S‑boxar och P‑boxar tillsammans med rundnycklar som härleds från den ursprungliga nyckeln (nyckelschema). Varje runda består typiskt av:
- En icke‑linjär substitution via S‑boxar, som utför små, lokala byten av bit‑ eller bytemönster.
- En linjär diffusion eller permutation (P‑box eller mixningslager) som sprider effekten av varje bit över flera positioner.
- Inblandning av rundnyckeln, oftast med XOR, för att koppla chifferstrukturen till den hemliga nyckeln.
Avkryptering uppnås genom att vända processen: använda inverserna till S‑boxarna och P‑lagren och applicera rundnycklarna i omvänd ordning.
S‑boxar (substitution)
En S‑box ersätter ett litet block av bitar (t.ex. 4 eller 8 bitar) med ett annat block av samma längd. För att kunna dekryptera måste S‑boxen vara inverterbar (en bijektion). En väl utformad S‑box uppfyller flera kryptografiska kriterier:
- Bijektivitet (för inverterbarhet).
- Hög icke‑linearitet — för att motstå linjär kryptanalys.
- Låg differential uniformitet — vilket minskar sannolikheten för effektiva differentialattacker.
- Hög algebraisk grad och komplex algebraisk struktur — för att försvåra algebraiska attacker.
- Ingen onödig struktur (t.ex. få fasta punkter eller speglingar) som kan utnyttjas av angripare.
Praktiskt exempel: AES använder en 8‑bitars S‑box konstruerad genom en invers i GF(2^8) följt av en affinitetstransformation för att nå god icke‑linearitet och låg differential sannolikhet.
P‑boxar och mixningslager (diffusion)
En P‑box permuterar bitar mellan S‑boxarnas utgångar så att varje S‑boxs effekt sprids till många andra S‑boxar i nästa runda. I modern design används ofta linjära mixningslager (t.ex. MixColumns i AES) istället för enkla bit‑permutationer. Dessa lager är ofta representerade av matriser över ett ändligt fält och kan vara MDS‑matriser (maximum distance separable) vilket ger stark diffusionsegenskap (högt så kallat branch‑number).
Målet med diffusion är att uppnå Shannons lavin‑egenskap: en liten ändring i klartexten (eller nyckeln) ska orsaka att ungefär hälften av utgångsbitarna ändras efter tillräckligt många ronder.
Rundnyckel och nyckelschema
Nyckeln används för att härleda en serie rundnycklar som blandas in i varje runda (vanligen med XOR). Ett säkert nyckelschema ska:
- Sprida nyckelens effekter över alla ronder så att en liten ändring i nyckeln påverkar alla rundnycklar.
- Undvika öppna mönster eller symmetrier som kan utnyttjas i nyckelåterställningsattacker.
Säkerhetsprinciper och designstrategier
Ett väl designat SP‑nätverk kombinerar förvirring och spridning (confusion and diffusion) enligt Claude Shannon. Designmål och analyser inkluderar:
- Differentialkryptanalys: begränsa sannolikheten för effektiva differentialkedjor genom att använda starka S‑boxar och ett diffusionlager med högt branch‑number, samt tillräckligt många ronder.
- Linjärkryptanalys: minimera korrelationer genom hög icke‑linearitet i S‑boxarna och lämplig rondstruktur.
- Wide‑trail‑strategin (t.ex. använd av Daemen och Rijmen i AES): analysera hur aktivt antal S‑boxar utvecklas över flera ronder för att sätta nedre gränser för svårigheten i differential och linjär analys.
- Provbar säkerhet: för vissa konstruktioner går det att visa att under vissa antaganden krävs fler ronder än ett visst tröskelvärde för att möjliggöra praktiska attacker.
Praktiska exempel
- AES (Rijndael): använder 8‑bitars S‑box, byte‑permution (ShiftRows) och ett linjärt mixningslager (MixColumns). Antalet ronder är 10, 12 resp. 14 beroende på nyckellängd (128/192/256 bitar).
- PRESENT: ett lättviktschiffer som använder 4‑bitars S‑boxar och en bit‑permutation, med många ronder (t.ex. 31) för att kompensera de små S‑boxarna.
- Kuznyechik och Kalyna: moderna exempel från olika standardiseringsriktningar som visar variationer i S‑box‑storlek och diffusionstekniker.
Prestanda och implementering
SP‑nätverk har ofta god inneboende parallellism eftersom S‑boxar i en runda kan beräknas oberoende. Detta gör SP‑konstruktioner särskilt lämpade för hårdvaruaccelerering eller moderna processorer med många exekveringsenheter. I kontrast kan vissa Feistel‑konstruktioner vara svårare att parallellisera.
Samtidigt kräver SP‑nätverk att S‑boxar och linjära lager är inverterbara om dekryptering ska vara möjlig. Hårdvaru‑ och mjukvaruimplementationer måste också ta hänsyn till sido‑kanalangrepp (t.ex. timing, strömförbrukning), och speciella motåtgärder kan behövas för att undvika läckage.
Skillnad mot Feistel‑nätverk
Både SP‑nätverk och Feistel‑nätverk uppnår förvirring och spridning, men med olika egenskaper:
- Feistel‑nätverk behöver inte ha inverterbara runda funktioner (eftersom strukturen garanterar inverterbarhet), medan SP‑nätverk kräver inverterbara S‑boxar och ett inverterbart linjärt lager för att dekryptera.
- SP‑nätverk ger ofta större parallellism och kan vara snabbare på hårdvara eller breda SIMD‑arkitekturer.
- Valet mellan SP och Feistel påverkas av implementeringsmål (prestanda, kodstorlek, minne, maskinvaru‑resurser) och säkerhetskrav.
Sammanfattning
Ett SP‑nätverk är en flexibel och välstuderad arkitektur för blockchiffer som uppnår god säkerhet genom kombinationen av starka icke‑linjära S‑boxar och effektiva diffusioner. Genom noggrann design av S‑boxar, diffusionlager och nyckelschema — samt tillräckligt många ronder — kan SP‑nätverk ge motståndskraft mot de vanligaste kryptanalytiska attackerna samtidigt som de lämpar sig väl för parallella och hårdvaruaccelererade implementationer.
Sök