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

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

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

Чтобы доказать, что имеет порядок 3, заметим, что касательная к точке — это прямая , пересекающаяся с кратностью 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 {(\mu -\delta )}{\mu }}}$

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

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

в аффинной плоскости (удовлетворяющей и ).${\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(3D^{3}-Du-12\right)^{3}}}}$$$${\displaystyle \varepsilon ={\frac {12\left(D^{3}-1\right)}{Dx+y+1}}}$$

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

В этом случае правильным способом будет использование формул Коши-Дебове, получая точку на бесконечности θ = (1 : −1 : 0) , то есть нейтральный элемент (обратный θ снова есть θ ). Пусть 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), то x -координата − P равна y ₁ , а y -координата − P равна x ₁ , т.е. или в проективных координатах .${\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 , тогда алгоритм задается следующим образом:

А = Х ₁ У ₂

В = Y1 _X2 ​_​

X ₃ = B Y ₁ - Y ₂ A

Y ₃ = X ₁ A - B X ₂

Z3 = Y2X2 - _X1Y1​​​​_​​_​

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

Пример

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

Х ₃ = 0 − 1 = −1

Y3 ₌ −1−0 = −1

Z3 = 0 − 0 = ₀

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

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

• А = Х ₁ ²
• В = Y ₁ ²
• Д = А + Б
• Г = ( Х ₁ + Y ₁ ) ² − Д
• X ₃ = (2 Y ₁ − G ) × ( X ₁ + A + 1)
• Y ₃ = ( Г − 2 X ₁ ) × ( Y ₁ + В + 1)
• Z ₃ = ( X ₁ − Y ₁ ) × ( Г + 2 Д )

Стоимость этого алгоритма составляет три умножения + три возведения в квадрат + 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), «Über die Elimination der Variabeln aus drei алгебраишен Gleichungen vom zweiten Grade mit zwei Variabeln», Journal 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.
• NP Smart (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. S2CID  30487134.