WikiSort.ru - Не сортированное

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

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

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

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

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

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

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

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

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

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

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

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

• 1‑й и 6‑й биты на входе равны «01».
• 2‑й, 3‑й, 4‑й и 5‑й биты на входе равны «1101».
• На пересечении строки «01» и столбца «1101» находим ячейку «1001» — значения бит на выходе.

Аппаратная реализация

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

• дешифратор;
• система коммутаторов;
• шифратор.

Дешифратор — устройство, преобразующее n‑разрядный двоичный сигнал в одноразрядный сигнал по основанию ${\displaystyle 2^{n}}$ .

Например, для s-блока, изображённого на рисунке, дешифратор выполняет преобразование трёхразрядного сигнала (${\displaystyle n=3}$ ) в восьмиразрядный (${\displaystyle 2^{3}=8}$ ).

Система коммутаторов — внутренние соединения, выполняющие перестановку бит. Если m=n, количество соединений равно ${\displaystyle 2^{n}}$ . Каждый входной бит отображается в выходной бит, расположенный в том же или ином разряде. Если число входов n и выходов m не равно, от каждого выхода дешифратора может идти ноль, одно, два или более соединений. Это же справедливо и для входов шифратора.

Для s-блока, изображённого на рисунке, ${\displaystyle n=m=3}$ , число соединений равно ${\displaystyle 2^{n}=2^{3}=8}$ .

Шифратор — устройство, переводящее сигнал из одноразрядного ${\displaystyle 2^{n}}$ -ричного в n‑разрядный двоичный.

Для s‑блока, изображённого на рисунке, можно составить следующую таблицу замен (таблицу подстановок).

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

Применение

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

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

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

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

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

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

Примечания

Литература

• Kaisa Nyberg (англ.) (1991). "Perfect nonlinear s-boxes" (PDF). Advances in cryptology - Eurocrypt (англ.) 1991: 378–386. Проверено 2007-02-20.  (недоступная ссылка)

• S. Mister and C. Adams (англ.) (1996). "Practical s-box design" (PostScript). Workshop on Selected areas in cryptography (англ.) (SAC 1996). Workshop record: 61–76. Проверено 2007-02-20. 

• Schneier, Bruce. Applied cryptography. Second edition. — John Wiley & Sons, 1996. — P. 296–298, 349. — ISBN 0-471-11709-9.

• Easttom, Chuck (2014). “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. Внешняя ссылка в |publisher= (справка на английском)

См. также

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

Для улучшения этой статьи желательно: Викифицировать статью. Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное.