16.4. Конечные поля и операции в алгоритме AES

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

16.4.1. Операции с байтами в AES

Чтобы определить операции сложения и умножения двух байтов, введём сначала представление байта в виде многочлена степени 7 или меньше. Байт

$$ a =( a_7, a_6, a_5, a_4, a_3, a_2, a_1, a_0) $$

преобразуется в многочлен $a(x)$ с коэффициентами 0 или 1 по правилу

$$ a(x) = a_{7}x^{7}+a_{6}x^{6}+a_{5}x^{5}+a_{4}x^{4}+a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}. $$

Далее байт трактуется как элемент конечного поля ${{\mathbb{GF}}(2^8)}$, заданного неприводимым многочленом, например

$$ m(x) = x^{8}+x^{4}+x^{3}+x +1. $$

Произведение многочленов $a(x)$ и $b(x)$ по модулю многочлена $m(x)$ записывают как

$$ c(x) = a(x) b(x) \mod m(x). $$

Остаток $c(x)$ представляет собой многочлен степени 7 или меньше. Его коэффициенты $(c_{7}, c_{6}, c_{5}, c_{4}, c_{3}, c_{2}, c_{1}, c_{0})$ образуют байт $c$, который и называется произведением байтов $a$ и $b$.

Сложение байтов осуществляется как $\oplus$ (исключающее ИЛИ), что является операцией сложения многочленов в двоичном поле.

Единичным элементом поля является байт $\mathrm{'00000001'}$, или $\mathrm{'01'}$ в шестнадцатеричной записи. Нулевым элементом поля является байт $\mathrm{'00000000'}$, или $\mathrm{'00'}$ в шестнадцатеричной записи. Одним из примитивных элементов поля является байт $\mathrm{'00000010'}$, или $\mathrm{'02'}$ в шестнадцатеричной записи. Байты часто записывают в шестнадцатеричной форме, но при математических преобразованиях они должны интерпретироваться как элементы поля ${{\mathbb{GF}}(2^8)}$.

Для каждого ненулевого байта $a$ существует обратный байт $b$ такой, что их произведение является единичным байтом:

$$ a b = 1 \mod m(x). $$

Обратный байт обозначается $b = a^{-1}$.

Для байта $a$, представленного многочленом $a(x)$, нахождение обратного байта $a^{-1}$ сводится к решению уравнения

$$ m(x) d(x) + b(x) a(x) = 1. $$

Если такое решение найдено, то многочлен $b(x) \mod m(x)$ является представлением обратного байта $a^{-1}$. Обратный элемент (байт) может быть найден с помощью расширенного алгоритма Евклида для многочленов.

Пример. Найти байт, обратный байту $a = \mathrm{'C1'}$, в шестнадцатеричной записи. Так как $a(x) = x^{7} + x^{6} + 1$, то с помощью расширенного алгоритма Евклида находим

$$ (x^{8} + x^{4} + x^{3} + x + 1) (x^{4} + x^{3} + x^{2} + x + 1) + (x^{7} + x^{6} + 1) (x^{5} + x^{3}) = 1. $$

Таким образом, обратный элемент поля, или обратный байт $\mathrm{'C1'}$, равен

$$ x^{5} + x^{3} = a^{-1} = \mathrm{'00101000'} = \mathrm{'28'}. $$

Пример. В алгоритме блочного шифрования AES байты рассматриваются как элементы поля Галуа ${{\mathbb{GF}}(2^8)}$. Сложим байты $\mathrm{'57'}$ и $\mathrm{'83'}$. Представляя их многочленами, находим:

$$ (x^6 + x^4 + x^2 + x + 1) + (x^7 + x + 1) = x^7 + x^6 + x^4 + x^2, $$

или в двоичной записи –

$$ 01010111 \oplus 10000011 = 11010100 = \mathrm{'D4'}. $$

Получили $\mathrm{'57'} + \mathrm{'83'} = \mathrm{'D4'}$.

Пример. Выполним в поле ${{\mathbb{GF}}(2^8)}$, заданном неприводимым многочленом

$$ m(x) = x^8 + x^4 + x^3 + x + 1 $$

(из алгоритма AES), операции с байтами: $\mathrm{'FA'} \cdot \mathrm{'A9'} + \mathrm{'E0'}$, где

$$ FA = 11111010, ~ A9 = 10101001, ~ E0 = 11100000, $$
$$ (x^7 + x^6 + x^5 + x^4 + x^3 +x)(x^7 + x^5 + x^3 + 1) + (x^7 + x^6 + x^5) \mod m(x) = $$
$$ = x^{14} + x^{13} + x^{10} + x^{8} + x^7 + x^3 + x \mod m(x) = $$
$$ = (x^{14} + x^{13} + x^{10} + x^{8} + x^7 + x^3 + x) + x^6 \cdot m(x) \mod m(x) = $$
$$ = x^{13} + x^9 + x^8 + x^6 + x^3 + x \mod m(x) = $$
$$ = (x^{13} + x^9 + x^8 + x^6 + x^3 + x) + x^5 \cdot m(x) \mod m(x) = $$
$$ = x^5 + x^3 + x \mod m(x) = \mathrm{'2A'}. $$

16.4.2. Операции над вектором из байтов в AES

Поле ${{\mathbb{GF}}(2^{nk})}$ можно задать как расширение степени $nk$ базового поля ${{\mathbb{GF}}(2)}$:

$$ \alpha \in {{\mathbb{GF}}(2^{nk})}, ~ \alpha = \sum\limits_{i=0}^{nk-1} a_i x^i, ~ a_i \in {{\mathbb{GF}}(2)} $$

с неприводимым многочленом $r(x)$ степени $nk$ над полем ${{\mathbb{GF}}(2)}$,

$$ r(x) = \sum\limits_{i=0}^{nk} a_i x^i, ~ a_i \in {{\mathbb{GF}}(2)}, ~ a_{nk} = 1. $$

Поле ${{\mathbb{GF}}(2^{nk})}$ можно задать и как расширение степени $k$ базового поля ${{\mathbb{GF}}(2^n)}$:

$$ \alpha \in {{\mathbb{GF}}((2^n)}^k), ~ \alpha = \sum\limits_{i=0}^{k-1} a_i x^i, ~ a_i \in {{\mathbb{GF}}(2^n)} $$

с неприводимым многочленом $r(x)$ степени $k$ над полем ${{\mathbb{GF}}(2^n)}$,

$$ r(x) = \sum\limits_{i=0}^{k} a_i x^i, ~ a_i \in {{\mathbb{GF}}(2^n)}, ~ a_k = 1. $$

Пример. В таблице [tab:irreducible-gf8] приведены примеры приводимых и неприводимых многочленов над полем ${{\mathbb{GF}}(2^8)}$.

МногочленРазложение
$\mathrm{'01'} x + \mathrm{'00'}$неприводимый
$\mathrm{'01'} x + \mathrm{'01'}$неприводимый
$\mathrm{'01'} x + \mathrm{'A9'}$неприводимый
$\mathrm{'01'} x^2 + \mathrm{'00'} x + \mathrm{'00'}$$(\mathrm{'01'} x) \cdot (\mathrm{'01'} x)$
$\mathrm{'1D'} x^2 + \mathrm{'AF'} x + \mathrm{'52'}$$(\mathrm{'41'} x + \mathrm{'0A'}) \cdot (\mathrm{'E3'} x + \mathrm{'5A'})$
$\mathrm{'01'} x^4 + \mathrm{'01'}$$(\mathrm{'01'} x + \mathrm{'01'})^4$
Таблица 16.4 — Примеры многочленов над полем ${{\mathbb{GF}}(2^8)}$

В алгоритме AES вектор-столбец $\mathbf{a}$ состоит из четырёх байтов $a_{0}, a_{1}, a_{2}, a_{3}$. Ему ставится в соответствие многочлен $\mathbf{a}(y)$ от переменной $y$ вида

$$ \mathbf{a}(y) = a_{3}y^{3}+a_{2}y^{2}+a_{1}y+a_{0}, $$

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

Многочлены $\mathbf{a}(y)$ и $\mathbf{b}(y)$ умножаются по модулю многочлена

$$ \mathbf{M}(y)= \mathrm{'01'} y^4 + \mathrm{'01'} = y^4 + 1, ~ \mathrm{'01'} \in {{\mathbb{GF}}(2^8)}, $$
$$ \mathbf{M}(y)= (\mathrm{'01'}, \mathrm{'00'},\mathrm{'00'}, \mathrm{'00'}, \mathrm{'01'}), $$

который не является неприводимым над ${{\mathbb{GF}}(2^8)}$.

Операция умножения по модулю $\mathbf{M}(y)$ обозначается $\otimes$:

$$ \mathbf{a}(y) ~ \mathbf{b}(y) \mod \mathbf{M}(y) ~\equiv~ \mathbf{a}(y) \otimes \mathbf{b}(y). $$

Операция «перемешивание столбца» в шифровании AES состоит в умножении многочлена столбца на

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

по модулю $\mathbf{M}(y)$. Многочлен $\mathbf{c}(y)$ имеет обратный многочлен

$$ \mathbf{d}(y) = \mathbf{c}^{-1}(y) \mod \mathbf{M}(y) = (\mathrm{0B}, \mathrm{0D}, \mathrm{09}, \mathrm{0E}) = $$
$$ = \mathrm{'0B'} y^3 + \mathrm{'0D'} y^2 + \mathrm{'09'} y + \mathrm{'0E'}, $$
$$ \mathbf{c}(y) \otimes \mathbf{d}(y) = (00, 00, 00, 01) = 1. $$

При расшифровании выполняется умножение на $\mathbf{d}(y)$ вместо $\mathbf{c}(y)$.

Так как

$$ y^j = y^{j \mod 4} \mod y^4+1, $$

где коэффициенты из поля ${{\mathbb{GF}}(2^8)}$, то произведение многочленов

$$ \mathbf{a}(y) = a_{3}y^{3}+ a_{2}y^{2} + a_{1}y + a_{0} $$

и

$$ \mathbf{b}(y) = b_{3}y^{3} + b_{2}y^{2} + b_{1}y + b_{0}, $$

обозначаемое как

$$ \mathbf{f}(y) = \mathbf{a}(y) \otimes \mathbf{b}(y) = f_{3}y^{3} + f_{2}y^{2} + f_{1}y + f_{0}, $$

содержит коэффициенты

$$ \begin{array}{ccccccccc} f_{0} & = & a_{0}b_{0} & + & a_{3}b_{1} & + & a_{2}b_{2} & + & a_{1}b_{3}, \\ f_{1} & = & a_{1}b_{0} & + & a_{0}b_{1} & + & a_{3}b_{2} & + & a_{2}b_{3}, \\ f_{2} & = & a_{2}b_{0} & + & a_{1}b_{1} & + & a_{0}b_{2} & + & a_{3}b_{3}, \\ f_{3} & = & a_{3}b_{0} & + & a_{2}b_{1} & + & a_{1}b_{2} & + & a_{0}b_{3}. \end{array} $$

Эти соотношения можно переписать также в матричном виде:

$$ \begin{array}{cccc} \left[ \begin{array}{c} f_{0} \\ f_{1} \\ f_{2} \\ f_{3} \end{array} \right] & = & \left[\begin{array}{cccc} a_{0} & a_{3} & a_{2} & a_{1} \\ a_{1} & a_{0} & a_{3} & a_{2} \\ a_{2} & a_{1} & a_{0} & a_{3} \\ a_{3} & a_{2} & a_{1} & a_{0} \end{array}\right] & \left[\begin{array}{c} b_{0} \\ b_{1} \\ b_{2} \\ b_{3} \end{array} \right] \end{array}. $$

Умножение матриц производится в поле ${{\mathbb{GF}}(2^8)}$. Матричное представление полезно, если нужно умножать фиксированный вектор на несколько различных векторов.

Пример. Вычислим для $\mathbf{a}(y) = (\mathrm{F2}, \mathrm{7E}, \mathrm{41}, \mathrm{0A})$ произведение $\mathbf{a}(y) \otimes \mathbf{c}(y)$:

$$ \mathbf{c}(y) = (03, 01, 01, 02), $$
$$ \mathbf{d}(y) = \mathbf{c}^{-1}(y) \mod \mathbf{M}(y) = (\mathrm{0B}, \mathrm{0D}, \mathrm{09}, \mathrm{0E}). $$
$$ \mathbf{a}(y) \otimes \mathbf{c}(y) = \left[ \begin{array}{cccc} \mathrm{0A} & \mathrm{F2} & \mathrm{7E} & \mathrm{41} \\ \mathrm{41} & \mathrm{0A} & \mathrm{F2} & \mathrm{7E} \\ \mathrm{7E} & \mathrm{41} & \mathrm{0A} & \mathrm{F2} \\ \mathrm{F2} & \mathrm{7E} & \mathrm{41} & \mathrm{0A} \\ \end{array} \right] \cdot \left[ \begin{array}{c} \mathrm{02} \\ \mathrm{01} \\ \mathrm{01} \\ \mathrm{03} \end{array} \right] = $$
$$ \left[ \begin{array}{ccccccc} \mathrm{0A} \cdot \mathrm{02} & \oplus & \mathrm{F2} & \oplus & \mathrm{7E} & \oplus & \mathrm{41} \cdot \mathrm{03} \\ \mathrm{41} \cdot \mathrm{02} & \oplus & \mathrm{0A} & \oplus & \mathrm{F2} & \oplus & \mathrm{7E} \cdot \mathrm{03} \\ \mathrm{7E} \cdot \mathrm{02} & \oplus & \mathrm{41} & \oplus & \mathrm{0A} & \oplus & \mathrm{F2} \cdot \mathrm{03} \\ \mathrm{F2} \cdot \mathrm{02} & \oplus & \mathrm{7E} & \oplus & \mathrm{41} & \oplus & \mathrm{0A} \cdot \mathrm{03} \\ \end{array} \right] = \left[ \begin{array}{c} \mathrm{5B} \\ \mathrm{F8} \\ \mathrm{BA} \\ \mathrm{DE} \end{array} \right]; $$
$$ \begin{array}{l} \mathbf{a}(y) \otimes \mathbf{c}(y) = \mathbf{b}(y), \\ \mathbf{b}(y) \otimes \mathbf{d}(y) = \mathbf{a}(y); \\ \end{array} $$
$$ \begin{array}{ccccc} (\mathrm{F2}, \mathrm{7E}, \mathrm{41}, \mathrm{0A}) & \otimes & (\mathrm{03}, \mathrm{01}, \mathrm{01}, \mathrm{02}) & = & (\mathrm{DE}, \mathrm{BA}, \mathrm{F8}, \mathrm{5B}), \\ (\mathrm{DE}, \mathrm{BA}, \mathrm{F8}, \mathrm{5B}) & \otimes & (\mathrm{0B}, \mathrm{0D}, \mathrm{09}, \mathrm{0E}) & = & (\mathrm{F2}, \mathrm{7E}, \mathrm{41}, \mathrm{0A}). \\ \end{array} $$