Алгоритм шифрования AES

Общие сведения о стандартах шифрования

В восьмидесятых годах двадцатого века главным симметричным криптографическим алгоритмом для внутреннего применения в США считался DES (Data Encryption Standard, то есть, стандарт шифрования данных). Но уже в девяностых годах начали выявляться его главные недостатки. Основным недостатком является длина ключа, которая составляет 56 бит. Данный размер стал превращаться в недостаточно большой по причине непрерывного роста производительности компьютерного оборудования, поскольку ключ можно было вскрыть способом стандартного перебора всех допустимых вариантов шифрования.

По этой причине в 1997-ом году NIST (National Institute of Standards and Technology, то есть, национальный институт стандартов и технологий) организовал проведение конкурса на новый стандарт симметричного криптографического алгоритма. NIST установил следующий набор обязательных требований к кандидатам:

1. 128-битная размерность блока шифруемых данных.
2. Не меньше трех размеров ключей (128, 192, 256 бит), которые обязан поддерживать алгоритм.
3. Возможность использования операций, которые можно легко реализовать аппаратным и программным обеспечением.
4. Простая организационная структура шифра, позволяющая заинтересованным сторонам самостоятельно осуществлять криптографический анализ.

Победил в этом конкурсе AES алгоритм Rijndael (далее алгоритм AES). Он показал отличный уровень устойчивости к атакам, сравнительно низкая степень энергопотребления и относительно малое время работы. Помимо этого, алгоритм обладает внутренним параллелизмом, за счет чего он может эффективно использовать процессорные ресурсы, и дополнительно уменьшить время работы алгоритма.

Алгоритм шифрования AES

Рассмотрим базовые понятия, которые необходимы для правильного понимания работы алгоритма. Прежде всего следует отметить, что алгоритм AES работает с байтами, которые могут быть интерпретированы как элементы конечного поля $F(2^8)$. В данном поле определяются операции сложения и умножения двух компонентов, итогом которых тоже будет компонент этого поля. Приведем анализ каждой из операций:

1. Сложение осуществляется при помощи операции xor, то есть сложение по модулю. Операция должна выполняться над двоичными числами поразрядно, то есть, если имеется два байта $P = {p_7, p_6, p_5, p_4, p_3, p_2, p_1, p_0}$ и $Q = {q_7, q_6, q_5, q_4, q_3, q_2, q_1, q_0}$, то итоговым результатом станет $R = {r_7, r_6, r_5, r_4, r_3, r_2, r_1, r_0}$, где $r_i = p_i xor r_i$.
2. Операция умножения. Для данной операции применяется отображение байта как полинома: $p(x) = p_7x^7 + p_6x^6 + p_5x^5 + p_4x^4 + p_3x^3 + p_2x^2 + p_1x + p_0$, умножение в поле $F(2^8)$ в данном представлении реализуется по модулю неприводимого в этом поле многочлена $m(x) = x^8 + x^4 + x^3 + x + 1$. То есть, для того получения результата умножения двух чисел в поле $F(2^8)$, следует представить их в форме полиномов $p(x)$ и $q(x)$, а далее взять остаток от деления на многочлен $m(x)$ произведения $p(x)$ и $q(x)$, а именно $r(x) = p(x)q(x) mod (m(x))$, и определить коэффициенты полинома $r(x)$, являющиеся 8-битовым числом в поле $F(2^8)$.

Рассмотрим алгоритм шифрования AES c размером ключа 128 бит. Прежде всего входные данные должны быть разбиты на блоки по 16 байт, а когда полный размер не является кратным 16 байтам, то данные должны быть дополнены до размера, кратного 16 байтам. Блоки можно представить в виде матрицы 4x4, обозначенной как state. Затем следует выполнить процедуру расширения ключа и к каждому блоку state должна быть применена операции 2-4. Алгоритм может быть представлен в виде следующих шагов:

1. Процедура расширения ключа (KeyExpansion).
2. Первоначальный раунд, который состоит в сложении state с основным ключом.
3. Выполнение девяти раундов шифрования, каждый из которых включает ряд преобразований, а именно, SubBytes, ShiftRows, MixColumns, AddRoundKey.
4. Выполнение финального раунда, который также состоит из набора преобразований, а именно, SubBytes, ShiftRows, AddRoundKey.

Рассмотрим более подробно все представленные выше преобразования. SubBytes выпоняет замену байтов state по таблице S-box. Каждый байт может быть представлен в виде двух шестнадцатеричных чисел b = (x, y), в которых x определяется четырьмя старшими разрядами b, а y определяется четырьмя младшими разрядами. В таблице S-box, имеющей размерность 16x16, расположены значения, предназначенные для замены исходного байта, то есть, значение b' на пересечении строки x и столбца y S-box используется в качестве замены исходному байту b, как показано на рисунке ниже.

Рисунок 1. Таблица. Автор24 — интернет-биржа студенческих работ

Преобразование ShiftRows является циклическим сдвигом строк state. Нулевая строка должна оставаться на месте, первая сместиться влево на один байт, вторая на два байта и третья на три байта соответственно:

Рисунок 2. Таблицы. Автор24 — интернет-биржа студенческих работ

Преобразование MixColumns представляет собой умножение каждого столбца state на фиксированную матрицу. То есть, это по сути реализуется линейное преобразование над столбцами state. При этом операции умножения и сложения производятся по правилам, которые были описаны выше:

Рисунок 3. Таблицы. Автор24 — интернет-биржа студенческих работ

Преобразование AddRoundKey является раундовым ключом, который поэлементно добавляется к state при помощи поразрядного XOR.

KeyExpansion является процедурой расширения основного ключа для формирования раундовых ключей, которые далее применяются в раундах шифрования. Расширенный ключ имеет в своем составе сорок четыре четырехбайтовых слова $(w_i)$, а именно, четыре слова на основной ключ и по четыре слова на десять раундовых ключей. То есть, полный размер расширенного ключа равняется 1408 бит. Процедура расширения ключа применяет массив Rcon и включает в свой состав следующие действия:

1. Четыре слова основного ключа переносятся в первые четыре слова расширенного ключа.
2. Когда число i без остатка делится на четыре, тогда $w_i =SubBytes(RotByte(w_{i-1 })) xor Rcon_{i/4}$.
3. В противном случае $w_i = w_{i-4} xor w_{i-1}$.