SP-network
W kryptografii, sieć SP lub sieć zastępczo-permutacji (SPN), to seria połączonych operacji matematycznych używanych w algorytmach szyfru blokowego, takich jak AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK i Square.
Taka sieć pobiera blok tekstu jawnego i klucza jako wejścia i stosuje kilka naprzemiennych "rund" lub "warstw" pól podmienionych (pól S) i pól permutacyjnych (pól P) do wytworzenia bloku szyfrującego. S-boxy i P-boxy przekształcają (pod-)bloki bitów wejściowych na bity wyjściowe. Wspólną cechą tych transformacji są operacje, które są wydajne sprzętowo, np. ekskluzywne lub (XOR) i obrót bitowy. Klucz jest wprowadzany w każdym obwodzie, zwykle w postaci "kluczy okrągłych" wyprowadzanych z niego. (W niektórych konstrukcjach, same S-boxy zależą od klucza).
Deszyfrowanie odbywa się poprzez proste odwrócenie procesu (przy użyciu odwrotności S-boxów i P-boxów i zastosowaniu kluczy okrągłych w odwrotnej kolejności).
S-box zastępuje mały blok bitów (wejście S-boxu) innym blokiem bitów (wyjście S-boxu). Zastąpienie to powinno być indywidualne, aby zapewnić odwracalność (stąd też odszyfrowanie). W szczególności długość wyjścia powinna być taka sama jak długość wejścia (na rysunku po prawej stronie znajdują się S-boxy z 4 bitami wejściowymi i 4 bitami wyjściowymi), co różni się od S-boxów w ogóle, które również mogą zmieniać długość, jak na przykład w DES (Data Encryption Standard). S-box zazwyczaj nie jest tylko permutacją bitów. Raczej dobry S-box będzie miał tę właściwość, że zmiana jednego bitu wejściowego zmieni około połowy bitów wyjściowych (lub efekt lawinowy). Będzie on również posiadał właściwość, że każdy bit wyjściowy będzie zależał od każdego bitu wejściowego.
P-box jest permutacją wszystkich bitów: pobiera wyjścia wszystkich S-boxów jednej rundy, permutuje bity i podaje je do S-boxów następnej rundy. Dobra P-box ma tę właściwość, że bity wyjściowe każdej S-box'y są rozdzielane na jak największą liczbę wejść S-box'ów.
Przy każdej rundzie klucz okrągły (uzyskany z klucza z kilkoma prostymi operacjami, na przykład przy użyciu S-boxów i P-boxów) jest łączony przy użyciu niektórych operacji grupowych, zazwyczaj XOR.
Pojedynczy typowy S-box lub pojedynczy P-box nie ma zbyt dużej siły kryptograficznej: S-box można by uznać za szyfr zastępczy, podczas gdy P-box można by uznać za szyfr transpozycyjny. Dobrze zaprojektowana sieć SP z kilkoma naprzemiennymi rundami S i P-boxów spełnia już jednak oczekiwania Shannon w zakresie właściwości dezorientacyjnych i dyfuzyjnych:
- Przyczyna dyfuzji jest następująca: Jeśli zmieni się jeden bit prostego tekstu, to jest on podawany do S-boxu, którego wyjście zmieni się na kilka bitów, wtedy wszystkie te zmiany są rozdzielane przez P-box na kilka S-boxów, stąd wyjścia wszystkich tych S-boxów są ponownie zmieniane na kilka bitów, i tak dalej. Wykonując kilka rund, każdy bit zmienia się kilka razy w przód i w tył, dlatego też na końcu szyfr zmienił się całkowicie, w sposób pseudolosowy. W szczególności, dla losowo wybranego bloku wejściowego, jeżeli obrócimy i-ty bit, to prawdopodobieństwo, że j-ty bit wyjściowy zmieni się w przybliżeniu o połowę, dla dowolnego i i i j, które jest kryterium "Strict Avalanche Criterion". I na odwrót, jeśli zmieni się jeden bit szyfru, a następnie spróbuje się go odszyfrować, w wyniku czego otrzymamy komunikat zupełnie inny od oryginalnego szyfru plaintext-SP, który nie jest łatwo przetwarzalny.
- Przyczyna pomyłki jest dokładnie taka sama jak w przypadku dyfuzji: zmiana jednego bitu klucza zmienia kilka okrągłych kluczy, a każda zmiana w każdym okrągłym kluczu dyfunduje na wszystkie bity, zmieniając szyfrogram w bardzo złożony sposób.
- Nawet jeśli napastnik w jakiś sposób uzyska jeden tekst jawny odpowiadający jednemu szyfrowi - atak znanego-zaszyfrowanego tekstu, lub co gorsza, atak wybranego tekstu jawnego lub wybranego-zaszyfrowanego - zamieszanie i rozproszenie utrudniają napastnikowi odzyskanie klucza.
Chociaż sieć Feistel, która wykorzystuje S-boxy (takie jak DES), jest dość podobna do sieci SP, istnieją pewne różnice, które sprawiają, że albo to, albo tamto ma większe zastosowanie w pewnych sytuacjach. Dla danej ilości zamieszania i dyfuzji, sieć SP ma więcej "wrodzonego paralelizmu", a więc - biorąc pod uwagę procesor z wieloma jednostkami wykonawczymi - może być obliczana szybciej niż sieć Feistel. Procesory z kilkoma jednostkami wykonawczymi - takie jak większość kart inteligentnych - nie mogą korzystać z tego wrodzonego paralelizmu. Również szyfratory SP wymagają, aby S-boxy były odwracalne (do dekodowania); wewnętrzne funkcje Feistel nie mają takich ograniczeń i mogą być konstruowane jako funkcje jednokierunkowe.
