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

Скрученная кривая Эдвардса уравнения $10x^{2}+y^{2}=1+6x^{2}y^{2}$

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

Определение

Извращенная кривая Эдвардса $E_{E,a,d}$ над полем $\mathbb {K}$ с характеристикой , не равной 2 (т. е. ни один элемент не является собственным аддитивным обратным), представляет собой аффинную плоскую кривую, определяемую уравнением:

$E_{E,a,d}:ax^{2}+y^{2}=1+dx^{2}y^{2}$

где $a,d$ являются отдельными ненулевыми элементами $\mathbb {K}$.

Каждая скрученная кривая Эдвардса является скручиванием Эдвардса кривой . Особый случай $a=1$ раскручивается кривой , поскольку кривая сводится к обычной Эдвардса .

Каждая скрученная кривая Эдвардса бирационально эквивалентна эллиптической кривой в форме Монтгомери и наоборот.

Групповое право

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

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

Позволять $\mathbb {K}$ быть полем с характеристикой, отличной от 2.Позволять $(x_{1},y_{1})$ и $(x_{2},y_{2})$ быть точками на скрученной кривой Эдвардса. Уравнение скрученной кривой Эдвардса записывается как;

$E_{E,a,d}$: $ax^{2}+y^{2}=1+dx^{2}y^{2}$.

Сумма этих баллов $(x_{1},y_{1}),(x_{2},y_{2})$ на $E_{E,a,d}$ является:

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

Нейтральный элемент — (0,1), а отрицательный — $(x_{1},y_{1})$ является $(-x_{1},y_{1})$

Эти формулы также работают для удвоения. Если а — квадрат в $\mathbb {K}$ и d является не квадратом в $\mathbb {K}$, эти формулы полны : это означает, что их можно использовать для всех пар точек без исключений; поэтому они также работают на удвоение, а нейтральные элементы и негативы принимаются в качестве входных данных.

Пример добавления

Дана следующая скрученная кривая Эдвардса с a = 3 и d = 2:

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

можно добавить баллы $P_{1}=(1,{\sqrt {2}})$ и $P_{2}=(1,-{\sqrt {2}})$ используя формулу, приведенную выше. В результате получается точка Р _3, имеющая координаты:

$x_{3}={\frac {x_{1}y_{2}+y_{1}x_{2}}{1+dx_{1}x_{2}y_{1}y_{2}}}=0,$

$y_{3}={\frac {y_{1}y_{2}-ax_{1}x_{2}}{1-dx_{1}x_{2}y_{1}y_{2}}}=-1.$

Удвоение на скрученных кривых Эдвардса

Удвоение можно выполнить по той же формуле, что и сложение.Удвоение очка $(x_{1},y_{1})$ на кривой $E_{E,a,d}$ является:

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

где

${\begin{aligned}x_{3}&={\frac {x_{1}y_{1}+y_{1}x_{1}}{1+dx_{1}x_{1}y_{1}y_{1}}}={\frac {2x_{1}y_{1}}{ax_{1}^{2}+y_{1}^{2}}}\\[6pt]y_{3}&={\frac {y_{1}y_{1}-ax_{1}x_{1}}{1-dx_{1}x_{1}y_{1}y_{1}}}={\frac {y_{1}^{2}-ax_{1}^{2}}{2-ax_{1}^{2}-y_{1}^{2}}}.\end{aligned}}$

Знаменатели при удвоении упрощаются с помощью уравнения кривой $dx^{2}y^{2}=ax^{2}+by^{2}-1$. Это уменьшает степень с 4 до 2 и позволяет проводить более эффективные вычисления.

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

Учитывая ту же скрученную кривую Эдвардса, приведенную в предыдущем примере, с a=3 и d=2, можно удвоить точку $P_{1}=(1,{\sqrt {2}})$. Точка 2П _1, полученная по формуле выше, имеет следующие координаты:

$x_{3}={\frac {2x_{1}y_{1}}{ax_{1}^{2}+y_{1}^{2}}}={\frac {2{\sqrt {2}}}{5}},$

$y_{3}={\frac {y_{1}^{2}-ax_{1}^{2}}{2-ax_{1}^{2}-y_{1}^{2}}}={\frac {1}{3}}.$

После некоторых небольших вычислений легко увидеть, что точка $P_{3}=\left({\frac {2{\sqrt {2}}}{5}},{\frac {1}{3}}\right)$ принадлежит кривой $3x^{2}+y^{2}=1+2x^{2}y^{2}$.

Расширенные координаты

Существует другой вид системы координат, с помощью которой можно представить точку на скрученных кривых Эдвардса.точка $(x,y,z)$ на $ax^{2}+y^{2}=1+dx^{2}y^{2}$ представлен как X , Y , Z , T, удовлетворяющий следующим уравнениям x = X / Z , y = Y / Z , xy = T / Z .

Координаты точки ( X : Y : Z : T ) называются расширенными скрученными координатами Эдвардса . Элемент идентификации представлен (0:1:1:0). Отрицательная точка равна (− X : Y : Z :− T ).

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

Координаты точки $(X_{1}:Y_{1}:Z_{1})$ называются обратными скрученными координатами Эдвардса на кривой ${\textstyle (X^{2}+aY^{2})Z^{2}=X^{2}Y^{2}+dZ^{4}}$с ${\textstyle X_{1}Y_{1}Z_{1}\neq 0}$; эта точка относительно аффинной $(Z_{1}/X_{1},Z_{1}/Y_{1})$ на $E_{E,a,d}$.Бернштейн и Ланге ввели эти перевернутые координаты для случая a = 1 и заметили, что координаты дополнительно экономят время.

Проективные скрученные координаты Эдвардса

Уравнение проективной скрученной кривой Эдвардса имеет вид: $(aX^{2}+Y^{2})Z^{2}=Z^{4}+dX^{2}Y^{2}$ Для Z ₁ ≠ 0 точка (X ₁ :Y ₁ :Z ₁ ) представляет собой аффинную точку ( x ₁ = X ₁ / Z ₁ , y ₁ = Y ₁ / Z ₁ ) на E _{E , a , d} .

Выражение эллиптической кривой в скрученной форме Эдвардса экономит время в арифметике, даже если ту же кривую можно выразить в форме Эдвардса.

Сложение в проективных скрученных кривых

Сложение на проективной скрученной кривой Эдвардса имеет вид

(X ₃ :Y ₃ :Z ₃ ) = (X ₁ :Y ₁ :Z ₁ ) + (X ₂ :Y ₂ :Z ₂ )

и стоит 10 умножений + 1 S пересчета + 2 D + 7 сложений , где 2 D — это одно умножение на a и одно на d .

Алгоритм

А знак равно Z ₁ · Z ₂ ,

Б = А ²

С = Х ₁ · Х ₂

Д = Y ₁ · Y ₂

Е = dC · D

F = Б - Е

Г = Б + Е

Икс ₃ знак равно А · F((Х ₁ + Y ₁ ) · (Икс ₂ + Y ₂ ) - C - D)

Y ₃ = А · G · (D − aC)

З ₃ = Ф · Г

Удвоение на проективных скрученных кривых

Удвоение на проективной скрученной кривой определяется выражением

(X3 _: Y3 _: Z3 ₎ = 2(X1 _: Y1 _: Z1 ₎ .

Это стоит 3 умножений + 4 S кварингов + 1 D + 7 сложений , где 1 D — умножение на a .

Алгоритм

Б = (Икс ₁ + Y ₁ ) ²

С = Х ₁ ²

Д = Y ₁ ²

Е = до нашей эры

Ф = Е + Д

Ч = Z ₁ ²

Дж = F - 2H

X ₃ = (B − C − D).J

Y ₃ = F · (E − D)

Z ₃ = Ф · Дж

См. также

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

Ссылки

• Дэниел Дж. Бернштейн; Марк Джой; Таня Ланге; Питер Биркнер; Кристиан Петерс, Искривленные кривые Эдвардса (PDF)

• Хусейн Хисил, Кеннет Вонг, Гэри Картер, Эд Доусон. (2008), «Возвращение к искривленным кривым Эдвардса» , Архив криптологии ePrint {{citation}}: CS1 maint: несколько имен: список авторов ( ссылка )

• Дэниел Дж. Бернштейн; Таня Ланге; Питер Биркнер; Кристиана Петерс, ECM с использованием кривых Эдвардса (PDF)

Внешние ссылки

• http://hyperelliptic.org/EFD/g1p/index.html
• http://hyperelliptic.org/EFD/g1p/auto-twisted.html
• Алгоритм Ed25519: http://ed25519.cr.yp.to/