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

Об s-блоке химических элементов см. s-элементы.

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

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

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

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

Программная реализация

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

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

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

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

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

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

Пример. Рассмотрим работу с таблицей пятого 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
Значение на входе дешифратора	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

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

Применение

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

Анализ n-разрядного s-блока при большом n крайне сложен, однако реализовать такой блок на практике очень сложно, так как число возможных соединений велико ($2^{n}$). На практике «блок подстановок» используется как элемент более сложных систем.

S-блоки используются в следующих шифрах:

• AES (англ. advanced encryption standard) — шифр, являющийся стандартным на территории США;
• ГОСТ 28147-89 — отечественный стандарт шифрования данных;
• DES (англ. data encryption standard) — шифр, являвшийся стандартным на территории США до принятия AES;
• Blowfish;
• Twofish.

Безопасность

При проектировании s‑блока особое внимание следует уделять составлению «таблицы подстановок». Многие годы исследователи искали закладки (уязвимости, известные только создателям) в таблицах подстановок восьми s‑блоков шифра DES. Авторы DES рассказали о том, чем руководствовались при составлении таблиц подстановок. Результаты дифференциального криптоанализа шифра DES показали, что числа в таблицах подстановок были тщательно подобраны так, чтобы увеличить стойкость DES к определённым видам атак. Бихам и Шамир обнаружили, что даже небольшие изменения в таблицах могут значительно ослабить DES.

Литература

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