S-блок (информатика)
S-блок (или блок подстановок, англ. s-box от substitution-box) — функция в коде программы или аппаратная система, принимающая на входе n бит, преобразующая их по определённому алгоритму и возвращающая на выходе m бит. n и m не обязательно равны[1].
S-блоки используются в блочных шифрах.
В электронике можно непосредственно применять схему, приведённую на рисунке. В программировании же создают таблицы замен (подстановочные таблицы, таблицы подстановок). Оба этих подхода являются эквивалентными, то есть данные, зашифрованные на компьютере, можно расшифровать на электронном устройстве и наоборот.
S-блок называется идеальным (англ. perfect s‑box)[2], если значения выходных бит вычисляются бент-функцией на основе значений входных бит и любая линейная комбинация выходных бит является бент-функцией от входных бит.
Программная реализация
Программная реализация s‑блока работает следующим образом:
- читается значение на входе (аргумент функции);
- выполняется поиск прочитанного значения по таблице;
- по определённому правилу выбирается ячейка таблицы; из ячейки читается выходное значение; выходное значение возвращается из функции.
Используемая таблица называется «таблицей замен» или «таблицей подстановок». Таблица может:
Например, для шифра (алгоритма) DES используется фиксированная таблица, а для шифров Blowfish и Twofish таблица создаётся на основе ключа.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/44/DES_S-box.jpg/300px-DES_S-box.jpg)
Пример[3]. Рассмотрим работу с таблицей пятого s‑блока () шифра DES. Пятый s‑блок принимает на входе 6 бит (), а на выходе возвращает 4 бита (). Пронумеруем входные биты слева направо от 1 до 6. Таблица подстановок имеет следующий вид:
S5 | Значения 2‑го, 3‑го, 4‑го и 5‑го бит на входе | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 | ||
Значения 1‑го и 6‑го бит на входе | 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 |
Пусть на вход подаются биты "011011". Найдём биты на выходе.
- 1‑й и 6‑й биты на входе равны «01».
- 2‑й, 3‑й, 4‑й и 5‑й биты на входе равны «1101».
- На пересечении строки «01» и столбца «1101» находим ячейку «1001» — значения бит на выходе.
Аппаратная реализация
![](http://upload.wikimedia.org/wikipedia/ru/thumb/5/50/S-block.svg/220px-S-block.svg.png)
Аппаратная реализация s‑блока (см. рис.) состоит из следующих устройств:
- дешифратор;
- система коммутаторов;
- шифратор.
Дешифратор — устройство, преобразующее n‑разрядный двоичный сигнал в одноразрядный сигнал по основанию .
Например, для s-блока, изображённого на рисунке, дешифратор выполняет преобразование трёхразрядного сигнала () в восьмиразрядный ().
Система коммутаторов — внутренние соединения, выполняющие перестановку бит. Если m=n, количество соединений равно . Каждый входной бит отображается в выходной бит, расположенный в том же или ином разряде. Если число входов n и выходов m не равно, от каждого выхода дешифратора может идти ноль, одно, два или более соединений. Это же справедливо и для входов шифратора.
Для s-блока, изображённого на рисунке, , число соединений равно .
Шифратор — устройство, переводящее сигнал из одноразрядного -ричного в n‑разрядный двоичный.
Для s‑блока, изображённого на рисунке, можно составить следующую таблицу замен (таблицу подстановок).
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
---|---|---|---|---|---|---|---|---|
Значение на входе дешифратора | 0002=010 | 0012=110 | 0102=210 | 0112=310 | 1002=410 | 1012=510 | 1102=610 | 1112=710 |
Номер выхода дешифратора (по рисунку), на котором установлено значение 1 (на других выходах установлено значение 0) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
Номер входа шифратора (по рисунку), на котором установлено значение 1 (на других входах установлено значение 0) | 3 | 0 | 1 | 4 | 6 | 7 | 2 | 5 |
Значение на выходе шифратора | 0112=310 | 0002=010 | 0012=110 | 1002=410 | 1102=610 | 1112=710 | 0102=210 | 1012=510 |
Пример. Пусть на входы шифратора, изображённого на рисунке, подаётся число 1102 (см. рисунок). Так как десятичное представление двоичного числа 1102 равно 610, на 6‑м выходе шифратора будет значение 1, а на других выходах — значение 0 (см. рисунок). С помощью системы коммутаторов значение 1 будет передано на 2‑й вход дешифратора (перестановка бит). Так как двоичное представление десятичного числа 210 равно 0102, на выходах дешифратора будет число 0102 (см. рисунок).
Применение
S-блоки используются в блочных шифрах при выполнении симметричного шифрования для сокрытия статистической связи между открытым текстом и шифротекстом.
Анализ n-разрядного s-блока при большом n крайне сложен, однако реализовать такой блок на практике очень сложно, так как число возможных соединений велико (). На практике «блок подстановок» используется как элемент более сложных систем.
S-блоки используются в следующих шифрах:
- AES (англ. advanced encryption standard) — шифр, являющийся стандартным на территории США;
- ГОСТ 28147-89 — отечественный стандарт шифрования данных;
- DES (англ. data encryption standard) — шифр, являвшийся стандартным на территории США до принятия AES;
- Blowfish;
- Twofish.
Безопасность
При проектировании s‑блока особое внимание следует уделять составлению «таблицы подстановок». Многие годы исследователи искали закладки (уязвимости, известные только создателям) в таблицах подстановок восьми s‑блоков шифра DES. Авторы DES рассказали[4] о том, чем руководствовались при составлении таблиц подстановок. Результаты дифференциального криптоанализа шифра DES показали, что числа в таблицах подстановок были тщательно подобраны так, чтобы увеличить стойкость DES к определённым видам атак. Бихам и Шамир обнаружили, что даже небольшие изменения в таблицах могут значительно ослабить DES[5].
Примечания
- ↑ Chandrasekaran, J. et al. A chaos based approach for improving non linearity in the s-box design of symmetric key cryptosystems // Advances in networks and communications: first international conference on computer science and information technology, CCSIT 2011, Bangalore, Индия, 2-4 января 2011 года. Proceedings, part 2. — Springer, 2011. — С. 516. — ISBN 978-3-642-17877-1.
- ↑ RFC 4086. Section 5.3 "Using s‑boxes for mixing"
- ↑ Buchmann Johannes A. 5. DES // Introduction to cryptography. — Corr. 2. print.. — New York, NY [u.a.]: Springer, 2001. — С. 119—120. — ISBN 0-387-95034-6.
- ↑ Coppersmith, Don[англ.]. The Data Encryption Standard (DES) and its strength against attacks (англ.) // IBM Journal of Research and Development[англ.] : journal. — 1994. — Vol. 38, no. 3. — P. 243—250. — doi:10.1147/rd.383.0243.
- ↑ Gargiulo's "S-Box modifications and their effect in DES-like encryption systems" Архивная копия от 20 мая 2012 на Wayback Machine. С. 9.
Литература
- Kaisa Nyberg [in английский] (1991). "Perfect nonlinear s-boxes" (PDF). Advances in cryptology - Eurocrypt (англ.) 1991. Brighton. pp. 378—386. Дата обращения: 20 февраля 2007. (недоступная ссылка)
- S. Mister; C. Adams [in английский] (1996). "Practical s-box design" (PostScript). Workshop on Selected areas in cryptography (англ.) (SAC 1996). Workshop record. Queen's University at Kingston. pp. 61—76. Дата обращения: 20 февраля 2007.
- Schneier, Bruce. Applied cryptography. Second edition (англ.). — John Wiley & Sons, 1996. — P. 296—298, 349. — ISBN 0-471-11709-9.
- Easttom, Chuck[англ.]. A guideline for creating cryptographic s-boxes (неопр.). — https://www.academia.edu/9192148/CREATING_CRYPTOGRAPHIC_S-BOXES_A_Guideline_for_Designing_Cryptographic_S-Boxes_by_Chuck_Easttom, 2014.
См. также
- Rijndael s-box (англ.)
- Биекция
- Булева функция
- Nothing up my sleeve number
- Шифр подстановки
- Permutation box (англ.) (англ. p-box)
Ссылки
- John Savard's "Questions of S-Box Design"
- Gargiulo's "S-Box Modifications and Their Effect in DES-like Encryption Systems"