Алгоритм Rijndael

Алгоритм Rijndael — это симметричный блочный шифр, разработанный бельгийскими криптографами Йоаном Дайменом и Винсентом Рейменом. В 2001 году алгоритм был принят Национальным институтом стандартов и технологий США (NIST) в качестве стандарта AES (Advanced Encryption Standard), после чего стал одним из наиболее широко используемых симметричных шифров в мире. Rijndael лёг в основу стандарта AES, однако сам термин «Rijndael» обозначает более широкое семейство шифров, из которого AES является подмножеством.

История создания

Предпосылки и конкурс NIST

В конце 1990-х годов стандарт шифрования DES (Data Encryption Standard), разработанный в 1970-х годах, перестал отвечать требованиям безопасности из-за относительно короткой длины ключа (56 бит) и уязвимости к атакам полного перебора. В 1997 году NIST объявил открытый конкурс на создание нового стандарта симметричного шифрования — AES. К участию были допущены алгоритмы с длиной ключа 128, 192 и 256 бит и размером блока 128 бит.

Разработка и представление

Йоан Даймен и Винсент Реймен, работавшие в то время в Католическом университете Лёвена (Бельгия), представили на конкурс шифр под названием Rijndael. Название является комбинацией фамилий авторов (Rijmen + Daemen). Алгоритм был разработан на основе более ранних шифров Square и Shark, предложенных теми же авторами. Rijndael отличался высокой производительностью как в программной, так и в аппаратной реализации, а также обладал гибкой архитектурой, позволяющей варьировать размер блока и ключа.

Победа в конкурсе и стандартизация

В 2000 году NIST объявил Rijndael победителем конкурса. Основными критериями выбора стали безопасность, эффективность, простота реализации и гибкость. В 2001 году стандарт AES был официально опубликован как FIPS PUB 197. При стандартизации NIST зафиксировал размер блока 128 бит, оставив три варианта длины ключа (128, 192, 256 бит). Таким образом, AES является подмножеством Rijndael, поскольку оригинальный Rijndael поддерживал также размеры блока 192 и 256 бит.

Общая структура и принципы работы

Симметричный блочный шифр

Rijndael относится к классу симметричных блочных шифров, где один и тот же ключ используется как для шифрования, так и для расшифрования. Данные разбиваются на блоки фиксированного размера (в AES — 128 бит), каждый из которых преобразуется независимо (или с использованием режимов сцепления блоков).

Подстановочно-перестановочная сеть

В отличие от многих предшественников (например, DES), использующих сеть Фейстеля, Rijndael построен на основе подстановочно-перестановочной сети (SP-сеть). Это означает, что каждый раунд шифрования состоит из последовательных операций подстановки (замены байтов) и перестановки (перемешивания байтов), что обеспечивает быстрое рассеивание и запутывание данных.

Состояние и ключевое расписание

Внутреннее состояние алгоритма представляется в виде двумерного массива байтов размером 4×4 (для блока 128 бит). Каждый байт состояния преобразуется в ходе раундов. Ключевое расписание (Key Schedule) генерирует из исходного ключа набор раундовых ключей, которые складываются по модулю 2 (XOR) с состоянием на каждом раунде.

Детальное описание раундовых преобразований

SubBytes (подстановка байтов)

На этом этапе каждый байт состояния заменяется другим байтом в соответствии с фиксированной таблицей замены (S-box). S-box построен на основе математических операций в поле Галуа GF(2⁸) и обладает свойствами нелинейности, что делает шифр устойчивым к линейному и дифференциальному криптоанализу.

ShiftRows (сдвиг строк)

Байты в строках состояния циклически сдвигаются влево. Первая строка не сдвигается, вторая — на 1 байт, третья — на 2 байта, четвёртая — на 3 байта. Эта операция обеспечивает перемешивание данных между столбцами.

MixColumns (перемешивание столбцов)

Каждый столбец состояния рассматривается как многочлен над GF(2⁸) и умножается на фиксированный многочлен по модулю x⁴ + 1. Эта операция дополнительно перемешивает байты внутри столбцов, обеспечивая диффузию.

AddRoundKey (добавление раундового ключа)

Состояние складывается по модулю 2 (XOR) с раундовым ключом, полученным из ключевого расписания. Эта операция вносит зависимость от ключа в каждый раунд.

Количество раундов и варианты

Количество раундов зависит от длины ключа и размера блока:

• Для AES-128 (ключ 128 бит, блок 128 бит) — 10 раундов.
• Для AES-192 (ключ 192 бит, блок 128 бит) — 12 раундов.
• Для AES-256 (ключ 256 бит, блок 128 бит) — 14 раундов.

В оригинальном Rijndael количество раундов могло варьироваться в зависимости от размера блока и ключа (например, для блока 256 бит и ключа 256 бит — 14 раундов).

Ключевое расписание (Key Schedule)

Ключевое расписание преобразует исходный ключ в набор раундовых ключей. Процесс включает:

• RotWord — циклический сдвиг последнего слова (4 байта) ключа.
• SubWord — применение S-box к каждому байту слова.
• XOR с константой раунда — константа (Rcon) зависит от номера раунда и является степенью двойки в поле GF(2⁸).

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

Режимы работы

Rijndael (как AES) обычно используется не как самостоятельный шифр, а в сочетании с режимами сцепления блоков. Наиболее распространённые режимы:

• ECB (Electronic Codebook) — каждый блок шифруется независимо; уязвим для атак по шаблонам, не рекомендуется для большинства применений.
• CBC (Cipher Block Chaining) — каждый блок XOR-ится с предыдущим зашифрованным блоком; требует вектор инициализации (IV).
• CTR (Counter) — шифрование счётчика; позволяет параллельную обработку и произвольный доступ.
• GCM (Galois/Counter Mode) — обеспечивает как шифрование, так и аутентификацию (AEAD).

Безопасность и криптоанализ

Устойчивость к известным атакам

На 2024 год AES (Rijndael) считается криптостойким алгоритмом. Наиболее эффективные известные атаки (биклинейный криптоанализ, атаки на основе связанных ключей) имеют сложность, значительно превышающую полный перебор ключа (2¹²⁸ для AES-128). Для AES-192 и AES-256 теоретические атаки снижают сложность до 2¹⁷⁶ и 2²⁵⁴ соответственно, что всё ещё не представляет практической угрозы.

Атаки по сторонним каналам

Аппаратные реализации Rijndael могут быть уязвимы к атакам по сторонним каналам (анализ времени выполнения, потребляемой мощности, электромагнитного излучения). Для защиты применяются методы маскирования, скремблирования и балансировки времени.

Квантовая устойчивость

Алгоритм не является квантово-устойчивым. Согласно оценкам, квантовый компьютер с достаточным количеством кубитов мог бы выполнить атаку Гровера, снизив эффективную стойкость AES-128 до 2⁶⁴ операций. Поэтому для долгосрочной защиты данных (например, государственных секретов) рекомендуется использовать AES-256.

Применение

Стандарт AES

AES является обязательным для защиты информации в государственных учреждениях США (в соответствии с FIPS 140-3) и широко применяется в коммерческих продуктах. Он используется в:

• Протоколах безопасности — TLS/SSL, IPsec, SSH, Wi-Fi Protected Access 2 (WPA2) и 3 (WPA3).
• Шифровании дисков — BitLocker, FileVault, LUKS, VeraCrypt.
• Архиваторах и файловых системах — 7-Zip, WinRAR, ZFS.
• Криптовалютах — Bitcoin, Ethereum (для хэширования и подписи, AES не используется напрямую, но применяется в некоторых кошельках).

Встраиваемые системы и аппаратные реализации

Благодаря высокой эффективности на процессорах с поддержкой инструкций AES-NI (AES New Instructions), Rijndael широко применяется в мобильных устройствах, смарт-картах, банкоматах и IoT-устройствах.

Критика и альтернативы

Критика

• Сложность ключевого расписания — некоторые исследователи (например, Джон Келси и Брюс Шнайер) отмечали, что ключевое расписание AES-128 обладает меньшей «диффузией» по сравнению с AES-256, что теоретически может сделать его уязвимым для атак на связанных ключах.
• Отсутствие аутентификации — сам по себе AES не обеспечивает целостность данных; требуется использование режимов аутентифицированного шифрования (GCM, CCM).
• Фиксированный размер блока — 128 бит может быть недостаточно для некоторых приложений (например, шифрование баз данных с большими объёмами данных), где предпочтительнее 256-битный блок (как в оригинальном Rijndael).

Альтернативы

• ChaCha20 — потоковый шифр, разработанный Дэниелом Бернштейном; популярен в протоколах TLS и VPN (например, WireGuard) благодаря высокой скорости на процессорах без аппаратной поддержки AES.
• Camellia — японский блочный шифр, одобренный ISO/IEC; используется в некоторых криптографических библиотеках.
• Кузнечик — российский стандарт симметричного шифрования (ГОСТ Р 34.12-2015), принятый в 2015 году, с размером блока 128 бит и ключом 256 бит.

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

• Название «Rijndael» произносится как «Рейндал» (в английской транскрипции — «Rine-dahl»).
• Авторы алгоритма — Йоан Даймен и Винсент Реймен — не получали лицензионных отчислений за использование AES, поскольку алгоритм был опубличен как общественное достояние.
• В 2003 году правительство США объявило, что AES может использоваться для защиты информации с грифом «Секретно» (Secret), а AES-256 — для защиты «Совершенно секретно» (Top Secret).
• В 2019 году NIST начал процесс стандартизации лёгких шифров (Lightweight Cryptography) для IoT, но AES остаётся основным стандартом для большинства применений.

Источники

• FIPS PUB 197 — Advanced Encryption Standard (AES), National Institute of Standards and Technology, 2001.
• Daemen, J., Rijmen, V. — The Design of Rijndael: AES — The Advanced Encryption Standard, Springer, 2002.
• Schneier, B. — Applied Cryptography, 2nd Edition, John Wiley & Sons, 1996.
• NIST Special Publication 800-38A — Recommendation for Block Cipher Modes of Operation, 2001.
• ГОСТ Р 34.12-2015 — Информационная технология. Криптографическая защита информации. Блочные шифры.