SP мережа або мережа замін перестановок англ substitution permutation network це ряд пов язаних математичних операцій що

SP-мережа, або мережа замін-перестановок (англ. substitution-permutation network) — це ряд пов'язаних математичних операцій що використовуються в блочних шифрах, наприклад AES. SP-мережу також використовують , SAFER, SHARK, і .

Схема трираундової мережі замін-перестановок, що шифрує 16 біт вхідного тексту в 16 біт вихідного. S-скрині — *S_i*’s, P-скрині — P і ключ раунду — *K_i*.

Така мережа приймає блок відкритого тексту і ключ на вході, і застосовує декілька «раундів» S-скринь і які чергуються для отримання блоку шифротексту. S- і P-скрині перетворють підблоки вхідних бітів на вихідні біти. Ці операції обираються такими щоб бути зручними для ефективного втілення в залізі, наприклад додавання за модулем 2 (XOR) і . Ключ вводиться в кожному раунді, зазвичай у вигляді ключа раунду (англ. round keys) похідного від нього. (Іноді самі S-скрині залежать від ключа.)

Розшифрування здійснюється зворотнім процесом (використанням обернених S- і P-скринь і застосуванням ключів раундів у зворотному порядку).

S-скриня замінює маленький блок бітів (дані на вході) на інший блок бітів (дані на виході). Ця заміна має бути однозначною, для гарантування оборотності (відповідно розшифрування). Зокрема довжина даних на вході може збігатись із довжиною даних на виході (зображення праворуч містить S-скрині для 4 біт на вході і виході), що не завжди має місце для S-скриньок, які також можуть змінювати довжину, наприклад DES. S-скрині це зазвичай не просто перестановка бітів. Вдала S-скринька має властивість змінювати близько половини бітів на виході через зміну одного біту на вході (лавиновий ефект). Також вона матиме властивість залежності кожного біту на виході від кожного біту на вході.

P-скриня — перестановка всіх бітів: вона отримує вихідні дані усіх S-скриньок поточного раунду, переставляє біти і передає результат S-скринькам наступного раунду. Хороша P-скриня має властивість: вихід будь-якої S-скрині розподіляється між якнайбільшою кількістю S-скринь наступного раунду.

На кожному раунді ключ раунду (отриманий з ключа за допомогою простих дій, наприклад, із використанням S- і P-скринь) додається через якусь просту групову дію, зазвичай XOR.

Одна S- або P-скриня не має особливої криптостійкості: S-скриню можна розглядати як підстановочний шифр, а P-скриню як перестановочний шифр. Однак, добре продумана SP-мережа з кількома почерговими раундами S- і P-скринь вже задовільняє властивостям плутанини і поширення (англ. confusion and diffusion) Шеннона:

Причина для поширення така: У випадку зміни одного біту відкритого тексту і подання його на вхід S-скрині, її вихід буде різнитись кількома бітами, тоді ці зміни розповсюджуються через P-скриню поміж кількома S-скринями, отже вихід всіх цих S-скринь знов змінюються в кількох бітах і т.д.. За кілька раундів кожен біт змінюється кілька разів, отже, з рештою, шифротекст змінюється повністю псевдовипадковим чином. Зокрема, для довільного блоку на вході, якщо змінюється i-й біт, тоді ймовірність зміни j-го біта на виході приблизно половина для будь-якого i та j, а це сувора умова лавиновості.

Причина для плутанини така сама як і для поширення: зміна одного біта ключа змінює кілька раундових ключів, і кожна така зміна поширюються мід усіма бітами, змінюючи шифротекст складним чином. І навпаки, зміна шифротексту змінить ключ повністю.

Хоча Мережа Фейстеля, яка використовує S-скрині (наприклад DES) дуже подібна до SP-мереж, тут є декілька відмінностей, що роблять кожну з них застосовнішою в певних умовах. Для даної кількості плутанини і поширення SP-мережа має більше «властивого паралелізму» (англ. inherent parallelism) отже — окремий процесор з більшою кількістю функціональних одиниць — може обробити її швидше ніж мережу Фейстеля. ЦПУ з малою кількістю функціональних одиниць — як більшість смарт-карт — не може отримати перевагу від цього властивого паралелізму.

Примітки

"Principles and Performance of Cryptographic Algorithms" [ 10 жовтня 2007 у Wayback Machine.] by Bart Preneel, Vincent Rijmen, and Antoon Bosselaers.
"The Skein Hash Function Family" [ 15 січня 2009 у Wayback Machine.] 2008 by Niels Ferguson, Stefan Lucks, Bruce Schneier, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, Jesse Walker page 40.

Джерела

Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography. CRC Press, 2007.
Douglas R. Stinson, Cryptography. Theory and Practice. Third edition. Chapman & Hall/CRC, 2006.

[1] "Principles and Performance of Cryptographic Algorithms" [ 10 жовтня 2007 у Wayback Machine.] by Bart Preneel, Vincent Rijmen, and Antoon Bosselaers.

[2] "The Skein Hash Function Family" [ 15 січня 2009 у Wayback Machine.] 2008 by Niels Ferguson, Stefan Lucks, Bruce Schneier, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, Jesse Walker page 40.