Скрученная кривая Эдвардса - Twisted Edwards curve

Искривленная кривая Эдвардса уравнения

{ displaystyle 10x ^ {2} + y ^ {2} = 1 + 6x ^ {2} y ^ {2}}

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

Определение

Каждый скрученный Кривая Эдвардса - это крутить из Кривая Эдвардса Искривленная кривая Эдвардса. ${ displaystyle E_ {E_ {a, d}}}$ через поле ${ Displaystyle mathbb {K}}$ который имеет ${ Displaystyle mathrm {char} ( mathbb {K}) neq 2}$ является аффинный плоская кривая, определяемая уравнением:

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

куда ${ displaystyle a, d}$ различные ненулевые элементы ${ Displaystyle mathbb {K}}$ . Особый случай ${ displaystyle a = 1}$ является раскрученный, поскольку кривая сводится к обычному Кривая Эдвардса.

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

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

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

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

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

E_E,а,d:

{ displaystyle ax ^ {2} + y ^ {2} = 1 + dx ^ {2} y ^ {2}}

.

Сумма этих баллов ${ Displaystyle (x_ {1}, y_ {1}), (x_ {2}, y_ {2})}$ на E_E,а,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}}} вправо)}

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

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

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

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

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

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

{ 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.}

Удвоение на изогнутых кривых Эдвардса

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

[2](Икс₁,у₁) = (Икс₃,у₃)

куда

{ displaystyle { begin {align} 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 {выравнивается}}}

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

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

{ displaystyle x_ {3} = { frac {x_ {1} y_ {1} + y_ {1} x_ {1}} {1 + dx_ {1} x_ {1} y_ {1} y_ {1}} } = { frac {2 { sqrt {2}}} {5}},}

{ displaystyle y_ {3} = { frac {y_ {1} y_ {1} -ax_ {1} x_ {1}} {1-dx_ {1} x_ {1} y_ {1} y_ {1}} } = { 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}}$ .

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

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

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

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

Координаты точки ${ 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})}$ на E_E,а,dБернштейн и Ланге ввели эти инвертированные координаты для случая a = 1 и заметили, что координаты дополнительно экономят время.

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

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

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

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

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

(ИКС₃: Y₃: Z₃) = (X₁: Y₁: Z₁) + (Х₂: Y₂: Z₂)

и стоит 10Mультипликации + 1SКвартинг + 2D + 7 аdditions, где 2D одно умножение на а и один d.

Алгоритм

А = Я₁ · Z₂,

В = А²

С = Х₁ · ИКС₂

D = Y₁ · Y₂

E = dC · D

F = B - E

G = B + E

Икс₃ = A · F ((X₁ + Y₁) · (ИКС₂ + Y₂) - C - D)

Y₃ = A · G · (D - aC)

Z₃ = F · G

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

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

(ИКС₃: Y₃: Z₃) = 2 (X₁: Y₁: Z₁).

Это стоит 3Mультипликации + 4Sдобыча + 1D + 7аdditions, где 1D умножение на а.

Алгоритм

B = (X₁ + Y₁)²

С = Х₁²

D = Y₁²

E = aC

F = E + D

H = Z₁²

J = F - 2H

Икс₃ = (B - C - D) .J

Y₃ = F · (E - D)

Z₃ = F · J^[1]

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

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

Примечания

^ ^а ^б Д. Дж. Бернштейн, П. Биркнер, М. Джой, Т. Ланге, К. Петерс, Скрученные кривые Эдвардса.
^ Дэниел Дж. Бернштейн; Питер Биркнер; Марк Джой; Таня Ланге; Кристиан Петерс. "Скрученные кривые Эдвардса" (PDF). Получено 28 января 2020.
^ Даниэль Дж. Бернштейн и Таня Ланге, Более быстрое сложение и удвоение эллиптических кривых

внешняя ссылка

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

[Twisted_Edwards_Curves-1] а ^б Д. Дж. Бернштейн, П. Биркнер, М. Джой, Т. Ланге, К. Петерс, Скрученные кривые Эдвардса.

[2] Дэниел Дж. Бернштейн; Питер Биркнер; Марк Джой; Таня Ланге; Кристиан Петерс. "Скрученные кривые Эдвардса" (PDF). Получено 28 января 2020.

[3] Даниэль Дж. Бернштейн и Таня Ланге, Более быстрое сложение и удвоение эллиптических кривых

[1]

[2]

[3]