О терминологии. Или почему «кошка» (которая изначально «лиса») не всегда «прыгает».

Если вы когда-нибудь читали описание криптоалгоритмов (например, классическую сеть Хорста Фейстеля), а потом открывали учебник по высшей алгебре, у вас могло возникнуть ощущение легкого когнитивного диссонанса. Слова одни и те же, но значат они разное. Давайте внесем ясность, используя иронию и классическую фразу "The quick brown fox jumps over the lazy dog".

1. Substitution (Замена): "Кошка вместо лисы"

В инженерном смысле (в тех же S-блоках) Substitution — это когда мы берем один объект и подменяем его другим по таблице или формуле.

Пример: Мы решили, что "fox" теперь всегда будет "cat".

Фраза превращается в: "The quick brown cat jumps over...". Объект подменили, но он остался на том же месте. Математик, глядя на это, скажет: "Это функция f(x) = y". И если эта замена уникальна (без коллизий), он назовет её перестановкой элементов множества. Вот тут и зарыта собака (ленивая).

2. Permutation (Перестановка): "Прыжок через собаку"

Для инженера Permutation (P-блок) — это изменение позиции. Мы не меняем буквы, мы меняем их местами.

Пример: "Fox jumps" превращается в "Jumps fox".

В классических шифрах P-блок просто перепутывает биты местами. Но для математика "перестановка" — это свойство самой функции замены. Если вы заменили 1 на 5, а 5 на 1 — это уже перестановка множества, даже если цифра стоит на том же месте в байте.

3. Инволюция: Зеркальный мир Фейстеля

Вспомним Хорста Фейстеля. Его гениальная сеть превращает любую "кривую" функцию в инволюцию. Инволюция — это высшая форма взаимности: если f(x) = y, то f(y) = x.

Важное отличие:

• Сеть Фейстеля: Является инволюцией по своей структуре. Вам не нужен отдельный алгоритм для расшифровки — вы просто прогоняете данные назад через те же блоки. "Кошка прыгнула через собаку" — и тем же движением вернулась обратно.
• AES (Rijndael): Не является инволюцией. Его S-блоки "однонаправленные". Если 1 превращается в 5, то 5 может превратиться в 9. Чтобы расшифровать AES, вам нужны совершенно другие таблицы и обратные операции. Кошка прыгнула, но обратно её нужно тащить за хвост другим способом.

Чтобы окончательно понять, как "кошка" совершает свой трюк, посмотрите на схему одного раунда ячейки Фейстеля:

       Входной блок (64/128 бит)
      __________ | __________
     |                       |
 [Левая часть L]       [Правая часть R]
     |                       |
     |                ( Копирование )-------+
     |                       |              |
     |                [  Функция f  ] <--- [Ключ K]
     |                (Substitution)        |
     |                       |              |
  ( XOR ) <----------- [Результат f]        |
     |                                      |
     v                                      v
 [Новая правая R']      [Новая левая L']
      \                     /
       \       Прыжок      /
        \  (Permutation)  /
         \      / \      /
          \    /   \    /
           \  /     \  /
            \/       \/
            /\       /\
           /  \     /  \
          /    \   /    \
    [Выход L]         [Выход R]
    

Обратите внимание: Функция f может быть любым сложным алгоритмом. Благодаря тому, что изменения вносятся только в одну половину, а затем стороны меняются местами, структура остается инволюционной.

Итог

Когда мы обсуждали многочлены Диксона или Ривеста, мы искали такие механизмы Замены (Substitution), которые математически являются идеальными Перестановками (Permutation).

Криптография — это искусство превращать простые "прыжки кошки" в нечитаемый хаос, сохраняя при этом возможность одним изящным движением вернуть "лису" на её законное место.

Иногда Fox становится Cat, но мы всё равно знаем, что это Fox. 🦊 🙂 😼