Алгоритм – победитель конкурса AES, объявленный в 2000 году, был разработан двумя бельгийскими криптографами Дименом (Daemen) и Рийменом (Rijmen). Эта криптосистема не является обобщением шифра Фейстеля. В основе алгоритма – повторяющиеся раунды, каждый из которых состоит из замен, перестановок и прибавления ключа. Кроме того, AES использует сильную математическую структуру: большинство его операций основано на арифметике поля . Однако в отличие от DES зашифрование и расшифрование в этом алгоритме – процедуры разные. Элементы поля хранятся в памяти компьютера в виде 8-битовых векторов (байтов). Например последовательность ‘1000 0011b’ соответствует многочлену X 7 + X + 1 над полем F2 или шестнадцатиричному числу ‘83h’.
Арифметические операции в поле соответствуют операциям над двоичными многочленами из F2[X] по модулю неприводимого многочлена
m(X) = X 8 + X 4 + X 3 + X + 1.
В алгоритме AES 32-битовые слова отождествляются с многочленами степени 3 из [X]. Отождествление делается в формате «перевертыш», то есть старший бит соответствует младшему коэффициенту многочлена. Так, например, слово
a0||a1||a2||a3
соответствует многочлену
a3X 3 + a2X 2 + a1X + a0.
Арифметика в алгоритме совпадает с арифметическими действиями в кольце многочленов [X] по модулю многочлена M(X) = X 4 + 1. Заметим, что многочлен M(X) = (X + 1)4 приводим, и, следовательно, арифметические действия в алгоритме отличны от операций поля, в частности, бывают пары ненулевых элементов, произведение которых равно 0.
AES – настраиваемый блочный алгоритм, который может работать с блоками из 128, 192 или 256 битов. Для каждой комбинации размера блока и размера ключа определено свое количество раундов. Здесь рассматривается самый простой вариант алгоритма, при котором блоки, как и ключ, состоят из 128 битов. В этом случае в алгоритме выполняется 10 раундов.
Алгоритм оперирует с внутренней байтовой матрицей размера 4 на 4, называемой матрицей состояний:
,
которую обычно записывают как вектор 32-битовых слов. Каждое слово в векторе представляет собой столбец матрицы. Подключи также хранятся в виде матрицы 4 на 4:
.