SP-síť
V kryptografii je síť SP nebo substitučně-permutační síť (SPN) řadou propojených matematických operací používaných v algoritmech blokových šifer, jako jsou AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK a Square.
Taková síť přijme jako vstup blok otevřeného textu a klíč a použije několik střídajících se "kol" nebo "vrstev" substitučních polí (S-boxes) a permutačních polí (P-boxes) k vytvoření bloku šifrového textu. S-boxy a P-boxy transformují (pod)bloky vstupních bitů na výstupní bity. Je běžné, že tyto transformace jsou operace, které lze efektivně provádět v hardwaru, jako je exkluzivní nebo (XOR) a bitová rotace. Klíč se zavádí v každém kole, obvykle ve formě "kruhových klíčů", které jsou od něj odvozeny. (V některých provedeních jsou na klíči závislé samotné S-boxy.)
Dešifrování se provádí jednoduše obráceným postupem (pomocí inverzí S-boxů a P-boxů a použitím kruhových klíčů v obráceném pořadí).
S-box nahrazuje malý blok bitů (vstup S-boxu) jiným blokem bitů (výstup S-boxu). Tato záměna by měla být jedna ku jedné, aby byla zajištěna invertibilita (tedy dešifrování). Zejména délka výstupu by měla být stejná jako délka vstupu (na obrázku vpravo jsou S-boxy se 4 vstupními a 4 výstupními bity), čímž se liší od S-boxů obecně, které by mohly měnit i délku, jako například v DES (Data Encryption Standard). S-box obvykle není pouhou permutací bitů. Dobrý S-box bude mít spíše tu vlastnost, že změna jednoho vstupního bitu změní přibližně polovinu výstupních bitů (neboli lavinový efekt). Bude mít také tu vlastnost, že každý výstupní bit bude záviset na každém vstupním bitu.
P-box je permutace všech bitů: vezme výstupy všech S-boxů jednoho kola, permutuje bity a vloží je do S-boxů dalšího kola. Dobrý P-box má tu vlastnost, že výstupní bity libovolného S-boxu jsou rozděleny na co nejvíce vstupů S-boxu.
V každém kole se klíč kola (získaný z klíče pomocí jednoduchých operací, například pomocí S-boxů a P-boxů) kombinuje pomocí některé skupinové operace, typicky XOR.
Samotný typický S-box nebo P-box nemá velkou kryptografickou sílu: S-box lze považovat za substituční šifru, zatímco P-box za transpoziční šifru. Dobře navržená síť SP s několika střídavými koly S- a P-boxů však již splňuje Shannonovy vlastnosti záměny a rozptylu:
- Důvodem difúze je následující: Pokud se změní jeden bit otevřeného textu, pak se přivede do S-boxu, na jehož výstupu se změní několik bitů, pak se všechny tyto změny rozdělí pomocí P-boxu mezi několik S-boxů, tudíž se na výstupech všech těchto S-boxů opět změní několik bitů atd. Při několika kolech se každý bit změní několikrát tam a zpět, proto se na konci šifrový text pseudonáhodným způsobem zcela změní. Konkrétně pro náhodně zvolený vstupní blok platí, že pokud se přehodí i-tý bit, pak pravděpodobnost, že se změní j-tý výstupní bit, je pro libovolné i a j přibližně poloviční, což je přísné lavinové kritérium. A naopak, pokud změníme jeden bit šifrového textu a pak se jej pokusíme dešifrovat, výsledkem bude zpráva zcela odlišná od původního otevřeného textu - šifry SP nejsou snadno ovlivnitelné.
- Důvod zmatení je úplně stejný jako u difúze: změna jednoho bitu klíče změní několik kruhových klíčů a každá změna každého kruhového klíče se rozptýlí po všech bitech, čímž se šifrový text změní velmi složitým způsobem.
- I když útočník nějakým způsobem získá jeden otevřený text odpovídající jednomu šifrovému textu - útok známým otevřeným textem, nebo ještě hůře, útok zvoleným otevřeným textem nebo zvoleným šifrovým textem - zmatení a rozptýlení ztěžují útočníkovi obnovení klíče.
Ačkoli Feistelova síť, která používá S-boxy (jako je DES), je dosti podobná sítím SP, existují některé rozdíly, které v určitých situacích umožňují lepší použití buď toho, nebo onoho. Při daném množství záměny a rozptylu má síť SP více "inherentního paralelismu", a tak - za předpokladu procesoru s mnoha prováděcími jednotkami - může být vypočtena rychleji než Feistelova síť. Procesory s malým počtem exekučních jednotek - jako je většina čipových karet - nemohou tento inherentní paralelismus využít. Také SP šifry vyžadují, aby S-boxy byly inverzní (aby bylo možné provést dešifrování); Feistelovy vnitřní funkce takové omezení nemají a mohou být konstruovány jako jednosměrné funkce.
