forked from vlsergey/infosec
-
Notifications
You must be signed in to change notification settings - Fork 0
/
aes_math.tex
193 lines (167 loc) · 13.8 KB
/
aes_math.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
\section{Конечные поля и операции в алгоритме AES}\index{шифр!AES|(}
\selectlanguage{russian}
В алгоритме блочного шифрования\index{шифр!блочный} AES преобразования над битами и байтами осуществляются специальными математическими операциями. Биты и байты понимаются как элементы поля.
\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{Единичным} элементом поля является байт $\mathrm{'00000001'}$, или $\mathrm{'01'}$ в шестнадцатеричной записи. \emph{Нулевым} элементом поля является байт $\mathrm{'00000000'}$, или $\mathrm{'00'}$ в шестнадцатеричной записи. Одним из \emph{примитивных} элементов поля является байт $\mathrm{'00000010'}$, или $\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{'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'}. \]
\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}[!ht]
\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
\index{шифр!AES|)}