кривая Эдвардса

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

Уравнение кривой Эдвардса над полем K , не имеющим характеристики 2, имеет вид:

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

для некоторого скаляра . Также следующая форма с параметрами c и d называется кривой Эдвардса:${\displaystyle d\in K\setminus \{0,1\}}$

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

где c ,  d  ∈  K с cd (1 −  c ⁴ · d ) ≠ 0.

Каждая кривая Эдвардса бирационально эквивалентна эллиптической кривой в форме Монтгомери и, таким образом, допускает алгебраический групповой закон, как только выбирается точка, служащая нейтральным элементом. Если K конечно, то значительная часть всех эллиптических кривых над K может быть записана как кривые Эдвардса. Часто эллиптические кривые в форме Эдвардса определяются как c=1, без потери общности. В следующих разделах предполагается, что c=1.

(См. также групповой закон кривых Вейерштрасса )

Всякая кривая Эдвардса над полем K с характеристикой, не равной 2, при этом бирационально эквивалентна эллиптической кривой над тем же полем: , где и точка отображается в бесконечность O. Это бирациональное отображение индуцирует группу на любой кривой Эдвардса.${\displaystyle x^{2}+y^{2}=1+dx^{2}y^{2}}$${\displaystyle d\neq 1}$${\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)\,}$

Противоположностью любой точки является . Точка имеет порядок 2, а точки имеют порядок 4. В частности, кривая Эдвардса всегда имеет точку порядка 4 с координатами в K .${\displaystyle (x,y)}$${\displaystyle (-x,y)}$${\displaystyle (0,-1)}$${\displaystyle (\pm 1,0)}$

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

Если 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}$

Одной из привлекательных особенностей закона сложения Эдвардса является то, что он строго унифицирован , т.е. его также можно использовать для удвоения точки, упрощая защиту от атак по сторонним каналам . Формула сложения выше быстрее других унифицированных формул и обладает сильным свойством полноты ^[2]

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

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

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

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

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

и рассмотрим две точки P ₁ =(x ₁ ,y ₁ ), P ₂ =(x ₂ ,y ₂ ) на ней. Пусть α ₁ и α ₂ будут углами такими, что:

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

Сумма P ₁ и P ₂ , таким образом, задается суммой «их углов». То есть, точка P ₃ =P ₁ +P ₂ является точкой на окружности с координатами (x ₃ ,y ₃ ), где:

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

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

Бирациональное отображение между кривой Эдвардса и соответствующей кубической эллиптической кривой отображает прямые линии в конические сечения ^[3] . Другими словами, для кривых Эдвардса три точки и лежат на гиперболе .${\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}),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),D=C}$

В контексте криптографии однородные координаты используются для предотвращения инверсий полей , которые появляются в аффинной формуле. Чтобы избежать инверсий в исходных формулах сложения Эдвардса, уравнение кривой можно записать в проективных координатах как:

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

Проективная точка соответствует аффинной точке на кривой Эдвардса.${\displaystyle (X:Y:Z)}$ ${\displaystyle (X/Z:Y/Z)}$

Элемент идентичности представлен как . Обратным элементом является .${\displaystyle (0:1:1)}$${\displaystyle (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 X_{3}=Z_{1}Z_{2}(X_{1}Y_{2}+X_{2}Y_{1})(Z_{1}^{2}Z_{2}^{2}-dX_{1}X_{2}Y_{1}Y_{2})}$

${\displaystyle Y_{3}=Z_{1}Z_{2}(Y_{1}Y_{2}-X_{1}X_{2})(Z_{1}^{2}Z_{2}^{2}+dX_{1}X_{2}Y_{1}Y_{2})}$

${\displaystyle Z_{3}=(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})}$

Сложение двух точек на кривой Эдвардса можно вычислить более эффективно ^[4] в расширенной форме Эдвардса , где :${\displaystyle (X:Y:Z:T)}$${\displaystyle T=XY/Z}$${\displaystyle (X_{3}:Y_{3}:Z_{3}:T_{3})=(X_{1}:Y_{1}:Z_{1}:T_{1})+(X_{2}:Y_{2}:Z_{2}:T_{2})}$

${\displaystyle A=X_{1}X_{2};B=Y_{1}Y_{2};C=dT_{1}T_{2};D=Z_{1}Z_{2};}$

${\displaystyle E=(X_{1}+Y_{1})(X_{2}+Y_{2})-A-B;F=D-C;G=D+C;H=B-A;}$

${\displaystyle X_{3}=E\cdot F;Y_{3}=G\cdot H;Z_{3}=F\cdot G;T_{3}=E\cdot H;}$

Удвоение может быть выполнено с помощью точно такой же формулы, как и сложение. Удвоение относится к случаю, когда входные данные ( x ₁ ,  y ₁ ) и ( x ₂ ,  y ₂ ) равны.

Удвоение очка : ${\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}}}$

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

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

Как и в предыдущем примере для закона сложения, рассмотрим кривую Эдвардса с 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)}$

Смешанное сложение имеет место, когда известно, что Z _{2 равен 1. В таком случае A=Z 1} ^. Z ₂ можно исключить, и общая стоимость сократится до 9 M +1 S +1 C +1 D +7 a

A= Z ₁ ^. Z ₂ // другими словами, A= Z ₁

В= Я ₁ ²

С=Х ₁ .Х ₂

Д=Y ₁ ^. Y ₂

E=d ^. C ^. D

Ф=БЫТЬ

Г=Б+Э

Икс ₃ знак равно А ^. F((X _I +Y ₁ ) ^. (X ₂ +Y ₂ )-CD)

Y ₃ = А. ^Г. ( DC ⁾

Z ₃ = ^С.Ф.Г​^​​

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

${\displaystyle 3(x_{1},y_{1})=\left({\frac {(x_{1}^{2}+y_{1}^{2})^{2}-(2y_{1})^{2}}{4(x_{1}^{2}-1)x_{1}^{2}-(x_{1}^{2}-y_{1}^{2})^{2}}}x_{1},{\frac {(x_{1}^{2}+y_{1}^{2})^{2}-(2x_{1})^{2}}{-4(y_{1}^{2}-1)y_{1}^{2}+(x_{1}^{2}-y_{1}^{2})^{2}}}y_{1}\right).\,}$

Для этой операции в стандартных координатах Эдвардса существует два набора формул. Первый стоит 9 M  + 4 S , а второй требует 7 M  + 7 S. Если отношение S/M очень мало, в частности, ниже 2/3, то второй набор лучше, а для больших отношений предпочтительнее первый. ^[5] Используя формулы сложения и удвоения (как упоминалось выше), точка ( X ₁  :  Y ₁  :  Z ₁ ) символически вычисляется как 3( X ₁  :  Y ₁  :  Z ₁ ) и сравнивается с ( X ₃  :  Y ₃  :  Z ₃ )

Пример утроения

Если задать кривую Эдвардса с d=2 и точкой P ₁ =(1,0), то точка 3P ₁ имеет координаты:

${\displaystyle x_{3}={\frac {(x_{1}^{2}+y_{1}^{2})^{2}-(2y_{1})^{2}}{4(x_{1}^{2}-1)x_{1}^{2}-(x_{1}^{2}-y_{1}^{2})^{2}}}x_{1}=-1}$

${\displaystyle y_{3}={\frac {(x_{1}^{2}+y_{1}^{2})^{2}-2(x_{1})^{2}}{-4(y_{1}^{2}-1)y_{1}^{2}+(x_{1}^{2}-y_{1}^{2})^{2}}}y_{1}=0}$

Итак, 3P ₁ =(-1,0)=P- _1. Этот результат можно также найти, рассматривая пример удвоения: 2P ₁ =(0,1), поэтому 3P ₁ = 2P ₁ + P ₁ = (0,-1) + P ₁ = -P ₁ .

Алгоритм

А=Х ₁ ²

В=Г ₁ ²

С=(2Z ₁ ) ²

Д=А+Б

Э=Д ²

F=2D.(AB)

G=EB.C

Н=ЭА.С

Я=Ф+Н

J=ФГ

X ₃ =GJX1

Y ₃ = HIY1

Z ₃ =IJZ1

Эта формула стоит 9 M  + 4 S

^{Бернштейн и Ланге ввели еще} более быструю систему координат для эллиптических кривых, называемую ^{перевернутыми} координатами Эдвардса ^{[6] ,} в которой координаты ( X  :  Y  :  Z ) удовлетворяют кривой ( X2  +  Y2 ) Z2  = ( ^dZ4 +  X2Y2  ) ^и соответствуют аффинной точке ( ^Z / X , Z  / Y ⁾ на кривой Эдвардса x2 +  y2  =  1 +  dx2y2 с ^{XYZ ≠} 0 .

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

Более подробную информацию об операциях с этими координатами см. на сайте http://hyperelliptic.org/EFD/g1p/auto-edwards-inverted.html

Существует еще одна система координат, с помощью которой можно представить кривую Эдвардса. Эти новые координаты называются расширенными координатами ^[7] и они даже быстрее инвертированных координат. Для получения дополнительной информации о временных затратах, требуемых для операций с этими координатами, см.: http://hyperelliptic.org/EFD/g1p/auto-edwards.html

• Скрученная кривая Эдвардса

Дополнительную информацию о времени выполнения, необходимом в конкретном случае, см. в Таблице затрат на операции на эллиптических кривых .

• Бернстайн, Даниэль ; Ланге, Таня (2007), Более быстрое сложение и удвоение на эллиптических кривых (PDF)
• Эдвардс, Гарольд М. (9 апреля 2007 г.), «Нормальная форма для эллиптических кривых», Бюллетень Американского математического общества , 44 (3): 393–422, doi : 10.1090/s0273-0979-07-01153-6 , ISSN  0002-9904
• Более быстрые групповые операции на эллиптических кривых , Х. Хисил, К. К. Вонг, Г. Картер, Э. Доусон
• DJBernstein, P.Birkner. T. Lange, C.Peters, Оптимизация двухосновного эллиптического кривой с одним скаляром (PDF){{citation}}: CS1 maint: multiple names: authors list (link)
• Вашингтон, Лоуренс К. (2008), Эллиптические кривые: теория чисел и криптография , Дискретная математика и ее приложения (2-е изд.), Chapman & Hall/CRC, ISBN 978-1-4200-7146-7
• Бернстайн, Дэниел ; Ланге, Таня , Обратные координаты Эдвардса (PDF)

• http://hyperelliptic.org/EFD/g1p/index.html
• http://hyperelliptic.org/EFD/g1p/auto-edwards.html