SP-sieť
V kryptografii je sieť SP alebo substitučno-permutačná sieť (SPN) rad prepojených matematických operácií, ktoré sa používajú v algoritmoch blokových šifier, ako sú AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK a Square.
Takáto sieť prijíma blok otvoreného textu a kľúč ako vstupy a použije niekoľko striedajúcich sa "kôl" alebo "vrstiev" substitučných polí (S-boxes) a permutačných polí (P-boxes) na vytvorenie bloku šifrového textu. S-boxy a P-boxy transformujú (pod)bloky vstupných bitov na výstupné bity. Je bežné, že tieto transformácie sú operácie, ktoré sa efektívne vykonávajú v hardvéri, ako napríklad exkluzívne alebo (XOR) a bitová rotácia. Kľúč sa zavádza v každom kole, zvyčajne vo forme "kruhových kľúčov", ktoré sú z neho odvodené. (V niektorých návrhoch samotné S-boxy závisia od kľúča.)
Dešifrovanie sa vykonáva jednoduchým obrátením procesu (použitím inverzie polí S a P a použitím kruhových kľúčov v obrátenom poradí).
S-box nahrádza malý blok bitov (vstup S-boxu) iným blokom bitov (výstup S-boxu). Táto zámena by mala byť jedna k jednej, aby sa zabezpečila invertovateľnosť (teda dešifrovanie). Najmä dĺžka výstupu by mala byť rovnaká ako dĺžka vstupu (na obrázku vpravo sú S-boxy so 4 vstupnými a 4 výstupnými bitmi), čo je rozdiel oproti S-boxom vo všeobecnosti, ktoré by mohli meniť aj dĺžku, ako napríklad v DES (Data Encryption Standard). S-box zvyčajne nie je jednoduchou permutáciou bitov. Dobrý S-box bude mať skôr takú vlastnosť, že zmena jedného vstupného bitu zmení približne polovicu výstupných bitov (alebo lavínový efekt). Bude mať tiež vlastnosť, že každý výstupný bit bude závisieť od každého vstupného bitu.
P-box je permutácia všetkých bitov: berie výstupy všetkých S-boxov jedného kola, permutuje bity a vkladá ich do S-boxov ďalšieho kola. Dobrý P-box má vlastnosť, že výstupné bity ktoréhokoľvek S-boxu sú rozdelené na čo najviac vstupov S-boxu.
V každom kole sa kľúč kola (získaný z kľúča pomocou jednoduchých operácií, napríklad pomocou S-boxov a P-boxov) skombinuje pomocou niektorej skupinovej operácie, zvyčajne XOR.
Samotný typický S-box alebo P-box nemá veľkú kryptografickú silu: S-box možno považovať za substitučnú šifru, zatiaľ čo P-box možno považovať za transpozičnú šifru. Dobre navrhnutá sieť SP s niekoľkými striedajúcimi sa kolami S- a P-boxov však už spĺňa Shannonove vlastnosti zámeny a difúzie:
- Dôvodom difúzie je nasledovné: Ak sa zmení jeden bit otvoreného textu, potom sa privedie do S-boxu, ktorého výstup sa zmení na niekoľkých bitoch, potom sa všetky tieto zmeny rozdelia pomocou P-boxu medzi niekoľko S-boxov, teda výstupy všetkých týchto S-boxov sa opäť zmenia na niekoľkých bitoch atď. Pri niekoľkých kolách sa každý bit zmení niekoľkokrát tam a späť, preto sa na konci šifrový text pseudonáhodným spôsobom úplne zmení. Konkrétne pre náhodne zvolený vstupný blok, ak sa otočí i-ty bit, potom pravdepodobnosť, že sa zmení j-ty výstupný bit, je približne polovičná, pre ľubovoľné i a j, čo je prísne lavínové kritérium. A naopak, ak zmeníme jeden bit šifrového textu a potom sa ho pokúsime dešifrovať, výsledkom bude správa úplne odlišná od pôvodného otvoreného textu - šifry SP nie sú ľahko poddajné.
- Dôvod zmätku je presne taký istý ako v prípade difúzie: zmena jedného bitu kľúča zmení niekoľko kruhových kľúčov a každá zmena každého kruhového kľúča sa rozšíri na všetky bity, čím sa šifrový text zmení veľmi zložitým spôsobom.
- Aj keď útočník nejakým spôsobom získa jeden otvorený text zodpovedajúci jednému šifrovému textu - útok známym otvoreným textom, alebo ešte horšie, útok zvoleným otvoreným textom alebo zvoleným šifrovým textom - zmätok a rozptýlenie sťažujú útočníkovi obnovenie kľúča.
Hoci Feistelova sieť, ktorá využíva S-boxy (ako napríklad DES), je dosť podobná sieťam SP, existujú určité rozdiely, vďaka ktorým je v určitých situáciách použiteľnejšia buď tá, alebo tá. Pri danom množstve zmätkov a rozptylov má SP sieť viac "vrodeného paralelizmu", a tak - za predpokladu procesora s mnohými vykonávacími jednotkami - sa dá vypočítať rýchlejšie ako Feistelova sieť. Procesory s malým počtom vykonávacích jednotiek - ako napríklad väčšina inteligentných kariet - nemôžu tento inherentný paralelizmus využiť. Šifry SP tiež vyžadujú, aby boli S-boxy invertovateľné (aby bolo možné vykonať dešifrovanie); Feistelove vnútorné funkcie takéto obmedzenie nemajú a môžu byť skonštruované ako jednosmerné funkcie.
