Кривая Доша–Икарта–Кохеля, ориентированная на удвоение

В математике кривая Доша–Икарта–Кохеля, ориентированная на удвоение, представляет собой форму, в которой может быть записана эллиптическая кривая . Это особый случай формы Вейерштрасса , и она также важна в криптографии эллиптических кривых , поскольку удвоение значительно ускоряет (вычисление как композиция 2- изогении и ее дуальной ). Она была введена Кристофом Дошем, Томасом Икартом и Дэвидом Р. Кохелем в работе «Эффективное скалярное умножение с помощью разложений изогении». ^[1]

Пусть будет полем и пусть . Тогда кривая Доша–Икарта–Кохеля, ориентированная на удвоение, с параметром a в аффинных координатах представляется следующим образом:${\displaystyle К}$${\displaystyle a\in K}$

${\displaystyle y^{2}=x^{3}+ax^{2}+16ax.}$

Эквивалентно, в проективных координатах :

${\displaystyle ZY^{2}=X^{3}+aZX^{2}+16aXZ^{2},}$

с и .${\displaystyle x={\frac {X}{Z}}}$${\displaystyle y={\frac {Y}{Z}}}$

Поскольку эта кривая является частным случаем формы Вейерштрасса , преобразования к наиболее распространенной форме эллиптической кривой (форме Вейерштрасса) не требуются.

Интересно проанализировать групповой закон в криптографии эллиптических кривых , определяя формулы сложения и удвоения, поскольку эти формулы необходимы для вычисления кратных точек [ n ] P (см. Возведение в степень путем возведения в квадрат ). В общем случае групповой закон определяется следующим образом: если три точки лежат на одной прямой, то они в сумме дают ноль. Таким образом, по этому свойству групповые законы различны для каждой формы кривой.

В этом случае, поскольку эти кривые являются частными случаями кривых Вейерштрасса, сложение — это просто стандартное сложение на кривых Вейерштрасса. С другой стороны, чтобы удвоить точку, можно использовать стандартную формулу удвоения, но это будет не так быстро. В этом случае нейтральным элементом является θ = (0 : 1 : 0) (в проективных координатах), для которого θ = − θ . Тогда, если P = ( x , y ) — нетривиальный элемент ( P ≠ θ ), то обратный элемент этой точки (по сложению) — − P = ( x , − y ) .

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

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

где

${\displaystyle x_{3}={\frac {-x_{1}^{3}+(x_{2}-a)x_{1}^{2}+(x_{2}^{2}+2ax_{2})x_{1}+y_{1}^{2}-2y_{2}y_{1}-x_{2}^{3}-ax_{2}^{2}+y_{2}^{2}}{x_{1}^{2}-2x_{2}x_{1}+x_{2}^{2}}}}$

и${\displaystyle y_{3}={\frac {(-y_{1}+2y_{2})x_{1}^{3}+(-ay_{1}+(-3y_{2}x_{2}+ay_{2}))x_{1}^{2}+((3 x_{2}^{2}+2ax_{2})y_{1}-2ay_{2}x_{2})x_{1}+(y_{1}^{3}-3y_{2}y_{1}^{2}+( -2x_{2}^{3}-ax_{2}^{2}+3y_{2}^{2})y_{1}+(y_{2}x_{2}^{3}+ay_{2}x_{2}^{2 }-y_{2}^{3}))}{-x_{1}^{3}+3x_{2}x_{1}^{2}-3x_{2}^{2}x_{1}+x_{2}^{3}}}.}$

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

${\displaystyle x_{3}=1/(4y_{1}^{2}x_{1}^{4}-8a/y_{1}^{2}x_{1}^{2}+64a^{2}/y_{1}^{2}}$

${\displaystyle y_{3}={\frac {1}{8y_{1}^{3}}}x_{1}^{6}+{\frac {-a^{2}+40a}{4y_{1}^{3}}}x_{1}^{4}+{\frac {ay_{1}^{2}+16a^{3}-640a^{2}}{4y_{1}^{3}}}x_{1}^{2}+{\frac {-4a^{2}y_{1}^{2}-512a^{3}}{y_{1}^{3}}}}$

Самым быстрым сложением является следующее (по сравнению с результатами, приведенными в: http://hyperelliptic.org/EFD/g1p/index.html), и его стоимость составляет 4 умножения, 4 возведения в квадрат и 10 сложений.

А = _Y2 - _Y1

АА = А ²

В = _Х2 - _Х1

СС = В ²

Ф = Х ₁ СС

Z3 = _2CC

Д _{= Х2З3}​

ZZ ₃ = Z ₃ ²

X ₃ = 2(AA-F)-aZ ₃ -D

Y ₃ = ((A+B) ² -AA-CC)(DX ₃ )-Y ₂ ZZ ₃

Пусть . Пусть P=(X ₁ ,Y ₁ )=(2,1), Q=(X ₂ ,Y ₂ )=(1,-1) и a=1, тогда${\displaystyle K=\mathbb {Q} }$

А=2

АА=4

В=1

СС=1

Ф=2

Z3 = ₄

Д=4

ЗЗ ₃ =16

Х ₃ =-4

Y3 = ₃₃₆

Таким образом, P+Q=(-4:336:4)

Следующий алгоритм является самым быстрым (для сравнения перейдите по следующей ссылке: http://hyperelliptic.org/EFD/g1p/index.html), а его стоимость составляет 1 умножение, 5 возведений в квадрат и 7 сложений.

А = Х ₁ ²

В = А-а16

С = а ₂ А

ГГ = Г ₁ ²

ГГ ₂ = 2ГГ

Z ₃ = 2YY ₂

Х ₃ = В ²

V = (Y ₁ +B) 2 - YY - X ₃

Y ₃ = V(X ₃ +64C+a(YY ₂ -C))

ZZ ₃ = Z ₃ ²

Пусть и a = 1. Пусть P = (-1,2), тогда Q = [2] P = (x3,y3) определяется как:${\displaystyle K=\mathbb {Q} }$

А=1

В=-15

С=2

ГГ=4

ГГ ₂ =8

Z3 = ₁₆

Х ₃ =225

В=27

Y3 ₌ 9693

ZZ3 = ₂₅₆

Таким образом, Q=(225:9693:16).

Вычисления сложения и удвоения должны выполняться максимально быстро, поэтому удобнее использовать следующее представление координат:

${\displaystyle x,y}$представлены, удовлетворяя следующим уравнениям:${\displaystyle X,Y,Z,ZZ}$

${\displaystyle x={\frac {X}{Z}}}$

${\displaystyle y={\frac {Y}{ZZ}}}$

${\displaystyle ZZ=Z^{2}}$

Тогда кривая Доша–Икарта–Коэля, ориентированная на удвоение, задается следующим уравнением:

${\displaystyle Y^{2}=ZX^{3}+aZ^{2}X^{2}+16aZ^{3}X}$.

В этом случае — общая точка с обратным . Более того, точки над кривой удовлетворяют: для всех ненулевых.${\displaystyle P=(X:Y:Z:ZZ)}$${\displaystyle -P=(X:-Y:Z:ZZ)}$${\displaystyle (X:Y:Z:Z^{2})=(\lambda X:\lambda ^{2}Y:\lambda Z:\lambda ^{2}Z^{2})}$${\displaystyle \лямбда}$

Более быстрые формулы удвоения для этих кривых и формулы смешанного сложения были введены Доче, Икартом и Коэлем; но в настоящее время эти формулы улучшены Дэниелом Дж. Бернстайном и Таней Ланге (см. ссылку EFD ниже).

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

• Christophe Doche, Thomas Icart и David R. Kohel (2006). "Эффективное скалярное умножение с помощью изогенических разложений". Public Key Cryptography - PKC 2006. Lecture Notes in Computer Science. Vol. 3958. Springer Berlin / Heidelberg. pp.  191– 206. doi :10.1007/11745853_13. ISBN 978-3-540-33851-2.

• Daniel J. Bernstein и Tanja Lange (2008). Анализ и оптимизация эллиптического скалярного умножения. Американское математическое общество. ISBN 9780821857892.

• http://hyperelliptic.org/EFD/g1p/index.html
• http://www.hyperelliptic.org/EFD/g1p/auto-2dik.html