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

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

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

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

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

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

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

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

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

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

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

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

S ₅		Значения 2‑го, 3‑го, 4‑го и 5‑го бит на входе
S ₅		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

Пусть на вход подаются биты " 0 1101 1 ". Найдём биты на выходе.

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 ₂ =0 ₁₀	001 ₂ =1 ₁₀	010 ₂ =2 ₁₀	011 ₂ =3 ₁₀	100 ₂ =4 ₁₀	101 ₂ =5 ₁₀	110 ₂ =6 ₁₀	111 ₂ =7 ₁₀
Номер выхода дешифратора (по ), на котором установлено значение 1 (на других выходах установлено значение 0)	0	1	2	3	4	5	6	7
Номер входа шифратора (по ), на котором установлено значение 1 (на других входах установлено значение 0)	3	0	1	4	6	7	2	5
Значение на выходе шифратора	011 ₂ =3 ₁₀	000 ₂ =0 ₁₀	001 ₂ =1 ₁₀	100 ₂ =4 ₁₀	110 ₂ =6 ₁₀	111 ₂ =7 ₁₀	010 ₂ =2 ₁₀	101 ₂ =5 ₁₀

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

Применение

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

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

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

AES ( англ. a dvanced e ncryption s tandard ) — шифр, являющийся стандартным на территории США ;
ГОСТ 28147-89 — отечественный стандарт шифрования данных;
DES ( англ. d ata e ncryption s tandard ) — шифр, являвшийся стандартным на территории США до принятия AES ;
Blowfish ;
Twofish .

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

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

Примечания

Chandrasekaran, J. et al. A chaos based approach for improving non linearity in the s-box design of symmetric key cryptosystems // Bangalore , Индия , 2-4 января 2011 года . Proceedings, part 2. — Springer, 2011. — С. 516. — ISBN 978-3-642-17877-1 .
. Section 5.3 "Using s‑boxes for mixing"
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 .
(англ.) ( . (англ.) // (англ.) ( : journal. — 1994. — Vol. 38 , no. 3 . — P. 243—250 . — doi : .
от 20 мая 2012 на Wayback Machine . С. 9.

Литература

[in английский] (1991). ( PDF ) . Advances in cryptology - (англ.) 1991 . Brighton . pp. 378—386 . Дата обращения: 20 февраля 2007 . (недоступная ссылка)
S. Mister; [in английский] (1996). ( PostScript ) . Workshop on (англ.) (SAC 1996). Workshop record . Queen's University at Kingston . pp. 61—76 . Дата обращения: 20 февраля 2007 .
Schneier, Bruce . (англ.) . — John Wiley & Sons , 1996. — P. —298, 349. — ISBN 0-471-11709-9 .
(англ.) ( . A guideline for creating cryptographic s-boxes (неопр.) . — , 2014.