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

Алгоритм AES обладает следующими параметрами:

• • длина ключа: га = 128, 192 или 256,
• • длина раундового ключа: s = 128,
• • длина блока обрабатываемых данных: п = 128,
• • количество раундов: г = 10, 12 или 14 в зависимости от длины ключа.

Алгоритм развертки ключа позволяет выработать последовательность к,…, к_г+ раундовых ключей и заключается в следующем. Исходный ключ к представляется в виде конкатенации «слов» размером 32 бита, то есть.

и величина с принимает значения 4, G или 8 в зависимости от длины ключа.

Величины h,…, 1_с являются начальными значениями последовательности, состоящей из 4(г + 1) элементов множества Fip. Для выработки остальных значений используются следующие рекуррентные соотношения. При с = 4, б для всех индексов г — с+ 1, …, 4(r + 1) выполнено равенство.

При с = 8 для всех индексов г = с + 1,…, 4(r + 1) выполнено равенство.

Приведенные соотношения используют две вспомогательные функции SubWord (): F’J² -" F:]² и RotWord (): F:]² -" F: J², а также набор констант щ,…, и_с— е Ff², образующих последовательность целых чисел.

1,2,4,8,16,32,64,128.

Функции Sub Word и RotWord определяются следующим образом. Представим а е Fip в виде конкатенации а = 0411"211^аз||"4, где ах,…, (X4 G F§, тогда.

где перестановка 7 г определена равенством (7.17).

Последовательность раундовых ключей к],…, k_r+i € F.^²⁸ алгоритма AES определяется равенствами ki = lu-zhi-2Ui-ihi для всех г = 1,…, r + 1.

Перейдем к описанию алгоритма зашифрования. Вначале исходное сообщение а € FJ,²⁸ представляется в виде конкатенации байт — элементов множества F⁸. Для алгоритма AES часто используют матричную форму представления сообщения а, то есть.

Каждый раундовый ключ /с_г, г = 1,…, г + 1, также представляется в виде конкатенации.

Алгоритм зашифрования представляет собой SP-сеть и определяется равенством (7.3), в котором преобразования U, R, W определяются следующим образом. Преобразование U не определено, и мы будем считать, что выполнено равенство U (a) — а для любого, а € F!²⁸.

Раундовое преобразование R (ki, a), i — 1,…, г, состоит из четырех простых преобразований.

1. Преобразование AddRoundKey представляет собой наложение ключа по модулю два и определяется равенством.

выполненным для всех г = 1,…, г.

2. Преобразование SubBytes представляет собой параллельное применение нелинейной перестановки тт, определенной нами выше равенством (7.17),.

3. Преобразование ShiftRows представляет собой перестановку байт сообщения а, имеющую наглядное геометрическое представление. Определим

Теперь легко заметить, что преобразование ShiftRows есть циклический сдвиг второй строки матрицы, соответствующей сообщению а, на одну позицию влево, третьей строки матрицы — на две позиции влево и четвертой строки матрицы — на три позиции влево.

4. Преобразование MixColumns представляет собой умножение столбцов матрицы, соответствующей заданному сообщению а, на некоторый фиксированный многочлен из кольца /?4(IF₂"), где поле F₂s порождено неприводимым над полем F₂ многочленом д (х) — X^s + х^л + х³ + х + 1, а кольцо ft₄(F₂s) порождено приводимым над полем F₂s многочленом к (х) = х⁴ + 1.

Преобразование MixColumns представляет собой отображение.

в котором коэффициенты bi,…, bie определяются следующим образом.

Рассмотрим многочлен с (х) — аго+одж+аг^+аз#³, коэффициенты которого принадлежат конечному полю F₂" и определяются равенствами.

Тогда коэффициенты ф,…, Ьщ удовлетворяют равенствам.

Приведенные умножения многочленов реализуются в соответствии с равенством (7.13) в кольце 7?4(F₂s) но модулю многочлена.

h (x) = x⁴ + 1. Например, для столбца коэффициентов Ь, 65, Ьд, 613 выполнено равенство.

тогда &i = a’oaj + a^as + «2⁹ + адащ в поле F₂s.

В приведенной выше матрице каждая строка начиная со второй является предыдущей строкой, циклически сдвинутой вправо на одну ячейку. Столь специфическая форма матрицы (7.20) обусловлена многочленом h (x) = х⁴ + 1, по модулю которого производится умножение в кольце 7?4(F₂s). Также напомним, что такие матрицы принято называть циркулянтом, или циркуляитпой матрицей.

Для практической реализации на ЭВМ определенное нами преобразование MixColumns является достаточно трудоемким. Для повышения его эффективности можно реализовать операцию умножения на коэффициенты ао, аз многочлена с (х) таблично, то есть в явном виде для всех a G F₂ задать перестановки.

Поскольку коэффициенты ад = «2 = 1, то они в операции умножения не участвуют. Следовательно, вычисление, например, коэффициента Ь может быть реализовано в виде.

Такой подход позволяет заменить достаточно трудоемкую операцию умножения в поле F₂s на табличную замену, которая реализуется существенно быстрее.

Таким образом, мы можем записать раундовое преобразование алгоритма AES в виде последовательности четырех простых преобразований.

для всех i = 1,…, г — 1.

Последнее раундовое преобразование, при i — г, отличается от всех предыдущих тем, что в нем не используется преобразование MixColumns, то есть

Заключительное преобразование W зависит от раундового ключа к_г+1 и представляет собой наложение ключа по модулю два, то есть определенное выше преобразование AddRoundKey.

Алгоритм расшифрования состоит в последовательном применении преобразований, обратных к введенным преобразованиям SubBytes, ShiftRows, MixColumns и AddRoundKey.

Поскольку большинство указанных преобразований тривиально, то и построение обратных к ним не составляет какого-либо труда.

Некоторая трудность возникает при обращении преобразования MixColumns, состоящего в умножении столбцов матрицы на фиксированный многочлен с (х) = ад + х + х² + азх³.

Определим многочлен с^-1 (ж) = 70 + 71 ж + 72Ж² + 73Ж³, где.

и 7j, как и коэффициенты многочлена с (х), принадлежат полю F₂e, порожденному многочленом д (х) = х⁸ + х⁴ + х³ + х + 1. Тогда выполнено равенство

в кольце R₄(?₂s).

Обратное преобразование к MixColumns состоит в умножении столбцов матрицы, соответствующей сообщению а, па многочлен с^-1(ж). В заключение мы предлагаем читателю самостоятельно проверить корректность равенства (7.21).