SP-hálózat
A kriptográfiában az SP-hálózat vagy szubsztitúciós-permutációs hálózat (SPN) olyan összekapcsolt matematikai műveletek sorozata, amelyeket olyan blokkos titkosítási algoritmusokban használnak, mint az AES (Rijndael), 3-Way, Kalyna, Kuznyecsik, PRESENT, SAFER, SHARK és Square.
Egy ilyen hálózat bemenetként a nyílt szöveg egy blokkját és a kulcsot veszi, és több váltakozó "kört" vagy "réteget" alkalmaz a helyettesítési dobozokból (S-dobozok) és a permutációs dobozokból (P-dobozok) a rejtjelezett szövegblokk előállításához. Az S-dobozok és a P-dobozok a bemeneti bitek (al)blokkjait kimeneti bitekké alakítják át. Ezek a transzformációk általában olyan műveletek, amelyek hardveresen hatékonyan elvégezhetők, mint például a kizárólagos vagy (XOR) és a bitenkénti forgatás. A kulcsot minden fordulóban bevezetik, általában a belőle származtatott "forduló kulcsok" formájában. (Egyes konstrukciókban maguk az S-dobozok is a kulcstól függenek).
A visszafejtés egyszerűen a folyamat megfordításával történik (az S-dobozok és a P-dobozok inverzeinek felhasználásával és a körkulcsok fordított sorrendben történő alkalmazásával).
Egy S-box egy kis bitblokkot (az S-box bemenete) egy másik bitblokkal (az S-box kimenete) helyettesít. Ennek a helyettesítésnek egy az egyhez kell lennie, hogy biztosítsa a megfordíthatóságot (tehát a dekódolást). Különösen a kimenet hosszának meg kell egyeznie a bemenet hosszával (a jobb oldali képen 4 bemeneti és 4 kimeneti bitet tartalmazó S-dobozok vannak), ami eltér az általános S-dobozoktól, amelyek a hosszúságot is megváltoztathatják, mint például a DES (Data Encryption Standard). Egy S-doboz általában nem egyszerűen a bitek permutációja. Egy jó S-doboz inkább azzal a tulajdonsággal rendelkezik, hogy egy bemeneti bit megváltoztatása a kimeneti bitek körülbelül felét változtatja meg (vagy lavinahatás). Az a tulajdonsága is megvan, hogy minden kimeneti bit minden bemeneti bit függvénye.
A P-doboz az összes bit permutációja: egy kör összes S-dobozának kimenetét veszi, a biteket permuttálja, és a következő kör S-dobozaiba táplálja. A jó P-doboznak az a tulajdonsága, hogy bármely S-doboz kimeneti bitjei a lehető legtöbb S-doboz bemenetére oszlanak el.
Minden egyes fordulóban a forduló kulcsát (amelyet a kulcsból néhány egyszerű művelettel, például S- és P-dobozok használatával kapunk) valamilyen csoportos művelettel, jellemzően XOR-ral kombináljuk.
Egyetlen tipikus S-doboz vagy egyetlen P-doboz önmagában nem rendelkezik nagy kriptográfiai erővel: egy S-dobozra úgy lehet gondolni, mint egy helyettesítési rejtjelezőre, míg egy P-dobozra úgy, mint egy transzpozíciós rejtjelezőre. Egy jól megtervezett SP-hálózat azonban, amelyben az S- és P-dobozok több körös váltakozásával már kielégíti a Shannon-féle zavarossági és diffúziós tulajdonságokat:
- A diffúzió oka a következő: Ha valaki megváltoztatja a plaintext egy bitjét, akkor az egy S-boxba kerül, amelynek kimenete több bitben is megváltozik, majd ezeket a változásokat a P-box több S-box között szétosztja, így az összes ilyen S-box kimenete ismét több bitben változik, és így tovább. Több menetben minden egyes bit többször változik oda-vissza, ezért a végére a rejtjelezett szöveg teljesen megváltozik, álvéletlenszerűen. Egy véletlenszerűen kiválasztott bemeneti blokk esetében, ha az i-edik bitet megfordítjuk, akkor annak valószínűsége, hogy a j-edik kimeneti bit megváltozik, körülbelül fele, bármilyen i és j esetén, ami a szigorú lavinakritérium. Fordítva, ha megváltoztatjuk a rejtjelezett szöveg egy bitjét, majd megpróbáljuk azt visszafejteni, az eredmény egy, az eredeti nyílt szövegtől teljesen eltérő üzenet lesz - a SP-kódok nem könnyen alakíthatók.
- A zavar oka pontosan ugyanaz, mint a diffúzióé: a kulcs egy bitjének megváltoztatása több körkulcsot is megváltoztat, és minden egyes körkulcsban bekövetkező változás az összes bitre átterjed, így a rejtjelezett szöveg nagyon összetett módon változik.
- Még ha a támadó valahogyan meg is szerez egy rejtjelezett szövegnek megfelelő egyszerű szöveget - ez egy ismert egyszerű szöveges támadás, vagy ami még rosszabb, egy választott egyszerű szöveges vagy választott rejtjelezett szöveges támadás -, a zavar és a diffúzió megnehezíti a támadó számára a kulcs visszaszerzését.
Bár az S-dobozokat használó Feistel-hálózat (mint például a DES) meglehetősen hasonlít az SP-hálózatokhoz, van néhány különbség, amely bizonyos helyzetekben ezt vagy azt teszi alkalmazhatóbbá. Egy SP-hálózat adott mennyiségű zavar és diffúzió esetén több "eredendő párhuzamossággal" rendelkezik, és így - egy sok végrehajtó egységgel rendelkező CPU esetén - gyorsabban kiszámítható, mint egy Feistel-hálózat. A kevés végrehajtó egységgel rendelkező CPU-k - mint például a legtöbb intelligens kártya - nem tudják kihasználni ezt a belső párhuzamosságot. Az SP-kódok továbbá megkövetelik, hogy az S-dobozok invertálhatók legyenek (a visszafejtés elvégzéséhez); a Feistel belső függvényeknél nincs ilyen korlátozás, és egyirányú függvényként is megkonstruálhatók.
