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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle (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)\,}$

^[3]

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

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

^[4]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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 {\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 {\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})}$.

Сумма двух точек на кривой Эдвардса с d = −30

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

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

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

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

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

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

${\displaystyle D=C}$

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

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

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

${\displaystyle C=x(1-y),}$

${\displaystyle D=C}$

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

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

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

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

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

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

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

${\displaystyle {\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}}}$

Обозначим:

${\displaystyle {\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}}}$

Тогда

${\displaystyle {\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 умножений в поле, одно возведение в квадрат и одно умножение на параметр кривой ${\displaystyle d}$, не считая простые операции сложения (вычитания).

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

Удвоение точки на кривой Эдвардса с d = −30

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

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

${\displaystyle {\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}}}$

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

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

${\displaystyle {\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}}}$

Обозначим:

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

Тогда

${\displaystyle {\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:

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

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

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

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

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

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

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