Кривые Эдвардса

Кривые Эдвардса — семейство эллиптических кривых, изученных профессором математик Гарольдом Эдвардсом в 2007 году^[1]. Концепция эллиптических кривых над конечными полями широко используется в эллиптической криптографии. Первыми, кто исследовал преимущества эллиптической кривой в форме Эдвардса перед эллиптической кривой в форме Вейерштрасса, были Даниэль Бернстайн и Тани Ланге: они доработали оригинальную кривую Эдвардса, введя новый параметр кривой, и получили закон сложения точек для модифицированной кривой.^[2]

Определение

Оригинальной кривой Эдвардса над полем K, не имеющим характеристики 2, называется уравнение вида

$x^{2}+y^{2}=c^{2}(1+x^{2}y^{2})$

для некоторого скаляра $c\in K\setminus \{0,1\}$ . Однако над конечным полем существует лишь несколько кривых, которые могут быть выражены в такой форме.

Поэтому Даниэлем Бернстайнем и Тани Ланге была предложена модификация кривой Эдвардса с ведением параметра d, не являющимся квадратичным вычетов в поле $K$ :^[2]

$x^{2}+y^{2}=c^{2}(1+dx^{2}y^{2})$ , $d(1-dc^{4})\neq 0$ , $\left({\frac {d}{p}}\right)=-1$ , где $\left({\frac {d}{p}}\right)$ — символ Лежандра, $c,d\in K$ , $p\neq 2$ — характеристика поля,

Эта модификация и называется эллиптической кривой в форме Эдвардса, или проще кривой Эдвардса.

Кривая Эдвардса изоморфна (бирационально эквивалентна) эллиптической кривой в форме Монтгомери и, следовательно, допускает наличие алгебраической группы при выборе нейтрального элемента. Если поле K конечно, то значительная часть эллиптических кривых над эти полем может быть записана в форме Эдвардса.

Подстановкой ${\frac {x}{c}}\rightarrow x,{\frac {y}{c}}\rightarrow y$ в исходное уравнение кривой Эдвардса можно получить изоморфную кривую в форме Эдвардса вида:

$x^{2}+y^{2}=1+d'x^{2}y^{2},d'=dc^{4}$

Выбор параметра с = 1 не умаляет общности, поэтому далее при рассмотрении кривых Эдвардса параметр с предполагается равным единице.

Групповой закон

(См. также групповой закон эллиптической кривой в форме Вейерштрасса)

Любая кривая Эдвардса вида $x^{2}+y^{2}=1+dx^{2}y^{2},d\neq 1$ над полем K с характеристикой $p\neq 2$ изоморфна эллиптической кривой в форме Монтгомери над тем же полем:

$(1/e)v^{2}=u^{3}+(4/e-2)u^{2}+u$ , где $e=1-d,u={\frac {1+y}{1-y}},v={\frac {2(1+y)}{x(1-y)}}$ и точка $P=(0,1)$ является нейтральным элементом. Такая изоморфная замена позволяет породить группу на любой кривой Эдвардса.

Закон сложения для кривых Эдвардса

Для любой эллиптической кривой сумма двух точек представляется рациональным выражением от координат этих точек, хотя в общем случае могут понадобиться несколько дополнительных формул для покрытия всех частных случаев. Для кривых Эдвардса, беря в качестве нейтрального элемента точку (0, 1), сумма точек $(x_{1},y_{1})$ и $(x_{2},y_{2})$ представляется формулой:

(x_{1},y_{1})+(x_{2},y_{2})=\left({\frac {x_{1}y_{2}+x_{2}y_{1}}{1+dx_{1}x_{2}y_{1}y_{2}}},{\frac {y_{1}y_{2}-x_{1}x_{2}}{1-dx_{1}x_{2}y_{1}y_{2}}}\right)\,

Вывод формулы для сложения двух точек

Утверждение

Пусть $P=(x,y)$ и $Q=(u,v)$ -- точки кривой Эдвардса и выполняются равенства $x^{2}+y^{2}=c^{2}(1+dx^{2}y^{)},u^{2}+v^{2}=c^{2}(1+du^{2}v^{2})$ . Пусть $X={\frac {xv+yu}{c(1+dxyuv)}},Y={\frac {yv-xu}{c(1-dxyuv)}}$ . Тогда $X^{2}+Y^{2}=c^{2}(1+dX^{2}Y^{2})$ .

Доказательство

Не умаляя общности примем $c=1$ (иначе замена переменных ${\frac {x}{c}}\rightarrow x,{\frac {y}{c}}\rightarrow y$ )

Рассмотрим полином $T=(xv+yu)^{2}(1-dxuyv)^{2}+(yv-xu)^{2}(1+dxuyv)^{2}-d(xv+yu)^{2}(yv-xu)^{2}$ , который после раскрытия скобок и приведений соответствующих слагаемых принимает следующий вид: $T=(x^{2}+y^{2}-(u^{2}+v^{2})dx^{2}y^{2})(u^{2}+v^{2}-(x^{2}+y^{2})du^{2}v^{2})$ . Из определения точек кривой в общем случае имеем:

$x^{2}+y^{2}=c^{2}(1+dx^{2}y^{)},u^{2}+v^{2}=c^{2}(1+du^{2}v^{2})$ .

Умножая второе равенство на $-dx^{2}y^{2}$ и вычитая результат из первого, получаем: $x^{2}+y^{2}-(u^{2}+v^{2})dx^{2}y^{2}=1-d^{2}x^{2}y^{2}u^{2}v^{2}$ Аналогично, $u^{2}+v^{2}-(x^{2}+y^{2})du^{2}v^{2}=1-d^{2}x^{2}y^{2}u^{2}v^{2}$ Отсюда получаем $T=(1-d^{2}x^{2}y^{2}u^{2}v^{2})^{2}$

Согласно условию точка $(X,Y)$ выражается через $x,y,u,v$ . Это позволяет нам получить следующее равенство: ${\begin{aligned}X^{2}+Y^{2}-dX^{2}Y^{2}&={\frac {(xv+yu)^{2}}{(1+dxyuv)^{2}}}+{\frac {(yv-xu)^{2}}{(1-dxyuv)^{2}}}-{\frac {d(xv+yu)^{2}(yv-xu)^{2}}{(1+dxyuv)^{2}(1-dxyuv)^{2}}}\\&={\frac {T}{(1+dxyuv)^{2}(1-dxyuv)^{2}}}\\&={\frac {T}{1-d^{2}x^{2}y^{2}u^{2}v^{2}}}=1\end{aligned}}$ .

Следовательно выполняется $X^{2}+Y^{2}=1+dX^{2}Y^{2}$

^[3]

Обратная точка определяется как $-(x,y)=(-x,y)$ . Любая Кривая Эдвардса имеет единственную точку 2-го порядка $(0,-1)$ и ровно 2 точки 4-го порядка $(\pm 1,0)$ с координатами в поле K.

Если d не является квадратичным вычетом в K и $\{(x_{1},y_{1}),(x_{2},y_{2})\}\in \{(x,y)|x^{2}+y^{2}=1+dx^{2}y^{2}\}$ , тогда кривая не имеет особых точек: в знаменателе $1+dx_{1}x_{2}y_{1}y_{2}\neq 0$ и $1-dx_{1}x_{2}y_{1}y_{2}\neq 0$ . Это свойство принято называть полнотой закона сложения для кривых Эдвардса. Оно выполняется, когда d не является квадратичным вычетом в поле K. Другими словами, выражения для суммы двух точек справедливы для любых пар точек кривой Эдвардса над полем K.^[2]

Доказательство свойства полноты

Утверждение

Для любых пар точек кривой Эдвардса знаменатели закона сложения не обращаются в нуль: $dx_{1}y_{1}x_{2}y_{1}\neq \pm 1$

Доказательство

Пусть точки $(x_{1},y_{1}),(x_{2},y_{2})$ принадлежат одной кривой $x^{2}+y^{2}=1+dx^{2}y^{2}$ и пусть $\theta =dx_{1}y_{1}x_{2}y_{2}$ .

От противного: пусть $\theta \in \{-1,1\}$ (Возьмем равной 1). Тогда $x_{1}y_{1}={\frac {1}{dx_{2}y_{2}}}$ и $x_{1}^{2}+y_{1}^{2}=1+{\frac {1}{dx_{2}^{2}y_{2}^{2}}}={\frac {x_{2}^{2}+y_{2}^{2}}{dx_{2}^{2}y_{2}^{2}}}$ .

${\begin{aligned}(x_{1}+y_{1})^{2}=x_{1}^{2}+y_{1}^{2}+2x_{1}y_{1}&={\frac {x_{2}^{2}+y_{2}^{2}}{dx_{2}^{2}y_{2}^{2}}}+{\frac {2}{dx_{2}y_{2}}}\\&={\frac {x_{2}^{2}+y_{2}^{2}+2x_{2}y_{2}}{dx_{2}^{2}y_{2}^{2}}}\\&={\frac {(x_{2}+y_{2})^{2}}{dx_{2}^{2}y_{2}^{2}}}\end{aligned}}$ .

Аналогично, $(x_{1}-y_{1})^{2}=x_{1}^{2}+y_{1}^{2}-2x_{1}y_{1}={\frac {x_{2}^{2}+y_{2}^{2}-2x_{2}y_{2}}{dx_{2}^{2}y_{2}^{2}}}={\frac {(x_{2}-y_{2})^{2}}{dx_{2}^{2}y_{2}^{2}}}$ .

Так как $d$ не является квадратичным вычетом, то оба равенства выполняются лишь тогда, когда одновременно $x_{1}+y_{1}=0$ и $x_{1}-y_{1}=0$ . Следовательно, $x_{1}=y_{1}$ , но кривая Эдвардса не содержит такой точки. Противоречие.

Аналогичным образом и для случая, когда $\theta =-1$ :

$(x_{1}+y_{1})^{2}=x_{1}^{2}+y_{1}^{2}+2x_{1}y_{1}={\frac {x_{2}^{2}+y_{2}^{2}-2x_{2}y_{2}}{dx_{2}^{2}y_{2}^{2}}}={\frac {(x_{2}-y_{2})^{2}}{dx_{2}^{2}y_{2}^{2}}}$ .

$(x_{1}-y_{1})^{2}=x_{1}^{2}+y_{1}^{2}-2x_{1}y_{1}={\frac {x_{2}^{2}+y_{2}^{2}+2x_{2}y_{2}}{dx_{2}^{2}y_{2}^{2}}}={\frac {(x_{2}+y_{2})^{2}}{dx_{2}^{2}y_{2}^{2}}}$ .

Вывод аналогичен.

^[4]

Если d является квадратичным вычетом в K, то существуют особые точки, то есть может быть пара точек $(x_{1},y_{1}),(x_{2},y_{2})\in \{(x,y)|x^{2}+y^{2}=1+dx^{2}y^{2}\}$ для которых один из знаменателей обращается в ноль: $1+dx_{1}x_{2}y_{1}y_{2}=0$ или $1-dx_{1}x_{2}y_{1}y_{2}=0$ .

Пример закона сложения

Рассмотрим эллиптическую кривую в форме Эдвардса с параметром d = 2

{\displaystyle }x^{2}+y^{2}=1+2x^{2}y^{2}

и точкой $P_{1}=(1,0)$ на ней.

Покажем, что сумма $P_{1}$ и нейтрального элемента $(0,1)$ дает снова $P_{1}$ . Действительно, используя выражения для закона сложения, получаем координаты точки суммы:

x_{3}={\frac {x_{1}y_{2}+y_{1}x_{2}}{1+2x_{1}x_{2}y_{1}y_{2}}}=1

y_{3}={\frac {y_{1}y_{2}-x_{1}x_{2}}{1-2x_{1}x_{2}y_{1}y_{2}}}=0

Геометрическая интерпретация

Для лучшего понимания можно рассмотреть геометрическую интерпретацию закона сложения:

Возьмем окружность радиуса 1:

{\displaystyle }x^{2}+y^{2}=1

и рассмотрим точки $P_{1}=(x_{1},y_{1}),P_{2}=(x_{2},y_{2})$ . Пусть $\alpha _{1}$ и $\alpha _{2}$ углы такие, что:

{\displaystyle }P_{1}=(x_{1},y_{1})=(\sin {\alpha _{1}},\cos {\alpha _{1}})

{\displaystyle }P_{2}=(x_{2},y_{2})=(\sin {\alpha _{2}},\cos {\alpha _{2}})

Сумма $P_{1}$ и $P_{2}$ будет «суммой их углов». То есть точка $P_{3}=P_{1}+P_{2}$ это точка $(x_{3},y_{3})$ на круге такая, что:

{\displaystyle }x_{3}=\sin({\alpha }_{1}+{\alpha }_{2})=\sin {\alpha }_{1}\cos {\alpha }_{2}+\sin {\alpha }_{2}\cos {\alpha }_{1}=x_{1}y_{2}+x_{2}y_{1}

{\displaystyle }y_{3}=\cos({\alpha }_{1}+{\alpha }_{2})=\cos {\alpha }_{1}\cos {\alpha }_{2}-\sin {\alpha }_{1}\sin {\alpha }_{2}=y_{1}y_{2}-x_{1}x_{2}.

Таким образом, формула сложения для точек на окружности радиуса 1:

{\displaystyle }(x_{1},y_{1})+(x_{2},y_{2})=(x_{1}y_{2}+x_{2}y_{1},y_{1}y_{2}-x_{1}x_{2})

.

Закон сложения на кривых Эдвардса

Точки на эллиптической кривой образуют абелеву группу: их можно складывать и умножать на целое число. Если эллиптическая кривая описывается несингулярным кубическим уравнением, то сумма двух точек $P$ и $Q$ , обозначаемая $P+Q$ , тесно связана с третьей точкой, являющейся точкой пересечения эллиптической кривой и прямой, проходящей через $P$ и $Q$ .

Изоморфное отображение между кривой Эдвардса и соответствующей эллиптической кривой отображает прямые линии в конические сечения^[5] $Axy+Bx+Cy+D=0$ . Другими словами, для кривой Эдвардса три точки $P$ , $Q$ и $-(P+Q)$ лежат на гиперболе.

Для двух различных точек $P_{1}=(x_{1},y_{1}),P_{2}=(x_{2},y_{2}),P_{1}\neq P_{2}$ , коэффициенты квадратичной формы:

$A=(x_{1}-x_{2})+(x_{1}y_{2}-x_{2}y_{1})$ ,

$B=(x_{2}y_{2}-x_{1}y_{1})+y_{1}y_{2}(x_{2}-x_{1})$ ,

$C=x_{1}x_{2}(y_{1}-y_{2}),$

$D=C$

В случае удвоения точки $P=(x,y)$ обратный элемент $-2P$ лежит на конусе, который касается кривой в точке $P$ . Коэффициенты квадратичной формы, определяющей конус:

$A=dx^{2}y-1$ ,

$B=y-x^{2}$ ,

$C=x(1-y),$

$D=C$

Проективные однородные координаты

(См. также проективные однородные координаты)

Самой трудоемкой операцией арифметики эллиптических кривых является операция взятия обратного элемента в поле (инверсия). Чтобы от нее избавиться переходят от аффинных двумерных координат к 3-х и 4-хмерным координатом, среди которых распространены проективные координаты.

Проективные координаты позволяют избежать 2-х инверсий в законе сложения. Ввод третьей переменней дает возможность заменить операцию инверсии другими операциями. Введем третью координату $Z$ как общий знаменатель в законе сложения. Обозначим $x={\frac {X}{Z}},y={\frac {Y}{Z}}$ , тогда исходное уравнение кривой Эдвардса примет вид:

$(X^{2}+Y^{2})Z^{2}=Z^{4}+dX^{2}Y^{2}$

Нейтральный элемент в проективных координатах: $(0:1:1)$

Нахождение обратной точки $-(X:Y:Z)=(-X:Y:Z)$

В проективных координатах $(X:Y:Z)$ сумма двух точек записывается как $(X_{1}:Y_{1}:Z_{1})+(X_{2}:Y_{2}:Z_{2})=(X_{3}:Y_{3}:Z_{3})$ . С учетом подстановок получается:

${\begin{aligned}y_{3}={\frac {Y_{3}}{Z_{3}}}&={\frac {({\frac {X_{1}Y_{2}}{Z_{1}Z_{2}}}+{\frac {X_{2}Y_{1}}{Z_{1}Z_{2}}})(1-d{\frac {X_{1}X_{2}Y_{1}Y_{2}}{Z_{1}^{2}Z_{2}^{2}}})}{(1+d{\frac {X_{1}X_{2}Y_{1}Y_{2}}{Z_{1}^{2}Z_{2}^{2}}})(1-d{\frac {X_{1}X_{2}Y_{1}Y_{2}}{Z_{1}^{2}Z_{2}^{2}}})))}}\\&={\frac {Z_{1}Z_{2}(Z_{1}^{2}Z_{2}^{2}-dX_{1}X_{2}Y_{1}Y_{2})(X_{1}Y_{2}+X_{2}Y_{1})}{(Z_{1}^{2}Z_{2}^{2}+dX_{1}X_{2}Y_{1}Y_{2})(Z_{1}^{2}Z_{2}^{2}-dX_{1}X_{2}Y_{1}Y_{2})}}\\x_{3}={\frac {X_{3}}{Z_{3}}}&={\frac {X_{3}}{Z_{3}}}={\frac {Z_{1}Z_{2}(Z_{1}^{2}Z_{2}^{2}+dX_{1}X_{2}Y_{1}Y_{2})(X_{1}X_{2}-Y_{1}Y_{2})}{(Z_{1}^{2}Z_{2}^{2}+dX_{1}X_{2}Y_{1}Y_{2})(Z_{1}^{2}Z_{2}^{2}-dX_{1}X_{2}Y_{1}Y_{2})}}\end{aligned}}$

Обозначим:

${\begin{aligned}&A=Z_{1}Z_{2};\\&B=A^{2};\\&C=X_{1}X_{2};\\&D=Y_{1}Y_{2};\\&E=dCD;\\&F=B-E;\\&G=B+E\end{aligned}}$

Тогда

${\begin{aligned}&Y_{3}=A\cdot F\cdot ((X_{1}+Y_{1})\cdot (X_{2}+Y_{2})-C-D)\\&X_{3}=A\cdot G\cdot (D-C)\\&Z_{3}=F\cdot G\\\end{aligned}}$

Всего получается 10 умножений в поле, одно возведение в квадрат и одно умножение на параметр кривой $d$ , не считая простые операции сложения (вычитания).

Закон удвоения

Удвоение может быть произведено с помощью тех же выражений, что и для закона сложения. Удвоение является частным случаем сложения двух одинаковых точек

$(x_{1},y_{1}),(x_{2},y_{2});x_{1}=x_{2},y_{1}=y_{2}$

Удвоение точки $P=(x,y)$ :

${\begin{aligned}(x,y)+(x,y)&=\left({\frac {2xy}{1+dx^{2}y^{2}}},{\frac {y^{2}-x^{2}}{1-dx^{2}y^{2}}}\right)\\[6pt]&=\left({\frac {2xy}{x^{2}+y^{2}}},{\frac {y^{2}-x^{2}}{2-x^{2}-y^{2}}}\right)\end{aligned}}$

Знаменатели были упрощены согласно уравнению кривой $x^{2}+y^{2}=1+dx^{2}y^{2}$ . Дальнейшая оптимизация достигается путем подсчета $2xy$ как $(x+y)^{2}-x^{2}-y^{2}$ . Это сокращает стоимость удвоения в гомоморфных координатах до 3M + 4S + 3C + 6a, в то время как обычное сложение стоит 10M + 1S + 1C + 1D + 7a. Здесь M — умножение в поле, S — возведение в квадрат в поле, D — стоимость умножение на параметр кривой d, a — сложение в поле.

В проективных координатах закон удвоения принимает вид:

${\begin{aligned}x_{3}={\frac {X_{3}}{Z_{3}}}&={\frac {2{\frac {X}{Z}}{\frac {Y}{Z}}\left(2-\left({\frac {X}{Z}}\right)^{2}-\left({\frac {Y}{Z}}\right)^{2}\right)}{\left(2-\left({\frac {X}{Z}}\right)^{2}-\left({\frac {Y}{Z}}\right)^{2}\right)\left(\left({\frac {X}{Z}}\right)^{2}+\left({\frac {Y}{Z}}\right)^{2}\right)}}\\&={\frac {2XY(X^{2}+Y^{2})}{(2Z^{2}-X^{2}-Y^{2})(X^{2}+Y^{2})}}\\y_{3}={\frac {Y_{3}}{Z_{3}}}&={\frac {\left(\left({\frac {X}{Z}}\right)^{2}-\left({\frac {Y}{Z}}\right)^{2}\right)\left(\left({\frac {X}{Z}}\right)^{2}+\left({\frac {Y}{Z}}\right)^{2}\right)}{\left(2-\left({\frac {X}{Z}}\right)^{2}-\left({\frac {Y}{Z}}\right)^{2}\right)\left(\left({\frac {X}{Z}}\right)^{2}+\left({\frac {Y}{Z}}\right)^{2}\right)}}\\&={\frac {(X^{2}-Y^{2})(X^{2}+Y^{2})}{(2Z^{2}-X^{2}-Y^{2})(X^{2}+Y^{2})}}\\\end{aligned}}$

Обозначим:

${\begin{aligned}&A=X^{2}\\&B=Y^{2}\\&C=Z^{2}\\&D=(A+B)\\&E=(A-B)\\&F=2C-A-B\\\end{aligned}}$

Тогда

${\begin{aligned}&X_{3}=2X\cdot Y\cdot F\\&Y_{3}=D\cdot E\\&Z_{3}=D\cdot F\\\end{aligned}}$

Всего получается 3 возведения в квадрат и 4 умножения в поле.

Пример удвоения

Как и примере с законом сложения, рассмотри кривую Эдвардса с параметром d=2:

$x^{2}+y^{2}=1+2x^{2}y^{2}$

и точку $P=(1,0)$ . Координаты точки $P_{2}=2P_{1}$ :

$x_{2}={\frac {2xy}{x^{2}+y^{2}}}=0$

$y_{2}={\frac {y^{2}-x^{2}}{2-(x^{2}+y^{2})}}=-1$

Точка, полученная удвоением P, имеет координаты $P_{2}=(0,-1)$ .

Применение

Кривые Эдвардса над конечными полями используются в криптографических приложениях, а также для факторизации целых чисел. Общая идея этих приложений заключается в том, что берется известный алгоритм, использующий свойства определенных конечных абелевых групп, и переписывается для использования групп рациональных точек кривых Эдвардса. Подробнее см. также

EdDSA — схема цифровой подписи с использованием кривых Эдвардса
ECDH — протокол Ди́ффи-Хе́ллмана на эллиптических кривых
ECQMV — протокол распределения общего ключа
ECIES — протокол направленного шифрования

См. также

Twisted Edwards curve — скрученные кривые Эдвардса, альтернативная форма представления кривых.

Ссылки

↑ Edwards, H.M. A normal form for elliptic curves. — Bulletin of the American Mathematical Society, July 2007. — P. 393—422.
↑ ¹ ² ³ Bernstein, D.J. Faster Addition and Doubling on Elliptic Curves / D.J. Bernstein, T. Lange. — Advancesin Cryptology—ASIACRYPT’20077 (Proc. 13th Int. Conf. On the Theory and Applicationof Cryptology and Information Security. Kuching, Malaysia. December 2–6, 2007), 2007.
↑ M.R. Dam. Edwards Elliptic Curves (Bachelor Thesis Mathematics). — 2012. — С. 11. Архивировано 13 декабря 2022 года.
↑ Бессалов А.В. Эллиптические кривые в форме Эдвардса и криптография. — Киев: Політехніка, 2017. — С. 20. Архивировано 11 декабря 2022 года.
↑ Christophe Arene, Tanja Lange, Michael Naehrig, Christophe Ritzenthaler. Faster Computation of the Tate Pairing (неопр.). Архивировано 11 декабря 2022 года.