Перегляд вихідного коду сторінки S-скриня

У [[криптографія|криптографії]], '''S-скриня''', '''S-блок''' ({{lang-en|Substitution-box, S-box}})&nbsp;— це засаднича складова [[шифрування з симетричними ключами]], яка виконує [[підстановочний шифр|підстановки]]. По суті це звичайна таблиця [[підстановочний шифр|підстановки]]. У [[блочний шифр|блочних шифрах]] їх здебільшого використовують для приховування зв'язків між ключем і [[шифротекст]]ом&nbsp;— властивість [[плутанина і поширення|плутанини]] введена [[Клод Шеннон|Шенноном]].<ref name="chandra-516">{{cite book|authors=Chandrasekaran, J. et al.|chapter=A Chaos Based Approach for Improving Non Linearity in the S-Box Design of Symmetric Key Cryptosystems|editors=Meghanathan, N. et al.|title=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|publisher=Springer|year=2011|isbn=9783642178771|page=516|url=http://books.google.com/books?id=pXOS4ZTUJLYC&pg=PA516|accessdate=4 травня 2012|archive-date=11 травня 2016|archive-url=https://web.archive.org/web/20160511195649/https://books.google.com/books?id=pXOS4ZTUJLYC&pg=PA516}}</ref> 

Загалом, S-скриня приймає ''m'' біт на вхід і перетворює їх в ''n'' біт на виході, де ''n'' не завжди дорівнює ''m''.<ref name="chandra-516" /> ''m''&times;''n'' S-скриню можна втілити як [[таблиця пошуку|таблицю пошуку]] з 2<sup>''m''</sup> слів ''n'' бітів кожне. Сталі таблиці звичайно використовуються в [[DES]], але в деяких [[шифр]]ах таблиці створюються динамічно як похідні від [[Ключ (криптографія)|ключа]] (наприклад, алгоритми шифрування [[Blowfish]] і [[Twofish]]).{{джерело}}

== S-скрині в DES==
Одним з добрих прикладів сталої таблиці є ця 6&times;4-бітів S-скриня з DES (S<sub>5</sub>):

{| class="wikitable" align="center"
! rowspan="2" colspan="2" | S<sub>5</sub> || colspan="16" align="center" | Внутрішні 4 біти на вході
|-
! 0000 !! 0001 !! 0010 !! 0011 !! 0100 !! 0101 !! 0110 !! 0111 !! 1000 !! 1001 !! 1010 !! 1011 !! 1100 !! style="background:#ffdead;" | 1101 !! 1110 !! 1111
|-
! rowspan="4" | Зовнішні біти 
! 00 
| 0010 || 1100 || 0100 || 0001 || 0111 || 1010 || 1011 || 0110 || 1000 || 0101 || 0011 || 1111 || 1101 || style="background:#ffdead;" | 0000 || 1110 || 1001
|-
! style="background:#deffad;" | 01
| style="background:#deffad;" | 1110 || style="background:#deffad;" | 1011 || style="background:#deffad;" | 0010 || style="background:#deffad;" | 1100 || style="background:#deffad;" | 0100 || style="background:#deffad;" | 0111 || style="background:#deffad;" | 1101 || style="background:#deffad;" | 0001 || style="background:#deffad;" | 0101 || style="background:#deffad;" | 0000 || style="background:#deffad;" | 1111 || style="background:#deffad;" | 1010 || style="background:#deffad;" | 0011 || style="background:#fefe2d;" | 1001 || style="background:#deffad;" | 1000 || style="background:#deffad;" | 0110
|-
! 10
| 0100 || 0010 || 0001 || 1011 || 1010 || 1101 || 0111 || 1000 || 1111 || 1001 || 1100 || 0101 || 0110 || style="background:#ffdead;" | 0011 || 0000 || 1110
|-
! 11
| 1011 || 1000 || 1100 || 0111 || 0001 || 1110 || 0010 || 1101 || 0110 || 1111 || 0000 || 1001 || 1010 || style="background:#ffdead;" | 0100 || 0101 || 0011
|}

Дані 6 бітів на вході і 4-біти на виході знаходяться через вибір рядка використовуючи зовнішні два біти (перший і останній), а стовпчик знаходиться по чотирьох внутрішніх бітах. Наприклад, вхід "'''0'''1101'''1'''" має зовнішні "'''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-скрині за умови сталості одного входового біту. 
Інший наслідок умов дизайну зауважили Мейєр і Матяс<ref>C.H. Meyer, S.M. Matyas, Cryptography: A New Dimension in Data Security, John Wiley &
Sons, New-York, 1982.</ref>:
:6. Зумисно відібрані S-скриньки потребують для втілення значно більше [[мінтерм]]ів ніж довільно обрані.


Після винайдення диференціального криптоаналізу, Дон Копперсміт оприлюднив умови використані при розробці S-скриньок<ref>Don Coppersmith, The Data Encryption Standard (DES) and its strength against attacks, Technical Report RC 18613, IBM T.J. Watson Center, December 1992.</ref><ref>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.</ref>:
# Кожна S-скринька повинна мати 6 біт на вході і 4 на виході. (У 1974 це був найбільший розмір S-скриньки, який можна була використати так, щоб DES вписувався в один чип.)
# Жоден виходовий біт S-скриньки не повинен бути занадто близьким до лінійної функції від входових бітів. (S-скриньки єдина нелінійна складова DES. В їхній нелінійності полягає сила алгоритму.)
# Кожен «рядок» S-скриніьки повинен містити всі можливі виходи. (Це увипадковлює вихід.)
# Якщо два входи різняться одним бітом, їх виходи мають різнитись не менше ніж двома бітами.
# Якщо два входи S-скриньки різняться двома середніми бітами, їх виходи повинні різнитися щонайменше двома бітами. (Ця й попередня умови забезпечують певне поширення.)
# Якщо два входи S-скриньки різняться своїми першими двома бітами й мають однакові останні, виходи мають бути різними.
# Для будь-якої 6-бітної різниці між входами, не більше ніж 8 з 32 пар входів, що проявляють таку різницю, можуть проявлятись в такій самій різниці виходів.

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

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

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

===Приклад невдалої S-скрині===
Розглянемо:
:<math>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)</math>
або тотожно:
:<math>S_i(x) = A_i \cdot x \pmod 2</math>
<math>\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}</math><br />
Тоді <math>S_i</math> є лінійною функцією.

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

== Примітки ==
{{reflist}}

== Посилання ==
* [http://www.ciphersbyritter.com/RES/SBOXDESN.HTM A literature survey on S-Box design] {{Webarchive|url=https://web.archive.org/web/20120414205050/http://www.ciphersbyritter.com/RES/SBOXDESN.HTM |date=14 квітня 2012 }}
* [http://www.quadibloc.com/crypto/co4513.htm John Savard's "Questions of S-Box Design"] {{Webarchive|url=https://web.archive.org/web/20120716203634/http://www.quadibloc.com/crypto/co4513.htm |date=16 липня 2012 }}
* [http://www.sans.org/reading_room/whitepapers/vpns/s-box-modifications-effect-des-like-encryption-systems_768 Gargiulo's "S-Box Modifications and Their Effect in DES-like Encryption Systems"] {{Webarchive|url=https://web.archive.org/web/20120520040808/http://www.sans.org/reading_room/whitepapers/vpns/s-box-modifications-effect-des-like-encryption-systems_768 |date=20 травня 2012 }}

[[Категорія:Криптографія з симетричними ключами]]