SP-мережа

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Нарис трираундової мережі замін-переставок, що шифрує 16 біт вхідного тексту в 16 біт вихідного. S-скрині — Si’s, P-скрині — P і ключ раунду — Ki.

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

Така мережа приймає блок відкритого тексту і ключ на вході, і застосовує декілька навперемінних «раундів» S-скринь і P-скринь для отримання блоку шифротексту. 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)[1] отже — окремий ЦПУ з більшою кількістю функціональних одиниць — може обробити її швидше ніж мережу Фейстеля. [2] ЦПУ з малою кількістю функціональних одиниць — як більшість смарт-карт — не може отримати перевагу від цього властивого паралелизму.

Примітки[ред.ред. код]

  1. "Principles and Performance of Cryptographic Algorithms" by Bart Preneel, Vincent Rijmen, and Antoon Bosselaers.
  2. "The Skein Hash Function Family" 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.