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]:
- Кожна S-скринька повинна мати 6 біт на вході і 4 на виході. (У 1974 це був найбільший розмір S-скриньки, який можна була використати так, щоб DES вписувався в один чип.)
- Жоден виходовий біт S-скриньки не повинен бути занадто близьким до лінійної функції від входових бітів. (S-скриньки єдина нелінійна складова DES. В їхній нелінійності полягає сила алгоритму.)
- Кожен «рядок» S-скриніьки повинен містити всі можливі виходи. (Це увипадковлює вихід.)
- Якщо два входи різняться одним бітом, їх виходи мають різнитись не менше ніж двома бітами.
- Якщо два входи S-скриньки різняться двома середніми бітами, їх виходи повинні різнитися щонайменше двома бітами. (Ця й попередня умови забезпечують певне поширення.)
- Якщо два входи S-скриньки різняться своїми першими двома бітами й мають однакові останні, виходи мають бути різними.
- Для будь-якої 6-бітної різниці між входами, не більше ніж 8 з 32 пар входів, що проявляють таку різницю, можуть проявлятись в такій самій різниці виходів.
Копперсміт зауважив, що кращою другою умовою була б:
- 2’. Жодна лінійна комбінація входових біт для S-скрині не має бути занадто близькою до лінійної функції від входових біт.
8 S-скриньок алгоритму DES були предметом наполегливих досліджень впродовж багатьох років, щоб перевірити, чи не залишили розробники чорний вхід.
Приклад невдалої S-скрині
ред.Розглянемо:
або тотожно:
Тоді є лінійною функцією.
S-скриня в AES
ред.S-скриня утворюється визначанням обернених елементів для входу в скінченне поле Rijndael (нуль,який не має оберненого, встановлюється в нуль). Обернений елемент потім піддається афінному перетворенню. Зворотна S-скриня є просто S-скриня запущена в протилежному напрямку. S-скриня працює як таблиця пошуку.
Примітки
ред.- ↑ а б 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.
- ↑ C.H. Meyer, S.M. Matyas, Cryptography: A New Dimension in Data Security, John Wiley & Sons, New-York, 1982.
- ↑ Don Coppersmith, The Data Encryption Standard (DES) and its strength against attacks, Technical Report RC 18613, IBM T.J. Watson Center, December 1992.
- ↑ 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.
Посилання
ред.- A literature survey on S-Box design [Архівовано 14 квітня 2012 у Wayback Machine.]
- John Savard's "Questions of S-Box Design" [Архівовано 16 липня 2012 у Wayback Machine.]
- Gargiulo's "S-Box Modifications and Their Effect in DES-like Encryption Systems" [Архівовано 20 травня 2012 у Wayback Machine.]