Rijndael

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

История

Разработка Rijndael началась в конце 1990-х годов. К тому времени стандарт шифрования DES (Data Encryption Standard), принятый в 1977 году, устарел: его ключ длиной 56 бит стал уязвим для атак полным перебором. В 1997 году NIST объявил конкурс на создание нового стандарта — AES. К участию были допущены 15 алгоритмов, из которых в финал вышли пять: MARS, RC6, Serpent, Twofish и Rijndael.

Авторы Rijndael — Йоан Даймен и Винсент Рэймен — представили свой алгоритм, основанный на структуре, названной ими «квадрат» (Square). 2 октября 2000 года NIST объявил Rijndael победителем конкурса. Основными причинами выбора стали высокая скорость работы на различных платформах, простота реализации, устойчивость к известным криптоаналитическим атакам и гибкость в поддержке разных длин ключа и блока. 26 ноября 2001 года AES был официально опубликован как стандарт FIPS PUB 197.

Структура и принцип работы

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

Основные параметры

В отличие от AES, который фиксирует длину блока в 128 бит, семейство Rijndael допускает длины блока и ключа, кратные 32 битам, в диапазоне от 128 до 256 бит. На практике AES использует следующие комбинации:

Раунды

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

1. SubBytes (Замена байтов). Каждый байт состояния (промежуточного массива данных) заменяется на другой байт в соответствии с нелинейной таблицей замены (S-блоком). S-блок построен на основе математических операций в поле Галуа GF(2⁸), что обеспечивает устойчивость к линейному и дифференциальному криптоанализу.
2. ShiftRows (Сдвиг строк). Строки состояния циклически сдвигаются влево на разное количество байтов: первая строка не сдвигается, вторая — на 1 байт, третья — на 2, четвёртая — на 3. Это обеспечивает перемешивание данных между столбцами.
3. MixColumns (Перемешивание столбцов). Каждый столбец состояния рассматривается как многочлен над GF(2⁸) и умножается по модулю на фиксированный многочлен. Этот этап обеспечивает диффузию (распространение влияния одного бита исходного текста на множество битов шифротекста).
4. AddRoundKey (Добавление раундового ключа). К состоянию применяется операция XOR с раундовым ключом, полученным из основного ключа с помощью процедуры расширения ключа.

Перед первым раундом выполняется начальное добавление ключа (AddRoundKey), а в последнем раунде этап MixColumns опускается.

Расширение ключа

Из исходного ключа шифрования с помощью алгоритма расширения (Key Expansion) генерируется необходимое количество раундовых ключей. Каждый раундовый ключ имеет ту же длину, что и блок. Процесс включает циклический сдвиг, замену байтов через S-блок и сложение с константами раунда.

Криптоанализ и безопасность

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

Известные атаки

• Атаки на уменьшенное число раундов. Существуют атаки, эффективные против версий Rijndael с меньшим количеством раундов (например, 6 или 7 раундов вместо 10). Однако они не представляют угрозы для полного шифра.
• Атаки по сторонним каналам. Криптоанализ, основанный на измерении времени выполнения, энергопотребления или электромагнитного излучения устройства, реализующего алгоритм, может быть эффективен против программных или аппаратных реализаций. Для защиты от таких атак применяются методы маскирования и сокрытия.
• Квантовые атаки. Согласно оценкам, квантовый компьютер с использованием алгоритма Гровера мог бы сократить эффективную длину ключа AES вдвое. То есть для взлома AES-128 потребовалось бы около 2⁶⁴ операций, что всё ещё считается практически невозможным при текущем уровне развития квантовых технологий.

Критика

Основные критические замечания в адрес Rijndael касаются не его криптостойкости, а структуры. В частности, математическая простота S-блока (основанного на обратной функции в поле Галуа) вызывает опасения, что в будущем могут быть найдены алгебраические атаки, использующие эту структуру. Однако на данный момент таких атак не существует.

Применение

Rijndael (AES) является одним из самых распространённых симметричных шифров в мире. Он используется в:

• Беспроводных сетях: протоколы WPA2 и WPA3 для защиты Wi-Fi.
• Интернет-протоколах: TLS (HTTPS), IPsec, SSH.
• Шифровании данных: BitLocker (Microsoft), FileVault (Apple), LUKS (Linux).
• Архиваторах и программах для шифрования файлов: 7-Zip, WinRAR, VeraCrypt.
• Государственных и военных системах: AES утверждён для защиты информации с грифом «секретно» и «совершенно секретно» правительством США (при использовании ключей 192 и 256 бит соответственно).

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

• Название «Rijndael» является комбинацией фамилий авторов: Rijmen и Daemen.
• Алгоритм был разработан до того, как NIST объявил конкурс на AES. Первая версия называлась Square и была представлена в 1997 году.
• В процессорах Intel, начиная с архитектуры Westmere (2010), появилась аппаратная поддержка инструкций AES-NI, что значительно ускоряет выполнение шифрования и дешифрования.

Источники

• Joan Daemen, Vincent Rijmen. The Design of Rijndael: AES — The Advanced Encryption Standard. Springer, 2002.
• National Institute of Standards and Technology. FIPS PUB 197: Advanced Encryption Standard (AES). 2001.
• William Stallings. Криптография и защита сетей: принципы и практика. Вильямс, 2021.
• Bruce Schneier. Прикладная криптография. Триумф, 2002.