diff options
Diffstat (limited to 'crypto-algebra')
| -rw-r--r-- | crypto-algebra/crypto-algebra.pdf | bin | 205623 -> 373652 bytes | |||
| -rw-r--r-- | crypto-algebra/crypto-algebra.tex | 11 | ||||
| -rw-r--r-- | crypto-algebra/lectures/lecture10.tex | 224 | ||||
| -rw-r--r-- | crypto-algebra/lectures/lecture11.tex | 13 | ||||
| -rw-r--r-- | crypto-algebra/lectures/lecture13.tex | 183 | ||||
| -rw-r--r-- | crypto-algebra/lectures/lecture3.tex | 176 | ||||
| -rw-r--r-- | crypto-algebra/lectures/lecture4.tex | 92 | ||||
| -rw-r--r-- | crypto-algebra/lectures/lecture5.tex | 164 | ||||
| -rw-r--r-- | crypto-algebra/lectures/lecture7.tex | 186 | ||||
| -rw-r--r-- | crypto-algebra/lectures/lecture8.tex | 191 | ||||
| -rw-r--r-- | crypto-algebra/lectures/lecture9.tex | 204 |
11 files changed, 1444 insertions, 0 deletions
diff --git a/crypto-algebra/crypto-algebra.pdf b/crypto-algebra/crypto-algebra.pdf Binary files differindex a8f0f3f..2412a6f 100644 --- a/crypto-algebra/crypto-algebra.pdf +++ b/crypto-algebra/crypto-algebra.pdf diff --git a/crypto-algebra/crypto-algebra.tex b/crypto-algebra/crypto-algebra.tex index bc2c47a..992621b 100644 --- a/crypto-algebra/crypto-algebra.tex +++ b/crypto-algebra/crypto-algebra.tex @@ -18,5 +18,16 @@ % Семестр 1 \input{lectures/lecture1.tex} \input{lectures/lecture2.tex} +\input{lectures/lecture3.tex} +\input{lectures/lecture4.tex} +\input{lectures/lecture5.tex} +% \input{lectures/lecture6.tex} +\input{lectures/lecture7.tex} +\input{lectures/lecture8.tex} +\input{lectures/lecture9.tex} +\input{lectures/lecture10.tex} +\input{lectures/lecture11.tex} +% \input{lectures/lecture12.tex} +\input{lectures/lecture13.tex} \end{document} diff --git a/crypto-algebra/lectures/lecture10.tex b/crypto-algebra/lectures/lecture10.tex new file mode 100644 index 0000000..c9da50d --- /dev/null +++ b/crypto-algebra/lectures/lecture10.tex @@ -0,0 +1,224 @@ +% Лекция 10 (13.11.23) +%% TODO: проверить рендеринг потому что maker не завёлся + +%% NOTE: 7 +\paragraph{Расширения конечных полей} + +%% NOTE: 39 +\begin{theorem}[Количество точек эллиптической кривой над конечным полем, + свойство эндоморфизма Фробениуса] + Пусть $E / \F_q$ --- эллиптическая кривая, + \begin{equation*} + \varphi : E \to E,\, (x, y) \to (x^q, y^q), --- + \end{equation*} + эндоморфизм Фробениуса степени $q$ и + \begin{equation*} + t = q + 1 - #E(\F_q). + \end{equation*} + \begin{enumerate} + \item + Пусть $\alpha, \beta \in \C$ --- корни полинома $T^2 - tT + q$. Тогда + $\alpha$ и $\beta$ --- комплексно-сопряжённые, удовлетворяющие условиям + $|\alpha| = |\beta| = \sqrt{q}$, и для любого $r \geq 1$ + \begin{equation*} + #E(\F_q^r) = q^r + 1 - \alpha^r - \beta^r. + \end{equation*} + \item + Эндоморфизм Фробениуса удовлетворяет условию + \begin{equation*} + \varphi^2 - t \varphi + q = 0 \text{в кольце эндоморфизмов } \fn{End}(E). + \end{equation*} + \end{enumerate} + \label{thm:39} +\end{theorem} + +\begin{theorem}[Теорема Вейля для эллиптических кривых, А. Вейль, 1949 г.] + Пусть $E / \F_q$ --- эллиптическая кривая. Тогда существует $t \in \Z$ такое, + что дзета-функция эллиптической кривой является рациональной функцией от $T$: + \begin{equation*} + Z(E/\F_q; T) = \frac{1 - tT + qT^2}{(1 - T)(1 - qT)}. + \end{equation*} + + Более того $1 - tT + qT^2 = (1 - \alpha T)(1 - \beta T)$ с $|\alpha| = |\beta| + = \sqrt{q}$. +\end{theorem} +\begin{proof} + Логарифмируем равенство + %% TODO: переписать + \begin{equation*} + \ln Z(E/\F_q; T) \bydef \sum_{r = 1}^\infty \frac{#E(\F_q^r) T^r}{r} + =%_теорема 39 пункт а) + \sum_{r = 1}^\infty \frac{(1 - \alpha^r - \beta^r + q^r) T^r}{r} = + \sum_{r = 1}^\infty \frac{T^r}{r} - \sum_{r = 1}^\infty \frac{(\alpha T)^r}{r} - +\sum_{r = 1}^\infty \frac{(\beta T)^r}{r} +\sum_{r = 1}^\infty \frac{(q T)^r}{r} +=_* +используя тождество +ln(1 - x) = ln(1 + (-x)) = \sum_{r = 1}^\infty \frac{(-1)^{r + 1} (-x)^r}{r} = - \sum_{r = 1}^\infty \frac{x^r}{r}, +получаем +=_* -ln(1 - T) + ln(1 - \alpha T) + ln(1 - \beta T) - ln(1 - qT) = ln \left( \frac{1 - \alpha T) (1 - \beta T)}{(1 - T) (1 - qT)} \right). + \end{equation*} + следовательно, + \begin{equation*} + Z(E/\F_q; T) = \frac{1 - \alpha T) (1 - \beta T)}{(1 - T) (1 - qT)} + \end{equation*} + + По теореме \ref{thm:39}, пункт а) \alpha и \beta являются комплексно-сопряжёнными корнями полинома $T^2 - tT + q$, удовлетворяющие условиям + $|\alpha| = |\beta| = \sqrt{q}$, тогда по теореме Виета + \begin{equation*} + \alpha + \beta = t \land \alpha \beta = q. + \end{equation*} + + Имеем + \begin{equation*} + (1 - \alpha T)(1 - \beta T) = 1 - \beta T - \alpha T + \alpha \beta T^2 = 1 - (\alpha + \beta) T + (\alpha \beta) T^2 = 1 - tT + qT^2 + \end{equation*} + + Получаем + \begin{equation*} + Z(E/\F_q; T) = \frac{1 - tT + qT^2}{(1 - T)(1 - qT)} + \end{equation*} + + Также + \begin{equation*} + t = \alpha + \beta = q + 1 - #E(\F_q) \in \Z. + \end{equation*} +\end{proof} + +Пусть $E/\F_q$ --- эллиптическая кривая. Величина +\begin{equation*} + t = q+ 1 - #E(\F_q) +\end{equation*} +называется \emph{следом Фробениуса}. + + +Примечание --- К теореме Хассе. Из рассуждений имеем +\begin{equation*} + |#E(\F_q) - (q + 1)| = |-t| = |t| = |\alpha + \beta| \leq |\alpha| + |\beta| \leq 2\sqrt{q} +\end{equation*} + +Так как $\alpha$ и $\beta$ вместе с $t$ определяют значение $#E(\F_q)$, то число +точек над $\F_q$ однозначно определяет число точек над любым его расширением. + +Таким образом, теорему Вейля для эллиптических кривых можно использовать, в +частности, для нахождения числа точек над расширениями высокой степени. + +\begin{example} + Вычислим число точек эллиптической кривой $y^2 + y = x^3$. Здесь есть три + $\F_2$-рациональные точки: $(0; 0)$, $(0; 1$, $\mathcal{O}$ --- и дзета-функция + данной эллиптической кривой над полем $\F_2$ вычисляется следующим образом: + %% TODO: часть 1, 2, 3, 4 +\end{example} + +%% NOTE: 9 +\paragraph{Скручивание эллиптических кривых} + +Скручивание $E/F$ --- это гладкая кривая $E'/F$, изоморфная $E$ над $\overline{F}$. +Два скручивания эквивалентны, если они изоморфны над $F$. + +%% TODO: \ref{8} +Пусть $E$ --- эллиптическая кривая, заданная уравнением (8) над конечным полем +$\F_q,\, v \in \F_q$ --- некоторый квадратичный невычет. + +Эллиптическая кривая $E'$: +\begin{equation*} + y^2 = x^3 + a'x + b'. +\end{equation*} +где $a' = v^2 a,\, b = v^3 b$, является скручиванием $E$ над полем $\F_q$. + +%% NOTE: 41 +\begin{theorem}[О порядках эллиптической кривой и её скручивания] + Пусть $E$ --- эллиптическая кривая над $\F_q$, $E'$ --- скручивание эллиптической + кривой $E$ над $\F_q$. Тогда + \begin{equation*} + #E(\F_q) + #E'(\F_q) = 2q + 2. + \end{equation*} +\end{theorem} +\begin{proof} + Пусть + \begin{equation*} + g(x) = x^3 + ax + b. + \end{equation*} + + Тогда кривая $E$ задаётся уравнением + \begin{equation*} + y^2 = g(x), + \end{equation*} + для кривой $E'$ получаем + \begin{equation*} + y^2 = x^3 + a'x + b' = x^3 + v^2 ax + v^3 b = v^3 \left( \left(\frac{x}{v}\right)^3 + a \frac{x}{v} + b \right) = + v^3 g \left( \frac{x}{v} \right), + \end{equation*} + то есть кривая $E'$ задаётся уравнением + \begin{equation*} + y^2 = v^3 g \left( \frac{x}{v} \right). + \end{equation*} + + Когда $x$ пробегает все значения из $\F_q$, $\frac{x}{v}$ также пробегает все + значения из $\F_q$. Таким образом, каждому корню полинома $g$ соответствует + одна точка на каждой из эллиптических кривых $E$ и $E'$. + + Каждому значению $g$, которое является квадратичным вычетом, соответствуют две + точки на $E$ и ни одной на $E'$, так как $v^3 g$ будет квадратичным невычетом. + + Обратно, каждому значению $g$, которое является квадратичным невычетом + соотвествует две точки на $E'$ и ни одной на $E$, так как $v^3 g$ будет + квадратичным вычетом. + + Поэтому каждое значение $g$ в сумме даёт две точки на кривых $E$ и $E'$. + Поскольку всего имеется $a$ значений $g$ (с учётом кратности), то получаем + аффинные $2q$ точки на кривых $E$ и $E'$. + + Так как каждая из этих кривых содержит $\mathcal{O}$, то общее количество + элементов на $E$ и $E'$ равно $2q + 2$. +\end{proof} + +Благодаря этому факту после того, как найден порядок кривой, порядок её скручивания +находится без вычисления. + +\begin{example} + Пусть $E: y^2 = x^3 + 9$ --- эллиптическая кривая над $\F_{29}$. Возьмём, + например, $2 \in \F_{29}$ --- квадратичный невычет, так как сравнение $x^2 - 2 + \equiv 0 \pmod{29}$ не имеет решений. + + То есть скручивание $E'$: + \begin{equation*} + y^2 = x^3 + v^3 b = x^3 + 2^3 \cdot 9 = x^3 + 72 + \end{equation*} + + Тогда + \begin{equation*} + #E(\F_{29}) + #E'(\F_{29}) = 2 \cdot 29 + 2 = 60. + \end{equation*} +\end{example} + + +%% NOTE: 9 +\paragraph{Строение группы точек эллиптической кривой.} + +%% NOTE: 42 +\begin{theorem}[Строение группы точек эллиптической кривой, определённой над + конечным полем]. + Пусть $E/\F_q$ --- эллиптическая кривая, заданная над конечным полем $\F_q$. + Тогда $E(\F_q)$ либо является циклической группой, либо изоморфна произведению + двух циклических групп: + \begin{equation*} + E(\F_q) \cong \Z_{d_1} \times \Z_{d_2}, + \end{equation*} + где $d_1 | d_2$ и $d_1 | (q - 1)$. +\end{theorem} + +Пусть $N = #E(\F_q)$. Разлагая каждую из циклических групп в произведение групп +порядков $p^n$ для разных простых, можно представить группу точек произвольной +эллиптической кривой единственным образом в виде произведения групп вида +\begin{equation*} + \Z_{p^\alpha} \times \Z_{p^\beta}, +\end{equation*} +где произведение берётся по всем простым делителям $N$ (здесь $\alpha \geq 1,\, +\beta \geq 0$). + +Под \emph{типом} абелевой группы $\F_q$-рациональных точек на $E$ понимается +список $(\dots, p^\alpha, p^\beta, \dots)_{p|N}$ порядков циклических +$p$-примерных сомножителей в указанном представлении в виде произведения +(если $\beta = 0$, $p^\beta$ опускаем). + diff --git a/crypto-algebra/lectures/lecture11.tex b/crypto-algebra/lectures/lecture11.tex new file mode 100644 index 0000000..fbf6e72 --- /dev/null +++ b/crypto-algebra/lectures/lecture11.tex @@ -0,0 +1,13 @@ +% Лекция 11 (20.11.23) + +Тип определяет группу с точностью до изоморфизма. Найти тип не всегда легко. + +\begin{example} + Найдём тип абелевой группы эллиптической кривой $y^2 = x^3 - x$, определённой + над $\F_{71}$. Найдём сначала число точек $N$. + + Заметим, что в сумме (\ref{eq:18}) члены для $x$ и для $-x$ сокращаются друг + с другом (то есть функция нечётная): + + %% TODO: дописать пример 1, 2, 3, 4 +\end{example} diff --git a/crypto-algebra/lectures/lecture13.tex b/crypto-algebra/lectures/lecture13.tex new file mode 100644 index 0000000..7b6414f --- /dev/null +++ b/crypto-algebra/lectures/lecture13.tex @@ -0,0 +1,183 @@ +% Лекция 13 (04.12.23) + +Соответствие $x \\ x'$ является взаимно однозначным и легко вычислимым. + +\begin{example} + Встроим открытый текст в координату точки эллиптической кривой, определённой + над конечным полем $\FF_{32} = \FF_{2^5}$. Пусть эллиптическая кривая $E(\FF_{32})$ + задана уравнением + \begin{equation*} + y^2 + xy = x^3 + t; + \end{equation*} + поле $\FF_{32}$ задано полиномом + \begin{equation*} + t^5 + t^2 + 1, + \end{equation*} + таким образом, $\FF_{32} = \FF_2 / (t^5 + t^2 + 1)$. + + Кривая имеет 16 точек. Открытый текст $t^3 + 1$ не является $x$-координатой + точки кривой. Вычисляем + \begin{align*} + \sqrt{t} &= t^{2^{5 - 1}} = t^{16} = * \\ + t^5 &= -t^2 - 1 = t^2 + 1; \\ + t^6 &= tt^5 = t(t^2 + 1) = t^3 + t; \\ + t^7 &= t^4 + t^2; \\ + t^8 &= t^5 + t^3 = t^3 + t^2 + 1; \\ + t^{16} &= (t^8)^2 = t^6 + 2t^5 + t^4 + 2t^3 + 2t^3 + 2t^2 + 1 + = t^4 + t^3 + t + 1. \\ + * &= t^4 + t^3 + t + 1. + \end{align*} + + Заменяем элемент $t^3 + 1$ на элемент, заданный уравнением + \begin{equation*} + \frac{1}{x} = \frac{1}{t^4 + t^3 + t + 1} + \frac{1}{t^3 + 1}. + \end{equation*} + + Получаем необходимую $x$-координату точки кривой: + \begin{align*} + \frac{1}{x} &= \frac{t^4 + t^3 + t + 1 + t^3 + 1}{(t^4 + t^3 + t + 1)(t^3 + 1)} = \\ + &= \frac{t(t^3 + 1)}{(t^4 + t^3 + t + 1)(t^3 + 1)} = \\ + &= \frac{t}{t^4 + t^3 + t + 1}; \\ + x &= t^3 + t^2 + \frac{1}{t} + 1 = \\ + &= t^3 + t^2 + (t^4 + t) + 1 = \\ + &= t^4 + t^3 + t^2 + t + 1. + \end{align*} +\end{example} + +%% NOTE: 3.3.2 +\subsubsection{Установление сеансового ключа} + +Рассмотрим аналог ключевого обмена Диффи--Хеллмана. Предположим, что Алиса и Боб +хотят договориться о ключе, которым будут впоследствии пользоваться в некоторой +классической криптосистеме. + +Ключом может служить <<случайная>> точка на эллиптической кривой $E$, так как +Алиса и Боб могут заранее договориться о способе преобразования её в целое число +(например, взять образ её координаты $x$ при некотором установленном в системе +простом отображении из $\FF_q$ в натуральные числа). + +Итак, предположим, что $E$ --- эллиптическая кривая над $\FF_q$, а $Q$ --- +согласованная (и общеизвестная) точка на кривой. Желательно, чтобы точка $Q$ +имела весьма большой порядок (равный либо $\#E(\FF_q)$, либо большому делителю +$\#E(\FF_q)$). + +Здесь точка $Q$ играет ту же роль, что и образующий элемент $g$ в системе +Диффи--Хеллмана для конечных полей. + +Договорённость может быть предварительной, или эллиптическая кривая может +создаваться непосредственно в ходе сеанса связи. + +Для установления сеансового ключа Алиса и Боб выполняют следующий протокол: +\begin{enumerate} + \item + Алиса случайным образом выбирает целое число $k_A$, которое держит в секрете. + \item + Алиса вычисляет точку $k_A Q \in E$ и посылает её Бобу (возможно открыто). + \item + Боб случайным образом выбирает целое число $k_B$, которое держит в секрете. + \item + Боб вычисляет точку $k_B Q \in E$ и посылает её Алисе (возможно открыто). + \item + Алиса умножает точку, которую она получила от Боба, на свой секретный ключ + $k_A$. Боб умножает точку, которую он получил от Алисы, на свой секретный + ключ $k_B$, тем самым получая общий ключ + \begin{equation*} + P = k_A k_B Q \in E + \end{equation*} +\end{enumerate} + +Ева, которая бы хотела шпионить за Алисой и Бобом, должна была бы определить $P += k_A k_B Q$, зная $Q$, $k_A Q$ и $k_B Q$, но не зная $k_A$ или $k_B$. + +Задача подслушивателя называется <<задачей Диффи--Хеллмана для эллиптических +кривых>>. + +Систему Диффи--Хеллмана можно взломать, если решить <<проблему дискретного +логарифма>> в группе точек эллиптической кривой $E$. + +\subsubsection{Шифрование} + +Протокол Диффи--Хеллмана модифицируется для передачи сообщений, используя +идею Эль-Гамаля. Пусть $E$ --- эллиптическая кривая над $\FF_q$, а $Q$ --- +согласованная (и общеизвестная) точка на кривой. + +Предположим, что набор единиц сообщения был встроен в $E$ некоторым +согласованным образом, и Боб хочет послать Алисе сообщение $M \in E$. + +\begin{enumerate} + \item + Алиса случайным образом выбирает целое число $k_A$, которое держит в секрете. + \item + Алиса вычисляет точку $k_A Q \in E$ и посылает её Бобу (возможно открыто). + \item + Боб случайным образом выбирает целое число $k_B$, которое держит в секрете. + \item + Боб вычисляет точку $k_B Q \in E$ и посылает её Алисе (возможно открыто). + \item + Боб выбирает другое секретное случайное целое число $l$. + \item + Боб отправляет Алисе пару точек + \begin{equation*} + (lQ, M + l(k_A q)). + \end{equation*} + \item + Чтобы расшифровать сообщение, Алиса умножает первую точку в паре на своё + секретное $k_A$, а затем вычитает результат из второй точки в паре: + \begin{equation*} + (M + l(k_A Q)) - k_A(lQ) = M. + \end{equation*} +\end{enumerate} + +Данную систему также можно будет взломать, если решить <<проблему дискретного +логарифма>> в группе точек эллиптической кривой $E$. + + +\subsubsection{Цифровая подпись} + +\paragraph{Протокол цифровой подписи Эль-Гамаля.} + +В протоколе цифровой подписи Эль-Гамаля открытый ключ проверки подписи сожержит +уравнение эллиптической кривой $E(F)$, образующую $Q$ простого порядка $r$ и +точку $P = lQ$. + +Секретным ключом формирования подписи является показатель $l$. Кроме того, в +протоколе подписи используется хэш-функция $h$ и функция $f$. В качестве +функции $f(R)$ могут использоваться функции от координат: $x_R$, $y_R$, +$x_R + y_R$ и т. п. + +Для получения цифровой подписи под сообщением $M$ необходимо выполнять +следующие действия (шаги) по алгоритму: +\begin{enumerate} + \item вычислить хэш-код сообщения $M: h(m)$; + \item + сгенерировать случайное (псевдослучайное) целое число $k$, удовлетворяющее + неравенству + \begin{equation*} + 0 < k < r; + \end{equation*} + \item + вычислить точку эллиптической кривой $R = kQ$, $R = (x_R, y_R)$; + \item + вычислить значение $s$ из решения сравнения + \begin{equation} + h(m) \equiv lf(R) + ks \pmod{r} + \label{eq:23} + \end{equation} +\end{enumerate} + +При этом необходимо, чтобы выполнялось неравенство $f(R) \neq 0 \pmod{r}$, в +противном случае вернуться к шагу 2. Если $f(R) \equiv 0 \pmod{r}$, то подпись +не зависит от персонального ключа. + +Исходными данными этого процесса являются ключ подписи $l$ и подписываемое +сообщение $M$, а входным результатом --- цифровая подпись $(R, s)$. + +При этом можно сократить объём подписи, задав вместо $R$ только координату +$x_R$ и знак координаты $y_R$ (0, если $y_R < \frac{p}{2}$, и 1, если $y_R +> \frac{p}{2}$), тогда при проверке подписи необходимо будет восстановить +координату $y_R$ решением квадратного уравнения в поле $F$. + +Для проверки цифровой подписи $(R, s)$ под полученным сообщением $M$ необходимо +выполнять следующие действия (шаги) по алгоритму: + +%% TODO: дописать diff --git a/crypto-algebra/lectures/lecture3.tex b/crypto-algebra/lectures/lecture3.tex new file mode 100644 index 0000000..826342c --- /dev/null +++ b/crypto-algebra/lectures/lecture3.tex @@ -0,0 +1,176 @@ +% Лекция 3 (18.09.23) + +Пусть $R$ --- некоторое кольцо. Подмножество $I \subseteq R, I \neq +\varnothing$, называется \emph{правым идеалом}, если +\begin{enumerate} + \item + $I$ является подгруппой аддитивной группы $R$ (то есть для любых $a, b \in + I$ выполняется $a + b \in I$); + \item + Для любых $x \in R$ и $a \in I$ выполняется $ax \in I$, то есть $Ix + \subseteq I$. +\end{enumerate} + +Аналогично определяется \emph{левый идеал}. Если идеал является одновременно +правым и левым, то его называют \emph{двусторонним идеалом} или просто +\emph{идеалом}. В коммутативных кольцах все идеалы двусторонние. + +\begin{example} + Если $r$ --- какой-то элемент из коммутативного кольца $R$, то множество $rR$ + всегда является идеалом в $R$. Говорят, что $rR$ --- \emph{главный идеал}, + порождённый элементом $r \in R$. +\end{example} + +\paragraph{Векторные пространства} %% NOTE: 6 + +\emph{Векторным пространством} $V$ над полем $F$ называется абелева группа +$(V, +)$ вместе с операцией умножения $\cdot : F \times V \to V$ (обычно +обозначаемой сопоставлением) такой, что для всех $a, b \in F$ и $v, w \in V$ +выполняются следующие аксиомы: +\begin{enumerate} + \item $a (v + w) = av + aw$; + \item $v (a + b) = av + bv$; + \item $(ab)v = a(bv)$; + \item $1v = v$. +\end{enumerate} + +Элементы $V$ называются \emph{векторами}, а элементы $F$ называются +\emph{скалярами}. Групповая операция $+$ называется \emph{векторным сложением}, +а операция умножения --- \emph{скалярным умножением}. + +Пусть $S = \set{v_1, v_2, \dots, v_n}$ --- конечное подмножество векторного +пространства $V$ над полем $F$. + +Линейная комбинация $S$ --- это выражение вида +\begin{equation*} + a_1 v_1 + a_2 v_2 + \dots + a_n v_n, +\end{equation*} +где каждое $a_i \in F$. + +Множество $S$ \emph{линейно зависимо} над $F$, если существуют скаляры $a_1, +a_2,$ $\dots, a_n$, не все нули, такие, что +\begin{equation*} + a_1 v_1 + a_2 v_2 + \dots + a_n v_n = 0 +\end{equation*} + +Если таких скаляров не существует, то $S$ \emph{линейно независимо} над $F$. + +Пусть $V$ --- векторное пространство над полем $F$. Его (конечным) +\emph{базисом} называется такое множество $n$ векторов $v_1, \dots, v_n$, что +любой $w \in V$ однозначно представим в виде линейной комбинации +\begin{equation*} + w = a_1 v_1 + \dots + a_n v_n, +\end{equation*} +где $a_i \in F$. + +\begin{theorem}[О базисе] %% NOTE: 12 + Пусть $V$ --- векторное пространство. Если существует один конечный базис $V$ + над $F$, то любой другой базис имеет то же число элементов. +\end{theorem} + +Если векторное пространство $V$ имеет базис, то количество элементов в базисе +называется \emph{размерностью} $V$ и обозначается $\dim V$. + +Если пространство не имеет конечного базиса, оно называется +\emph{бесконечномерным}. + +\begin{example} + Полиномы степени $\leq n$ над любым полем $F$ образуют $(n + 1)$-мерное + векторное пространство над $F$ с базисом $1, x, x^2, \dots, x^n$ (базис + не определяется однозначно, например, $1, 1 + x, 1 + x^2, \dots, 1 + + x^n$ --- тоже базис). Коммутативное кольцо все полиномов $F[x]$ является + бесконечномерным векторным пространством над полем $F$. +\end{example} + +Пусть $K$ --- расширение поля $F$. Тогда $K$ можно рассматривать как векторное +пространство над подполем $F$, где векторное сложение и скалярное умножение --- +это операции сложения и умножения в поле $K$. + +Это означает, что $(K, +)$ --- абелева группа и что определено умножение её +элементов на элементы $F$ (скаляры), подчиняющиеся тождествам +\begin{enumerate} + \item $a (bv) = (ab) v$; + \item $(a + b) v = av + bv$; + \item $a (v + w) = av + aw$; + \item $1v = v$. +\end{enumerate} +для всех $a, b \in F$ и $v, w \in K$. + +Размерность этого векторного пространства называется \emph{степенью} $K$ над +$F$ и обозначается $[K: F]$. Если эта степень конечна, то $K$ называется +\emph{конечным расширением} F. + +\begin{theorem}[О конечном расширении] + Пусть $F, K, L$ --- поля. Если $L$ --- конечное расширение $K$ и $K$ --- + конечное расширение $F$, то $L$ также является конечным расширением $F$ и + \[ [L: F] = [L: K] [K: F] \] +\end{theorem} + + +\paragraph{Расширения полей.} + +Пусть $F$ и $K$ --- два поля, причём $F \subset K (K / F)$. Поле $K$ называется +\emph{простым расширением} поля $F$, если существует такой элемент $a \in K$, +что $K = F(a)$ --- наименьшее подполе $K$, содержащее $F$ и $a$. Элемент $a$ +называется \emph{примитивным элементом} расширения. Подполе поля $K$, отличное +от $K$, называется \emph{собственным полем}. \emph{Простым} называется поле, не +содержащее собственных полей. + +Элемент $a \in K$ называется \emph{алгебраическим} над полем $F$, если он +удовлетворяет алгебраическому уравнению +\begin{equation*} + f(a) = \sum_{k = 0}^n c_k a^k = 0, +\end{equation*} +где $c_0, \dots, c_n \in F$. + +Полином $f(x)$ называется \emph{аннулирующим полиномом элемента $a$}. + +Среди всех аннулирующих полиномов можно выбрать полином наименьшей степени +со старшим коэффициентом, равным единице. Такой полином называется +\emph{минимальным полиномом} элемента $a$ (минимальный полином неприводим, то +есть не разлагается в произведение полиномов меньшей степени). + +Алгебраичность элемента измеряется размерностью подполя, которое он порождает. + +Расширение полей $F \subset K$ называется \emph{алгебраическим}, если любой +элемент $a \in K$ алгебраичен над $F$. Коротко говорят, что расширение $K$ +конечно (алгебраично) над $F$. + +Итак, поле $F(a)$ содержит кольцо $R$ полиномов от переменной $a$ с +коэффициентами из $F$, $R = \set{\sum c_k a^k}$, $c_k \in F$. + +Имеет место изоморфизм $R \cong F[x] / f(x)$, более того +\begin{equation*} + F(a) = R \cong F[x] / f(x), +\end{equation*} +где $F[x]$ --- кольцо полиномов от одной переменной $x$, $x$ --- формальная +переменная, не имеющая отношения к полю $F(a)$, $a$ --- элемент поля $F(a)$, +$f(x)$ --- неприводимый над $F$ полином такой, что $f(a) = 0$. + +Элемент $a$ удовлетворяет уравнению $f(a) = 0$, которое называется +\emph{уравнением, определяющим поле $F(a)$.} + +Таким образом, любой элемент поля $F(a)$ в этом случае является полиномом. С +такими полиномами можно обращаться как с классами вычетов по модулю $f(x)$, то +есть степень каждого из них меньше степени полинома $f(x)$. Для некоторого +полинома $f(a) \in F[a]$ равенство $f(a) = 0$ эквивалентно сравнению $f(a) +\equiv 0 \pmod{f(a)}$. + +\begin{example} + Пусть $F = \set{0, 1}$. Построим алгебраическое расширение $F(t)$ степени 4. + Выберем неприводимый полином вида $f(x) = x^4 + x + 1$. Обозначим корень + этого полинома через $t$. Тогда $F(t) = F[t] / f(t)$. +\end{example} + +Поле $K$ называется \emph{алгебраически замкнутым}, если любой полином из +$K[x]$ степени, большей нуля, имеет в $K$ корень, то есть любое алгебраическое +над полем $K$ число принадлежит этому полю (то есть любой полином из $K[x]$ +раскладывается на линейные множители). + +Поле $K \supset F$ называется \emph{алгебраическим замыканием} поля $F$, если +$K$ алгебраично над $F$ и алгебраически замкнуто. + +\begin{theorem}[Об алгебраичности расширения конечной степени] + Всякое расширение $F \subset K$ конечной степени алгебраично, то есть все + элементы поля $K$ алгебраичны над полем $F$. +\end{theorem} diff --git a/crypto-algebra/lectures/lecture4.tex b/crypto-algebra/lectures/lecture4.tex new file mode 100644 index 0000000..88feafe --- /dev/null +++ b/crypto-algebra/lectures/lecture4.tex @@ -0,0 +1,92 @@ +% Лекция 4 (18.09.23) + +\paragraph{Модель решётки.} + +Пусть $X$ --- конечное множество. Бинарное отношение <<$\leq$>> на множестве $X$ +называется \emph{отношением частичного порядка}, когда для любых $a, b, c \in X$ +выполняются три свойства: +\begin{enumerate} + \item рефлексивность: $a \leq a$; + \item транзитивность: $(a \leq b, b \leq c) \implies (a \leq c)$; + \item антисимметричность: $(a \leq b, b \leq a) \implies (a = b)$. +\end{enumerate} + +Множество $X$ с заданной на нём частичной упорядоченностью называется +\emph{частично упорядоченным}. + +Если $a, b \in X$ и $a \leq b$, то, в зависимости от обстоятельств, говорят, +что $a$ \emph{меньше или равно} $b$, $a$ \emph{содержится в} $b$, $a$ +\emph{предшествует} $b$. + +Для $a, b \in X$ элемент $c = a \oplus b \in X$ называется \emph{наименьшей +верхней гранью}, когда выполняются условия: +\begin{enumerate} + \item $a \leq c, b \leq c$; + \item для $d \in X$ истинно $(a \leq d, b \leq d) \implies (c \leq d)$. +\end{enumerate} + +Для $a, b \in X$ элемент $c = a \otimes b \in X$ называется \emph{наибольшей +нижней гранью}, когда выполняются условия: +\begin{enumerate} + \item $c \leq a, c \leq b$; + \item для $d \in X$ истинно $(d \leq a, d \leq b) \implies (d \leq c)$. +\end{enumerate} + +Для пары элементов частично упорядоченного множества $X$ не обязательно +существует наименьшая верхняя (наибольшая нижняя) грань, но, если она +существует, то из антисимметричности следует её единственность. + +Эти элементы называют также \emph{точными} (\emph{верхней} и \emph{нижней} +соответственно) \emph{гранями} подмножества $X^* \subseteq X$. + +Пусть $X$ --- частично упорядоченное множество. $(X, \leq)$ называется +\emph{решёткой}, если каждое его конечное подмножество имеет точную нижнюю и +точную верхнюю грани, то есть, когда $\forall a, b \in X$ существуют +$a \otimes b \in X$ и $a \oplus b \in X$. + +\begin{lemma} %% TODO: пронумеровать (лемма 1) + Для любого набора $S = \set{a_1, a_2, \dots, a_n}$ элементов решётки $(X, + \leq)$ существуют единственные элементы: + \begin{itemize} + \item + $\oplus S = a_1 \oplus a_2 \oplus \dots \oplus a_n$ --- наименьшая + верхняя грань $S$; + \item + $\otimes S = a_1 \otimes a_2 \otimes \dots \otimes a_n$ --- наибольшая + нижняя грань $S$. + \end{itemize} +\end{lemma} + +Для решётки $(X, \leq)$ существует максимальный элемент $high = \oplus X$ и +минимальный элемент $low = \otimes X$. + +\emph{Линейная решётка (линейная шкала)} из $n$ элементов --- это линейное +упорядоченное множество; можно всегда считать $X = \set{0, 1, \dots, n}$. + +Как правило, решётки представляют с помощью ориентированных графов. При этом +вершинами графа являются элементы множества $X$, и если для $a_1, a_2 \in X$ +справедливо неравенство $a_1 \leq a_2$, то в графе существует путь из $a_1$ в +$a_2$. + +Частным важным случаем решёток является \emph{решётка подмножеств некоторого +конечного множества $U$}. Пусть $U$ --- конечное множество, $X = 2^{U}$ --- +множество всех подмножеств множества $U$. Определим решётку $(X, \leq)$ с +бинарным отношением частичного порядка <<$\leq$>>, где для $a, b \subseteq U$, +$a, b \in X$ выполняется условие: $a \leq b \iff a \subseteq b$. При этом $a +\oplus b = a \cup b,\, a \otimes b = a \cap b$. + +Пусть $(L, \leq)$ --- линейная решётка, $(X, \leq)$ --- решётка подмножеств $U$. +Определим \emph{решётку многоуровневой безопасности} $(X \times L, \leq)$ с +бинарным отношением частичного порядка <<$\leq$>>, где для $(a, \alpha), +(b, \beta) \in X \times L$ выполняется условие: $(a, \alpha) \leq (b, \beta) +\iff a \subseteq b, a \leq b$. + +При этом +\begin{align*} + (a, \alpha) \oplus (b, \beta) &= (a \cup b, \max\set{\alpha, \beta}) \\ + (a, \alpha) \otimes (b, \beta) &= (a \cap b, \min\set{\alpha, \beta}) \\ +\end{align*} + +На практике при использовании решёток многоуровневой безопасности решётка +$(L, \leq)$ является линейной шкалой уровней конфиденциальности, а $(X, \leq)$ +--- решёткой подмножеств множества неирархических категорий информации. diff --git a/crypto-algebra/lectures/lecture5.tex b/crypto-algebra/lectures/lecture5.tex new file mode 100644 index 0000000..dda14e3 --- /dev/null +++ b/crypto-algebra/lectures/lecture5.tex @@ -0,0 +1,164 @@ +% Лекция 5 (25.09.23) + +%% NOTE: 8 +\paragraph{Конечное поле} --- это поле $F$, содержащее конечное число элементов. + +\begin{theorem}[Существование и единственность конечных полей] + \begin{enumerate} + \item + Если $F$ --- конечное поле, то $F$ содержит $p^m$ элементов для некоторого + простого числа $p$ и целого числа $m \geq 1$. + \item + Для каждого простого числа $p$ и целого числа $m \geq 1$ существует + единственное (с точностью до изоморфизма) конечное поле порядка $p^m$. + \end{enumerate} +\end{theorem} + +Конечное поле порядка $p^m$ обозначается $\FF_{p^m}$ или $GF(p^m)$ и +называется \emph{полем Галуа}. Заметим, что если $p$ --- простое число, то +$\Z_p$ --- поле, а значит, каждое поле порядка $p$ изоморфно $\Z_p$. + +\begin{theorem}[О свойствах поля $\mathbb{F}_q$] + Если $\FF_q$ --- конечное поле порядка $q = p^m$, $p$ --- простое число, + то характеристикой $\FF_q$ является $p$. Более того, $\FF_q$ содержит в + качестве подполя простое поле $\FF_p = \Z_p$. Следовательно, $\FF_q$ можно + рассматривать как расширение поля $\Z_p$ степени $m$. +\end{theorem} + +Группа ненулевых элементов $\FF_q$ обозначается $\FF^*_q$. +\emph{Образующий элемент $g$} конечного поля $\FF_q$ есть элемент порядка $q - +1$. + +\begin{theorem}[О циклической группе $\FF_q$] + Каждое конечное поле имеет образующий элемент. Если $g$ --- образующий элемент + $\FF^*_q$, то $g^j$ также является образующим элементом $\iff \gcd(j, q - 1) = + 1$. Таким образом, всего имеется $\varphi(q - 1)$ различных образующих + элементов $\FF^*_q$, где $\varphi$ --- функция Эйлера. +\end{theorem} + +\begin{theorem}[Единственность конечного поля порядка $q = p^f$] + Если $\FF_q$ --- поле из $q = p^f$ элементов, то каждый элемент удовлетворяет + уравнению $x^q - x = 0$, а $\FF_q$ --- это в точности множество корней этого + уравнения. + + Обратно, для каждой степени простого числа $q = p^f$ поле разложения над + $\FF_p$ многочлена $x^q - x$ является полем из $q$ элементов. +\end{theorem} + +Пусть $K$ --- расширение степени $n$ конечного поля $F = \FF_p$. \emph{След +элемента $x \in K$} в поле $F$ определяется как сумма +\begin{equation*} + Tr(x) = x + x^p + \dots + x^{p^{n - 1}} +\end{equation*} + +\begin{theorem}[След элемента] + След $Tr$ является гомоморфизмом аддитивных групп $K \to F$. +\end{theorem} + +%% NOTE: 9 +\paragraph{Логарифмирование.} + +Наличие в конечном поле примитивного элемента $a$ позволяет ввести понятие +логарифма для ненулевых элементов этого поля. Пусть $G$ --- конечная +мультипликативная группа. \emph{Задача дискретного логарифмирования} состоит в +решении при заданных $a, b \in G$ уравнения \[a^x = b\] относительно целого $x$, +$0 \leq x < n = \text{ord } a$. + +Решение $x$ называется \emph{дискретным логарифмом}, или \emph{индексом}, $b$ +по основанию $a$ и обозначается $\text{ind}_a b$. + +\emph{Примечание} --- Когда групповая операция в $G$ записывается аддитивно, то +рассматривается уравнение $xa = b$. + +По сути, \emph{эллиптическая кривая над конечным полем} --- это конечная абелева +группа, в которой можно ставить задачу о вычислении дискретных логарифмов. + +\subsection{Введение в эллиптические кривые} + +\paragraph{Аффинные алгебраические многообразия, проективная плоскость.} + +Пусть $F$ --- поле, $F^*$ --- множество обратимых элементов поля $F$. + +\emph{Аффинным $n$-мерным пространством $A^n(F)$} над $F$ называется множество +точек \[\set{P = (x_1, \dots, x_n)} \in F^n\] значения $x_1, \dots, x_n$ +называются \emph{аффинными координатами}. + +\emph{Аффинное алгебраическое многообразие (множество) $V$} --- это подмножество +аффинного пространства, на котором обращаются в нуль полиномы $f_1, \dots, f_k +\in F[x_1, \dots, x_n]$: +\begin{equation*} + V = \set{P \in F^n | f_1(P) = 0, \dots, f_k(P) = 0} +\end{equation*} + +В случае $n = 2$ аффинное пространство называется \emph{аффинной плоскостью}, а +алгебраическое многообразие, идеал которого образован одиночным полиномом, --- +(плоской) \emph{алгебраической кривой}. + +Степень полинома, задающего кривую, называется \emph{степенью кривой}. + +\emph{Неприводимая алгебраическая кривая} задаётся неприводимым (над алгебраическим +замыканием $\overline{F}$ поля $F$) полиномом из кольца $F[x, y]$. + +\begin{example} + Алгебраическая кривая, заданная полиномом + \begin{equation*} + f(x, y) = (xy + 1)(x^2 + y^2 + 1) + \end{equation*} + + Полином $f(x, y)$ раскладывается на множители, поэтому алгебраическая кривая + является объединением кривых + \begin{equation*} + xy + 1 = 0 \land x^2 + y^2 + 1 = 0 + \end{equation*} + + Вместо этой кривой можно рассмотреть две более простых алгебраических кривых, + задаваемых неразложимыми делителями левой части уравнения. Таким образом, + изучение алгебраической кривой сводится к изучению её подмножеств, задаваемых + нулями неприводимых полиномов. +\end{example} + +Алгебраическую кривую $E$, заданную уравнением с коэффициентами из поля $F$, +будем обозначать $E/F$; алгебраическую кривую, точки которой лежат в $F^2$, +будем обозначать $E(F)$. + +Даже если уравнение $f(x, y) = 0$, задающее кривую $E$, имеет коэффициенты +из простого поля $F$, множество решений этого уравнения (и, соответственно, +множество точек кривой) может рассматриваться над расширением поля $F$, +например, над его алгебраическим замыканием. + +\emph{Аффинная прямая $A^1(F)$} над полем $F$ представляет собой поле $F$. + +\emph{Проективной прямой $P^1(F)$} над полем $F$ называется множество пар +\begin{equation*} + \set{X, Y} \in F^2 \backslash (0, 0) +\end{equation*} +с эквивалентностью $(X, Y) \equiv (aX, aY)$, если $a \in F^*$. + +Если $Y \neq 0$, то каждая точка $(X, Y) \in P^1(F)$ эквивалентна точке $(x, +1)$ аффинной прямой: просто полагаем $x = X / Y$. Но на проективной прямой есть +точка вида $(X, 0)$, соответствующая аффинной точке. + +Эта точка $P_\infty$ называется \emph{бесконечно удалённой}. Поэтому +\begin{equation*} + P^1(F) = A^1(F) \cup \set{P_\infty} +\end{equation*} + +\emph{Проективной плоскостью} $P^2(F)$ над полем $F$ называется множеством троек +\begin{equation*} + \set{X, Y, Z} \in F^3 \backslash (0, 0, 0) +\end{equation*} +с эквивалентностью $(X, Y, Z) \equiv (aX, aY, aZ)$, если $a \in F^*$. Здесь +$X, Y, Z$ --- проективные координаты. + +Свяжем аффинную плоскость с проективной. Полагая +\begin{equation*} + x = \frac{X}{Z}, y = \frac{Y}{Z}, Z \neq 0, +\end{equation*} +получаем биекцию между множеством точек $(x, y)$ аффинной плоскости и +подмножеством точек $(x, y, 1)$ проективной плоскости. + +Однако на проективной плоскости есть точки с нулевой $Z$-координатой, которые не +соответствуют никаким точкам аффинной плоскости. + +Тем самым проективную плоскость можно представить как объединение всех точек +$(x, y)$ обычной (<<аффинной>>) плоскости с точками, для которых $Z = 0$. diff --git a/crypto-algebra/lectures/lecture7.tex b/crypto-algebra/lectures/lecture7.tex new file mode 100644 index 0000000..a618f56 --- /dev/null +++ b/crypto-algebra/lectures/lecture7.tex @@ -0,0 +1,186 @@ +% Лекция 7 (09.10.23) + +\paragraph{Нормальные формы эллиптической кривой, дискриминант и $j$-инвариант.} + +\emph{Эллиптическая кривая} --- это пара $(E, P_\infty)$, где $E$ --- гладкая +кубическая кривая и $P_\infty \in E$. Существуют наиболее употребительные +(нормальные) формы уравнения эллиптической кривой, получаемые линейной заменой +переменных. Большинство из них являются частными случаями \emph{обобщённой +формы Вейерштрасса}, содержащей единственную бесконечно удалённую точку, которая +является точной перегиба, а бесконечно удалённая прямая является касательной в +этой точке. + +\emph{Эллиптическая кривая} $E$ записывается \emph{уравнением Вейерштрасса} вида +\begin{equation} + y^2 + a_1 x y + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6 + \label{eq:weierstrass} +\end{equation} + +Если $a_1, a_2, a_3, a_4, a_6 \in F$, то говорят, что $E$ определена над $F$. + +%% TODO: Примечание +Заметим, что в уравнении (\ref{eq:weierstrass}) нет коэффициента $a_5$. Это +объясняется тем, что индексы коэффициентов имеют следующий смысл. Видим, что +$y = x^\frac{3}{2} + o(x)$. Сделав замену +\begin{equation*} + \begin{cases} + x = t^2 + o(t) \\ + y = t^2 + o(t) + \end{cases} +\end{equation*} +можно переписать (\ref{eq:weierstrass}) в виде +\begin{equation*} + t^6 + a_1 t^5 + a_3 t^3 = t^6 + a_2 t^4 + a_4 t^2 + a_6 +\end{equation*} +%% END + +Для обозначения эллиптической кривой используют запись $E$ или $E/F$, чтобы +подчеркнуть, что кривая определена над $F$. + +Точки, лежащие на эллиптической кривой, являются решениями $(x, y) \in F^2$ +уравнения (\ref{eq:weierstrass}) (это так называемые \emph{аффинные точки}); +единственную, лежащую на $E$ (в проективной плоскости), точку на бесконечности, +в дальнейшем будем обозначать $\mathcal{O}$. + +Если $K$ --- некоторое расширение поля $F$, то $E(K)$ обозначает множество +точек $(x, y) \in K^2$, которые удовлетворяют (\ref{eq:weierstrass}), их +называют $K$-рациональными вместе с точкой $\mathcal{O}$ + +Для того, чтобы кривая (\ref{eq:weierstrass}) была эллиптической, она +должна быть гладкой. Это означает, что не существует подходящих $(x, y) +\in E(\overline{F})$, где $\overline{F}$ --- алгебраической замыкание $F$, +удовлетворяющих двум уравнениям +\begin{align*} + a_1 y &= 3x^2 + 2a_2 x + a_4, \\ + 2y + a_1 x + a_3 &= 0. +\end{align*} + +\emph{Дискриминантом} уравнения Вейерштрасса является величина +\begin{equation*} + \Delta = -b_2^2 b_8 - 8 b_4^3 - 27 b_6^2 + 9 b_2 b_4 b_6, +\end{equation*} +где +\begin{align*} + b_2 &= a_1^2 + 4 a_2, \\ + b_4 &= 2 a_4 + a_1 a_3, \\ + b_6 &= a_3^2 + 4 a_6, \\ + b_8 &= a_1^2 a_6 + 4 a_2 a_6 - a_1 a_3 a_4 + a_2 a_3^2 - a_4^2. \\ +\end{align*} + +В случае $\Delta \neq 0$ $j$-инвариантом эллиптической кривой $F$ называется +величина +\begin{equation*} + j(E) = \frac{c_4^3}{\Delta}, +\end{equation*} +где $c_4 = b_2^2 - 24 b_4$. + +%% TODO: теорема 20 +\begin{theorem}[Критерий гладкости кривой, заданной уравнением Вейерштрасса] + Кривая $E$, заданная уравнением Вейерштрасса (\ref{eq:weierstrass}), гладкая + $\iff \Delta(E) \neq 0$. +\end{theorem} + +Будем рассматривать только гладкие кубические кривые. Две эллиптические кривые +$E$ и $\widetilde{E}$ над полем $F$, заданные уравнениями +%% TODO: дописать + +Эллиптические кривые, заданные над полем $F$, могут быть не изоморфными над +этим полем, но могут стать изоморфными над расширением. + +\begin{theorem}[Критерий изоморфности эллиптических кривых] %% NOTE: 21 + Две эллиптические кривые $E_1$ и $E_2$ изоморфны над $\overline{F} \iff + j(E_1) j(E_2)$. +\end{theorem} + +%% TODO: ссылка на уравнение (3) +Замена переменных (3) в уравнении (\ref{eq:weierstrass}) называется +\emph{допустимой}. Это преобразование обратимо и обратное преобразование также +допустимо. Кроме того, допустима тождественная замена переменных, поэтому +всякая эллиптическая кривая изоморфна сама себе. + +Композиция допустимых преобразований также является допустимой. Таким образом, +изоморфизм эллиптических кривых является отношением эквивалентности, и +множество эллиптических кривых разбивается на классы эквивалентных, причём +каждый класс эллиптических кривых, изоморфных над алгебраическим данного поля, +однозначно определяется величиной $j$-инварианта. + +\begin{theorem}[Об изоморфных эллиптических кривых над полем характеристики 2] + Всякая эллиптическая кривая над полем характеристики 2 изоморфны некоторой + эллиптической кривой одного из следующих видов: + \begin{equation} + y^2 + xy = x^3 + b_2 x^2 + b_6 + \label{eq:char2_1} + \end{equation} + или + \begin{equation} + y^2 + b_3 y = x^3 + b_4 x + b_6 + \label{eq:char2_2} + \end{equation} +\end{theorem} +\begin{proof} + Пусть $F$ --- поле характеристики 2, $E$ --- эллиптическая кривая, заданная + уравнением (\ref{eq:weierstrass}). + + Если $a_1 \neq 0$, то произведём в (\ref{eq:weierstrass}) замену переменных + \begin{equation*} + (x, y) \mapsto (a_1^2 x + a_1^{-1} a_3, a_1^3 y), + \end{equation*} + получим + \begin{align*} %% TODO: сделать красиво + &(a_1^3 y)^2 + a_1 (a_1^2 x + a_1^{-1} a_3) a_1^3 y + a_3 a_1^3 y = \\ + &= (a_1^2 x + a_1^{-1} a_3)^3 + a_2 (a_1^2 x + a_1^{-1} a_3)^2 + a_4 (a_1^2 x + + a_1^{-1} a_3) + a_6, \\ + &a_1^6 y^2 + a_1^6 xy + a_1^3 a_3 y + a_1^3 a_3 y = \\ + &= (a_1^4 x^2 + 2 a_1^2 x a_1^{-1} a_3 + a_1^{-2} a_3^2)(a_1^2 x + a_1^{-1} + a_3 + a_2) + a_1^2 a_4 x + a_1^{-1} a_4 a_3 + a_6,\\ + &a_1^6 y^2 + a_1^6 xy = \\ + &= a_1^6 x^3 + a_1^3 a_3 x^2 + a_1^4 a_2 x^2 + a_3^2 x + + a_1^{-3} a_3^3 + a_1^{-2} a_2 a_3^2 + a_1^2 a_4 x + a_1^{-1} a_4 a_3 + a_6,\\ + &a_1^6 y^2 + a_1^6 xy =\\ + &= a_1^6 x^3 + (a_1^3 a_3 + a_1^4 a_2) x^2 + (a_3^2 + a_1^2 a_4) x + + a_1^{-3} a_3^3 + a_1^{-2} a_2 a_3^2 + a_1^{-1} a_4 a_3 + a_6. + \end{align*} + + Получим, что данная замена переводит $E$ в кривую + \begin{equation} + y^2 + xy = x^3 + \widetilde{a}_2 x^2 + \widetilde{a}_4 x + \widetilde{a}_6 + \label{eq:char2_tmp1} + \end{equation} + + Произведём в (\ref{eq:char2_tmp1}) замену переменных $(x, y) \mapsto (x, y + + \widetilde{a}_4)$: + \begin{align*} + y^2 + \widetilde{a}_4^2 + xy &= x^3 + \widetilde{a}_2 x^2 + \widetilde{a}_6, \\ + y^2 + xy &= x^3 + \widetilde{a}_2 x^2 + (\widetilde{a}_6 - \widetilde{a}_4^2). + \end{align*} + + Получим, что данная замена переводит кривую (\ref{eq:char2_tmp1}) в кривую + (\ref{eq:char2_1}). + + Если $a_1 = 0$, то замена переменных $(x, y) \mapsto (x + a_2, y)$ переводит + $E$ в кривую вида (\ref{eq:char2_2}). +\end{proof} + +%% TODO: 23 +\begin{theorem}[Об изоморфных эллиптических кривых над полем характеристики $\neq 2$] + Всякая эллиптическая кривая над полем характеристики $\neq 2$ изоморфна + некоторой эллиптической кривой вида + \begin{equation} + y_2 = x^3 + b_2 x^2 + b_4 x + b_6. + \label{eq:isom_neq2} + \end{equation} +\end{theorem} +\begin{proof} + Пусть $F$ --- поле характеристики $\neq 2$, $E$ --- эллиптическая кривая, + заданная уравнением (\ref{eq:weierstrass}). + + Сделаем замену переменных + \begin{equation*} + (x, y) \mapsto (x, y - \frac{a_1}{2} x - \frac{a_3}{2}), + \end{equation*} + получим + %% TODO: дописать eq1 + + Таким образом, получили, что данная замена переводит кривую $E$ в кривую + (\ref{eq:isom_neq2}). +\end{proof} diff --git a/crypto-algebra/lectures/lecture8.tex b/crypto-algebra/lectures/lecture8.tex new file mode 100644 index 0000000..c7f1d0d --- /dev/null +++ b/crypto-algebra/lectures/lecture8.tex @@ -0,0 +1,191 @@ +% Лекция 8 (16.10.23) + +%% NOTE: 24? +\begin{theorem}[Об изоморфных эллиптических кривых над полем характеристики $> 3$] + Всякая эллиптическая кривая над полем характеристики $> 3$ изоморфна + эллиптической кривой вида + \begin{equation*} %% NOTE: 8 + y^2 = x^3 + ax + b + \end{equation*} +\end{theorem} +\begin{proof} + Пусть $F$ --- поле характеристики $> 3$, $E$ --- эллиптическая кривая, + заданная уравнением (2). Согласно теореме 23 данная кривая изоморфна кривой + (7). Тогда сделаем в (7) замену переменных + \begin{equation*} + (x, y) \mapsto (x - \frac{b_2}{3}, y), + \end{equation*} + получим + %% TODO: дописать eq1 + \begin{align*} + y^2 &= \left(x - \frac{b_2}{3}\right)^3 + b_2 \left(x - \frac{b_2}{3}\right)^2 + + b_4 \left(x - \frac{b_2}{3}\right) + b_6, \\ + y^2 &= x^3 - b_2 x^2 + \frac{b_2^2}{3}x - \frac{b_2^3}{27} + b_2 + \left(x^2 - \frac{2b_2}{3}x + \frac{b_2^2}{9}\right) + b_4 x - \frac{b_2 b_4}{3} + b_6, \\ + \dots + \end{align*} + + Таким образом, данная замена переводит кривую (7) в (8). +\end{proof} + +Для эллиптической кривой, заданной уравнением (8), формулы для дискриминанта и +$j$-инварианта принимают вид +\begin{align*} + \Delta &= -16 (4a^3 + 27b^2), \\ + j(E) &= -1728 \frac{64a^3}{\Delta} = 1728 \frac{4a^3}{4a^3 + 27b^2} +\end{align*} + +В уравнении левая сторона ($y^2$) имеет степень 2, в то время как правая сторона +имеет степень 3 ($x^3$). Это означает, что горизонтальная линия может пересекать +кривую в трёх точках, если все корни вещественные. Однако вертикальная линия +может пересечь кривую самое большее в двух точках. + +\begin{example} + На рисунке 14 показаны две эллиптические кривые с уравнениями + \begin{equation*} + y^2 = x^3 - 9x \land y^2 = x^3 - 1 \; (y^2 = (x - 1)(x^2 + x + 1)) + \end{equation*} + %% TODO: рисунок 1 (14) + + Таким образом, обе кривые гладкие. Однако первое имеет три вещественных корня + ($x = \pm 3, x = 0$), второе --- только один вещественные корень ($x = 1$) и + два мнимых ($x = \pm \frac{\sqrt{3} i - 1}{2}$; удовлетворяют уравнению + $x^2 + x + 1 = 0$). +\end{example} + +%% NOTE: 4 +\paragraph{Сложение точек эллиптической кривой.} + +Существует ряд эквивалентных способов для описания группового закона сложения +точек эллиптической кривой. Геометрически этот закон можно сформулировать +следующим образом: \emph{три коллинеарные точки на эллиптической кривой дают +нулевую сумму}. Операция сложения точек на эллиптической кривой, введённая по +данному правилу, превращает эллиптическую кривую в коммутативную группу. + +Далее будут рассмотрены формулы сложения точек эллиптической кривой, которые +вытекают из данного правила. В качестве нулевого элемента выбирается точка +$\mathcal{O}$ на бесконечности. Таким образом, для любой точки $P \in E$ +имеют место равенства +\begin{equation*} + P + \mathcal{O} = \mathcal{O} + P = P. +\end{equation*} + +Секущая, проходящая через бесконечно удалённую точку $\mathcal{O}$ и данную +точку кривой $P$, является вертикальной прямой. + +Пусть $P \ne \mathcal{O}$ --- точка эллиптической кривой $E$ и $l$ --- +вертикальная прямая, проходящая через точку $P = (x_1, y_1)$. Эта прямая +пересекает $E$ ещё в точке $Q$ (с учётом кратности). Таким образом, $-P = Q$. + +Пусть $Q = (x_2, y_2)$. Так как она лежит на вертикальной прямой $l$, то +$x_1 = x_2$. Тогда $y_2$ является решением уравнения +\begin{equation} %% NOTE: 9 + y^2 + f_1(x_1) y - f_3(x_1) = 0, + \label{eq:9} +\end{equation} +где $f_1(x) = a_1 x + a_3$, $f_3(x) = x^3 + a_2 x^2 + a_4 x + a_6$. + +Уравнение (\ref{eq:9}) имеет два корня $y_1$ и $y_2$. По теореме Виета +\begin{equation*} + y_1 + y_2 = -f_1(x_1), +\end{equation*} +откуда получаем +\begin{equation*} + y_2 = -y_1 - f_1(x_1). +\end{equation*} + +Итак, +\begin{equation} + -(x_1, y_1) = (x_1, -y_1 - a_1 x_1 - a_3). + \label{eq:10} +\end{equation} + +Может оказаться, что $y_2 = y_1$ и, соответственно, $-P = P$. Это возможно, если +вертикальная прямая, проходящая через $P$, касается кривой $E$ в точке $P$. + +Рассмотрим, как вычисляется сумма двух различных точек $P_1 = (x_1, y_1)$ и +$P_2 = (x_2, y_2)$ на эллиптической кривой. Предположим, что $P_1, P_2 \neq +\mathcal{O}$ и $P_1 \neq \pm P_2$. Тогда $x_1 \neq x_2$. Пусть $l$ --- прямая, +проходящая через точки $P_1$ и $P_2$. Уравнение $l$ имеет вид +\begin{equation} + y = \alpha x + \beta. + \label{eq:11} +\end{equation} + +Коэффициенты $\alpha$ и $\beta$ --- решения системы. +\begin{equation*} + \begin{cases} + y_1 = \alpha x_1 + \beta, \\ + y_2 = \alpha x_2 + \beta. + \end{cases} +\end{equation*} + +Тогда +\begin{align*} + \alpha &= \frac{y_1 - y_2}{x_1 - x_2}, \\ + \beta &= y_1 - \alpha x_1 = y_2 - \alpha x_2. +\end{align*} + +Прямая $l$ пересекает эллиптическую кривую $E$ в некоторой третьей точке +$Q = -(P_1 + P_2) = (\widetilde{x_3}, \widetilde{y_3})$. + +Подставляя (\ref{eq:11}) в уравнение Вейерштрасса, получаем +\begin{equation*} + (\alpha x + \beta)^2 + (\alpha x + \beta) (a_1 x + a_3) - (x^3 + a_2 x^2 + + a_4 x + a_6) = 0. +\end{equation*} + +Кубическое уравнение +\begin{equation*} + -x^3 + (\alpha^2 + a_1 \alpha - a_2) x^2 + (2 \alpha \beta + a_3 \alpha + a_1 + \beta - a_4) x + (\beta^2 + a_3 \beta - a_6) = 0 +\end{equation*} +имеет три корня: $x_1, x_2, \widetilde{x_3}$. + +По теореме Виета +\begin{equation*} + x_1 + x_2 + \widetilde{x_3} = \alpha^2 + a_1 \alpha - a_2. +\end{equation*} + +Таким образом, +\begin{equation*} + \begin{cases} + \widetilde{x_3} = -x_1 - x_2 + \alpha^2 + a_1 \alpha - a_2, \\ + \widetilde{y_3} = \alpha \widetilde{x_3} + \beta = (y_1 - \alpha x_1) + + \alpha \widetilde{x_3} = y_1 - \alpha(x_1 - \widetilde{x_3}) + \end{cases} +\end{equation*} + +Получаем, $P_1 + P_2 = -Q = -(\widetilde{x_3}, \widetilde{y_3})$, используя +(\ref{eq:10}), находим +\begin{equation*} + P_1 + P_2 = (x_3, y_3), +\end{equation*} +где +\begin{equation} + \begin{cases} + x_3 = -x_1 - x_2 + \alpha^2 + a_1 \alpha - a_2, \\ + y_3 = -y_1 + \alpha (x_1 - x_3) - a_1 x_3 - a_3. + \end{cases} +\end{equation} + +\begin{example} + На рисунке 15 представлен типичный случай сложения точек $P_1$ и $P_2$. Чтобы + найти $P_1 + P_2$, проводим прямую $\overline{P_1 P_2}$ и в качестве $P_1 + P_2$ + берём точку, симметричную относительно оси $x$ третьей точке, определяемой + пересечением прямой $\overline{P_1 P_2}$ и кривой. + + %% TODO: рис 2 (15) +\end{example} + +Найдём правило вычисления удвоенной точки $P + P$. Будем предполагать, что +$P \neq -P$. Чтобы найти $P + P$, проведём касательную через точку $P$. Эта +прямая задаётся уравнением (\ref{eq:11}). + +Для нахождения углового коэффициента касательной $\alpha$ нужно найти полнй +дифференциал от полинома $f(x, y)$, задающего кривую в форме Вейерштрасса +(2). Получим +\begin{equation} %% TODO: другое \delta + df(x, y) = \frac{\partial f}{\partial x} dx + \frac{\partial f}{\partial y} dy. +\end{equation} + diff --git a/crypto-algebra/lectures/lecture9.tex b/crypto-algebra/lectures/lecture9.tex new file mode 100644 index 0000000..1077224 --- /dev/null +++ b/crypto-algebra/lectures/lecture9.tex @@ -0,0 +1,204 @@ +% Лекция 9 (23.10.23) + +Угловой коэффициент касательной равен +\begin{equation*} + \alpha = \frac{dy}{dx} +\end{equation*} + +Имеем $f'_x dx = -f'_y dy,\, \frac{dy}{dx} = -\frac{f'_x}{f'_y}$. + +Поэтому угловой коэффициент касательной равен +\begin{equation} + \alpha = \frac{3 x_1^2 + 2 a_2 x_1 + a_4 - a_1 y_1}{2 y_1 + a_1 x_1 + a_3} + \label{eq:13} +\end{equation} + +Таким образом, удвоенная точка также вычисляется по формулам (\ref{eq:12}), +но с $\alpha$, найденным по (\ref{eq:13}). + +\begin{example} + Рассмотрим эллиптическую кривую $y^2 = x^3 - 12x$. + + Пусть $x_1 = x_2 = 6$, тогда $y_1 = y_2 = 12$. + + \begin{align*} + \alpha &= \frac{3 x_1^2 + 2 a_2 x_1 + a_4 - a_1 y_1}{2 y_1 + a_1 x_1 + a_3} + = \frac{3 \cdot 6^2 - 12}{2 \cdot 12} = 4 \\ + \beta &= y_1 - \alpha x_1 = 12 - 4 \cdot 6 = -12 + \end{align*} + + Таким образом, касательная, проходящая через точку $P_1 = P_2 = (6, 12)$ + имеет вид $y = 4x - 12$. + + В результате $P_1 + P_2 = 2 P_1 = P_3 = (x_3, y_3)$, где + \begin{align*} + x_3 &= -x_1 - x_2 + \alpha^2 + a_1 \alpha - a_2 = -6 - 6 + 4^2 = 4 \\ + y_3 &= -y_1 + \alpha (x_1 - x_3) - a_1 x_3 - a_3 = -12 + 4 (6 - 4) = -4 + \end{align*} + + %% TODO: рис 1 +\end{example} + +%% TODO: рис 2 + +\begin{theorem}[Группа точек эллиптической кривой] + Пусть $F$ --- поле, $E/F$ --- эллиптическая кривая. Тогда для любого + расширения $K$ поля $F$ относительно введённой выше операции <<$+$>> множество + $E(K)$ образует абелеву группу. Операция сложения задаётся по следующим + правилам: + \begin{enumerate} + \item + для любой точки $P \in E$ верно $P + \mathcal{O} = \mathcal{O} + P = P$; + \item + для любой точки $P = (x, y) \neq \mathcal{O}$ точка $-P$ находится по + формуле \[ -P = (x, -y - a_1 x - a_3); \] + \item + для любых точек $P_1 = (x_1, y_1) \neq \mathcal{O}$, $P_2 = (x_2, y_2) + \neq \mathcal{O}$ сумма точек $P_1 + P_2 = P_3 = (x_3, y_3)$ задаётся + следующими формулами: + \begin{enumerate} + \item если $P_2 = -P_1$, то $P_3 = \mathcal{O}$; + \item если $P_2 \neq -P_1$, то + \begin{equation} + \begin{cases} + \alpha = \begin{cases} + \frac{3x_1^2 + 2a_2 x_1 + a_4 - a_1 y_1}{2y_1 + a_1 x_1 + a_3}, + &\text{если } x_1 = x_2, \\ + \frac{y_1 - y_2}{x_1 - x_2}, &\text{если } x_1 \neq x_2, + \end{cases} \\ + x_3 = -x_1 - x_2 + \alpha^2 + a_1 \alpha - a_2, \\ + y_3 = -y_1 + \alpha (x_1 - x_3) - a_1 x_3 - a_3. + \end{cases} + \label{eq:14} + \end{equation} + \end{enumerate} + \end{enumerate} +\end{theorem} + +\begin{corollary}[Об операции сложения в группе точек эллиптической кривой над + полем характеристики $> 3$] + Для кривой, заданной уравнением (\ref{eq:8}), формулы (\ref{eq:14}) принимают + упрощённый вид: + \begin{equation} + \begin{cases} + \alpha = \begin{cases} + \frac{3 x_1^2 + a}{2y_1}, &\text{если } x_1 = x_2, \\ + \frac{y_1 - y_2}{x_1 - x_2}, &\text{если } x_1 \neq x_2, + \end{cases} \\ + x_3 = -x_1 - x_2 + \alpha^2, \\ + y_3 = -y_1 + \alpha (x_1 - x_3). + \end{cases} + \label{eq:15} + \end{equation} + Кроме того, противоположная к $P = (x, y)$ точка равна $-P = (x, -y)$. + + Порядком точки $P$ на эллиптической кривой называется такое наименьшее + натуральное число $N$, что $NP = \mathcal{O}$. +\end{corollary} + +Такого конечного $N$ может не существовать. Часто требуется найти точки +конечного порядка на эллиптической кривой. + +\begin{example} + Найти порядок точки $P = (0, -3)$ на эллиптической кривой $y^2 = x^3 + 9$. + + Применяя (\ref{eq:15}), находим, что $2P = (0, 3)$, получаем $2P = -P$, откуда + $3P - \mathcal{O}$. Итак, $P$ имеет порядок 3. +\end{example} + +\emph{Гиперэллиптической кривой} над полем $F$ называется аффинная кривая, +задаваемая уравнением $y^2 + h(x) y = f(x)$ и не имеющая особых точек +на аффинной плоскости над $\overline{F}$, где $h$, $f$ --- полиномы с +коэффициентами из $F$, $\deg(f) = 2g + 1$, $\deg(h) \leq g$. + +Натуральное число $g$ называется \emph{родом кривой}. Эллиптическую кривую +можно рассматривать как гиперэллиптическую кривую рода 1. + +Алгебраическая формула (\ref{eq:14}) для сложения точек на эллиптической +кривой имеет смысл над любым полем. + +\paragraph{Изогении.} + +Пусть $E_1$ и $E_2$ --- эллиптические кривые. \emph{Изогенией} из $E_1$ в +$E_2$ называется морфизм $\varphi : E_1 \to E_2$, удовлетворяющий условию +$\varphi(\mathcal{O}) = \mathcal{O}$. Две эллиптические кривые $E_1$ и $E_2$ +\emph{изогенны}, если существует изогения из $E_1$ до $E_2$ с $\varphi(E_1) \neq +\set{\mathcal{O}}$. + +Изогения эллиптических кривых является отношением эквивалентности. + +Эллиптические кривые являются абелевыми группами, поэтому отображения между +ними образуют группы. Обозначим множество изогений из $E_1$ в $E_2$ через +\begin{equation*} + \fn{Hom}(E_1, E_2) = \set{\text{изогении } E_1 \to E_2} +\end{equation*} + +Сумма двух изогений определяется формулой +\begin{equation*} + (\varphi + \psi)(P) = \varphi(P) + \psi(P), +\end{equation*} +также $\varphi + \psi$ --- морфизм, поэтому это изогения. + +Следовательно, $\fn{Hom}(E_1, E_2)$ --- группа. Если $E_1 = E_2$, то можно также +составить изогении. Таким образом, если $E$ --- эллиптическая кривая, то +\begin{equation*} + \fn{End}(E) = \fn{Hom}(E, E) +\end{equation*} +является кольцом, закот сложения которого указан выше, а умножение --- это +композиция +\begin{equation*} + (\varphi \psi)(P) \equiv \varphi(\psi(P)). +\end{equation*} + +Также имеет место дистрибутивный закон. Кольцо $\fn{End}(E)$ называется +\emph{кольцом эндоморфизмов} эллиптической кривой $E$. + +Обратимые элементы кольца $\fn{End}(E)$ образуют группу автоморфизмов $E$ +которая обозначается $\fn{Aut}(E)$. + +\begin{example} + Для каждого $m \in \Z$, изогения умножения на $m$ обозначается + \begin{align*} + [m] &: E \to E \\ + [m]P &= \underbrace{P + P + \dots + P}_m + \end{align*} + при $m < 0$ полагают $[m]P = [-m](-P)$ и $[0]P = \mathcal{O}$. + + $[m]$ --- морфизм, а значит, изогения, поскольку он явно переводит + $\mathcal{O}$ в $\mathcal{O}$. + + Пусть $E$ --- эллиптическая кривая, $m \in \Z, m \geq 1$. \emph{Подгруппа} + $m$-кручения $E$, обозначаемая $E[m]$, --- это множество точек $E$ порядка + $m$: + \begin{equation*} + E[m] = \set{P \in E : [m]P = \mathcal{O}}. + \end{equation*} + \emph{Подгруппа кручения $E$}, обозначаемая $E_{tors}$, представляет собой + множество точек конечного порядка: + \begin{equation*} + E_{tors} = \bigcup_{m = 1}^\infty E[m]. + \end{equation*} +\end{example} + +Если $E$ определено над $F$, то $E_{tors}(F)$ обозначает точки конечного порядка +в $E(F)$. Пусть $F$ --- поле характеристики $p > 0$, $q = p^r$ и $E/F$ --- +эллиптическая кривая, заданная уравнением Вейерштрасса (\ref{eq:2}). + +Кривая $E^{(q)}/f$ определяется возведением коэффициентов уравнения для $E$ в +степень $q$, морфизм Фробениуса $\varphi_q$ определяется как +\begin{equation*} + \varphi_q : E \to E^{(q)}, (x, y) \to (x^q, y^q) +\end{equation*} + +$E^{(q)}$ является гладкой эллиптической кривой, $\Delta(E^{(q)}) = \Delta(E)^q$ +и $j(E^{(q)}) = j(E)^q$. + +Так как $F$ --- конечное поле с $q$ элементами, тогда отображение $q$-й степени +на $F$ является тождественным, поэтому $E^{(q)} = E$ и $\varphi_q$ является +эндоморфизмом $E$, называемым \emph{эндоморфизмом Фробениуса}. + +Множество точек, зафиксированных $\varphi_q$, (точки с координатами из поля $F$ +остаются неподвижными) есть в точности конечная группа $E(\mathbb{F}_q)$. + +Этот факт лежит в основе доказательства теоремы Хассе об оценке количества +$\mathbb{F}_q$-рациональных точек эллиптической кривой $E$. |