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

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

Принципиальная схема 3-разрядного s-блока

S-блок (англ. s-box от substitution-box) — программный код или аппаратная система, выполняющая перестановку бит по таблице. Каждый входной бит отображается в выходной бит, расположенный в том же или ином разряде. Перестановка бит по таблице — промежуточная операция в алгоритмах симметричного шифрования.

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

• дешифратор — устройство, преобразующее n-разрядный двоичный сигнал в одноразрядный сигнал по основанию $2^{n}$;
• система коммутаторов внутренних соединений (количество соединений равно $2^{n}!$);
• шифратор — устройство, переводящее сигнал из одноразрядного $2^{n}$-ричного в n-разрядный двоичный.

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

В общем случае s-блок может иметь несовпадающее число входов/выходов, в этом случае в системе коммутации от каждого выхода дешифратора может идти не строго одно соединение, а 2 или более или не идти вовсе. То же самое справедливо и для входов шифратора.

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

Таблица замены для приведённого 3-разрядного 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

Применяется в таких алгоритмах симметричного шифрования как:

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

Литература

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