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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

На любой эллиптической кривой сумма двух точек задается рациональным выражением координат точек, хотя в общем случае может потребоваться использовать несколько формул, чтобы охватить все возможные пары. Для кривой Эдвардса, принимая нейтральный элемент в качестве точки (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)\,$

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

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

$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 ₁ =(x ₁ ,y ₁ ), P ₂ =(x ₂ ,y ₂ ). Пусть α ₁ и α ₂ — углы такие, что:

${\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 ₁ и P ₂ , таким образом, определяется суммой «их углов». То есть точка P ₃ =P ₁ +P ₂ является точкой на окружности с координатами (x ₃ ,y ₃ ), где:

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

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

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

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

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

Бирациональное отображение между кривой Эдвардса и соответствующей кубической эллиптической кривой отображает прямые линии в конические сечения. $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$

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

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

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

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

Элемент идентификации представлен $(0:1:1)$. Обратная сторона $(X:Y:Z)$ является $(-X:Y:Z)$.

Формула сложения в однородных координатах имеет вид: $(X_{1}:Y_{1}:Z_{1})+(X_{2}:Y_{2}:Z_{2})=(X_{3}:Y_{3}:Z_{3})$

где

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

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

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

Алгоритм

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

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

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

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

удвоение

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

Удвоение очка $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}$. Это снижает стоимость удвоения в гомоморфных координатах до 3 M + 4 S + 3 C + 6 a , в то время как общее сложение стоит 10 M + 1 S + 1 C + 1 D + 7 a . Здесь M — умножение полей, S — возведение полей в квадрат, D — стоимость умножения на параметр кривой d , а — сложение полей.

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

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

Смешанное дополнение

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

Алгоритм

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

Б= Я ₁ ²

С=Х ₁ .Х ₂

Д=Д ₁ ^. Д ₂

Е=д ^. С ^. Д

Ф=БЫТЬ

Г=Б+Е

Х ₃ = А ^. F((XI ₊ Y ₁ ) ^. (X ₂ +Y ₂ )-CD)

Y ₃ = А ^. Г ^. (округ Колумбия)

З ₃ =С ^. Ф ^. Г

утроение

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

$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, то лучше использовать второй набор, а для более высоких отношений следует отдать предпочтение первому. Используя формулы сложения и удвоения (как упоминалось выше), точка ( X ₁ : Y ₁ : Z ₁ ) символически вычисляется как 3 ( X ₁ : Y ₁ : Z ₁ ) и сравнивается с ( X ₃ : Y ₃ : Z _{3 ).} )

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

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

$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$

$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- ₁ . Этот результат также можно найти, рассматривая пример удвоения: 2P ₁ =(0,1), поэтому 3P ₁ = 2P ₁ + P ₁ = (0,-1) + P ₁ = -P ₁ .

Алгоритм

А=Х ₁ ²

Б=Д ₁ ²

С=( _2Z1 ) ²

Д=А+Б

Е=Д ²

F=2D.(AB)

G=EB.C

H=EA.C

Я=Ф+Ч

Дж=ФГ

Х ₃ =GJX1

Д ₃ = ПРИВЕТ1

З ₃ =IJZ1

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

Инвертированные координаты Эдвардса

Бернштейн и Ланге представили еще более быструю систему координат для эллиптических кривых, названную перевернутыми координатами Эдварда. в которой координаты ( X : Y : Z ) удовлетворяют кривой ( X ² + И ² ) С ² = ( дZ ⁴ + Х ² И ² ) и соответствуетк аффинной точке ( Z / X , Z / Y ) на кривой Эдвардса x ² + и ² = 1 + дх ² и ² с XYZ ≠ 0.

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

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

Расширенные координаты для кривых Эдвардса

Существует еще одна система координат, с помощью которой можно представить кривую Эдвардса. Эти новые координаты называются расширенными координатами. и даже быстрее, чем в инвертированных координатах. Подробнее о временных затратах, необходимых при операциях с этими координатами, см.: 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
• Быстрые групповые операции на эллиптических кривых , Х. Хисил, К. К. Вонг, Г. Картер, Э. Доусон
• Дж.Бернштейн, П.Биркнер. Т. Ланге, К. Питерс, Оптимизация односкалярного умножения с двойной базой на эллиптической кривой (PDF) {{citation}}: CS1 maint: несколько имен: список авторов ( ссылка )
• Вашингтон, Лоуренс К. (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