За подробными сведениями об эллиптических кривых отправляем читателя к [1], [2]. Ниже мы будем рассматривать материал, необходимый для решения типовых расчетных задач.
Предположим, что $$\mathbb{K}$$ - поле: либо поле $$\mathbb{R}$$ вещественных чисел, либо поле $$\mathbb{Q}$$ рациональных чисел, либо поле $$\mathbb{C}$$ комплексных чисел, либо поле $$GF(q)$$ из $$q = {p}^{\gamma }$$ элементов, $$p$$ - простое (см. ниже пример кривой над $$GF(z)=\mathbb{Z}_7$$. Напомним, что характеристикой поля $$\mathbb{K}$$ называется наименьшее такое натуральное число $$p = \fchar \mathbb{K}$$, что $$p \cdot 1 = 0$$, где 1 и 0 - единичный и нулевой элементы $$\mathbb{K}$$ соответственно.
Определение 4.1 Алгебраической кривой порядка $$n$$ над полем $$\mathbb{K}$$ называется множество пар $$(x, y)$$, $$x, y \in \mathbb{K}$$, удовлетворяющих уравнению $$F(x, y) = 0$$, где $$F(x, y)$$ - многочлен степени $$n$$ с коэффициентами из $$\mathbb{K}$$.
Напомним, что степенью одночлена называется сумма степеней входящих в него переменных, а степенью многочлена - максимальная из степеней составляющих его одночленов.
Пример 4.1 Степень одночлена $$5x^{2}y^{3}$$ равна $$5$$, а степень многочлена $$5x^{2}y^{3 }+ 7xy^{5 }+ 3$$ равна $$6$$.
Определение 4.2 Пары $$(x, y)$$ элементов поля $$\mathbb{K}$$, удовлетворяющие уравнению кривой, называются ее точками.
Определение 4.3 Точка $$(x_0,y_0)$$ кривой $$F(x, y) = 0$$ называется неособой, если значения частных производных многочлена $$F$$ в ней не равны нулю одновременно.
Частные производные $$\frac{{\partial}F}{{\partial}x},\frac{{\partial}F}{{\partial}y}$$ определяются известными формальными правилами дифференцирования, применяемыми к многочленам над произвольным полем (линейность дифференцирования и правило Лейбница), из которых следует: если многочлен $$F(x, y)$$ записан по степеням $$x$$:
$$F(x, y) = {a}_{0}(y) + {a}_{1}(y)x + {\dots} + {a}_{n}(y) {x}^{n},$$то
$$\frac{{\partial}F}{{\partial}x}={a}_{1}(y) +2 {a}_{2}(y)x + {\dots} + n {a}_{n}(y) {x}^{n-1},$$и аналогичная формула имеет место для частного дифференцирования по переменной $$y$$.
Определение 4.4 Кривая называется неособой, или гладкой, если все её точки неособые. В любой такой точке $$({x}_{0}, {y}_{0})$$ к ней можно провести касательную, т. е. прямую, определяемую уравнением
$$(x - {x}_{0}) \cdot \frac{{\partial}F}{{\partial}x}( {x}_{0}, {y}_{0}) + (y - {y}_{0}) \cdot \frac{{\partial}F}{{\partial}y}( {x}_{0}, {y}_{0}) = 0.$$Определение 4.5 Гладкая кривая третьего порядка над полем $$\mathbb{K}$$ называется эллиптической кривой над тем же полем, если на ней есть хотя бы одна точка.
Но если даже точек нет, то они могут появиться, если рассмотреть эту кривую над каким-нибудь расширением поля $$\mathbb{K}$$.
Будем также считать принадлежащей эллиптической кривой бесконечно удаленную точку $$\mathcal{O}$$, являющейся точкой перересечения эллиптической кривой и любой вертикальной прямой.
Произвольную эллиптическую кривую над полем $$\mathbb{K}$$ можно преобразовать заменой переменных к виду:
$$y^2 + a_1 xy + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6,\qquad a_i\in \mathbb{K}.$$Если характеристика основного поля не равна 2 или 3, то это уравнение можно преобразовать к виду:
$$y^2 = x^3 + ax + b,\qquad a,b\in \mathbb{K}.$$Теорема 4.1 Кривая $$E$$, заданная уравнением (4.2), является гладкой тогда и только тогда, когда
$$\Delta(E) = \frac{4a^3+27b^2}{108} \neq 0$$Выражение $$\Delta(E)$$ является дискриминантом многочлена $$f(x)=x^3+ax+b$$, и равно нулю тогда и только тогда, когда этот многочлен имеет кратные корни.
Будем временно полагать, что $$\mathbb{K} = \mathbb{R}$$, т. е. что эллиптическая кривая - обычная плоская кривая (с добавлением еще одной, бесконечно удалённой, точки $$\mathcal{O}$$). В графической интерпретации следует себе представлять ее расположенной на оси y в предельном направлении, определяемом все более "крутыми" касательными к кривой.
Она является "третьей точкой пересечения" с кривой для любой вертикальной прямой: такая прямая пересекается с кривой в точках вида $$(x_1,y_1)$$, $$(x_1,-y_1)$$ и в точке $$\mathcal{O}$$.
Определение 4.6 Пусть $$E$$ - эллиптическая кривая над полем вещественных чисел и пусть $$P$$ и $$Q$$ - две точки на $$E$$. Определим точки $$-P$$ и $$P+Q$$ по следующим правилам.
).
Здесь приведен типичный случай сложения точек $$P_1$$ и $$P_2$$. Чтобы найти $$P_3 = P_1 + P_2$$, проводим прямую $$\overline{{P}_{1}{P}_{2}}$$ и в качестве $$P_1+P_2$$ берем точку, симметричную относительно оси $$x$$ третьей точке $$P_3'$$, определяемой пересечением прямой $$\overline{{P}_{1}{P}_{2}}$$ и кривой. Если бы $$P_1$$ совпадала с $$P_2$$, т. е. если бы нам нужно было найти $$2P_1$$, мы использовали бы касательную к кривой в $$P_1$$: тогда точка $$2P_1$$ симметрична третьей точке, в которой эта касательная пересекает кривую.
(рис 4.1) Пример геометрического построения суммы точек эллиптической кривой
(Взята эллиптическая кривая $$y^2=x^3-x$$)
В случае, когда основное поле не снабжено топологией (т.е. на нём не определено понятие предела), понятие касательной приходится заменять на прямую, проходящую через данную точку кривой, и формальные частные произоводные которой в этой точке совпадает с формальными частными производными уравнения кривой.
Обозначим $$({x}_{1},{y}_{1})$$, $$(x_2,y_2)$, $(x_3,y_3)$$ - координаты точек $$P$$, $$Q$$ и $$P + Q$$ соответственно. Мы хотим выразить $${x}_{3}$$ и $${y}_{3}$$ через $${x}_{1}$$, $${y}_{1}$$, $${x}_{2}$$ и $${y}_{2}$$.
Если $$x_1=x_2$$, $$y_1\neq y_2$$, либо $$y_1=y_2=0$$, то $$P_3=\mathcal{O}$$. В остальных случаях получаем:
$$ \begin{array}{l} x_3 = \lambda^2 - x_1 -x_2, \quad y_3 = \lambda(x_1-x_3) - y_1,\\ \lambda = \left\{ \begin{array}{l}\dfrac{y_2-y_1}{x_2-x_1}, \text{~если~}x_1\neq x_2,\\ \dfrac{3x_1^2+a}{2y_1}, \text{~если~}x_1=x_2 \text{~и~} y_1=y_2\neq 0. \end{array} \right. \end{array} $$Пример 4.3 Пусть $$P = (-3, 9)$$ и $$Q = (-2, 8)$$ - точки на эллиптической кривой $$y^2=x^3-36x$$. Найти $$P + Q$$ и $$2P$$.
Решение. Подстановка $$x_1=-3$$, $$y_1=9$$, $$x_2=-2$$, $$y_2=8$$ в (4.1) при $$x_1\neq x_2$$ дает $$x_3=6$$, $$y_3=0$$. Непосредственной подстановкой координат точки $$P+Q=(6,0)$$ в уравнение кривой можно убедиться в том, что она также лежит на ней.
Для нахождения $$2P$$ используем второй вариант формулы (4.4) с $$x_1=x_2$$. Подставляя $$x_1=x_2=-3$$, $$y_1=y_2=9$$, $$a=-36$$, находим $$x_3=25/4$$, $$y_3=-35/8$$. Точка $$2P = (25/4, -35/8)$$ также принадлежит рассматриваемой кривой.
Теорема 4.2 Множество точек эллиптической кривой вместе с бесконечно удаленной точкой $$\mathcal{O}$$ относительно операции, введённой в определении 4.6, образуют коммутативную группу.
Если $$n$$ - целое число, то, как и в любой коммутативной группе, $$nP$$ обозначает сумму $$n$$ точек $$P$$ при $$n>0$$ и сумму $$|n|$$ точек $$-P$$, если $$n\leq 0$$.
Порядком $$n$$ точки $$P$$ на эллиптической кривой называется такое наименьшее натуральное число, что $$nP=\mathcal{O}$$; разумеется, такого конечного $$n$$ может и не существовать, в этом случае мы будем говорить о точке бесконечного порядка. Часто требуется найти точки конечного порядка на эллиптической кривой, в особенности на эллиптических кривых, определенных над полем рациональных чисел $$\mathbb{Q}$$.
Пример 4.4 Найти порядок точки $$P = (2, 3)$$ на $$y^2=x^3+1$$.
Решение. Применяя (4.1), находим, что $$2P = (0, 1)$$, $$4P = 2(2P) = (0, -1)$$. Поэтому $$4P = -2P$$ и, следовательно, $$6P = \mathcal{O}$$. Тем самым порядок $$P$$ может быть равен 2, 3 или 6. Но $$2P = (0,1) \neq \mathcal{O}$$, а если бы $$P$$ имела порядок 3, то было бы $$4P = P$$, что неверно. Итак, $$P$$ имеет порядок 6.
Рассмотрим эллиптические кривые над конечным полем $$GF(q)$$, $$q=p^r$$, где $$p$$ - простое число. В зависимости от характетистики поля уравнение кривой можно привести к одному из видов:
$$y^2+cy=x^3+ax+b\text{~или~}y^2+xy=x^3+ax^2+b\qquad \text{при}\ \ p=2,$$ $$y^2=x^3+ax^2+bx+c\qquad \text{при}\ p=3,$$или к виду (4.2) при $$p>3$$.
Особый интерес для криптографии представляет объект, называемый эллиптический группой по модулю $$p$$, где $$p$$ является простым числом.
Далее мы, говоря об эллиптической кривой, если не оговорено противное, будем иметь в виду именно группу точек кривой над полем $$GF(p)$$ простого порядка $$p$$, заданной уравнением (4.2), причем $$4a^3 + 27b^2 \neq 0 ~(\mod p)$$. Эту группу мы будем обозначать $$E_p(a,b)$$.
Пример 4.5 Пусть $$p = 23$$. Рассмотрим эллиптическую кривую $$y^2=x^3+x+1$$.
В этом случае $$a= b= 1$$ и мы имеем $$4 \cdot {1}^{3} + 27 \cdot {1}^{2} ~(\mod 23) \neq 0$$, что удовлетворяет условиям эллиптической группы по модулю 23.
Нас интересуют только целые значения от $$(0, 0)$$ до $$(p, p)$$ в квадранте неотрицательных чисел, удовлетворяющих уравнению по модулю $$p$$. В нашем случае список точек можно создать по следующим правилам.
| $$y$$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |
| $$f(y)$$ | 0 | 1 | 4 | 9 | 16 | 2 | 13 | 3 | 18 | 12 | 8 | 6 | 6 | 8 | 12 | 18 | 3 | 13 | 2 | 16 | 9 | 4 | 1 |
| $$x$$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |
| $$f(x)$$ | 1 | 3 | 11 | 8 | 0 | 16 | 16 | 6 | 15 | 3 | 22 | 9 | 16 | 3 | 22 | 10 | 19 | 9 | 9 | 2 | 17 | 14 | 22 |
Теперь сравниваем числа в нижних строках табл. 4.1 и табл. 4.2. Число, попавшее в обе строки, определяет две точки кривой. Так, число 1 содержится и в нижней строке табл. 4.1, и в нижней строке табл. 4.2. Число 1 определяет точки $$(0,1)$$ и $$(0,22)$$; число 8 дает тоже две точки, находим по верхним строкам их координаты: это $$(3, 10)$$ и $$(3, 13)$$, и т. д. Таким образом, выбираем точки (отличные от $$\mathcal{O}$$), являющиеся элементами $$E_{23}(1,1)$$. Получаем табл. 4.3. Пара чисел $$(x, y)$$, для которой $$y^2\equiv x^3+ax+b ~(\mod p)$$, включается в таблицу соответствий: это точка кривой.
| $$(0, 1)$$ | $$(6, 4)$$ | $$(12, 19)$$ |
| $$(0, 22)$$ | $$(6, 19)$$ | $$(13, 7)$$ |
| $$(1, 7)$$ | $$(7, 11)$$ | $$(13, 16)$$ |
| $$(1, 16)$$ | $$(7, 12)$$ | $$(17, 3)$$ |
| $$(3, 10)$$ | $$(9, 7)$$ | $$(17,20)$$ |
| $$(3, 13)$$ | $$(9, 16)$$ | $$(18,3)$$ |
| $$(4, 0)$$ | $$(11, 3)$$ | $$(18,20)$$ |
| $$(5, 4)$$ | $$(11, 20)$$ | $$(19,5)$$ |
| $$(5, 19)$$ | $$(12, 4)$$ | $$(19,18)$$$ |
В криптографии применяются кривые, параметры которых являются большими (порядка 50 десятичных знаков) числами. В таких случаях перечисление всех точек кривой нереально за приемлемое время. Более того, даже определение количества точек кривой - весьма непростая задача.
Важной является
Теорема 4.1 (теорема Хассе) Пусть $$N$$ - число точек на эллиптической кривой, определенной над $$\mathbb{F}_{q}$$. Тогда $$|N-(q+1)|\leq 2 \sqrt{q}$$.
Для нахождения случайной точки эллиптической кривой $${y}^{2}={x}^{3}+{ax}+b$$ над полем простого порядка $$p$$ можно использовать следующий алгоритм:
Пример 4.6 Найти случайную точку эллиптической кривой $${E}_{29}\left(1,12\right)$$.
Решение. Пусть выбрано случайное число $$x = 7$$. Находим: $$f={7}^{3}+7+12=14\mod29.$$ Вычисляем символ Лежандра-Якоби:
$$\left(\frac{14}{29}\right)=\left(\frac{2}{29}\right) \cdot \left(\frac{7}{29}\right)={\left(-1\right)}^{\frac{{29}^{2}-1}{8}}{\left(-1\right)}^{\frac{\left(7-1\right)\left(29-1\right)}{4}}\left(\frac{29}{7}\right)=-\left(\frac{1}{7}\right)=-1.$$Следовательно, $$f$$ не является квадратичным вычетом по модулю $$p$$; выбираем другой $$x$$.
Пусть выбрано случайное число $$x = 4$$. Находим $$f={4}^{3}+4+12=22~(\mod 29).$$ Вычисляем символ Лежандра-Якоби:
$$\left(\frac{22}{29}\right)=\left(\frac{2}{29}\right) \cdot \left(\frac{11}{29}\right)={\left(-1\right)}^{\frac{{29}^{2}-1}{8}}{\left(-1\right)}^{\frac{\left(11-1\right)\left(29-1\right)}{4}}\left(\frac{29}{11}\right)=-\left(\frac{7}{11}\right)=-{\left(-1\right)}^{\frac{\left(7-1\right)\left(11-1\right)}{4}}\left(\frac{11}{7}\right)=\left(\frac{4}{7}\right)=1.$$Итак, $$f$$ - квадратичный вычет. Найдём корень из $$f$$ по модулю $$p$$.
Имеем: $$29=4 \cdot 7+1$$. В алгоритме Тонелли-Шенкса получаем $$s = 2$, $q = 7$$. Мы уже знаем, что $$z = 14$$ является квадратичным невычетом; вычислим $$c={z}^{q}=12$$. Вычисляем $${R}_{0}={f}^{\frac{q+1}{2}}={22}^{4}=23\mod29.$$ При проверке видим, что $${R}_{0}^{2}=7\mod29=-22~(\mod 29).$$ Поэтому корнем из 22 будет число $${R}_{0} \cdot c$$. В самом деле, $${\left({R}_{0} \cdot c\right)}^{2}=-22 \cdot {c}^{2}=-22 \cdot {z}^{14}=-22 \cdot \left(\frac{z}{29}\right)~(\mod 29)=22$$.
Итак, найдена точка $$(4, 22)$$ эллиптической кривой.
Проиллюстрируем примерами сложение точек кривой, построенной над конечным полем.
Пример 4.7 Выбрана кривая $$E_{751}(-1,1)$$, т. е. $$y^2=x^3-x+1~(\mod 751)$$. Найдем точку $$3G=3\cdot(0, 1)$$.
Для нахождения $$3G$$ используем правила сложения точек эллиптической кривой (4.2).
Вычисляем $$2G$$:
$$\lambda = \frac{3(0^2)-1}{2\cdot1}=\frac{-1}{2}\equiv \frac{-1+751}{2}~(\mod 751) = 375,$$ $$x_3=375^2-0-0=140625\equiv188 ~(\mod 751),$$ $$y_3=375(0-188)-1=-70501\equiv93 ~(\mod 23).$$Итак, мы нашли $$2G= (188,93)$$. Теперь находим $$3G$$:
$$\lambda=\frac{188-0}{93-1}=\frac{188}{92}\equiv 368 ~(\mod 751),$$ $$x_3=368^2-0-188=135236\equiv56 ~(\mod 751),$$ $$y_3=368(0-56)-1=20607\equiv 419 ~(\mod 751).$$Таким образом, мы нашли точку $$3G=3\cdot(0,1)=(56,419)$$.
Данный алгоритм аналогичен алгоритму возведения в степень по модулю, см. параграф 1.2.2.
Рассмотрим алгоритм вычисления точки $$kP$$. Представим число $$k$$ в двоичном виде:
$$k = {k}_{0} + {k}_{1} \cdot 2 + {k}_{2} \cdot {2}^{2} + {\dots} + {k}_{r} \cdot {2}^{r},\ {k}_{i} \in 0,1.$$Далее, положим $${P}_{0} = P$$, $${P}_{1} = 2 {P}_{0} = 2P$$, $$\dots$, ${P}_{r} = {2P}_{r-1} = {2}^{r}P$$.
Откуда
$${kP}=\sum_{i=0}^r{k_i\cdot {P}_{i}}.$$Таким образом, мы можем вычислить $$kP$$ самое большее за $${2\log }_{2}k$$ шагов, каждый из которых представляет собой сложение точек на кривой.
Пример 4.8 Найти $$100\cdot P$$.
Представляем 100 в виде $$100 = {2}^{6}+{2}^{5}+{2}^{2}.$$ Далее, $${P}_{0}=P,{P}_{1}={2P}_{0}=2P$$, $${P}_{2}={2P}_{1}={2}^{2} \cdot P$$, $${P}_{3}=2 \cdot {P}_{2}={2}^{3} \cdot P$$, $${P}_{4}=2 \cdot {P}_{3}={2}^{4} \cdot P$$, $${P}_{5}=2 \cdot {P}_{4}={2}^{5} \cdot P$$, $${P}_{6}=2{ \cdot P}_{5}={2}^{6} \cdot P$$.
Теперь $$100P = {P}_{6}+{P}_{5}+{P}_{2}$$.
Мы нашли точку $$100P$$, произведя 6 удвоений и 2 сложения точек на кривой.
Пример 4.9 Найти точку $$nP$$, кривая: $${E}_{751}\left(-1,1\right)$$, $$n = 122$$, $$P = (49, 568)$$.
Решение.
$$ \begin{align*} nP = 122 \cdot (49, 568) = 2 \cdot (49, 568) + {2}^{3} \cdot (49, 568) + {2}^{4} \cdot (49, 568) +\\ + {2}^{5} \cdot (49, 568) + {2}^{6} \cdot (49, 568) = (173, 132) + (327, 108) +\\ + (519, 713) + (425, 663) + (377, 456) = (417, 614). \end{align*} $$Пример 4.10 Найти порядок точки $$(3, 1)$$ кривой $${E}_{11}(2,1)$$ порядка $$16$$.
Решение. По теореме Лагранжа, порядок точки является делителем 16, то есть одним из чисел 2, 4, 8, 16. Пользуясь формулами (4.2), будем последовательно удваивать точку, пока не получим нейтральный элемент группы.
$$2 \cdot \left(3,1\right)=\left(9,0\right);\ 4 \cdot (3,1) = 2 \cdot \left(9,0\right)=\mathcal{O}.$$Следовательно, порядок точки $$(3, 1)$$ равен 4.
Пример 4.11 Найти порядок точки $$P=(30, 21)$$ кривой $${E}_{41}\left(3,1\right)$$ порядка $$48$$.
.
(рис 4.2) Дерево делителей числа 48
Совершая обход этого дерева, будем получать кратные точки. Например, чтобы получить $$24\cdot P$$, сначала удвоим точку четыре раза, получив $$16\cdot P$$, затем от $$16\cdot P$$ придём по стрелке к $$24\cdot P = 16\cdot P + 8\cdot P$$.
Заметим, что вариантов построения такого дерева может быть много. Число ребер в дереве с 10 вершинами - всегда 9, а операция удвоения точки всегда быстрее сложения произвольных двух точек. Поэтому оптимальным будет проводить вычисления по дереву на рисунке рис 4.3, содержащему наибольшее число удвоений.
(рис 4.3) Более оптимальное дерево делителей числа 48
$$1 \cdot \left(30,21\right)=\left(30,21\right)$$
$$2 \cdot \left(30,21\right)=(31,23)$$
$$3 \cdot \left(30,21\right)=\left(30,21\right)+\left(31,23\right) = \left(25,30\right)$$
$$6 \cdot \left(30,21\right)=2 \cdot 3 \cdot \left(30,21\right)=2 \cdot \left(25,30\right)=\left(24,30\right)$$
$$12 \cdot \left(30,21\right)=2 \cdot 6 \cdot \left(30,21\right)=2 \cdot \left(24,30\right)=\left(29,0\right)$$
$$24 \cdot \left(30,21\right)=2 \cdot 12 \cdot \left(30,21\right)=2 \cdot \left(29,0\right)=\left({\infty},{\infty}\right)$$
Теперь мы знаем, что порядок точки есть делитель числа 24, поэтому нам осталось пройти только те вершины дерева, в которых записаны делители числа 24. Например, вершину 16 мы рассматривать не будем.
$$4 \cdot \left(30,21\right)=2 \cdot \left(31,23\right)=\left(4,6\right)$$ $$8 \cdot \left(30,21\right)=2 \cdot \left(4,6\right)=\left(28,15\right).$$Итак, 24 - наименьшее число, при умножении точки на которое мы получим нейтральный элемент. Поэтому порядок точки равен 24.
Еще раз отметим, что во многих случаях определение порядка кривой является самостоятельной и весьма не простой задачей.
За подробными сведениями об эллиптических кривых отправляем читателя к [1], [2]. Ниже мы будем рассматривать материал, необходимый для решения типовых расчетных задач.
Предположим, что $$\mathbb{K}$$ - поле: либо поле $$\mathbb{R}$$ вещественных чисел, либо поле $$\mathbb{Q}$$ рациональных чисел, либо поле $$\mathbb{C}$$ комплексных чисел, либо поле $$GF(q)$$ из $$q = {p}^{\gamma }$$ элементов, $$p$$ - простое (см. ниже пример кривой над $$GF(z)=\mathbb{Z}_7$$. Напомним, что характеристикой поля $$\mathbb{K}$$ называется наименьшее такое натуральное число $$p = \fchar \mathbb{K}$$, что $$p \cdot 1 = 0$$, где 1 и 0 - единичный и нулевой элементы $$\mathbb{K}$$ соответственно.
Определение 4.1 Алгебраической кривой порядка $$n$$ над полем $$\mathbb{K}$$ называется множество пар $$(x, y)$$, $$x, y \in \mathbb{K}$$, удовлетворяющих уравнению $$F(x, y) = 0$$, где $$F(x, y)$$ - многочлен степени $$n$$ с коэффициентами из $$\mathbb{K}$$.
Напомним, что степенью одночлена называется сумма степеней входящих в него переменных, а степенью многочлена - максимальная из степеней составляющих его одночленов.
Пример 4.1 Степень одночлена $$5x^{2}y^{3}$$ равна $$5$$, а степень многочлена $$5x^{2}y^{3 }+ 7xy^{5 }+ 3$$ равна $$6$$.
Определение 4.2 Пары $$(x, y)$$ элементов поля $$\mathbb{K}$$, удовлетворяющие уравнению кривой, называются ее точками.
Определение 4.3 Точка $$(x_0,y_0)$$ кривой $$F(x, y) = 0$$ называется неособой, если значения частных производных многочлена $$F$$ в ней не равны нулю одновременно.
Частные производные $$\frac{{\partial}F}{{\partial}x},\frac{{\partial}F}{{\partial}y}$$ определяются известными формальными правилами дифференцирования, применяемыми к многочленам над произвольным полем (линейность дифференцирования и правило Лейбница), из которых следует: если многочлен $$F(x, y)$$ записан по степеням $$x$$:
$$F(x, y) = {a}_{0}(y) + {a}_{1}(y)x + {\dots} + {a}_{n}(y) {x}^{n},$$то
$$\frac{{\partial}F}{{\partial}x}={a}_{1}(y) +2 {a}_{2}(y)x + {\dots} + n {a}_{n}(y) {x}^{n-1},$$и аналогичная формула имеет место для частного дифференцирования по переменной $$y$$.
Определение 4.4 Кривая называется неособой, или гладкой, если все её точки неособые. В любой такой точке $$({x}_{0}, {y}_{0})$$ к ней можно провести касательную, т. е. прямую, определяемую уравнением
$$(x - {x}_{0}) \cdot \frac{{\partial}F}{{\partial}x}( {x}_{0}, {y}_{0}) + (y - {y}_{0}) \cdot \frac{{\partial}F}{{\partial}y}( {x}_{0}, {y}_{0}) = 0.$$Определение 4.5 Гладкая кривая третьего порядка над полем $$\mathbb{K}$$ называется эллиптической кривой над тем же полем, если на ней есть хотя бы одна точка.
Но если даже точек нет, то они могут появиться, если рассмотреть эту кривую над каким-нибудь расширением поля $$\mathbb{K}$$.
Будем также считать принадлежащей эллиптической кривой бесконечно удаленную точку $$\mathcal{O}$$, являющейся точкой перересечения эллиптической кривой и любой вертикальной прямой.
Произвольную эллиптическую кривую над полем $$\mathbb{K}$$ можно преобразовать заменой переменных к виду:
$$y^2 + a_1 xy + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6,\qquad a_i\in \mathbb{K}.$$Если характеристика основного поля не равна 2 или 3, то это уравнение можно преобразовать к виду:
$$y^2 = x^3 + ax + b,\qquad a,b\in \mathbb{K}.$$Теорема 4.1 Кривая $$E$$, заданная уравнением (4.2), является гладкой тогда и только тогда, когда
$$\Delta(E) = \frac{4a^3+27b^2}{108} \neq 0$$Выражение $$\Delta(E)$$ является дискриминантом многочлена $$f(x)=x^3+ax+b$$, и равно нулю тогда и только тогда, когда этот многочлен имеет кратные корни.
Будем временно полагать, что $$\mathbb{K} = \mathbb{R}$$, т. е. что эллиптическая кривая - обычная плоская кривая (с добавлением еще одной, бесконечно удалённой, точки $$\mathcal{O}$$). В графической интерпретации следует себе представлять ее расположенной на оси y в предельном направлении, определяемом все более "крутыми" касательными к кривой.
Она является "третьей точкой пересечения" с кривой для любой вертикальной прямой: такая прямая пересекается с кривой в точках вида $$(x_1,y_1)$$, $$(x_1,-y_1)$$ и в точке $$\mathcal{O}$$.
Определение 4.6 Пусть $$E$$ - эллиптическая кривая над полем вещественных чисел и пусть $$P$$ и $$Q$$ - две точки на $$E$$. Определим точки $$-P$$ и $$P+Q$$ по следующим правилам.
).
Здесь приведен типичный случай сложения точек $$P_1$$ и $$P_2$$. Чтобы найти $$P_3 = P_1 + P_2$$, проводим прямую $$\overline{{P}_{1}{P}_{2}}$$ и в качестве $$P_1+P_2$$ берем точку, симметричную относительно оси $$x$$ третьей точке $$P_3'$$, определяемой пересечением прямой $$\overline{{P}_{1}{P}_{2}}$$ и кривой. Если бы $$P_1$$ совпадала с $$P_2$$, т. е. если бы нам нужно было найти $$2P_1$$, мы использовали бы касательную к кривой в $$P_1$$: тогда точка $$2P_1$$ симметрична третьей точке, в которой эта касательная пересекает кривую.
(рис 4.1) Пример геометрического построения суммы точек эллиптической кривой
(Взята эллиптическая кривая $$y^2=x^3-x$$)
В случае, когда основное поле не снабжено топологией (т.е. на нём не определено понятие предела), понятие касательной приходится заменять на прямую, проходящую через данную точку кривой, и формальные частные произоводные которой в этой точке совпадает с формальными частными производными уравнения кривой.
Обозначим $$({x}_{1},{y}_{1})$$, $$(x_2,y_2)$, $(x_3,y_3)$$ - координаты точек $$P$$, $$Q$$ и $$P + Q$$ соответственно. Мы хотим выразить $${x}_{3}$$ и $${y}_{3}$$ через $${x}_{1}$$, $${y}_{1}$$, $${x}_{2}$$ и $${y}_{2}$$.
Если $$x_1=x_2$$, $$y_1\neq y_2$$, либо $$y_1=y_2=0$$, то $$P_3=\mathcal{O}$$. В остальных случаях получаем:
$$ \begin{array}{l} x_3 = \lambda^2 - x_1 -x_2, \quad y_3 = \lambda(x_1-x_3) - y_1,\\ \lambda = \left\{ \begin{array}{l}\dfrac{y_2-y_1}{x_2-x_1}, \text{~если~}x_1\neq x_2,\\ \dfrac{3x_1^2+a}{2y_1}, \text{~если~}x_1=x_2 \text{~и~} y_1=y_2\neq 0. \end{array} \right. \end{array} $$Пример 4.3 Пусть $$P = (-3, 9)$$ и $$Q = (-2, 8)$$ - точки на эллиптической кривой $$y^2=x^3-36x$$. Найти $$P + Q$$ и $$2P$$.
Решение. Подстановка $$x_1=-3$$, $$y_1=9$$, $$x_2=-2$$, $$y_2=8$$ в (4.1) при $$x_1\neq x_2$$ дает $$x_3=6$$, $$y_3=0$$. Непосредственной подстановкой координат точки $$P+Q=(6,0)$$ в уравнение кривой можно убедиться в том, что она также лежит на ней.
Для нахождения $$2P$$ используем второй вариант формулы (4.4) с $$x_1=x_2$$. Подставляя $$x_1=x_2=-3$$, $$y_1=y_2=9$$, $$a=-36$$, находим $$x_3=25/4$$, $$y_3=-35/8$$. Точка $$2P = (25/4, -35/8)$$ также принадлежит рассматриваемой кривой.
Теорема 4.2 Множество точек эллиптической кривой вместе с бесконечно удаленной точкой $$\mathcal{O}$$ относительно операции, введённой в определении 4.6, образуют коммутативную группу.
Если $$n$$ - целое число, то, как и в любой коммутативной группе, $$nP$$ обозначает сумму $$n$$ точек $$P$$ при $$n>0$$ и сумму $$|n|$$ точек $$-P$$, если $$n\leq 0$$.
Порядком $$n$$ точки $$P$$ на эллиптической кривой называется такое наименьшее натуральное число, что $$nP=\mathcal{O}$$; разумеется, такого конечного $$n$$ может и не существовать, в этом случае мы будем говорить о точке бесконечного порядка. Часто требуется найти точки конечного порядка на эллиптической кривой, в особенности на эллиптических кривых, определенных над полем рациональных чисел $$\mathbb{Q}$$.
Пример 4.4 Найти порядок точки $$P = (2, 3)$$ на $$y^2=x^3+1$$.
Решение. Применяя (4.1), находим, что $$2P = (0, 1)$$, $$4P = 2(2P) = (0, -1)$$. Поэтому $$4P = -2P$$ и, следовательно, $$6P = \mathcal{O}$$. Тем самым порядок $$P$$ может быть равен 2, 3 или 6. Но $$2P = (0,1) \neq \mathcal{O}$$, а если бы $$P$$ имела порядок 3, то было бы $$4P = P$$, что неверно. Итак, $$P$$ имеет порядок 6.
Рассмотрим эллиптические кривые над конечным полем $$GF(q)$$, $$q=p^r$$, где $$p$$ - простое число. В зависимости от характетистики поля уравнение кривой можно привести к одному из видов:
$$y^2+cy=x^3+ax+b\text{~или~}y^2+xy=x^3+ax^2+b\qquad \text{при}\ \ p=2,$$ $$y^2=x^3+ax^2+bx+c\qquad \text{при}\ p=3,$$или к виду (4.2) при $$p>3$$.
Особый интерес для криптографии представляет объект, называемый эллиптический группой по модулю $$p$$, где $$p$$ является простым числом.
Далее мы, говоря об эллиптической кривой, если не оговорено противное, будем иметь в виду именно группу точек кривой над полем $$GF(p)$$ простого порядка $$p$$, заданной уравнением (4.2), причем $$4a^3 + 27b^2 \neq 0 ~(\mod p)$$. Эту группу мы будем обозначать $$E_p(a,b)$$.
Пример 4.5 Пусть $$p = 23$$. Рассмотрим эллиптическую кривую $$y^2=x^3+x+1$$.
В этом случае $$a= b= 1$$ и мы имеем $$4 \cdot {1}^{3} + 27 \cdot {1}^{2} ~(\mod 23) \neq 0$$, что удовлетворяет условиям эллиптической группы по модулю 23.
Нас интересуют только целые значения от $$(0, 0)$$ до $$(p, p)$$ в квадранте неотрицательных чисел, удовлетворяющих уравнению по модулю $$p$$. В нашем случае список точек можно создать по следующим правилам.
| $$y$$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |
| $$f(y)$$ | 0 | 1 | 4 | 9 | 16 | 2 | 13 | 3 | 18 | 12 | 8 | 6 | 6 | 8 | 12 | 18 | 3 | 13 | 2 | 16 | 9 | 4 | 1 |
| $$x$$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |
| $$f(x)$$ | 1 | 3 | 11 | 8 | 0 | 16 | 16 | 6 | 15 | 3 | 22 | 9 | 16 | 3 | 22 | 10 | 19 | 9 | 9 | 2 | 17 | 14 | 22 |
Теперь сравниваем числа в нижних строках табл. 4.1 и табл. 4.2. Число, попавшее в обе строки, определяет две точки кривой. Так, число 1 содержится и в нижней строке табл. 4.1, и в нижней строке табл. 4.2. Число 1 определяет точки $$(0,1)$$ и $$(0,22)$$; число 8 дает тоже две точки, находим по верхним строкам их координаты: это $$(3, 10)$$ и $$(3, 13)$$, и т. д. Таким образом, выбираем точки (отличные от $$\mathcal{O}$$), являющиеся элементами $$E_{23}(1,1)$$. Получаем табл. 4.3. Пара чисел $$(x, y)$$, для которой $$y^2\equiv x^3+ax+b ~(\mod p)$$, включается в таблицу соответствий: это точка кривой.
| $$(0, 1)$$ | $$(6, 4)$$ | $$(12, 19)$$ |
| $$(0, 22)$$ | $$(6, 19)$$ | $$(13, 7)$$ |
| $$(1, 7)$$ | $$(7, 11)$$ | $$(13, 16)$$ |
| $$(1, 16)$$ | $$(7, 12)$$ | $$(17, 3)$$ |
| $$(3, 10)$$ | $$(9, 7)$$ | $$(17,20)$$ |
| $$(3, 13)$$ | $$(9, 16)$$ | $$(18,3)$$ |
| $$(4, 0)$$ | $$(11, 3)$$ | $$(18,20)$$ |
| $$(5, 4)$$ | $$(11, 20)$$ | $$(19,5)$$ |
| $$(5, 19)$$ | $$(12, 4)$$ | $$(19,18)$$$ |
В криптографии применяются кривые, параметры которых являются большими (порядка 50 десятичных знаков) числами. В таких случаях перечисление всех точек кривой нереально за приемлемое время. Более того, даже определение количества точек кривой - весьма непростая задача.
Важной является
Теорема 4.1 (теорема Хассе) Пусть $$N$$ - число точек на эллиптической кривой, определенной над $$\mathbb{F}_{q}$$. Тогда $$|N-(q+1)|\leq 2 \sqrt{q}$$.
Для нахождения случайной точки эллиптической кривой $${y}^{2}={x}^{3}+{ax}+b$$ над полем простого порядка $$p$$ можно использовать следующий алгоритм:
Пример 4.6 Найти случайную точку эллиптической кривой $${E}_{29}\left(1,12\right)$$.
Решение. Пусть выбрано случайное число $$x = 7$$. Находим: $$f={7}^{3}+7+12=14\mod29.$$ Вычисляем символ Лежандра-Якоби:
$$\left(\frac{14}{29}\right)=\left(\frac{2}{29}\right) \cdot \left(\frac{7}{29}\right)={\left(-1\right)}^{\frac{{29}^{2}-1}{8}}{\left(-1\right)}^{\frac{\left(7-1\right)\left(29-1\right)}{4}}\left(\frac{29}{7}\right)=-\left(\frac{1}{7}\right)=-1.$$Следовательно, $$f$$ не является квадратичным вычетом по модулю $$p$$; выбираем другой $$x$$.
Пусть выбрано случайное число $$x = 4$$. Находим $$f={4}^{3}+4+12=22~(\mod 29).$$ Вычисляем символ Лежандра-Якоби:
$$\left(\frac{22}{29}\right)=\left(\frac{2}{29}\right) \cdot \left(\frac{11}{29}\right)={\left(-1\right)}^{\frac{{29}^{2}-1}{8}}{\left(-1\right)}^{\frac{\left(11-1\right)\left(29-1\right)}{4}}\left(\frac{29}{11}\right)=-\left(\frac{7}{11}\right)=-{\left(-1\right)}^{\frac{\left(7-1\right)\left(11-1\right)}{4}}\left(\frac{11}{7}\right)=\left(\frac{4}{7}\right)=1.$$Итак, $$f$$ - квадратичный вычет. Найдём корень из $$f$$ по модулю $$p$$.
Имеем: $$29=4 \cdot 7+1$$. В алгоритме Тонелли-Шенкса получаем $$s = 2$, $q = 7$$. Мы уже знаем, что $$z = 14$$ является квадратичным невычетом; вычислим $$c={z}^{q}=12$$. Вычисляем $${R}_{0}={f}^{\frac{q+1}{2}}={22}^{4}=23\mod29.$$ При проверке видим, что $${R}_{0}^{2}=7\mod29=-22~(\mod 29).$$ Поэтому корнем из 22 будет число $${R}_{0} \cdot c$$. В самом деле, $${\left({R}_{0} \cdot c\right)}^{2}=-22 \cdot {c}^{2}=-22 \cdot {z}^{14}=-22 \cdot \left(\frac{z}{29}\right)~(\mod 29)=22$$.
Итак, найдена точка $$(4, 22)$$ эллиптической кривой.
Проиллюстрируем примерами сложение точек кривой, построенной над конечным полем.
Пример 4.7 Выбрана кривая $$E_{751}(-1,1)$$, т. е. $$y^2=x^3-x+1~(\mod 751)$$. Найдем точку $$3G=3\cdot(0, 1)$$.
Для нахождения $$3G$$ используем правила сложения точек эллиптической кривой (4.2).
Вычисляем $$2G$$:
$$\lambda = \frac{3(0^2)-1}{2\cdot1}=\frac{-1}{2}\equiv \frac{-1+751}{2}~(\mod 751) = 375,$$ $$x_3=375^2-0-0=140625\equiv188 ~(\mod 751),$$ $$y_3=375(0-188)-1=-70501\equiv93 ~(\mod 23).$$Итак, мы нашли $$2G= (188,93)$$. Теперь находим $$3G$$:
$$\lambda=\frac{188-0}{93-1}=\frac{188}{92}\equiv 368 ~(\mod 751),$$ $$x_3=368^2-0-188=135236\equiv56 ~(\mod 751),$$ $$y_3=368(0-56)-1=20607\equiv 419 ~(\mod 751).$$Таким образом, мы нашли точку $$3G=3\cdot(0,1)=(56,419)$$.
Данный алгоритм аналогичен алгоритму возведения в степень по модулю, см. параграф 1.2.2.
Рассмотрим алгоритм вычисления точки $$kP$$. Представим число $$k$$ в двоичном виде:
$$k = {k}_{0} + {k}_{1} \cdot 2 + {k}_{2} \cdot {2}^{2} + {\dots} + {k}_{r} \cdot {2}^{r},\ {k}_{i} \in 0,1.$$Далее, положим $${P}_{0} = P$$, $${P}_{1} = 2 {P}_{0} = 2P$$, $$\dots$, ${P}_{r} = {2P}_{r-1} = {2}^{r}P$$.
Откуда
$${kP}=\sum_{i=0}^r{k_i\cdot {P}_{i}}.$$Таким образом, мы можем вычислить $$kP$$ самое большее за $${2\log }_{2}k$$ шагов, каждый из которых представляет собой сложение точек на кривой.
Пример 4.8 Найти $$100\cdot P$$.
Представляем 100 в виде $$100 = {2}^{6}+{2}^{5}+{2}^{2}.$$ Далее, $${P}_{0}=P,{P}_{1}={2P}_{0}=2P$$, $${P}_{2}={2P}_{1}={2}^{2} \cdot P$$, $${P}_{3}=2 \cdot {P}_{2}={2}^{3} \cdot P$$, $${P}_{4}=2 \cdot {P}_{3}={2}^{4} \cdot P$$, $${P}_{5}=2 \cdot {P}_{4}={2}^{5} \cdot P$$, $${P}_{6}=2{ \cdot P}_{5}={2}^{6} \cdot P$$.
Теперь $$100P = {P}_{6}+{P}_{5}+{P}_{2}$$.
Мы нашли точку $$100P$$, произведя 6 удвоений и 2 сложения точек на кривой.
Пример 4.9 Найти точку $$nP$$, кривая: $${E}_{751}\left(-1,1\right)$$, $$n = 122$$, $$P = (49, 568)$$.
Решение.
$$ \begin{align*} nP = 122 \cdot (49, 568) = 2 \cdot (49, 568) + {2}^{3} \cdot (49, 568) + {2}^{4} \cdot (49, 568) +\\ + {2}^{5} \cdot (49, 568) + {2}^{6} \cdot (49, 568) = (173, 132) + (327, 108) +\\ + (519, 713) + (425, 663) + (377, 456) = (417, 614). \end{align*} $$Пример 4.10 Найти порядок точки $$(3, 1)$$ кривой $${E}_{11}(2,1)$$ порядка $$16$$.
Решение. По теореме Лагранжа, порядок точки является делителем 16, то есть одним из чисел 2, 4, 8, 16. Пользуясь формулами (4.2), будем последовательно удваивать точку, пока не получим нейтральный элемент группы.
$$2 \cdot \left(3,1\right)=\left(9,0\right);\ 4 \cdot (3,1) = 2 \cdot \left(9,0\right)=\mathcal{O}.$$Следовательно, порядок точки $$(3, 1)$$ равен 4.
Пример 4.11 Найти порядок точки $$P=(30, 21)$$ кривой $${E}_{41}\left(3,1\right)$$ порядка $$48$$.
.
(рис 4.2) Дерево делителей числа 48
Совершая обход этого дерева, будем получать кратные точки. Например, чтобы получить $$24\cdot P$$, сначала удвоим точку четыре раза, получив $$16\cdot P$$, затем от $$16\cdot P$$ придём по стрелке к $$24\cdot P = 16\cdot P + 8\cdot P$$.
Заметим, что вариантов построения такого дерева может быть много. Число ребер в дереве с 10 вершинами - всегда 9, а операция удвоения точки всегда быстрее сложения произвольных двух точек. Поэтому оптимальным будет проводить вычисления по дереву на рисунке рис 4.3, содержащему наибольшее число удвоений.
(рис 4.3) Более оптимальное дерево делителей числа 48
$$1 \cdot \left(30,21\right)=\left(30,21\right)$$
$$2 \cdot \left(30,21\right)=(31,23)$$
$$3 \cdot \left(30,21\right)=\left(30,21\right)+\left(31,23\right) = \left(25,30\right)$$
$$6 \cdot \left(30,21\right)=2 \cdot 3 \cdot \left(30,21\right)=2 \cdot \left(25,30\right)=\left(24,30\right)$$
$$12 \cdot \left(30,21\right)=2 \cdot 6 \cdot \left(30,21\right)=2 \cdot \left(24,30\right)=\left(29,0\right)$$
$$24 \cdot \left(30,21\right)=2 \cdot 12 \cdot \left(30,21\right)=2 \cdot \left(29,0\right)=\left({\infty},{\infty}\right)$$
Теперь мы знаем, что порядок точки есть делитель числа 24, поэтому нам осталось пройти только те вершины дерева, в которых записаны делители числа 24. Например, вершину 16 мы рассматривать не будем.
$$4 \cdot \left(30,21\right)=2 \cdot \left(31,23\right)=\left(4,6\right)$$ $$8 \cdot \left(30,21\right)=2 \cdot \left(4,6\right)=\left(28,15\right).$$Итак, 24 - наименьшее число, при умножении точки на которое мы получим нейтральный элемент. Поэтому порядок точки равен 24.
Еще раз отметим, что во многих случаях определение порядка кривой является самостоятельной и весьма не простой задачей.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.