SP-сеть. 
Криптографические методы защиты информации

Выше мы рассматривали алгоритмы блочного шифрования, построенные по принцип}' сети Фейстеля. Другим способом построения блочных шифров является «подстановочно-перестановочная сеть», основанная на многократном применении однотипных раундовых преобразований, состоящих из подстановок, перестановок и операций наложения ключа. Одним из первых шифров, построенных по такому принципу, был алгоритм «Люцифер», легший в основу алгоритма DES. Среди других алгоритмов, относимых к классу SP-сетей, можно выделить алгоритмы IDEA, AES и Serpent, а также российский алгоритм «Кузнечик».

Как и ранее, мы рассматриваем алгоритм зашифрования, задаваемый равенством (7.3). В SP-сети каждое рауидовое преобразование R состоит из трех шагов.

• 1. Шаг наложения раундового ключа на вектор а € F^, как правило, достаточно тривиален. Раундовый ключ либо складывается с вектором, но модулю два, либо разбивается на несколько «слов», каждое из которых складывается по модулю некоторого целого числа.
• 2. Пусть I > п — фиксированное натуральное число. Шаг подстановки заключается в применении нелинейного преобразования S : FJ —" ®2, основанного на параллельном применении ко входному сообщению а некоторого числа подстановок.

Пусть d — натуральное число, такое, что d делит нацело п и I. Исходное сообщение а € F!> представляется в виде конкатенации d «слов» длины ^ бит:

п

К каждому «слову» а* € F?, г = 1,… , d применяется нелиней;

п 1_

ная подстановка щ : F| -> F|, то есть.

При этом подстановки яд,…, 7гd могут как совпадать, так и различаться для всех индексов г = 1,…, d.

В случае когда I > п говорят, что S реализует подстановку с расширением. Примером такого преобразования является алгоритм DES, описанный нами выше.

Вместе с тем стоит отметить, что подстановки с расширением в современных шифрах встречаются редко и, как правило, выполняется равенство I = п. В этом случае каждая подстановка яд,…, 7г^ реализует взаимно однозначное отображение множества F. J в себя, то есть является перестановкой. Поскольку на практике выбираются нелинейные перестановки, то данный шаг также называют шагом нелинейного преобразования.

3. На шаге линейного преобразования к сообщению а применяется матричное преобразование L: F^l₂ ?₂. Наиболее простой способ его задания заключается в следующем.

Представим сообщение в g Fj в виде вектора а = (ai,…, сц), где oi,…, а/ € {0,1}. Тогда преобразование L может быть записано в виде.

При этом на матрицу С накладывается очевидное требование ее обратимости, то есть выполнение условия det С Ф 0. В противном случае однозначное расшифрование невозможно.

Добавим, ч то явный вид матрицы? существенно задает преобразование вектора а. Так, обратимая матрица С, у которой в каждой строке содержится только один отличный от нуля элемент, задает простую перестановку бит вектора а. Подобные матрицы часто использовались в ранних блочных шифрах, в частности в алгоритме «Люцифер».

Можно рассматривать матричное преобразование L, заданное не двоичной матрицей, а матрицей, элементами которой являются элементы некоторого конечного поля F₂, i. такого, что d делит п нацело. Примерами таких преобразований служат алгоритмы «Rijndael» и «Кузнечик».

В англоязычной литературе принято обозначать шаг наложения раундового ключа символом «X» (от английского «хог», обозначающего сложение по модулю 2), шаг нелинейного преобразования — символом «S» («substitution» — подстановка), шаг линейного преобразования — символом «L» («linear» — линейный). Эти сокращения дали подстановочно-перестановочной сети другое, более короткое, название — XSL-сеть.

Приведем несколько конкретных примеров шифров, построенных по принципу SP-сети.