Подстановочно-перестановочная сеть

Подстановочно-перестановочная сеть (англ. Substitution-Permutation Network, SPN) — это класс итеративных блочных шифров, в основе построения которых лежит многократное чередование двух типов преобразований: подстановки (замены) и перестановки (перемешивания). Данная архитектура является одной из фундаментальных в современной симметричной криптографии и лежит в основе многих широко распространённых алгоритмов шифрования, включая AES (Advanced Encryption Standard).

История и происхождение

Концепция подстановочно-перестановочных сетей была впервые формально описана в 1949 году американским математиком Клодом Шенноном в его работе «Теория связи в секретных системах». Шеннон предложил два основных принципа, необходимых для построения стойких шифров: перемешивание (confusion) и рассеивание (diffusion).

• Перемешивание — это преобразование, которое делает статистическую связь между ключом и шифротекстом максимально сложной. В SPN эту функцию выполняют блоки подстановки (S-блоки).
• Рассеивание — это преобразование, которое распространяет влияние каждого бита открытого текста на множество битов шифротекста. В SPN эту функцию выполняют перестановки (P-блоки) и последующие раунды.

Шеннон предположил, что чередование этих двух операций, повторённое достаточное количество раз, может создать шифр, который будет практически неотличим от случайной перестановки. Первые практические реализации SPN появились в 1970-х годах, однако широкое распространение архитектура получила после принятия AES в 2001 году.

Структура и принцип работы

SPN-шифр обрабатывает блок данных фиксированной длины, применяя к нему последовательность раундов. Каждый раунд, как правило, состоит из трёх этапов:

1. Раундовое ключевое сложение (AddRoundKey): блок данных объединяется с раундовым ключом (производным от основного ключа шифрования) с помощью операции «исключающее ИЛИ» (XOR).
2. Подстановка (SubBytes): каждый байт (или группа битов) блока заменяется на другой байт в соответствии с таблицей замены — S-блоком. S-блоки обычно являются нелинейными преобразованиями, что обеспечивает перемешивание.
3. Перестановка (ShiftRows + MixColumns): биты или байты блока перемешиваются. В классической SPN этот этап может быть реализован как фиксированная перестановка битов (P-блок) или как более сложное линейное преобразование, как в AES, где перестановка разделена на два шага: циклический сдвиг строк (ShiftRows) и перемешивание столбцов (MixColumns).

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

Пример упрощённой SPN

Рассмотрим шифр с 16-битным блоком и 4-битными S-блоками. Раунд будет выглядеть следующим образом:

1. XOR с ключом: 16-битный блок складывается с 16-битным раундовым ключом.
2. Подстановка: блок разбивается на четыре 4-битных фрагмента. Каждый фрагмент заменяется по своему S-блоку (или по одному и тому же).
3. Перестановка: 16 бит, полученных после замены, перемешиваются в новом порядке (например, бит 0 становится битом 7, бит 1 — битом 12 и т.д.).

После нескольких таких раундов (например, 4-5) шифротекст становится практически неотличим от случайного набора битов.

Классификация и виды

Хотя SPN является общей архитектурой, на её основе построено множество конкретных алгоритмов, которые различаются по следующим параметрам:

• Размер блока: 64 бита (например, Square, 3-Way), 128 бит (AES, Anubis, ARIA) и другие.
• Размер ключа: 128, 192, 256 бит (AES) или другие значения.
• Количество раундов: от 4-5 (для учебных примеров) до 14 и более (AES-256).
• Тип S-блоков: могут быть фиксированными (AES), случайными (KHAZAD) или генерироваться на основе ключа (Twofish).
• Тип P-блоков: могут быть простыми перестановками битов (PRESENT) или более сложными линейными преобразованиями на основе кодов Рида-Соломона (AES).

Применение

Подстановочно-перестановочные сети являются основой для многих современных стандартов и протоколов шифрования:

• AES (Rijndael): принятый в 2001 году стандарт шифрования США, используемый по всему миру для защиты государственных и коммерческих данных. Является наиболее известным и изученным SPN-шифром.
• ГОСТ Р 34.12-2015 «Магма» (Кузнечик): российский стандарт блочного шифрования. «Кузнечик» (блок 128 бит) также является SPN-шифром, хотя его структура более сложна, чем у AES.
• PRESENT: лёгкий шифр, предназначенный для устройств с ограниченными ресурсами (RFID-метки, датчики). Отличается очень простой структурой SPN.
• Serpent: один из финалистов конкурса AES, известный своей высокой надёжностью и использованием большого количества S-блоков.
• Square: предшественник AES, на основе которого была разработана архитектура Rijndael.

Криптоанализ и стойкость

SPN-шифры считаются очень стойкими к большинству известных методов криптоанализа, в первую очередь к линейному и дифференциальному криптоанализу. Стойкость обеспечивается за счёт:

• Нелинейности S-блоков: они должны быть спроектированы так, чтобы минимизировать корреляцию между входными и выходными битами (линейная аппроксимация) и вероятность появления дифференциальных характеристик.
• Лавинного эффекта: перестановка гарантирует, что изменение одного бита на входе S-блока приведёт к изменению многих битов на выходе следующего раунда.
• Достаточного количества раундов: число раундов выбирается таким образом, чтобы даже самый эффективный известный метод атаки требовал нереалистично большого количества вычислительных ресурсов.

Тем не менее, для некоторых SPN-шифров были найдены атаки, сокращающие полный перебор ключей. Например, для шифра PRESENT известны атаки на версии с уменьшенным числом раундов, но полный 31-раундовый шифр остаётся стойким.

Сравнение с сетью Фейстеля

SPN является альтернативой другой распространённой архитектуре — сети Фейстеля (Feistel network). Основные различия:

SPN обычно обеспечивает более быстрое рассеивание, чем сеть Фейстеля, что позволяет использовать меньшее количество раундов для достижения той же стойкости. Однако SPN требует, чтобы все преобразования были обратимыми, что усложняет проектирование.

Интересные факты

• Название «Rijndael» (произносится как «Райн-дал») образовано от имён создателей — бельгийских криптографов Винсента Рэймена (Vincent Rijmen) и Йоана Дамена (Joan Daemen).
• S-блоки в AES построены на основе математической операции взятия обратного элемента в конечном поле Галуа GF(2⁸), что обеспечивает их высокую нелинейность.
• В шифре «Кузнечик» (ГОСТ Р 34.12-2015) используется 10 раундов, и его S-блок был выбран на основе строгих критериев стойкости к дифференциальному и линейному криптоанализу.

Источники

• Shannon, C. E. (1949). "Communication Theory of Secrecy Systems". Bell System Technical Journal.
• Daemen, J., & Rijmen, V. (2002). The Design of Rijndael: AES — The Advanced Encryption Standard. Springer.
• Bogdanov, A., Knudsen, L. R., Leander, G., Paar, C., Poschmann, A., Robshaw, M. J. B., ... & Vikkelsoe, C. (2007). "PRESENT: An Ultra-Lightweight Block Cipher". CHES 2007.
• ГОСТ Р 34.12-2015. «Информационная технология. Криптографическая защита информации. Блочные шифры».