S-блок (информатика)

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

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

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

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

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

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

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

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

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

Пример^[3]. Рассмотрим работу с таблицей пятого s‑блока (${\displaystyle S_{5}}$) шифра DES. Пятый s‑блок принимает на входе 6 бит (${\displaystyle n=6}$), а на выходе возвращает 4 бита (${\displaystyle m=4}$). Пронумеруем входные биты слева направо от 1 до 6. Таблица подстановок имеет следующий вид:

Пусть на вход подаются биты "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‑блока, изображённого на рисунке, можно составить следующую таблицу замен (таблицу подстановок).

Пример. Пусть на входы шифратора, изображённого на рисунке, подаётся число 110₂ (см. рисунок). Так как десятичное представление двоичного числа 110₂ равно 6₁₀, на 6‑м выходе шифратора будет значение 1, а на других выходах — значение 0 (см. рисунок). С помощью системы коммутаторов значение 1 будет передано на 2‑й вход дешифратора (перестановка бит). Так как двоичное представление десятичного числа 2₁₀ равно 010₂, на выходах дешифратора будет число 010₂ (см. рисунок).

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].

• 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"