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

Кривые Эдвардса уравнения x ²  +  y ²  = 1 +  d  · x ² · y ² по действительным числам для d  = −300 (красный), d  = − √ 8 (желтый) и d  = 0,9 (синий)

В математике кривые Эдвардса представляют собой семейство эллиптических кривых, изученных Гарольдом Эдвардсом в 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})}$.

Дополнение к кривым Эдвардса

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

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

Точки на эллиптической кривой образуют абелеву группу: можно складывать точки и брать целые кратные одной точки. Когда эллиптическая кривая описывается невырожденным кубическим уравнением, то сумма двух точек 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

Смотрите также

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

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

Примечания

1. Бернстайн, Даниэль; Ланге, Таня (3 марта 2014 г.), Как разработать систему подписи на эллиптической кривой
2. Daniel. J. Bernstein, Tanja Lange, стр. 3, Более быстрое сложение и удвоение на эллиптических кривых
3. Кристоф Арен; Таня Ланге; Майкл Наериг; Кристоф Ритценталер (2009). "Быстрое вычисление спаривания Тейта". arXiv : 0904.0854 . Bibcode :2009arXiv0904.0854A . Получено 28 февраля 2010 г.
4. Хусейн Хисил, Кеннет Кун-Хо Вонг, Гэри Картер и Эд Доусон. Пересмотр скрученных кривых Эдвардса . В ASIACRYPT 2008, страницы 326–343, 2008
5. Бернстайн и др., Оптимизация двухосновной эллиптической кривой с одиночным скалярным умножением
6. Дэниел Дж. Бернстайн. Таня Ланге, стр. 2, Перевернутые координаты Эдварда
7. Х. Хисил, К. К. Вонг, Г. Картер, Э. Доусон Более быстрые групповые операции на эллиптических кривых

Ссылки

• Бернстайн, Даниэль ; Ланге, Таня (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