S-скриня

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

У криптографії, S-скриня, S-блок (англ. Substitution-box, S-box) — це засаднича складова шифрування з симетричними ключами, яка виконує підстановки. По суті це звичайна таблиця підстановки. У блочних шифрах їх здебільшого використовують для приховування зв'язків між ключем і шифротекстом — властивість плутанини введена Шенноном.[1]

Загалом, S-скриня приймає m біт на вхід і перетворює їх в n біт на виході, де n не завжди дорівнює m.[1] m×n S-скриню можна втілити як таблицю пошуку з 2m слів n бітів кожне. Сталі таблиці звичайно використовуються в DES, але в деяких шифрах таблиці створюються динамічно як похідні від ключа (наприклад, алгоритми шифрування Blowfish і Twofish).[Джерело?]

S-скрині в DES[ред.ред. код]

Одним з добрих прикладів сталої таблиці є ця 6×4-бітів S-скриня з DES (S5):

S5 Внутрішні 4 біти на вході
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
Зовнішні біти 00 0010 1100 0100 0001 0111 1010 1011 0110 1000 0101 0011 1111 1101 0000 1110 1001
01 1110 1011 0010 1100 0100 0111 1101 0001 0101 0000 1111 1010 0011 1001 1000 0110
10 0100 0010 0001 1011 1010 1101 0111 1000 1111 1001 1100 0101 0110 0011 0000 1110
11 1011 1000 1100 0111 0001 1110 0010 1101 0110 1111 0000 1001 1010 0100 0101 0011

Дані 6 бітів на вході і 4-біти на виході знаходяться через вибір рядка використовуючи зовнішні два біти (перший і останній), а стовпчик знаходиться по чотирьох внутрішніх бітах. Наприклад, вхід "011011" має зовнішні "01" і внутрішні біти "1101"; відповідний вихід "1001".

У своїх коментарях NSA відзначило такі вимоги до дизайну S-скриньок:

1. Жодна S-скриня не є лінійною або афінною функцію від свого входу.
2. Зміна 1 входового біту має як наслідок зміну щонайменше 2 бітів на виході.
3. S(x) і S(x+001100) мусять різнитись не менш як двома бітами.

Наступні, NSA відзначила як «спричинені вимогами до дизайну»:

4. S(x) =/= S(x+11ab00) для будь-якого вибору a і b.
5. S-скрині обирали таким чином, щоб мінімізувати різницю між кількістю 1 і 0 у будь-якому виході S-скрині за умови сталості одного входового біту.

Інший наслідок умов дизайну зауважили Мейєр і Матяс[2]:

6. Зумисно відібрані S-скриньки потребують для втілення значно більше мінтермів ніж довільно обрані.


Після винайдення диференціального криптоаналізу, Дон Копперсміт оприлюднив умови використані при розробці S-скриньок[3][4]:

  1. Кожна S-скринька повинна мати 6 біит на вході і 4 на виході. (У 1974 це був найбільший розмір S-скриньки, який можна була використати так, щоб DES вписувався в один чип.)
  2. Жоден виходовий біт S-скриньки не повинен бути занадто близьким до лінійної функції від входових бітів. (S-скриньки єдина нелінійна складова DES. В їхній нелінійності полягає сила алгоритму.)
  3. Кожен «рядок» S-скриніьки повинен містити всі можливі виходи. (Це увипадковлює вихід.)
  4. Якщо два входи різняться одним бітом, їх виходи мають різнитись не менше ніж двома бітами.
  5. Якщо два входи S-скриньки різняться двома середніми бітами, їх виходи повинні різнитися щонайменше двома бітами. (Ця й попередня умови забезпечують певне поширення.)
  6. Якщо два входи S-скриньки різняться своїми першими двома бітами й мають однакові останні, виходи мають бути різними.
  7. Для будь-якої 6-бітної різниці між входами, не більше ніж 8 з 32 пар входів, що проявляють таку різницю, можуть проявлятись в такій самій різниці виходів.

Копперсміт зауважив, що кращою другою умовою була б:

2’. Жодна лінійна комбінація входових біт для S-скрині не має бути занадто близькою до лінійної функції від входових біт.

8 S-скриньок алгоритму DES були предметом наполегливих досліджень впродовж багатьох років, щоб перевірити, чи не залишили розробники чорний вхід.

Приклад невдалої S-скрині[ред.ред. код]

Розглянемо:

S_i(x_1, x_2, ..., x_6) = (x_2 \oplus x_3, x_1 \oplus x_4 \oplus x_5, x_1 \oplus x_6, x_2 \oplus x_3 \oplus x_6)

або тотожно:

S_i(x) = A_i \cdot x \pmod 2

\begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1  \end{pmatrix}\times\begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6  \end{pmatrix} = \begin{pmatrix} x_2 \oplus x_3 \\ x_1 \oplus x_4 \oplus x_5 \\ x_1 \oplus x_6 \\ x_2 \oplus x_3 \oplus x_6  \end{pmatrix}
Тоді S_i є лінійною функцією.

S-скриня в AES[ред.ред. код]

S-скриня утворюється визначанням обернених елементів для входу в GF(2^8) = GF(2)[x]/(x^8 + x^4 + x^3 + x + 1), скінченне поле Rijndael (нуль,який не має оберненого, встановлюється в нуль). Обернений елемент потім піддається афінному перетворенню. Зворотна S-скриня є просто S-скриня запущена в протилежному напрямку. S-скриня працює як таблиця пошуку.

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

  1. а б Chandrasekaran, J. et al. (2011). «A Chaos Based Approach for Improving Non Linearity in the S-Box Design of Symmetric Key Cryptosystems». У Meghanathan, N. et al. Advances in Networks and Communications: First International Conference on Computer Science and Information Technology, CCSIT 2011, Bangalore, India, January 2-4, 2011. Proceedings, Part 2. Springer. с. 516. ISBN 9783642178771. 
  2. C.H. Meyer, S.M. Matyas, Cryptography: A New Dimension in Data Security, John Wiley & Sons, New-York, 1982.
  3. Don Coppersmith, The Data Encryption Standard (DES) and its strength against attacks, Technical Report RC 18613, IBM T.J. Watson Center, December 1992.
  4. Don Coppersmith, The Data Encryption Standard (DES) and its strength against attacks, IBM Journal of Research and Development, Vol. 38, n. 3, pp. 243-250, May 1994.

Посилання[ред.ред. код]