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

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

Определение

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

Позволять $K$ быть полем и рассмотрим эллиптическую кривую $E$ в следующем частном случае формы Вейерштрасса над $K$: $$Y^{2}+a_{1}XY+a_{3}Y=X^{3}$$где кривая имеет дискриминант $\Delta =\left(a_{3}^{3}\left(a_{1}^{3}-27a_{3}\right)\right)=a_{3}^{3}\delta .$Тогда точка $P=(0,0)$ имеет порядок 3.

Чтобы доказать это $P=(0,0)$ имеет порядок 3, заметим, что касательная к $E$ в $P$ это линия $Y=0$ который пересекает $E$ с кратностью 3 при $P$.

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

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

Сначала позвольте $\mu$ обозначим корень многочлена $$T^{3}-\delta T^{2}+{\delta ^{2} \over 3}T+a_{3}\delta ^{2}=0.$$

Затем $$\mu ={\delta -a_{1}\delta ^{2/3} \over 3}.$$

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

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

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

которая называется кубической формой Гессе (в проективных координатах ) $$C:x^{3}+y^{3}+1=3Dxy$$

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

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

Начиная с кривой Гессе, бирационально эквивалентное уравнение Вейерштрасса имеет вид $$v^{2}=u^{3}-27D\left(D^{3}+8\right)u+54\left(D^{6}-20D^{3}-8\right),$$при преобразованиях: $$(x,y)=\left(\eta \left(u+9D^{2}\right),-1+\eta \left(3D^{3}-Dx-12\right)\right)$$и $$(u,v)=\left(-9D^{2}+\varepsilon x,3\varepsilon \left(y-1\right)\right)$$где: $$\eta ={\frac {6\left(D^{3}-1\right)\left(v+9D^{3}-3Du-36\right)}{\left(u+9D^{2}\right)^{3}+\left(3D^{3}-Du-12\right)^{3}}}$$и $$\varepsilon ={\frac {12\left(D^{3}-1\right)}{Dx+y+1}}$$

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

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

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

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

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

удвоение

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

$$[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)$$

Добавление

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

$$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 ) . Затем:

$$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 ₂ ) на эллиптической кривой Гессе:

$$(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 ₁ Икс ₂

Х ₃ = Б 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

З ₃ = 0 − 0 = 0

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

удвоение

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

• А = Х ₁ ²
• Б = Y ₁ ²
• Д = А + Б
• G = ( X ₁ + Y ₁ ) ² − Д
• Икс ₃ знак равно (2 Y ₁ - г ) × ( Икс ₁ + А + 1)
• Y ₃ знак равно ( г - 2 Икс ₁ ) × ( Y ₁ + B + 1)
• Z ₃ знак равно ( Икс ₁ - Y ₁ ) × ( г + 2 D )

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

Пример

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

X = (2 . (−1) − 2) (−1 + 1 + 1) = −4

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

Z = (−1 − (−1)) ((−4) + 2, 2) = 0

То есть, $2P=(-4:-2:0)$

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

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

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

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

• $x=X/Z$
• $y=Y/Z$
• $XX=X\cdot X$
• $YY=Y\cdot Y$
• $ZZ=Z\cdot Z$
• $XY=2\cdot X\cdot Y$
• $YZ=2\cdot Y\cdot Z$
• $XZ=2\cdot X\cdot Z$

См. также

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

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

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

Ссылки

• Отто Гессе (1844), «Об исключении переменных из трех алгебраических уравнений второй степени с двумя переменными», Журнал чистой и прикладной математики , 10, стр. 68–96.
• Марк Джой, Жан-Жак Кискатер (2001). «Эллиптические кривые Гессеса и атаки по боковым каналам». Криптографическое оборудование и встроенные системы — CHES 2001 . Конспекты лекций по информатике. Том. 2162. Springer-Verlag Berlin Heidelberg 2001. стр. 402–410. дои : 10.1007/3-540-44709-1_33 . ISBN  978-3-540-42521-2 .
• НП Смарт (2001). «Гессенская форма эллиптической кривой». Криптографическое оборудование и встроенные системы — CHES 2001 . Конспекты лекций по информатике. Том. 2162. Springer-Verlag Berlin Heidelberg 2001. стр. 118–125. дои : 10.1007/3-540-44709-1_11 . ISBN  978-3-540-42521-2 . S2CID   30487134 .