S-блоки

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

S-блок (англ. s-box от substitution-box), «блок подстановок» — функция в коде программы или аппаратная система, принимающая на входе n бит, преобразующая их по определённому алгоритму и возвращающая на выходе m бит. n и m не обязательно равны[1].

S-блоки используются в блочных шифрах.

В электронике можно непосредственно применять схему, приведённую на рисунке. В программировании же создают таблицы замен (подстановочные таблицы, таблицы подстановки). Оба этих подхода являются эквивалентными, то есть файл, зашифрованный на компьютере, можно расшифровать на электронном устройстве и наоборот.

S-блок называется идеальным (англ. perfect s‑box)[2], если значения выходных бит вычисляются бент-функцией на основе значений входных бит и любая линейная комбинация выходных бит является бент-функцией от входных бит.

Программная реализация[править | править вики-текст]

Программная реализация s‑блока работает следующим образом:

  • читается значение на входе (аргумент функции);
  • выполняется поиск прочитанного значения по таблице;
  • по определённому правилу выбирается ячейка таблицы; из ячейки читается выходное значение; выходное значение возвращается из функции.

Используемая таблица называется «таблицей замен» или «таблицей подстановок». Таблица может:

  • быть неизменной (фиксированной) (англ. static);
  • генерироваться на основе ключа (англ. dynamic).

Например, для шифра DES используется фиксированная таблица, а для шифров Blowfish и Twofish таблица создаётся на основе ключа.

Таблицы замен s‑блоков шифра DES

Пример[3]. Рассмотрим работу с таблицей пятого s‑блока (S_5) шифра DES. Пятый s‑блок принимает на входе 6 бит (n=6), а на выходе возвращает 4 бита (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" — значения бит на выходе.

Аппаратная реализация[править | править вики-текст]

Принципиальная схема трёхразрядного (n=3) s-блока

Аппаратная реализация s‑блока (см. рис.) состоит из следующих устройств:

Дешифратор — устройство, преобразующее nразрядный двоичный сигнал в одноразрядный сигнал по основанию 2^n.

Например, для s-блока, изображённого на рисунке, дешифратор выполняет преобразование трёхразрядного сигнала (n=3) в восьмиразрядный (2^3=8).

Система коммутаторов — внутренние соединения, выполняющие перестановку бит. Если m=n, количество соединений равно 2^n. Каждый входной бит отображается в выходной бит, расположенный в том же или ином разряде. Если число входов n и выходов m не равно, от каждого выхода дешифратора может идти ноль, одно, два или более соединений. Это же справедливо и для входов шифратора.

Для s-блока, изображённого на рисунке, n=m=3, число соединений равно 2^n=2^3=8.

Шифратор — устройство, переводящее сигнал из одноразрядного 2^n-ричного в n‑разрядный двоичный.

Для s‑блока, изображённого на рисунке, можно составить следующую таблицу замен (таблицу подстановок).

0 1 2 3 4 5 6 7
Значения бит на входе 000 001 010 011 100 101 110 111
Значения бит на выходе 011 000 001 100 110 111 010 101

Применение[править | править вики-текст]

S-блоки используются в блочных шифрах при выполнении симметричного шифрования для сокрытия статистической связи между открытым текстом и шифротекстом.

Анализ n-разрядного s-блока при большом n крайне сложен, однако реализовать такой блок на практике очень сложно, так как число возможных соединений велико (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].

Примечания[править | править вики-текст]

  1. 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.
  2. RFC 4086. Section 5.3 "Using s‑boxes for mixing"
  3. 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.
  4. Coppersmith, Don (1994). «The Data Encryption Standard (DES) and its strength against attacks» (PDF). IBM Journal of Research and Development 38 (3): 243–250. DOI:10.1147/rd.383.0243. Проверено 2007-02-20.
  5. Gargiulo's "S-Box modifications and their effect in DES-like encryption systems". С. 9.

Литература[править | править вики-текст]

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]