Advanced Encryption Standard

Алгоритм блочного шифрования
Название:	AES, Rijndael-AES, Rijndael
Разработчик:	В.Риджмен, Д.Даймон
Создан:	1998 г.
Опубликован:	2001 г.
Размер ключа:	128/192/256 бит
Размер блока:	128 бит
Число раундов:	10/12/14
Тип:	Substitution permutation network

Advanced Encryption Standard (AES), также известный, как Rijndael — симметричный алгоритм блочного шифрования (размер блока 128 бит, ключ 128/192/256 бит), финалист конкурса AES и принятый в качестве американского стандарта шифрования правительством США. Выбор был сделан с расчётом на повсеместное использование и активный анализ алгоритма, как это было с его предшественником, DES. Государственный институт стандартов и технологий (англ. National Institute of Standards and Technology, NIST) США опубликовал предварительную спецификацию AES 26 ноября 2001 года, после пятилетней подготовки. 26 мая 2002 года AES был объявлен стандартом шифрования. По состоянию на 2006 год AES является одним из самых распространённых алгоритмов симметричного шифрования.

История

Необходимость в принятии нового стандарта была вызвана небольшой длиной ключа DES (56 бит), что позволяло применить метод грубой силы (полный перебор ключей) против этого алгоритма. Кроме того, архитектура DES была ориентирована на аппаратную реализацию, и программная реализация алгоритма на платформах с ограниченными ресурсами не давала достаточного быстродействия. Модификация 3-DES обладала достаточной длиной ключа, но при этом была ещё медленнее.

Начало конкурса

2 января 1997 года NIST объявляет [1] о намерении выбрать преемника для DES, являвшегося американским стандартом с 1977 года. Однако, вместо опубликования алгоритма, NIST принял различные предложения от заинтересованных сторон о том, каким образом следует выбирать алгоритм. Бурный отклик со стороны открытого криптографического сообщества привёл к объявлению конкурса (12 сентября 1997 г.). Свой алгоритм могла предложить любая организация или группа исследователей. Требования к новому стандарту были следующими:

• блочный шифр.
• длина блока, равная 128 битам.
• ключи длиной 128, 192 и 256 бит.

Подобные шифры были довольно редки во время объявления конкурса; возможно, лучшим был Square. Дополнительно кандидатам рекомендовалось:

• использовать операции, легко реализуемые как аппаратно (в микрочипах), так и программно (на персональных компьютерах и серверах)
• ориентироваться на 32-разрядные процессоры
• не усложнять без необходимости структуру шифра для того, чтобы все заитересованные стороны были в состоянии самостоятельно провести независимый криптоанализ алгоритма и убедиться, что в нём не заложено каких-либо недокументированных возможностей.

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

1-й и 2-й раунды

20 августа 1998 года на 1-й конференции AES был объявлен список из 15 кандидатов: CAST-256, CRYPTON, DEAL, DFC, E2, FROG, HPC, LOKI97, MAGENTA, MARS, RC6, Rijndael, SAFER+, Serpent, Twofish. В последующих обсуждениях эти алгоритмы подвергались всестороннему анализу, причём исследовались не только криптографические свойства, такие как стойкость к известным атакам, отсутствие слабых ключей, но и практические аспекты реализации: оптимизацию скорости выполнения кода на различных архитектурах (от ПК до смарт-карт и аппаратных реализаций), возможность оптимизации размера кода, возможность распаралелливания. В марте 1999 года прошла 2-я конференция AES, а в августе 1999 года были объявлены 5 финалистов: MARS, RC6, Rijndael, Serpent и Twofish. Все эти алгоритмы были разработаны авторитетными криптографами с мировым именем. На 3-й конференции AES в апреле 2000 года авторы выступили с докладами о своих алгоритмах.

Третья конференция AES

Третья конференция AES прошла в Нью-Йорке 13 и 14 апреля 2000 года, незадолго до завершения второго этапа. На ней присутствовало 250 участников, многие из которых приехали из-за рубежа. Двухдневная конференция была разделена на восемь сессий, по четыре в день, плюс к тому состоялась неформальная дополнительная сессия, подводившая итоги первого дня. На сессиях первого дня обсуждались вопросы, связанные с программируемыми матрицами (FPGA), проводилась оценка реализации алгоритмов на различных платформах, в том числе PA-RISC, IA-64, Alpha, высокоуровневых смарт-картах и сигнальных процессорах, сравнивалась производительность претендентов на стандарт, анализировалось число раундов в алгоритмах-кандидатах. На сессиях второго дня был проанализирован Rijndael с сокращённым числом раундов и показана его слабость в этом случае, обсуждался вопрос об интегрировании в окончательный стандарт всех пяти алгоритмов-претендентов, ещё раз тестировались все алгоритмы. В конце второго дня была проведена презентация, на которой претенденты рассказывали о своих алгоритмах, их достоинствах и недостатках. О Rijndael рассказал Винсент Риджмен, заявивший о надёжности защиты, высокой общей производительности и простоте архитектуры своего кандидата.

Выбор победителя

2 октября 2000 года было объявлено[2], что победителем конкурса стал алгоритм Rijndael, и началась процедура стандартизации. 28 февраля 2001 года был опубликован проект, а 26 ноября 2001 года AES был принят как FIPS 197.

Историческую ретроспективу конкурса можно проследить на веб-сайте NIST [3].

Описание алгоритма

Строго говоря, AES не тождественнен Rijndael, так как Rijndael поддерживает широкий диапазон длин ключей и блоков. В AES размер блока фиксирован и равен 128 бит, размер ключа может быть 128, 192 или 256 бит, а в Rijndael поддерживаются различные длины ключей и блоков — от 128 до 256 бит, с шагом 32 бита. Ключ шифрования может быть расширен, используя процедуру Rijndael’s key schedule. Большинство вычислений в AES выполняются в конечных полях. AES оперирует с массивом 4x4 байта, называемые состоянием. На каждом раунде алгоритма (число раундов зависит от длины ключа) выполняются 4 действия:

1. SubBytes — Нелинейная подстановка байт с использованием специально выбранной таблицы подстановки lookup table.
2. ShiftRows — Циклический сдвиг вправо каждой строки матрицы на определённое число байт, зависящее от номера строки и размера блока. Для длины блоков от 128 до 196 бит первая строка не сдвигается, вторая строка сдвигается на 1 байт, третья на 2, четвёртая на 3. Для длины блока 256 бит третья строка сдвигается на 3 байта, четвёртая на 4 байта.
3. MixColumns — Операция перемешивания байт каждого столбца матрицы путём умножения столбца на определённую матрицу.
4. AddRoundKey — Каждый байт структуры комбинируется с ключом раунда (ключ каждого раунда получают из ключа шифрования используя процедуру key schedule).

Ссылки

• О процессе принятия AES (русск.)
• AES cтандарт (русск.)