SP-сеть

SP-сеть (от англ. Substitution-Permutation network, сеть подстановочно-перестановочного типа) — это класс криптографических преобразований, используемых в симметричных блочных шифрах. Основная идея заключается в многократном чередовании двух этапов: подстановки (замены блоков данных по нелинейному правилу) и перестановки (перемешивания битов или байтов). Такая структура обеспечивает быстрое рассеивание (diffusion) и запутывание (confusion) информации, что является ключевым требованием для стойкости шифра к криптоанализу.

История

Концепция SP-сети была впервые формально описана в 1949 году Клодом Шенноном в статье «Теория связи в секретных системах», где он ввёл понятия рассеивания и запутывания. Однако практическое применение началось с разработки алгоритма Lucifer в начале 1970-х годов в исследовательском центре IBM. Этот шифр стал предшественником стандарта DES (Data Encryption Standard), который, хотя и базируется на сети Фейстеля, заимствовал многие принципы SP-структуры.

В 1990-х годах, после появления атак на DES, интерес к SP-сетям возрос. В 1997 году был опубликован шифр Rijndael, разработанный бельгийскими криптографами Йоаном Дайменом и Винсентом Рейменом. В 2000 году он победил в конкурсе Национального института стандартов и технологий США (NIST) и стал новым стандартом AES (Advanced Encryption Standard). AES является классическим примером SP-сети и до сих пор остаётся одним из самых распространённых симметричных шифров в мире.

Устройство и принцип работы

SP-сеть состоит из последовательности раундов. Каждый раунд включает два основных преобразования:

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

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

Пример: AES

В шифре AES (длина блока 128 бит, длина ключа 128/192/256 бит) каждый раунд (кроме последнего) состоит из четырёх этапов:

1. SubBytes — замена каждого байта с использованием S-блока (таблица 16×16).
2. ShiftRows — циклический сдвиг строк в матрице состояния.
3. MixColumns — умножение каждого столбца на фиксированный полином (обеспечивает перестановку на уровне байтов).
4. AddRoundKey — наложение раундового ключа.

В последнем раунде этап MixColumns опускается. Такая структура обеспечивает высокую стойкость и эффективность как в программной, так и в аппаратной реализации.

Классификация

SP-сети можно классифицировать по нескольким признакам:

• По размеру блока: 64-битные (например, PRESENT), 128-битные (AES, Serpent), 256-битные (редко).
• По числу раундов: от 10 (AES-128) до 32 (Serpent).
• По типу S-блоков: фиксированные (AES) или динамические (зависящие от ключа, как в Twofish).
• По архитектуре: чистая SP-сеть (AES) или гибридная (например, Camellia сочетает SP-сеть с сетью Фейстеля).

Применение

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

• Стандарты шифрования: AES (США, Россия — ГОСТ Р 34.12-2015 «Кузнечик» также использует SP-сеть), Serpent, PRESENT (лёгкая криптография для IoT).
• Хеш-функции: некоторые алгоритмы (например, SHA-3) основаны на SP-подобных структурах (губка).
• Аутентификация и имитозащита: режимы работы блочных шифров (GCM, CCM) используют SP-сеть как базовый примитив.
• Аппаратные модули: смарт-карты, SIM-карты, криптографические ускорители.

Преимущества и недостатки

Преимущества

• Высокая скорость: за счёт параллельной обработки S-блоков и простых линейных операций.
• Хорошее рассеивание: изменение одного бита влияет на все биты блока уже после нескольких раундов.
• Доказанная стойкость: к дифференциальному и линейному криптоанализу при правильном проектировании S-блоков.

Недостатки

• Сложность проектирования S-блоков: они должны быть нелинейными, сбалансированными и устойчивыми к атакам.
• Чувствительность к атакам по сторонним каналам: при неоптимальной реализации (например, в микроконтроллерах) возможны утечки через время выполнения или потребление энергии.
• Меньшая гибкость: по сравнению с сетью Фейстеля, где размер блока может быть произвольным, SP-сеть требует фиксированного размера блока.

Криптоанализ SP-сетей

Основные методы атак на SP-сети включают:

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

Сравнение с другими структурами

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

• S-блоки AES были разработаны с использованием теории конечных полей и обладают математически доказанной стойкостью к дифференциальному криптоанализу.
• Шифр «Кузнечик» (ГОСТ Р 34.12-2015) использует SP-сеть с 10 раундами и 128-битным блоком, но его S-блоки отличаются от AES.
• В 2019 году группа исследователей предложила атаку на AES с пониженным числом раундов (до 7), но полный 10-раундовый AES остаётся стойким.