Гессенская форма эллиптической кривой

В геометрии , то Гессиан кривой является плоским кривым аналогичен лепестком Декарта . Он назван в честь немецкого математика Отто Гессе . Эта кривая была предложена для применения в криптографии эллиптических кривых , потому что арифметика в этом представлении кривой быстрее и требует меньше памяти, чем арифметика в стандартной форме Вейерштрасса . ^[1]

Определение [ править ]

Кривая Гессе уравнения ${\ displaystyle x ^ {3} + y ^ {3} + 1 = 0,3xy}$

Пусть - поле и рассмотрим эллиптическую кривую в следующем частном случае формы Вейерштрасса над :${\ displaystyle K}$ ${\ displaystyle E}$${\ displaystyle K}$

${\ displaystyle Y ^ {2} + a_ {1} XY + a_ {3} Y = X ^ {3}}$

где кривая имеет дискриминант Тогда точка имеет порядок 3.${\ displaystyle \ Delta = \ left (a_ {3} ^ {3} \ left (a_ {1} ^ {3} -27a_ {3} \ right) \ right) = a_ {3} ^ {3} \ delta .}$${\ Displaystyle P = (0,0)}$

Чтобы доказать, что это имеет порядок 3, заметим, что касательная к точке at - это прямая, пересекающаяся с кратностью 3 в точке .${\ Displaystyle P = (0,0)}$${\ displaystyle E}$${\ displaystyle P}$${\ displaystyle Y = 0}$${\ displaystyle E}$${\ displaystyle P}$

И наоборот, если даны точки 3-го порядка на эллиптической кривой, обе определены над полем, можно привести кривую к форме Вейерштрасса так, чтобы касательная в точке была прямой . Тогда уравнение кривой будет с .${\ displaystyle P}$${\ displaystyle E}$${\ displaystyle K}$${\ Displaystyle P = (0,0)}$${\ displaystyle P}$${\ displaystyle Y = 0}$${\ displaystyle Y ^ {2} + a_ {1} XY + a_ {3} Y = X ^ {3}}$${\ displaystyle a_ {1}, a_ {3} \ in K}$

Теперь, чтобы получить кривую Гессе, необходимо выполнить следующее преобразование :

Сначала обозначим корень многочлена${\ displaystyle \ mu}$

${\displaystyle T^{3}-\delta T^{2}+{\delta ^{2} \over 3}T+a_{3}\delta ^{2}=0.}$

потом

${\displaystyle \mu ={\delta -a_{1}\delta ^{2/3} \over 3}.}$

Обратите внимание, что если имеет конечное поле порядка , то каждый элемент имеет уникальный кубический корень ; в целом, лежит в поле расширения K . ${\displaystyle K}$${\displaystyle q\equiv 2{\pmod {3}}}$${\displaystyle K}$${\displaystyle \mu }$

Теперь, определяя следующее значение , получается другая кривая C, которая бирационально эквивалентна E:${\textstyle D={\frac {3(\mu -\delta )}{\mu }}}$

${\displaystyle C}$ : ${\displaystyle x^{3}+y^{3}+z^{3}=Dxyz}$

которая называется кубической формой Гессе (в проективных координатах )

${\displaystyle C}$ : ${\displaystyle x^{3}+y^{3}+1=Dxy}$

в аффинной плоскости (удовлетворяющая и ).${\textstyle x={\frac {X}{Z}}}$${\textstyle y={\frac {Y}{Z}}}$

Кроме того, (иначе кривая была бы особой ).${\displaystyle D^{3}\neq 1}$

Исходя из кривой Гессе, бирационально эквивалентное уравнение Вейерштрасса дается формулой

${\displaystyle v^{2}=u^{3}-27D\left(D^{3}+8\right)u+54\left(D^{6}-20D^{3}-8\right),}$

при преобразованиях:

${\displaystyle (x,y)=\left(\eta \left(u+9D^{2}\right),-1+\eta \left(3D^{3}-Dx-12\right)\right)}$

а также

${\displaystyle (u,v)=\left(-9D^{2}+\varepsilon x,3\varepsilon \left(y-1\right)\right)}$

где:

${\displaystyle \eta ={\frac {6\left(D^{3}-1\right)\left(v+9D^{3}-3Du-36\right)}{\left(u+9D^{2}\right)^{3}+\left(3Dd-Du-12\right)^{3}}}}$

а также

${\displaystyle \varepsilon ={\frac {12\left(D^{3}-1\right)}{Dx+y+1}}}$

Групповой закон [ править ]

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

В этом случае, правильный способ заключается в использовании формулы Коши-Desboves', получая точку на бесконечности θ = (1: 1: 0) , то есть, нейтральный элемент (обратный & thetas является θ снова). Пусть P = ( x ₁ , y ₁ ) - точка на кривой. Прямая содержит точку P и бесконечно удаленную точку θ . Следовательно, - P - третья точка пересечения этой прямой с кривой. Пересекая эллиптическую кривую с прямой, получается следующее условие ${\displaystyle y=-x+(x_{1}+y_{1})}$${\displaystyle x_{2}-(x_{1}+y_{1})\cdot x+x_{1}\cdot y_{1}=\theta }$

Так как не равен нуль (поскольку D ³ отличен 1), то х координата - Р является у ₁ и у координаты - Р является й ₁ , то есть, или в проективных координатах .${\displaystyle x_{1}+y_{1}+D}$${\displaystyle -P=(y_{1},x_{1})}$${\displaystyle -P=(Y_{1}:X_{1}:Z_{1})}$

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

Удвоение

Теперь, если это точка на эллиптической кривой, можно определить операцию "удвоения", используя формулы Коши-Дебова:${\displaystyle P=(X_{1}:Y_{1}:Z_{1})}$

${\displaystyle [2]P=\left(Y_{1}\cdot \left(X_{1}^{3}-Z_{1}^{3}\right):X_{1}\cdot \left(Z_{1}^{3}-Y_{1}^{3}\right):Z_{1}\cdot \left(Y_{1}^{3}-X_{1}^{3}\right)\right)}$

Добавление

Таким же образом для двух разных точек, скажем и , можно определить формулу сложения. Пусть R обозначает сумму этих точек, R = P + Q , тогда ее координаты определяются как:${\displaystyle P=(X_{1}:Y_{1}:Z_{1})}$${\displaystyle Q=(X_{2}:Y_{2}:Z_{2})}$

${\displaystyle R=\left(Y_{1}^{2}\cdot X_{2}\cdot Z_{2}-Y_{2}^{2}\cdot X_{1}\cdot Z_{1}:X_{1}^{2}\cdot Y_{2}\cdot Z_{2}-X_{2}^{2}\cdot Y_{1}\cdot Z_{1}:Z_{1}^{2}\cdot X_{2}\cdot Y_{2}-Z_{2}^{2}\cdot X_{1}\cdot Y_{1}\right)}$

Алгоритмы и примеры [ править ]

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

Предложение . Пусть P = ( X, Y, Z ) - точка на эллиптической кривой Гессе E ( K ) . Потом:

${\displaystyle 2(X:Y:Z)=(Z:X:Y)+(Y:Z:X)}$ (2).

Кроме того, мы имеем ( Z : X : Y ) ≠ ( Y : Z : X ) .

Наконец, в отличие от других параметризаций , здесь нет вычитания для вычисления отрицания точки. Следовательно, этот алгоритм сложения также можно использовать для вычитания двух точек P = ( X ₁ : Y ₁ : Z ₁ ) и Q = ( X ₂ : Y ₂ : Z ₂ ) на эллиптической кривой Гессе:

${\displaystyle (X_{1}:Y_{1}:Z_{1})-(X_{2}:Y_{2}:Z_{2})=(X_{1}:Y_{1}:Z_{1})+(Y_{2}:X_{2}:Z_{2})}$ (3)

Подводя итог, можно сказать, что, адаптируя порядок входных данных в соответствии с уравнением (2) или (3), алгоритм сложения, представленный выше, может использоваться безразлично для: добавления 2 (разн.) Точек, удвоения точки и вычитания 2 точек только 12 умножений и 7 вспомогательных переменных, включая 3 переменные результата. До изобретения кривых Эдвардса эти результаты представляют собой самый быстрый из известных способов реализации скалярного умножения эллиптической кривой для обеспечения устойчивости к атакам по побочным каналам .

Для некоторых алгоритмов защита от атак по сторонним каналам не требуется. Значит, для этих удвоений можно быстрее. Поскольку существует множество алгоритмов, здесь приведены только лучшие для формул сложения и удвоения, с одним примером для каждого из них:

Дополнение [ править ]

Пусть P ₁ = ( X ₁ : Y ₁ : Z ₁ ) и P ₂ = ( X ₂ : Y ₂ : Z ₂ ) - две точки, отличные от θ . Предполагая, что Z ₁ = Z ₂ = 1, алгоритм задается следующим образом:

А = Х ₁ Y ₂

В = Y ₁ X ₂

X ₃ = B Y ₁ - Y ₂ А

Y ₃ = Х ₁ А - В Х ₂

Z ₃ = Y ₂ X ₂ - X ₁ Y ₁

Необходимая стоимость составляет 8 умножений и 3 сложения Стоимость повторного добавления 7 умножений и 3 сложений, в зависимости от первой точки.

Пример

Учитывая следующие точки на кривой для d = −1, P ₁ = (1: 0: −1) и P ₂ = (0: −1: 1) , тогда, если P ₃ = P ₁ + P _2, имеем:

Х ₃ = 0 - 1 = -1

Y ₃ = −1−0 = −1

Z ₃ = 0 - 0 = 0

Тогда: P ₃ = (−1: −1: 0)

Удвоение [ править ]

Пусть P  = ( X ₁  :  Y ₁  :  Z ₁ ) - точка, тогда формула удвоения задается следующим образом:

• А = Х ₁ ²
• B = Y ₁ ²
• D = А  +  В
• G = ( X ₁  +  Y ₁ ) ²  -  D
• Х ₃ = (2 Y ₁  -  G ) × ( Х ₁  +  A  + 1)
• Y ₃ = ( G  - 2 X ₁ ) × ( Y ₁  +  B  + 1)
• Z ₃ = ( Х ₁  -  Y ₁ ) × ( G  + 2 D )

Стоимость этого алгоритма составляет три умножения + три квадрата + 11 сложений + 3 × 2.

Пример

Если - точка над кривой Гессе с параметром d = −1 , то координаты определяются как:${\displaystyle P=(-1:-1:1)}$${\displaystyle 2P=(X:Y:Z)}$

Х = (2. (−1) - 2) (−1 + 1 + 1) = −4

Y = (−4-2. (−1)) ((−1) + 1 + 1) = −2

Z = (−1 - (−1)) ((−4) + 2. 2) = 0

Это, ${\displaystyle 2P=(-4:-2:0)}$

Расширенные координаты [ править ]

Существует еще одна система координат, с помощью которой можно представить кривую Гессе; эти новые координаты называются расширенными координатами . Они могут ускорить сложение и удвоение. Для получения дополнительной информации об операциях с расширенными координатами см .:

http://hyperelliptic.org/EFD/g1p/auto-hessian-extended.html#addition-add-20080225-hwcd

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

${\displaystyle x=X/Z}$

${\displaystyle y=Y/Z}$

${\displaystyle XX=X\cdot X}$

${\displaystyle YY=Y\cdot Y}$

${\displaystyle ZZ=Z\cdot Z}$

${\displaystyle XY=2\cdot X\cdot Y}$

${\displaystyle YZ=2\cdot Y\cdot Z}$

${\displaystyle XZ=2\cdot X\cdot Z}$

См. Также [ править ]

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

Скрученные кривые Гессе

Внешние ссылки [ править ]

• http://hyperelliptic.org/EFD/g1p/index.html

Заметки [ править ]

Ссылки [ править ]

• Отто Гессе (1844 г.), «Убер умирает устранение дер Вариабельн aus drei algebraischen Gleichungen vom zweiten Grade mit zwei Variabeln», Журнал für die reine und angewandte Mathematik , 10, стр. 68–96
• Марк Джой, Жан-Жак Кискватер (2001). «Эллиптические кривые Гессе и атаки по боковым каналам». Криптографическое оборудование и встроенные системы - CHES 2001 . Конспект лекций по информатике. 2162 . Springer-Verlag Berlin Heidelberg 2001. С. 402–410. DOI : 10.1007 / 3-540-44709-1_33 . ISBN 978-3-540-42521-2.
• Н.П. Смарт (2001). «Гессенская форма эллиптической кривой». Криптографическое оборудование и встроенные системы - CHES 2001 . Конспект лекций по информатике. 2162 . Springer-Verlag Berlin Heidelberg 2001. С. 118–125. DOI : 10.1007 / 3-540-44709-1_11 . ISBN 978-3-540-42521-2.