aes_math.tex

\section{Конечные поля и операции в алгоритме AES}
\selectlanguage{russian}

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

\subsection{Определение поля Галуа}

%Группой называется множество $\Gr$, в котором задана операция $\centerdot$ между двумя элементами группы и удовлетворяются аксиомы:
%\begin{enumerate}
%    \item Замкнутость -- $\forall a,b \in \Gr: a \centerdot b = c \in \Gr$.
%    \item Ассоциативность -- $\forall a,b,c \in \Gr: (a \centerdot b) \centerdot c = a \centerdot (b \centerdot c)$.
%    \item Существование единичного элемента -- $\exists ~ e \in \Gr: e\centerdot a = a \centerdot e = a$.
%    \item Существование обратного элемента -- $\forall a \in \Gr ~ \exists ~ b \in \Gr: a \centerdot b = b \centerdot a = e$.
%\end{enumerate}

\textbf{Полем} называется множество $\F$, для которого\index{поле}
\begin{itemize}
    \item заданы операции умножения <<$\cdot$>> и сложения <<$+$>>;
    \item выполняются аксиомы группы по сложению <<$+$>> для всего множества $\F$: \\
        1. для $a,b,c \in \F$ верно $a+b \in \F$, \\
        2. $(a+b)+c = a+(b+c)$, \\
        3. существует нулевой элемент -- ноль 0, $a+0=0+a=a$, \\
        4. существует единственный обратный элемент $-a$: \\
        \indent \indent \indent ~~~~~~ $a + (-a) = (-a) + a = 0$;
    \item выполняются аксиомы группы по умножению <<$\cdot$>> для множества $\{ \F \backslash 0 \}$, за исключением нуля: \\
        1. для $a,b,c \in \{ \F \backslash 0 \}$ верно \\
        \indent \indent \indent ~~~~~~ $a \cdot b \in \{ \F \backslash 0 \}$, \\
        \indent \indent \indent ~~~~~~ $(a \cdot b) \cdot c = a \cdot (b \cdot c)$, \\
        2. существует единичный элемент -- единица 1, ~ $a \cdot 1 = 1 \cdot a = a$, \\
        3. существует единственный обратный элемент $a^{-1}:$ \\
        \indent \indent \indent ~~~~~~ $a \cdot a^{-1} = a^{-1} \cdot a = 1$, \\
        к нулю 0 не существует обратного элемента и $a \cdot 0 = 0$;
%    \item Удовлетворяющее аксиомам группы по сложению и умножению, обратный элемент по умножению существует ко всем элементам кроме 0.
    \item операции сложения и умножения коммутативны
        \[ \begin{array}{l}
            a + b = b + a, \\
            a \cdot b = b \cdot a; \\
        \end{array} \]
    \item выполняется свойство дистрибутивности
        \[ a \cdot (b + c) = (a \cdot b) + (a \cdot c). \]
\end{itemize}

Примеры \emph{бесконечных} полей (с бесконечным числом элементов) -- поле рациональных чисел $\group{Q}$, поле вещественных чисел $\group{R}$, поле комплексных чисел $\group{C}$ с обычными операциями сложения и умножения.

В криптографии рассматриваются \emph{конечные} поля (с конечным числом элементов), называемые также \textbf{полями Галуа}.

Число элементов в любом конечном поле равно $p^n$, где $p$ -- простое число и $n$ -- натуральное число. Обозначения поля Галуа: $\GF{p}, \GF{p^n}, \F_p, \F_{p^n}$ (аббревиатура от Galois field). Все поля Галуа $\GF{p^n}$ изоморфны друг другу (существует взаимно однозначное отображение между полями, сохраняющее действие всех операций). Другими словами, существует только одно поле Галуа $\GF{p^n}$ для фиксированных $p, n$.

Приведем примеры конечных полей.

Двоичное поле $\GF{2}$ состоит из двух элементов:
    \[ \GF{2} = \{0, 1\} \]
с операцией $(\cdot)$ обычного умножения и сложения  $\oplus$ по модулю 2 (исключающее ИЛИ, XOR).

Поле
    \[ \GF{3} = \{0, 1, 2\} \]
состоит из 3-х элементов с операциями умножения $(\cdot \mod 3)$ и сложения $(+ \mod 3)$ по модулю.

Двоичное поле $\GF{2^n}$ строится \textbf{расширением} \emph{базового} поля $\GF{2}$. Элемент поля задается многочленом степени $n-1$ (или меньше) с коэффициентами из базового поля $\GF{2}$:
    \[ \alpha = \sum\limits_{i=0}^{n-1} a_i x^i, ~ a_i \in \GF{2}. \]
Сложение многочленов -- сложение коэффициентов при одинаковых степенях $x^i$ в поле $\GF{2}$, т.е. по $\text{XOR}$. Умножение многочленов в поле -- обычное умножение многочленов со сложением и умножением коэффициентов в поле $\GF{2}$ и дальнейшим приведением результата по модулю неприводимого многочлена $m(x)$ над полем $\GF{2}$.

Многочлен над базовым полем $\GF{p}$ называется \textbf{неприводимым}\index{многочлен!неприводимый}, если он не раскладывается на множители, и \textbf{приводимым}\index{многочлен!приводимый}, если раскладывается на множители.

Говорят, что неприводимый над базовым полем $\GF{p}$ многочлен $m(x)$ степени $n$ задает поле $\GF{p^n}$, если операция умножения в поле определена по модулю $m(x)$ (сложение определяется базовым полем, умножение -- многочленом $m(x)$). Количество элементов в поле определяется степенью $m(x)$) и равно $p^n$. Элементы поля есть остатки от деления на $m(x)$ и имеют степень не выше $n-1$.

Многочлен $g(x)$ называется \textbf{примитивным элементом}\index{многочлен!примитивный} (генератором) поля, если его степени порождают все ненулевые элементы, т.е. $\GF{p^n} \setminus \{0\}$, заданное неприводимым многочленом $m(x)$, за исключением нуля:
    \[ \GF{p^n} \setminus \{0\} = \{ g(x), g^2(x), g^3(x), \dots, g^{p^n-1}(x) = 1 \mod m(x) \}. \]

Неприводимый многочлен $\mod m(x)$ называется  \textbf{примитивным}\index{многочлен!примитивный}, если $g(x)=x$.

\example
В табл. \ref{tab:irreducible-gf2} приведены примеры многочленов \emph{над полем} $\GF{2}$.
\begin{table}[h!]
    \centering
    \caption{Пример многочленов над полем $\GF{2}$\label{tab:irreducible-gf2}}
    \begin{tabular}{|c|c|c|}
        \hline
        Многочлен & \parbox{2.5cm}{Упрощенная запись} & Разложение \\
        \hline
        $'1' x + '0'$ & $x$ & неприводимый \\
        $'1' x + '1'$ & $x+1$ & неприводимый \\
        $'1' x^2 + '0' x + '0'$ & $x^2$ & $x \cdot x$ \\
        $'1' x^2 + '0'x + '1'$ & $x^2 + 1$ & $(x+1) \cdot (x+1)$ \\
        $'1' x^2 + '1' x + '0'$ & $x^2 + x$ & $x \cdot (x+1)$ \\
        $'1' x^2 + '1' x + '1'$ & $x^2 + x + 1$ & неприводимый \\
        $'1' x^3 + '0' x^2 + '0' x + '1'$ & $x^3 + 1$ & $(x+1) \cdot (x^2+x+1)$ \\
        \hline
    \end{tabular}
\end{table}
\exampleend


\subsection{Операции с байтами в 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}. \]

Далее байт трактуется как элемент конечного поля $\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$ (исключающее ИЛИ), что является операцией сложения многочленов в двоичном поле.

\emph{Единичным} элементом поля является байт 00000001, или $\mathrm{'01'}$ в шестнадцатеричной записи. \emph{Нулевым} элементом поля является байт 00000000, или $\mathrm{'00'}$ в шестнадцатеричной записи. Одним из \emph{примитивных} элементов поля является байт (0 0 0 0 0 0 1 0), или $\mathrm{'02'}$ в шестнадцатеричной записи. Байты часто записывают в шестнадцатеричной форме, но при математических преобразованиях они должны интерпретироваться как элементы поля $\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}$. Обратный элемент (байт) может быть найден с помощью расширенного алгоритма Евклида для многочленов.

\example
Найти байт, обратный байту $a = \mathrm{'83'}$ в шестнадцатеричной записи. Так как $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{'83'}$ равен
    \[ x^{5} + x^{3}, ~ a^{-1} = \mathrm{'00101000'} = \mathrm{'28'}. \]
\exampleend

\example
В алгоритме блокового шифрования AES байты рассматриваются как элементы поля Галуа $\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'}$.
\exampleend

\example
Выполним в поле $\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'}. \]
\exampleend


\subsection{Операции над вектором из байтов в AES}
%\subsection{Многочлены над полем в алгоритме AES}

Поле $\GF{2^{nk}}$ можно задать как расширение степени $nk$ базового поля $\GF{2}$:
    \[ \alpha \in \GF{2^{nk}}, \alpha = \sum\limits_{i=0}^{nk-1} a_i x^i, ~ a_i \in \GF{2} \]
с неприводимым многочленом $r(x)$ степени $nk$ над полем $\GF{2}$,
    \[ r(x) = \sum\limits_{i=0}^{nk} a_i x^i, ~ a_i \in \GF{2}, ~ a_{nk} = 1. \]

Поле $\GF{2^{nk}}$ можно задать и как расширение степени $k$ базового поля $\GF{2^n}$:
    \[ \alpha \in \GF{(2^n}^k), \alpha = \sum\limits_{i=0}^{k-1} a_i x^i, ~ a_i \in \GF{2^n} \]
с неприводимым многочленом $r(x)$ степени $k$ над полем $\GF{2^n}$,
    \[ r(x) = \sum\limits_{i=0}^{k} a_i x^i, ~ a_i \in \GF{2^n}, ~ a_k = 1. \]

\example
В табл. \ref{tab:irreducible-gf8} приведены примеры приводимых и неприводимых многочленов над полем $\GF{2^8}$.
\begin{table}[h!]
    \centering
    \caption{Примеры многочленов над полем $\GF{2^8}$\label{tab:irreducible-gf8}}
    \begin{tabular}{|c|c|}
        \hline
        Многочлен & Разложение \\
        \hline
        $\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$ \\
        \hline
    \end{tabular}
\end{table}
\exampleend

В алгоритме 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}, \]
причем коэффициенты многочлена (байты) интерпретируются как элементы поля $\GF{2^{8}}$. Это значит, что при сложении или умножении двух таких многочленов их коэффициенты складываются и перемножаются, как определено выше.

Многочлены $\mathbf{a}(y)$ и $\mathbf{b}(y)$ умножаются по модулю многочлена
    \[ \mathbf{M}(y)= \mathrm{'01'} y^4 + \mathrm{'01'} = y^4 + 1, ~ \mathrm{'01'} \in \GF{2^8}, \]
    \[ \mathbf{M}(y)= (\mathrm{'01'}, \mathrm{'00'},\mathrm{'00'}, \mathrm{'00'}, \mathrm{'01'}), \]
который \emph{не} является неприводимым над $\GF{2^8}$.
%Следовательно, многочлен $\mathbf{a}(y)$ задает многочлен третьей степени над полем $\GF{2^8}$, но не является элементом поля $\GF{2^{32}}$.

Операция умножения по модулю $\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, \]
где коэффициенты из поля $\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}.
\]

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

\example
Вычислим для $\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}
\]
\exampleend