SP-nätverk
Inom kryptografi är ett SP-nätverk, eller substitution-permutationsnätverk (SPN), en serie länkade matematiska operationer som används i blockchifferalgoritmer som AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK och Square.
Ett sådant nätverk tar ett block av klartexten och nyckeln som indata och tillämpar flera omväxlande "rundor" eller "lager" av substitutionsboxar (S-boxar) och permutationsboxar (P-boxar) för att producera chiffertexten. S-boxarna och P-boxarna omvandlar (sub-)block av ingående bitar till utgående bitar. Det är vanligt att dessa omvandlingar är operationer som är effektiva att utföra i hårdvara, t.ex. exklusivt eller (XOR) och bitvis rotation. Nyckeln införs i varje omgång, vanligen i form av "omgångsnycklar" som härleds från den. (I vissa konstruktioner är själva S-boxarna beroende av nyckeln).
Avkryptering sker genom att helt enkelt vända processen (genom att använda S-boxarnas och P-boxarnas inverser och tillämpa de runda nycklarna i omvänd ordning).
En S-box ersätter ett litet block av bitar (S-boxens ingång) med ett annat block av bitar (S-boxens utgång). Denna ersättning bör vara en till en för att säkerställa inverterbarhet (och därmed dekryptering). Framför allt bör utgångslängden vara densamma som ingångslängden (i bilden till höger finns S-boxar med 4 ingångs- och 4 utgångsbitar), vilket skiljer sig från S-boxar i allmänhet som också kan ändra längden, till exempel i DES (Data Encryption Standard). En S-box är vanligtvis inte bara en permutation av bitarna. En bra S-box har snarare den egenskapen att en ändring av en ingångsbit ändrar ungefär hälften av utgångsbitarna (eller en lavinverkan). Den kommer också att ha egenskapen att varje utgångsbit kommer att bero på varje ingångsbit.
En P-box är en permutation av alla bitar: den tar utgångarna från alla S-boxar i en runda, permuterar biterna och matar dem till S-boxarna i nästa runda. En bra P-box har den egenskapen att utdatabitarna från en S-box fördelas på så många S-boxingångar som möjligt.
Vid varje runda kombineras rundnyckeln (som erhålls från nyckeln med några enkla operationer, t.ex. med hjälp av S-boxar och P-boxar) med hjälp av någon gruppoperation, vanligtvis XOR.
En enda typisk S-box eller P-box har inte mycket kryptografisk styrka: en S-box kan betraktas som ett substitutionschiffer, medan en P-box kan betraktas som ett transpositionschiffer. Ett väl utformat SP-nätverk med flera alternerande omgångar av S- och P-boxar uppfyller dock redan Shannons förvirrings- och spridningsegenskaper:
- Orsaken till spridningen är följande: Om man ändrar en bit av klartexten, matas den in i en S-box, vars utgång ändras med flera bitar, sedan distribueras alla dessa ändringar av P-boxen till flera S-boxar, vilket innebär att utgångarna från alla dessa S-boxar återigen ändras med flera bitar, och så vidare. Genom att göra flera omgångar ändras varje bit flera gånger fram och tillbaka, vilket innebär att chiffertexten i slutet har ändrats helt och hållet, på ett pseudo slumpmässigt sätt. Om man för ett slumpmässigt valt ingångsblock vänder på den i:e biten är sannolikheten för att den j:e utgångsbiten ändras ungefär hälften, för alla i och j, vilket är det strikta kriteriet för en lavin. Omvänt, om man ändrar en bit i chiffertexten och sedan försöker dekryptera den, blir resultatet ett meddelande som är helt annorlunda än den ursprungliga klartexten - SP-chiffer är inte lätt att ändra.
- Orsaken till förvirringen är exakt densamma som till spridningen: om man ändrar en bit i nyckeln ändras flera av de runda nycklarna, och varje ändring i varje runda nyckel sprids över alla bitar och ändrar chiffertexten på ett mycket komplicerat sätt.
- Även om en angripare på något sätt får tag på en klartext som motsvarar en chiffertext - en attack med känd klartext, eller ännu värre, en attack med vald klartext eller vald chiffertext - gör förvirringen och spridningen det svårt för angriparen att återskapa nyckeln.
Även om ett Feistel-nätverk som använder S-boxar (som DES) är ganska likt SP-nätverk finns det vissa skillnader som gör att det ena eller det andra är mer tillämpbart i vissa situationer. För en given mängd förvirring och spridning har ett SP-nätverk mer "inneboende parallellism" och kan därför - med en CPU med många exekveringsenheter - beräknas snabbare än ett Feistel-nätverk. Processorer med få utförarenheter - som de flesta smartkort - kan inte dra nytta av denna inneboende parallellitet. SP-krypteringar kräver också att S-boxar är inverterbara (för att kunna dekryptera). Feistels inre funktioner har ingen sådan begränsning och kan konstrueras som envägsfunktioner.
