5.6. Стандарт шифрования США AES

До 2001 г. стандартом шифрования данных в США был DES (аббревиатура от Data Encryption Standard), который был принят в 1980 году. Входной блок открытого текста и выходной блок шифрованного текста DES составляли по 64 бита каждый, длина ключа – 56 бит (до процедуры расширения). Алгоритм основан на ячейке Фейстеля с s-блоками и таблицами расширения и перестановки битов. Количество раундов – 16.

Для повышения криптостойкости и замены стандарта DES был объявлен конкурс на новый стандарт AES (аббревиатура от Advanced Encryption Standard). Победителем конкурса стал шифр Rijndael. Название составлено с использованием первых слогов фамилий его создателей (Rijmen и Daemen). В русскоязычном варианте читается как «Рэндал» [123]. 26 ноября 2001 года шифр был утверждён в качестве стандарта FIPS 197 и введён в действие 26 мая 2002 года [39].

AES – это раундовый блочный шифр с переменной длиной ключа (128, 192 или 256 бит) и фиксированными длинами входного и выходного блоков (128 бит).

5.6.1. Состояние, ключ шифрования и число раундов

Различные преобразования воздействуют на результат промежуточного шифрования, называемый состоянием ($\mathsf{State}$). Состояние представлено $(4 \times 4)$-матрицей из байтов $a_{i,j}$.

Ключ шифрования раунда ($\mathsf{Key}$) также представляется прямоугольной $(4 \times \mathsf{Nk})$-матрицей из байтов $k_{i,j}$, где $\mathsf{Nk}$ равно длине ключа, разделённой на 32, то есть 4, 6 или 8.

Эти представления приведены ниже:

$$ \mathsf{State} = \left[ \begin{array}{cccc} a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3} \\ a_{1,0} & a_{1,1} & a_{1,2} & a_{1,3} \\ a_{2,0} & a_{2,1} & a_{2,2} & a_{2,3} \\ a_{3,0} & a_{3,1} &a_{3,2} & a_{3,3} \\ \end{array} \right], $$

$$ \mathsf{Key} = \left[ \begin{array}{cccc} k_{0,0} & k_{0,1} & k_{0,2} & k_{0,3} \\ k_{1,0} & k_{1,1} & k_{1,2} & k_{1,3} \\ k_{2,0} & k_{2,1} & k_{2,2} & k_{2,3} \\ k_{3,0} & k_{3,1} & k_{3,2} & k_{3,3} \\ \end{array} \right]. $$

Иногда блоки символов интерпретируются как одномерные последовательности из 4-байтных векторов, где каждый вектор является соответствующим столбцом прямоугольной таблицы. В этих случаях таблицы можно рассматривать как наборы из 4, 6 или 8 векторов, нумеруемых в диапазоне $0 \dots 3$, $0 \dots 5$ или $0 \dots 7$ соответственно. В тех случаях, когда нужно пометить индивидуальный байт внутри 4-байтного вектора, используется обозначение $(a, b, c, d)$, где $a$, $b$, $c$, $d$ соответствуют байтам в одной из позиций ($0$, $1$, $2$, $3$) в столбце или векторе.

Входные и выходные блоки шифра AES рассматриваются как последовательности 16 байтов $(a_0, a_1, \dots, a_{15})$. Преобразование входного блока $(a_0, \dots, a_{15})$ в исходную $(4 \times 4)$-матрицу состояния $\mathsf{State}$ или преобразование конечной матрицы состояния в выходную последовательность проводится по правилу (запись по столбцам):

$$ a_{i,j} = a_{i + 4j}, ~ i = 0 \dots 3, ~ j = 0 \dots 3. $$

Аналогично ключ шифрования может рассматриваться как последовательность байтов $(k_0, k_1, \dots, k_{4 \cdot \mathsf{Nk} - 1})$, где $\mathsf{Nk} = 4, 6, 8$. Число байтов в этой последовательности равно 16, 24 или 32, а номера этих байтов находятся в интервалах $0 \dots 15$, $0 \dots 23$ или $0 \dots 31$ соответственно. $(4 \times \mathsf{Nk})$-матрица ключа шифрования $\mathsf{Key}$ задаётся по правилу:

$$ k_{i,j} = k_{i + 4j}, ~ i = 0 \dots 3, ~ j = 0 \dots \mathsf{Nk} - 1. $$

Число раундов $\mathsf{Nr}$ зависит от длины ключа. Его значения приведены в таблице ниже.

Длина ключа, биты	128	192	256
$\mathsf{Nk}$	4	6	8
Число раундов $\mathsf{Nr}$	10	12	14

5.6.2. Операции в поле

При переходе от одного раунда к другому матрицы состояния и ключа шифрования раунда подвергаются ряду преобразований. Преобразования могут осуществляться над:

отдельными байтами или парами байтов (необходимо определить операции сложения и умножения);
столбцами матрицы, которые рассматриваются как 4-мерные векторы с соответствующими байтами в качестве элементов;
строками матрицы.

В алгоритме шифрования AES байты рассматриваются как элементы поля ${{\mathbb{GF}}(2^8)}$, а вектор-столбцы из четырёх байтов – как многочлены третьей степени над полем ${{\mathbb{GF}}(2^8)}$. В приложении 16 дано подробное описание этих операций.

Хотя определение операций дано через их математическое представление, в реализациях шифра AES активно используются таблицы с заранее вычисленными результатами операций над отдельными байтами, включая взятие обратного элемента и перемножение элементов в поле ${{\mathbb{GF}}(2^8)}$ (на что требуется 256 байт и 64 КиБ памяти соответственно).

5.6.3. Операции одного раунда шифрования

В каждом раунде шифра AES, кроме последнего, производятся следующие 4 операции:

замена байтов, $\mathsf{SubBytes}$;
сдвиг строк, $\mathsf{ShiftRows}$;
перемешивание столбцов, $\mathsf{MixColumns}$;
добавление текущего ключа, $\mathsf{AddRoundKey}$.

В обозначениях, близких к языку С, можно записать программу в следующем виде:

$$ \begin{array}{l} \mathsf{Round(State, RoundKey)} \{ \\ ~~~~ \mathsf{SubBytes(State)}; \\ ~~~~ \mathsf{ShiftRows(State)}; \\ ~~~~ \mathsf{MixColumns(State)}; \\ ~~~~ \mathsf{AddRoundKey(State, RoundKey)}; \\ \} \\ \end{array} $$

В последнем раунде исключается операция «перемешивание столбцов». Этот раунд можно записать в следующем виде:

$$ \begin{array}{l} \mathsf{Round(State, RoundKey)} \{ \\ ~~~~ \mathsf{SubBytes(State)}; \\ ~~~~ \mathsf{ShiftRows(State)}; \\ ~~~~ \mathsf{AddRoundKey(State, RoundKey)}; \\ \} \\ \end{array} $$

В этих обозначениях все «функции», а именно: $\mathsf{Round}$, $\mathsf{SubBytes}$, $\mathsf{ShiftRows}$, $\mathsf{MixColumns}$ и $\mathsf{AddRoundKey}$ воздействуют на матрицы, определяемые указателем $\mathsf{(State, RoundKey)}$. Сами преобразования описаны в следующих разделах.

Замена байтов $\mathsf{SubBytes}$

Нелинейная операция «замена байтов» действует независимо на каждый байт $a_{i,j}$ текущего состояния. Таблица замены (или s-блок) является обратимой и формируется последовательным применением двух преобразований.

Сначала байт $a$ представляется как элемент $a(x)$ поля Галуа ${{\mathbb{GF}}(2^8)}$ и заменяется на обратный элемент $a^{-1} \equiv a^{-1}(x)$ в поле. Байт $\mathrm{'00'}$, для которого обратного элемента не существует, переходит сам в себя.
Затем к обратному байту $a^{-1} = (x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7)$ применяется аффинное преобразование над полем ${{\mathbb{GF}}(2^8)}$ следующего вида:
$$ \left[ \begin{array}{c} y_{0} \\ y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \\ y_{5} \\ y_{6} \\ y_{7} \\ \end{array} \right] = \left[ \begin{array}{cccccccc} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \ \end{array} \right] \cdot \left[ \begin{array}{c} x_{0} \\ x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \\ x_{6} \\ x_{7} \\ \end{array} \right] + \left[ \begin{array}{c} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \\ \end{array} \right]. $$

В полиномиальном представлении это аффинное преобразование имеет вид

$$Y(z)=(z^4)X(z)(1+z+z^2+z^3+z^4)\mod(1+z^8) + F(z).$$

Применение описанных операций s-блока ко всем байтам текущего состояния обозначено

$$ \mathsf{SubBytes(State)}. $$

Обращение операции $\mathsf{SubBytes(State)}$ также является заменой байтов. Сначала выполняется обратное аффинное преобразование, а затем от полученного байта берётся обратный.

Сдвиг строк $\mathsf{ShiftRows}$

Для выполнения операции «сдвиг строк» строки в таблице текущего состояния циклически сдвигаются влево. Величина сдвига различна для различных строк. Строка $0$ не сдвигается вообще. Строка $1$ сдвигается на $C_1=1$ позицию, строка $2$ – на $C_2=2$ позиции, строка $3$ – на $C_3=3$ позиции.

Перемешивание столбцов $\mathsf{Mix Columns}$

При выполнении операции «перемешивание столбцов» столбцы матрицы текущего состояния рассматриваются как многочлены над полем ${{\mathbb{GF}}(2^8)}$ и умножаются по модулю многочлена $y^4 +1$ на фиксированный многочлен $\mathbf{c}(y)$, где

$$ \mathbf{c}(y) = \mathrm{'03'} y^3 + \mathrm{'01'} y^2 + \mathrm{'01'} y + \mathrm{'02'}. $$

Этот многочлен взаимно прост с многочленом $y^4 + 1$ и, следовательно, обратим. Перемножение удобнее проводить в матричном виде. Если $\mathbf{b}(y) = \mathbf{c}(y) \otimes \mathbf{a}(y)$, то

$$ \left[ \begin{array}{c} b_{0} \\ b_{1} \\ b_{2} \\ b_{3} \\ \end{array}\right] = \left[ \begin{array}{cccc} \mathrm{'02'} & \mathrm{'03'} & \mathrm{'01'} & \mathrm{'01'} \\ \mathrm{'01'} & \mathrm{'02'} & \mathrm{'03'} & \mathrm{'01'} \\ \mathrm{'01'} & \mathrm{'01'} & \mathrm{'02'} & \mathrm{'03'} \\ \mathrm{'03'} & \mathrm{'01'} & \mathrm{'01'} & \mathrm{'02'} \\ \end{array} \right] \cdot \left[ \begin{array}{c} a_{0} \\ a_{1} \\ a_{2} \\ a_{3} \\ \end{array} \right]. $$

Обратная операция состоит в умножении на многочлен $\mathbf{d}(y)$, обратный многочлену $\mathbf{c}(y)$ по модулю $y^4 + 1$, то есть

$$ (\mathrm{'03'} y^{3} + \mathrm{'01'} y^{2} + \mathrm{'01'} y + \mathrm{'02'}) \otimes \mathbf{d}(y) = \mathrm{'01'}. $$

Этот многочлен равен

$$ \mathbf{d}(y) = \mathrm{'0B'} y^3 + \mathrm{'0D'} y^2 + \mathrm{'09'} y + \mathrm{'0E'}. $$

Добавление ключа раунда $\mathsf{AddRoundKey}$

Операция «добавление ключа раунда» состоит в том, что матрица текущего состояния складывается по модулю 2 с матрицей ключа текущего раунда. Обе матрицы должны иметь одинаковые размеры. Матрица ключа раунда вычисляется с помощью процедуры расширения ключа, описанной ниже. Операция «добавление ключа раунда» обозначается $\mathsf{AddRoundKey(State, RoundKey)}$.

$$\begin{eqnarray} \left[ \begin{array}{cccc} a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3} \\ a_{1,0} & a_{1,1} & a_{1,2} & a_{1,3} \\ a_{2,0} & a_{2,1} & a_{2,2} & a_{2,3} \\ a_{3,0} & a_{3,1} & a_{3,2} & a_{3,3} \end{array} \right] \oplus \left[ \begin{array}{cccc} k_{0,0} & k_{0,1} & k_{0,2} & k_{0,3} \\ k_{1,0} & k_{1,1} & k_{1,2} & k_{1,3} \\ k_{2,0} & k_{2,1} & k_{2,2} & k_{2,3} \\ k_{3,0} & k_{3,1} & k_{3,2} & k_{3,3} \end{array} \right] = \\ = \left[ \begin{array}{cccc} b_{0,0} & b_{0,1} & b_{0,2} & b_{0,3} \\ b_{1,0} & b_{1,1} & b_{1,2} & b_{1,3} \\ b_{2,0} & b_{2,1} & b_{2,2} & b_{2,3} \\ b_{3,0} & b_{3,1} & b_{3,2} & b_{3,3} \end{array} \right]. \end{eqnarray}$$

5.6.4. Процедура расширения ключа

Матрица ключа текущего раунда вычисляется из исходного ключа шифра с помощью специальной процедуры, состоящей из расширения ключа и выбора раундового ключа. Основные принципы этой процедуры состоят в следующем:

суммарная длина ключей всех раундов равна длине блока, умноженной на увеличенное на 1 число раундов. Для блока длины 128 бит и 10 раундов общая длина всех ключей раундов равна 1408;
с помощью ключа шифра находят расширенный ключ;
ключи раунда выбираются из расширенного ключа по правилу: ключ первого раунда состоит из первых 4 столбцов матрицы расширенного ключа, второй ключ – из следующих 4 столбцов и т. д.

Расширенный ключ – это матрица $\mathsf{W}$, состоящая из $4(\mathsf{Nr} + 1)$ 4-байтных вектор-столбцов, каждый столбец $i$ обозначается $\mathsf{W}[i]$.

Далее рассматривается только случай, когда ключ шифра состоит из 16 байтов. Первые $\mathsf{Nk} = 4$ столбца содержат ключ шифра. Остальные столбцы вычисляются рекурсивно из столбцов с меньшими номерами.

Для $\mathsf{Nk} = 4$ имеем 16-байтный ключ

$$ \mathsf{Key} = (\mathsf{Key}[0], \mathsf{Key}[1], \dots, \mathsf{Key}[15]). $$

Приведём алгоритм расширения ключа для $\mathsf{Nk} = 4$.

algorithmht $\mathsf{KeyExpansion}(\mathsf{Key}, \mathsf{W})$ algorithmic $i=0$ $\mathsf{Nk} - 1$ $\mathsf{W}[i] = (\mathsf{Key}[4i], ~ \mathsf{Key}[4i+1], ~ \mathsf{Key}[4i+2], ~ \mathsf{Key}[4i+3])^T$; $i = \mathsf{Nk}$ $4(\mathsf{Nr} + 1) - 1$ $\mathsf{temp} = \mathsf{W}[i-1]$; ($i = 0 \mod \mathsf{Nk}$) $\mathsf{temp} = \mathsf{SubWord}(\mathsf{RotWord}(\mathsf{temp})) ~ \oplus ~ \mathsf{Rcon}[i ~/~ \mathsf{Nk}]$; $\mathsf{W}[i] = \mathsf{W}[i - \mathsf{Nk}] ~ \oplus ~ \mathsf{temp}$;

Здесь $\mathsf{SubWord}(\mathsf{W}[i])$ обозначает функцию, которая применяет операцию «замена байтов» (или s-блок) $\mathsf{SubBytes}$ к каждому из 4 байтов столбца $\mathsf{W}[i]$. Функция $\mathsf{RotWord}(\mathsf{W}[i])$ осуществляет циклический сдвиг вверх байт столбца $\mathsf{W}[i]$: если $\mathsf{W}[i] = (a, b, c, d)^T$, то $\mathsf{RotWord}(\mathsf{W}[i]) = (b, c, d, a)^T$. Векторы-константы $\mathsf{Rcon}[i]$ определены ниже.

Как видно из этого описания, первые $\mathsf{Nk} = 4$ столбца заполняются ключом шифра. Все следующие столбцы $\mathsf{W}[i]$ равны сумме по модулю $2$ предыдущего столбца $\mathsf{W}[i-1]$ и столбца $\mathsf{W}[i-4]$. Для столбцов $\mathsf{W}[i]$ с номерами $i$, кратными $\mathsf{Nk} = 4$, к столбцу $\mathsf{W}[i-1]$ применяются операции $\mathsf{RotWord(W)}$ и $\mathsf{SubWord(W)}$, а затем производится суммирование по модулю 2 со столбцом $\mathsf{W}[i-4]$ и константой раунда $\mathsf{Rcon}[i ~/~ 4]$.

Векторы-константы раундов определяются следующим образом:

$$ \mathsf{Rcon}[i] = (\mathsf{RC}[i], \mathrm{'00'}, \mathrm{'00'}, \mathrm{'00'})^T, $$

где байт $\mathsf{RC}[1] = \mathrm{'01'}$, а байты $\mathsf{RC}[i] = \alpha^{i-1}, ~ i = 2, 3, \dots$; байт $\alpha = \mathrm{'02'}$ – это примитивный элемент поля ${{\mathbb{GF}}(2^8)}$.

Пример. Пусть $\mathsf{Nk} = 4$. В этом случае ключ шифра имеет длину 128 бит. Найдём столбцы расширенного ключа. Столбцы $\mathsf{W}[0], \mathsf{W}[1], \mathsf{W}[2], \mathsf{W}[3]$ непосредственно заполняются битами ключа шифра. Номер следующего столбца $\mathsf{W}[4]$ кратен $\mathsf{Nk}$, поэтому

$$ \mathsf{W}[4] = \mathsf{SubWord}(\mathsf{RotWord}(\mathsf{W}[3])) \oplus \mathsf{W}[0] \oplus \left[ \begin{array}{c} \mathrm{'01'} \\ \mathrm{'00'} \\ \mathrm{'00'} \\ \mathrm{'00'} \\ \end{array} \right]. $$

Далее имеем:

$$ \begin{array}{l} \mathsf{W}[5] = \mathsf{W}[4] \oplus \mathsf{W}[1], \\ \mathsf{W}[6] = \mathsf{W}[5] \oplus \mathsf{W}[2], \\ \mathsf{W}[7] = \mathsf{W}[6] \oplus \mathsf{W}[3]. \\ \end{array} $$

Затем:

$$ \mathsf{W}[8] = \mathsf{SubWord}(\mathsf{RotWord}(\mathsf{W}[7])) \oplus \mathsf{W}[4] \oplus \left[ \begin{array}{c} \alpha \\ \mathrm{'00'}\\ \mathrm{'00'}\\ \mathrm{'00'}\\ \end{array} \right] , $$

$$ \begin{array}{l} \mathsf{W}[9] = \mathsf{W}[8] \oplus \mathsf{W}[5], \\ \mathsf{W}[10] = \mathsf{W}[9] \oplus \mathsf{W}[6], \\ \mathsf{W}[11] = \mathsf{W}[10] \oplus \mathsf{W}[7] \\ \end{array} $$

и т. д.

Ключ $i$-го раунда состоит из столбцов матрицы расширенного ключа

$$ \mathsf{RoundKey} = (\mathsf{W}[4(i-1)], \mathsf{W}[4(i-1) + 1], \ldots, \mathsf{W}[4i-1]). $$

В настоящее время американский стандарт шифрования AES де-факто используется во всём мире в негосударственных системах передачи данных, если позволяет законодательство страны. C 2010 года процессоры Intel поддерживают специальный набор инструкций для шифра AES.