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

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Twisted Edwards curve" – news · newspapers · books · scholar · JSTOR (January 2010) (Learn how and when to remove this message)

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

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

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

где — различные ненулевые элементы .${\displaystyle a,d}$${\displaystyle \mathbb {K} }$

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

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

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

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

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

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

${\displaystyle (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), а отрицательный —${\displaystyle (x_{1},y_{1})}$${\displaystyle (-x_{1},y_{1})}$

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

Пример сложения

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

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

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

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

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

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

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

где

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

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

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

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

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

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

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

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

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

Координаты точки называются перевернутыми скрученными координатами Эдвардса на кривой с ; эта точка соответствует аффинной на . Бернштейн и Ланге ввели эти перевернутые координаты для случая a=1 и заметили, что координаты дополнительно экономят время.${\displaystyle (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}$${\displaystyle (Z_{1}/X_{1},Z_{1}/Y_{1})}$${\displaystyle E_{E,a,d}}$

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

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

Добавление на проективной скрученной кривой Эдвардса задается формулой

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

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

Алгоритм

А = _Z1 · _Z2 ,

В = А ²

С = Х ₁ · Х ₂

Д = _Y1 · _Y2

Е = dС · D

Ф = В − Е

Г = Б + Э

X ₃ = A · F((X ₁ + Y ₁ ) · (X ₂ + Y ₂ ) − C − D)

Y ₃ = А · Г · (Д − аС)

Я ₃ = Ф · Г

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

(X ₃ :Y ₃ :Z ₃ ) = 2(X ₁ :Y ₁ :Z ₁ ).

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

Алгоритм

В = (X ₁ + Y ₁ ) ²

С = Х ₁ ²

Д = Y ₁ ²

Е = аС

Ф = Э + Д

Н = Z ₁ ²

J = F − 2H

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

Y ₃ = F · (E − D)

Z ₃ = F · J ^[1]

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

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

• Хусейн Хисил, Кеннет Вонг, Гэри Картер, Эд Доусон. (2008), «Повторный взгляд на скрученные кривые Эдвардса», Архив Cryptology ePrint{{citation}}: CS1 maint: multiple names: authors list (link)

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

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