Алгоритм AES (Rijndael)

Алгоритм – победитель конкурса AES, объявленный в 2000 году, был разработан двумя бельгийскими криптографами Дименом (Daemen) и Рийменом (Rijmen). Эта криптосистема не является обобщением шифра Фейстеля. В основе алгоритма – повторяющиеся раунды, каждый из которых состоит из замен, перестановок и прибавления ключа. Кроме того, AES использует сильную математическую структуру: большинство его операций основано на арифметике поля . Однако в отличие от DES зашифрование и расшифрование в этом алгоритме – процедуры разные. Элементы поля хранятся в памяти компьютера в виде 8-битовых векторов (байтов). Например последовательность ‘1000 0011b’ соответствует многочлену X ⁷ + X + 1 над полем F ₂ или шестнадцатиричному числу ‘83h’.

Арифметические операции в поле соответствуют операциям над двоичными многочленами из F ₂[ X ] по модулю неприводимого многочлена

m (X) = X ⁸ + X ⁴ + X ³ + X + 1.

В алгоритме AES 32-битовые слова отождествляются с многочленами степени 3 из [ X ]. Отождествление делается в формате «перевертыш», то есть сташий бит соответствует младшему коэффициенту многочлена. Так, например, слово

a ₀|| a ₁|| a ₂|| a ₃

соответствует многочлену

a ₃ X ³ + a ₂ X ² + a ₁ X + a ₀.

Арифметика в алгоритме совпадает с арифметическими действиями в кольце многочленов [ X ] по модулю многочлена M (X) = X ⁴ + 1. Заметим, что многочлен M (X) = (X + 1)⁴ приводим, и, следовательно, арифметические действия в алгоритме отличны от операций поля, в частности, бывают пары ненулевых элементов, произведение которых равно 0.

AES – настраиваемый блочный алгоритм, который может работать с блоками из 128, 192 или 256 битов. Для каждой комбинации размера блока и размера ключа определено свое количество раундов. Здесь рассматривается самый простой вариант алгоритма, при котором блоки, как и ключ, состоят из 128 битов. В этом случае в алгоритме выполняется 10 раундов.

Алгоритм оперирует с внутренней байтовой матрицей размера 4 на 4, называемой матрицей состояний:

,

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

.