Русская Википедия:S-блок (информатика)
S-блок (или блок подстановок, Шаблон:Lang-en от Шаблон:Lang-en2) — функция в коде программы или аппаратная система, принимающая на входе n бит, преобразующая их по определённому алгоритму и возвращающая на выходе m бит. n и m не обязательно равны[1].
S-блоки используются в блочных шифрах.
В электронике можно непосредственно применять схему, приведённую на рисунке. В программировании же создают таблицы замен (подстановочные таблицы, таблицы подстановок). Оба этих подхода являются эквивалентными, то есть данные, зашифрованные на компьютере, можно расшифровать на электронном устройстве и наоборот.
S-блок называется идеальным (Шаблон:Lang-en)[2], если значения выходных бит вычисляются бент-функцией на основе значений входных бит и любая линейная комбинация выходных бит является бент-функцией от входных бит.
Программная реализация
Программная реализация s‑блока работает следующим образом:
- читается значение на входе (аргумент функции);
- выполняется поиск прочитанного значения по таблице;
- по определённому правилу выбирается ячейка таблицы; из ячейки читается выходное значение; выходное значение возвращается из функции.
Используемая таблица называется «таблицей замен» или «таблицей подстановок». Таблица может:
- быть неизменной (фиксированной) (Шаблон:Lang-en);
- генерироваться на основе ключа (Шаблон:Lang-en).
Например, для шифра (алгоритма) DES используется фиксированная таблица, а для шифров Blowfish и Twofish таблица создаётся на основе ключа.
Пример[3]. Рассмотрим работу с таблицей пятого s‑блока (<math>S_5</math>) шифра DES. Пятый s‑блок принимает на входе 6 бит (<math>n=6</math>), а на выходе возвращает 4 бита (<math>m=4</math>). Пронумеруем входные биты слева направо от 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» — значения бит на выходе.
Аппаратная реализация
Аппаратная реализация s‑блока (см. рис.) состоит из следующих устройств:
- дешифратор;
- система коммутаторов;
- шифратор.
Дешифратор — устройство, преобразующее n‑разрядный двоичный сигнал в одноразрядный сигнал по основанию <math>2^n</math>.
Например, для s-блока, изображённого на рисунке, дешифратор выполняет преобразование трёхразрядного сигнала (<math>n=3</math>) в восьмиразрядный (<math>2^3=8</math>).
Система коммутаторов — внутренние соединения, выполняющие перестановку бит. Если m=n, количество соединений равно <math>2^n</math>. Каждый входной бит отображается в выходной бит, расположенный в том же или ином разряде. Если число входов n и выходов m не равно, от каждого выхода дешифратора может идти ноль, одно, два или более соединений. Это же справедливо и для входов шифратора.
Для s-блока, изображённого на рисунке, <math>n=m=3</math>, число соединений равно <math>2^n=2^3=8</math>.
Шифратор — устройство, переводящее сигнал из одноразрядного <math>2^n</math>-ричного в 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 |
Пример. Пусть на входы шифратора, изображённого на рисунке, подаётся число 1102 (см. рисунок). Так как десятичное представление двоичного числа 1102 равно 610, на 6‑м выходе шифратора будет значение 1, а на других выходах — значение 0 (см. рисунок). С помощью системы коммутаторов значение 1 будет передано на 2‑й вход дешифратора (перестановка бит). Так как двоичное представление десятичного числа 210 равно 0102, на выходах дешифратора будет число 0102 (см. рисунок).
Применение
S-блоки используются в блочных шифрах при выполнении симметричного шифрования для сокрытия статистической связи между открытым текстом и шифротекстом.
Анализ n-разрядного s-блока при большом n крайне сложен, однако реализовать такой блок на практике очень сложно, так как число возможных соединений велико (<math>2^n</math>). На практике «блок подстановок» используется как элемент более сложных систем.
S-блоки используются в следующих шифрах:
- AES (Шаблон:Lang-en) — шифр, являющийся стандартным на территории США;
- ГОСТ 28147-89 — отечественный стандарт шифрования данных;
- DES (Шаблон:Lang-en) — шифр, являвшийся стандартным на территории США до принятия AES;
- Blowfish;
- Twofish.
Безопасность
При проектировании s‑блока особое внимание следует уделять составлению «таблицы подстановок». Многие годы исследователи искали закладки (уязвимости, известные только создателям) в таблицах подстановок восьми s‑блоков шифра DES. Авторы DES рассказали[4] о том, чем руководствовались при составлении таблиц подстановок. Результаты дифференциального криптоанализа шифра DES показали, что числа в таблицах подстановок были тщательно подобраны так, чтобы увеличить стойкость DES к определённым видам атак. Бихам и Шамир обнаружили, что даже небольшие изменения в таблицах могут значительно ослабить DES[5].
Примечания
Литература
См. также
- Rijndael s-boxШаблон:Ref-en
- Биекция
- Булева функция
- Nothing up my sleeve number
- Шифр подстановки
- Permutation boxШаблон:Ref-en (Шаблон:Lang-en)
Ссылки
- John Savard's "Questions of S-Box Design"
- Gargiulo's "S-Box Modifications and Their Effect in DES-like Encryption Systems"
- ↑ Шаблон:Книга
- ↑ RFC 4086. Section 5.3 "Using s‑boxes for mixing"
- ↑ Шаблон:Книга
- ↑ Шаблон:Статья
- ↑ Gargiulo's "S-Box modifications and their effect in DES-like encryption systems" Шаблон:Wayback. С. 9.