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

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

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

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

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

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

Программная реализация 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$) в 8-и разрядный ($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 рассказали о том, чем руководствовались при составлении таблиц подстановок. Результаты дифференциального криптоанализа шифра DES показали, что числа в таблицах подстановок были тщательно подобраны так, чтобы увеличить стойкость DES к определённым видам атак. Бихам и Шамир обнаружили, что даже небольшие изменения в таблицах могут значительно ослабить DES.

Литература

• Kaisa Nyberg (1991). "Perfect nonlinear s-boxes" (PDF). Advances in cryptology - EUROCRYPT '91. Brighton. pp. 378—386. Дата обращения: 20 февраля 2007. {{cite conference}}: Неизвестный параметр |booktitle= игнорируется (|book-title= предлагается) (справка)
• S. Mister and C. Adams (1996). "Practical S-Box Design" (PostScript). Workshop on Selected Areas in Cryptography (SAC '96) Workshop Record. Queens University. pp. 61—76. Дата обращения: 20 февраля 2007. {{cite conference}}: Неизвестный параметр |booktitle= игнорируется (|book-title= предлагается) (справка)
• Schneier, Bruce. Applied Cryptography, Second Edition. — John Wiley & Sons, 1996. — P. 296–298, 349. — ISBN 0-471-11709-9.

Ссылки

• John Savard's "Questions of S-Box Design"
• Gargiulo's "S-Box Modifications and Their Effect in DES-like Encryption Systems"