Алгоритм шифрования «Кузнечик»: как работает российский блочный шифр

«Кузнечик» — современный российский симметричный алгоритм шифрования. Он работает с блоками по 128 бит и использует ключ длиной 256 бит. Алгоритм входит в ГОСТ 34.12-2018 и применяется в системах криптографической защиты информации.

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

Что такое «Кузнечик»

«Кузнечик» — симметричный блочный шифр.

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

Блочный — что данные обрабатываются частями фиксированной длины.

У «Кузнечика»:

• размер блока — 128 бит, или 16 байт;
• размер ключа — 256 бит, или 32 байта.

Алгоритм был впервые стандартизован в ГОСТ Р 34.12-2015, а затем вошёл в ГОСТ 34.12-2018. Международное описание опубликовано в RFC 7801 под названием Kuznyechik — именно такая транслитерация используется в англоязычном техническом документе. Буквальный перевод русского слова кузнечик — grasshopper, но официальное англоязычное название алгоритма не переводят.

Почему алгоритм называется «Кузнечик»

У названия есть любопытная история.

В профессиональной среде распространена расшифровка:

КУЗ — Кузьмин,
НЕЧ — Нечаев,
И К — «и компания».

То есть «КУЗ-НЕЧ-ИК» читается как своеобразная игра слов: «Кузьмин, Нечаев и компания». Именно такую версию приводят публикации о происхождении названия алгоритма. При этом в самом ГОСТе эта расшифровка официально не закреплена, поэтому корректнее считать её общепринятой профессиональной версией, а не формальным названием из стандарта.

Есть и более прозаичное объяснение: авторы алгоритма отмечали, что название продолжает традицию криптографических алгоритмов с необычными и труднопроизносимыми именами вроде Rijndael и Keccak.

Как работает шифрование «Кузнечик»

Алгоритм несколько раз преобразует один 128-битный блок.

В каждом раунде используются три основные операции:

• X — смешивание данных с ключом;
• S — нелинейная замена;
• L — линейное перемешивание.

Такую конструкцию называют подстановочно-перестановочной сетью.

Если упростить, каждый раунд делает три вещи: добавляет влияние ключа, ломает простые зависимости между байтами и распространяет изменения по всему блоку.

Шаг 1. Смешивание с ключом

Сначала данные объединяются с очередным раундовым ключом с помощью операции XOR.

Для отдельных битов XOR работает так:

0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0

Эта операция быстро и обратимо смешивает данные с секретным ключом.

Самого XOR для надёжного шифрования недостаточно, поэтому сразу после него выполняются более сложные преобразования.

Шаг 2. Нелинейная замена

Далее каждый байт заменяется другим по специальной таблице — S-блоку.

Таблица содержит 256 значений: по одному для каждого возможного байта от 0 до 255.

Условно принцип можно представить так:

10 заменить на 45,
45 заменить на 1,
1 заменить на 238.

Реальная таблица зафиксирована стандартом.

Главная задача S-преобразования — добавить нелинейность. Благодаря этому нельзя описать шифр набором простых линейных уравнений и легко восстановить исходные данные.

Шаг 3. Линейное преобразование

После подстановки выполняется L-преобразование.

Его задача — распространить влияние каждого изменённого байта на весь блок.

Если изменить один бит исходного текста, после нескольких раундов это изменение затронет множество битов результата.

Так появляется эффект, важный для стойкого шифра: два почти одинаковых сообщения дают совершенно разные шифротексты.

Сколько раундов используется

Из исходного 256-битного ключа алгоритм получает 10 раундовых ключей.

Первые девять раундов выполняют последовательность:

X → S → L

После этого применяется десятый раундовый ключ.

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

Откуда берутся раундовые ключи

Пользователь задаёт один ключ длиной 256 бит.

Алгоритм делит его на две части и с помощью специальной процедуры развёртки получает остальные раундовые ключи.

При этом используются те же типы преобразований: XOR, подстановки, линейное преобразование и специальные константы.

То есть раундовые ключи не выбираются случайно и не задаются вручную — они вычисляются из исходного секрета.

Как происходит расшифрование

Все преобразования «Кузнечика» обратимы.

При расшифровании используются обратные операции:

• обратное линейное преобразование;
• обратная S-подстановка;
• раундовые ключи в обратном порядке.

Если ключ правильный, исходный текст восстанавливается полностью.

Если нет — получается бессмысленный набор данных.

Почему одного алгоритма недостаточно

«Кузнечик» шифрует один блок размером 16 байт.

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

Режим определяет, как обрабатывать последовательность блоков и как связывать их между собой.

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

Поэтому в реальных системах безопасность зависит не только от самого «Кузнечика», но и от правильно выбранного режима, генерации ключей и всей реализации.

Насколько велик ключ

Ключ длиной 256 бит даёт:

2²⁵⁶ возможных вариантов.

Это настолько большое пространство, что полный перебор практически нереален.

Но стойкий алгоритм ещё не означает автоматически безопасную систему.

На практике злоумышленнику часто проще:

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

Поэтому криптографическая стойкость — только одна часть общей безопасности.

«Магма» и «Кузнечик»: в чём разница

ГОСТ 34.12-2018 описывает два блочных шифра — «Магму» и «Кузнечик».

У обоих ключ длиной 256 бит, но архитектура разная.

Размер блока

«Магма» — 64 бита.
«Кузнечик» — 128 бит.

Более крупный блок удобнее при обработке больших объёмов данных и снижает ряд ограничений, связанных с повторением блоков.

Архитектура

«Магма» использует сеть Фейстеля и развивает идеи более раннего ГОСТ 28147-89.

«Кузнечик» построен как подстановочно-перестановочная сеть.

Число раундов

У «Магмы» — 32 раунда.

У «Кузнечика» — 10 раундовых ключей и девять основных преобразований X–S–L перед финальным наложением ключа.

Само число раундов ничего не говорит о сравнительной стойкости: раунды у этих алгоритмов устроены по-разному.

Где используется «Кузнечик»

Алгоритм предназначен для программной и аппаратной реализации в системах криптографической защиты информации.

Он может использоваться в:

• защищённых каналах связи;
• средствах шифрования;
• аппаратных криптомодулях;
• корпоративных системах;
• государственных информационных системах.

Сам «Кузнечик» — не программа и не готовое приложение, а математически точно описанный алгоритм.

Его можно реализовать в программном коде, микросхеме или специальном криптографическом устройстве.

От шифровальных машин к математике

«Кузнечик» хорошо показывает, как изменилась криптография за XX век.

В «Энигме» и других роторных машинах шифрование выполняли физические диски, контакты и провода.

В современных алгоритмах ту же задачу решают математические преобразования, которые процессор выполняет за доли секунды.

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

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