Перейти до вмісту

S-скриня

Матеріал з Вікіпедії — вільної енциклопедії.
(Перенаправлено з 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 біти на вході
0000000100100011010001010110011110001001101010111100110111101111
Зовнішні біти 00 0010110001000001011110101011011010000101001111111101000011101001
01 1110101100101100010001111101000101010000111110100011100110000110
10 0100001000011011101011010111100011111001110001010110001100001110
11 1011100011000111000111100010110101101111000010011010010001010011

Дані 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-скриня в AES

[ред. | ред. код]

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

Примітки

[ред. | ред. код]
  1. 1 2 Chandrasekaran, J. та ін. (2011). A Chaos Based Approach for Improving Non Linearity in the S-Box Design of Symmetric Key Cryptosystems. У Meghanathan, N. та ін. (ред.). 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. Архів оригіналу за 11 травня 2016. Процитовано 4 травня 2012.
  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.

Посилання

[ред. | ред. код]