Меню Главная Случайная статья Настройки S-блок (информатика) Материал из https://ru.wikipedia.org S-блок (или блок подстановок, англ. s-box от substitution-box) — функция в коде программы или аппаратная система, принимающая на входе n бит, преобразующая их по определённому алгоритму и возвращающая на выходе m бит. n и m не обязательно равны[1]. S-блоки используются в блочных шифрах. В электронике можно непосредственно применять схему, приведённую на рисунке. В программировании же создают таблицы замен (подстановочные таблицы, таблицы подстановок). Оба этих подхода являются эквивалентными, то есть данные, зашифрованные на компьютере, можно расшифровать на электронном устройстве и наоборот. S-блок называется идеальным (англ. perfect sbox)[2], если значения выходных бит вычисляются бент-функцией на основе значений входных бит и любая линейная комбинация выходных бит является бент-функцией от входных бит. Содержание 1 Программная реализация 2 Аппаратная реализация 3 Применение 4 Безопасность 5 Примечания 6 Литература 7 См. также 8 Ссылки Программная реализация Программная реализация sблока работает следующим образом: читается значение на входе (аргумент функции); выполняется поиск прочитанного значения по таблице; по определённому правилу выбирается ячейка таблицы; из ячейки читается выходное значение; выходное значение возвращается из функции. Используемая таблица называется «таблицей замен» или «таблицей подстановок». Таблица может: быть неизменной (фиксированной) (англ. static); генерироваться на основе ключа (англ. dynamic). Например, для шифра (алгоритма) DES используется фиксированная таблица, а для шифров Blowfish и Twofish таблица создаётся на основе ключа. Пример[3]. Рассмотрим работу с таблицей пятого sблока (${\displaystyle S_{5}}$) шифра DES. Пятый sблок принимает на входе 6 бит (${\displaystyle n=6}$), а на выходе возвращает 4 бита (${\displaystyle m=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» — значения бит на выходе. Аппаратная реализация Аппаратная реализация sблока (см. рис.) состоит из следующих устройств: дешифратор; система коммутаторов; шифратор. Дешифратор — устройство, преобразующее nразрядный двоичный сигнал в одноразрядный сигнал по основанию ${\displaystyle 2^{n}}$. Например, для s-блока, изображённого на рисунке, дешифратор выполняет преобразование трёхразрядного сигнала (${\displaystyle n=3}$) в восьмиразрядный (${\displaystyle 2^{3}=8}$). Система коммутаторов — внутренние соединения, выполняющие перестановку бит. Если m=n, количество соединений равно ${\displaystyle 2^{n}}$. Каждый входной бит отображается в выходной бит, расположенный в том же или ином разряде. Если число входов n и выходов m не равно, от каждого выхода дешифратора может идти ноль, одно, два или более соединений. Это же справедливо и для входов шифратора. Для s-блока, изображённого на рисунке, ${\displaystyle n=m=3}$, число соединений равно ${\displaystyle 2^{n}=2^{3}=8}$. Шифратор — устройство, переводящее сигнал из одноразрядного ${\displaystyle 2^{n}}$-ричного в 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 крайне сложен, однако реализовать такой блок на практике очень сложно, так как число возможных соединений велико (${\displaystyle 2^{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 sboxes for mixing" 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. Литература 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"