“`html
SP-сеть (Substitution–Permutation Network) представляет собой математическую модель и структуру для построения блочных шифров. Она объединяет два ключевых принципа: подстановки (S-boxes) и перестановки (P-boxes), разработанные Хорнетом Сартори в 1970-х годах.
Что такое SP-сеть?
Концепция SP-сети описывает последовательность преобразований, которые применяются к входным данным блочного шифра для обеспечения его секретности. Эти преобразования делятся на два типа:
- Подстановка (Substitution): Операция, которая заменяет отдельные биты или группы битов другим значением согласно заданному табличному преобразованию.
- Перестановка (Permutation/Rearrangement): Операция, которая перемешивает биты без изменения их самих, изменяя их порядок в выходной последовательности. Иногда называемая P-boxом.
Идея заключается в том, что блочный шифр должен обеспечивать два противоположных по существу свойства:
- Замешательство (Confusion): Сложная математическая связь между любым битом выходного текста и любым битом ключа шифра. Это достигается в первую очередь за счет подстановок.
- Переплетение (Diffusion): Быстрое распространение влияния каждого разряда входного открытого текста на все выходные биты, а также противоположное – влияние ключа должно ощущаться по всему блоку. Это достигается за счет перестановок и последующих подстановок.
Принцип работы SP-сети: Подстановка (Substitution)
Подстановочный этап является основным инструментом для создания замешательства. На этом этапе входные данные разбиваются на более мелкие фрагменты, называемые словами или группами битов (например, 4-битными блоками). Каждый из этих фрагментов независимо проходит через подстановочный преобразователь – S-box.
S-box представляет собой табличное соответствие между входным и выходным состояниям. Например, стандартный 4-битовый S-box имеет вход с 16 возможными комбинациями битов (от 0000 до 1111) и выход, который также представлен 4-битовой комбинацией, но для каждой входной есть уникальное выходное значение согласно таблице. Таблица может быть нелинейной, что делает обратное восстановление исходных данных из выходного значения крайне сложным.
Рассмотрим простой пример 4-битового S-box:
| Простой 4-битовый S-box | ||||
|---|---|---|---|---|
| Вход (Hex) | A | B | C | D |
| 0-9 (0x0 – 0x9) | Выход: A’B’C’D’ | |||
Преимущество S-box заключается в его способности усложнить связь между отдельными битами. Каждый входной блок картируется на выходной блок независимо от других частей данных, что создает нелинейность и повышает устойчивость к линейному криптоанализу.
Принцип работы SP-сети: Перестановка (Permutation/Rearrangement)
Перестановочный этап, или P-box, отвечает за создание переплетения. Он работает с выходом подстановки и перемешивает его биты в определенном порядке.
Для этого используется таблица перестановки (P-table) – двумерная структура данных, которая содержит информацию о том, сколько раз каждый входной бит должен попасть в каждый выходной. Таблица может быть представлена следующим образом:
Пример 8-битового P-box для 4-битовой подстановки (после 32 S-box применений на каждом шаге):
| P-table (Пример) |
|---|
Перестановка обеспечивает необходимое разнообразие и перемешивание. Она связывает выходные биты различных подстановок друг с другом, а также пересмешивает биты внутри одного результата подстановки с учетом ключа шифра.
Общая структура SP-сети
Блок шифрования в SP-сетре проходит через несколько раундов. Каждый раунд последовательно выполняет два основных действия:
- Подстановка (S-box): Входной блок данных разбивается на n S-box, каждый из которых независимо преобразует свою часть.
- Перестановка (P-box): Результаты подстановки перемешиваются согласно P-table. Это может включать пересечение выходных битов и их распределение по новому порядку перед следующим раундом.
После завершения всех раундов, независимо от того, является ли шифр самобалансирующимся или нет, добавляется финальная подстановка (обычно соответствует S-box). Это гарантирует замешательство даже на последнем этапе.
Также может использоваться принцип обратимости: каждое преобразование в SP-сети должно быть обратимым. Это ключевая особенность, поскольку шифр должен обеспечивать возможность расшифровки с тем же секретным ключом (или его производными). Композиция подстановок и перестановок также должна сохранять свойство обратимости.
Хотя SP-сеть является теоретической моделью, многие современные блочные шифры используют её концепции. Например, алгоритм AES (Rijndael) содержит подстановку (S-box), которая используется на каждом раунде, и сложную линейную перестановку в начале и конце каждого раунда.
“`
Добавить комментарий