SP-мрежа
В криптографията SP-мрежата или мрежата от замествания и пермутации (SPN) е поредица от свързани математически операции, използвани в алгоритми за блокови шифри като AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK и Square.
Такава мрежа приема блок от открития текст и ключа като входни данни и прилага няколко редуващи се "кръга" или "слоеве" от кутии за заместване (S-boxes) и кутии за пермутация (P-boxes), за да получи блока с шифровия текст. S-boxes и P-boxes трансформират (под)блокове от входни битове в изходни битове. Обикновено тези трансформации са операции, които са ефективни за изпълнение в хардуера, като например изключващо или (XOR) и побитово завъртане. Ключът се въвежда във всеки рунд, обикновено под формата на "рундови ключове", получени от него. (В някои дизайни самите S-боксове зависят от ключа.)
Декриптирането се извършва чрез просто обръщане на процеса (използване на инверсиите на S-boxes и P-boxes и прилагане на кръговите ключове в обратен ред).
S-box замества малък блок от битове (входа на S-box) с друг блок от битове (изхода на S-box). Това заместване трябва да бъде едно към едно, за да се осигури инвертируемост (следователно и декриптиране). По-специално, дължината на изхода трябва да е същата като дължината на входа (на картинката вдясно има S-boxes с 4 входни и 4 изходни бита), което е различно от S-boxes по принцип, които могат да променят и дължината, както например в DES (Data Encryption Standard). Обикновено една S-кутия не е просто пермутация на битовете. Добрата S-кутия по-скоро има свойството, че промяната на един входен бит ще промени около половината от изходните битове (или лавинообразен ефект). Тя също така ще има свойството, че всеки изходен бит ще зависи от всеки входен бит.
P-box е пермутация на всички битове: той взема изходите на всички S-box от един рунд, пермутира битовете и ги подава към S-box на следващия рунд. Добрият P-box има свойството изходните битове на всеки S-box да се разпределят към възможно най-много входове на S-box.
На всеки рунд ключът на рунда (получен от ключа с някои прости операции, например с помощта на S-boxes и P-boxes) се комбинира с помощта на някоя групова операция, обикновено XOR.
Само един типичен S-box или един P-box няма голяма криптографска сила: S-box може да се разглежда като шифър за заместване, а P-box - като шифър за транспониране. Въпреки това една добре проектирана SP мрежа с няколко редуващи се кръга от S- и P-боксове вече удовлетворява свойствата на Шанън за объркване и дифузия:
- Причината за дифузията е следната: Ако се промени един бит от открития текст, той се подава в S-box, чийто изход ще се промени с няколко бита, след това всички тези промени се разпределят от P-box между няколко S-box, следователно изходите на всички тези S-box отново се променят с няколко бита и т.н. При няколко кръга всеки бит се променя няколко пъти напред и назад, поради което до края шифротекстът се променя напълно по псевдослучаен начин. В частност, за произволно избран входен блок, ако се обърне i-тият бит, тогава вероятността, че j-тият изходен бит ще се промени, е приблизително наполовина, за всеки i и j, което е строгият критерий за лавина. Обратно, ако се промени един бит от шифровия текст и след това се направи опит за дешифриране, резултатът е съобщение, напълно различно от оригиналния открит текст - шифрите на SP не са лесно поддаващи се на подмяна.
- Причината за объркването е точно същата като за дифузията: промяната на един бит от ключа променя няколко от кръговите ключове и всяка промяна във всеки кръгов ключ се разпространява върху всички битове, променяйки шифровия текст по много сложен начин.
- Дори ако нападателят получи по някакъв начин един чист текст, съответстващ на един шифров текст - атака с познат чист текст или още по-лошо - атака с избран чист текст или избран шифров текст - объркването и разпространението затрудняват нападателя да възстанови ключа.
Въпреки че мрежата на Feistel, която използва S-boxes (като DES), е доста подобна на SP мрежите, има някои разлики, които правят тази или онази мрежа по-приложима в определени ситуации. За дадено количество объркване и разсейване, SP мрежата има повече "присъщ паралелизъм" и така - при наличие на процесор с много изпълнителни единици - може да се изчисли по-бързо от Feistel мрежата. Процесорите с малко изпълнителни единици - като повечето смарт карти - не могат да се възползват от този присъщ паралелизъм. Също така SP шифрите изискват S-боксовете да са инвертируеми (за да се извърши декриптиране); вътрешните функции на Файстел нямат такова ограничение и могат да бъдат конструирани като еднопосочни функции.
