SP-netværk
Inden for kryptografi er et SP-netværk eller substitutions-permutationsnetværk (SPN) en række sammenkædede matematiske operationer, der anvendes i blokchifferalgoritmer som AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK og Square.
Et sådant netværk tager en blok af klarteksten og nøglen som input og anvender flere skiftende "runder" eller "lag" af substitutionsbokse (S-bokse) og permutationsbokse (P-bokse) for at frembringe den krypterede tekstblok. S-boxes og P-boxes omdanner (sub-)blokke af inputbits til outputbits. Det er almindeligt, at disse transformationer er operationer, der er effektive at udføre i hardware, f.eks. eksklusivt eller (XOR) og bitvis rotation. Nøglen indføres i hver runde, normalt i form af "runde nøgler", der er afledt af den. (I nogle designs afhænger selve S-boksene af nøglen).
Dekryptering sker ved simpelthen at vende processen om (ved hjælp af de omvendte S-boxes og P-boxes og ved at anvende de runde nøgler i omvendt rækkefølge).
En S-boks erstatter en lille blok af bits (S-boksens input) med en anden blok af bits (S-boksens output). Denne substitution skal være en-til-en for at sikre invertibilitet (og dermed dekryptering). Især skal outputets længde være den samme som inputets længde (billedet til højre har S-bokse med 4 input- og 4 outputbits), hvilket adskiller sig fra S-bokse generelt, der også kan ændre længden, som f.eks. i DES (Data Encryption Standard). En S-box er normalt ikke blot en permutation af bits. En god S-box har snarere den egenskab, at en ændring af en inputbit vil ændre omkring halvdelen af outputbitsene (eller en lavineeffekt). Den vil også have den egenskab, at hver udgangsbit vil afhænge af hver enkelt indgangsbit.
En P-boks er en permutation af alle bits: den tager udgangene fra alle S-boksene i en runde, permuterer bitsene og sender dem ind i S-boksene i den næste runde. En god P-boks har den egenskab, at outputbits fra en S-boks fordeles på så mange S-boksindgange som muligt.
Ved hver runde kombineres den runde nøgle (som fås fra nøglen ved hjælp af nogle enkle operationer, f.eks. ved hjælp af S-boxes og P-boxes) ved hjælp af en gruppeoperation, typisk XOR.
En enkelt typisk S-boks eller en enkelt P-boks alene har ikke megen kryptografisk styrke: en S-boks kan betragtes som en substitutionscifring, mens en P-boks kan betragtes som en transpositionscifring. Et veludformet SP-net med flere skiftende runder med S- og P-bokse opfylder imidlertid allerede Shannons forvirrings- og spredningsegenskaber:
- Grunden til udbredelsen er følgende: Hvis man ændrer en bit i klarteksten, så føres den ind i en S-boks, hvis output ændres på flere bits, så fordeles alle disse ændringer af P-boksen på flere S-bokse, og derfor ændres outputtet af alle disse S-bokse igen på flere bits, osv. I flere omgange ændres hver bit flere gange frem og tilbage, og til sidst er den krypterede tekst derfor ændret fuldstændigt på en pseudorandommæssig måde. Hvis man for en tilfældigt valgt indgangsblok vender den i-te bit, er sandsynligheden for, at den j-te udgangsbit ændres, ca. halvdelen for enhver i og j, hvilket er det strenge kriterium for en lavine. Omvendt, hvis man ændrer en bit af den krypterede tekst og derefter forsøger at dekryptere den, er resultatet en meddelelse, der er helt forskellig fra den oprindelige klartekst - SP-chifre er ikke let at ændre.
- Årsagen til forvirring er nøjagtig den samme som til diffusion: Ændring af en bit i nøglen ændrer flere af de runde nøgler, og hver ændring i hver runde nøgle spreder sig over alle bits og ændrer cifferteksten på en meget kompleks måde.
- Selv hvis en angriber på en eller anden måde får fat i én klartekst, der svarer til én ciffertekst - et angreb med kendt klartekst eller værre endnu, et angreb med valgt klartekst eller valgt ciffertekst - gør forvirringen og spredningen det vanskeligt for angriberen at genvinde nøglen.
Selv om et Feistel-netværk, der anvender S-bokse (som DES), minder meget om SP-netværk, er der nogle forskelle, som gør det ene eller det andet mere anvendeligt i visse situationer. For en given mængde forvirring og spredning har et SP-netværk mere "iboende parallelitet" og kan derfor - givet en CPU med mange eksekveringsenheder - beregnes hurtigere end et Feistel-netværk. CPU'er med få udførelsesenheder - som f.eks. de fleste smart cards - kan ikke udnytte denne iboende parallelitet. SP-krypteringer kræver også, at S-boxes skal være invertible (for at kunne dekrypteres); Feistels indre funktioner har ikke en sådan begrænsning og kan konstrueres som envejsfunktioner.
