Скрученные кривые Гессе
Тип эллиптической кривой

В математике скрученные кривые Гессе являются обобщением кривых Гессе ; они были введены в криптографии эллиптических кривых для ускорения формул сложения и удвоения и для строгой унификации арифметики. В некоторых операциях (см. последние разделы) они близки по скорости к кривым Эдвардса . Скрученные кривые Гессе были введены Бернштейном , Ланге и Коэлем. [1]

Определение

Скрученная кривая Гессе уравнения 10 х 3 + у 3 + 1 = 15 х у {\displaystyle 10x^{3}+y^{3}+1=15xy}

Пусть K — поле . Скрученная гессиановая форма в аффинных координатах задается выражением:

а ⋅ х 3 + у 3 + 1 = г ⋅ х ⋅ у {\displaystyle a\cdot x^{3}+y^{3}+1=d\cdot x\cdot y}

и в проективных координатах по

а ⋅ Х 3 + И 3 + З 3 = г ⋅ Х ⋅ И ⋅ З , {\displaystyle a\cdot X^{3}+Y^{3}+Z^{3}=d\cdot X\cdot Y\cdot Z,}

где x = X / Z и y = Y / Z и a , d ∈ K. Эти кривые бирационально эквивалентны кривым Гессе , а кривые Гессе являются всего лишь частным случаем скрученных кривых Гессе, в которых a = 1 .

Рассматривая уравнение a · x 3 + y 3 + 1 = d · x · y , отметим, что если a имеет кубический корень в K , то существует единственный b такой, что a = b 3 ; в противном случае необходимо рассмотреть поле расширения K , такое как K ( a 1/3 ) . Тогда, поскольку b 3 x 3 = ax 3 , определяющее t = bx , для выполнения преобразования необходимо следующее уравнение (в форме Гессе):

т 3 + у 3 + 1 = г ⋅ х ⋅ у {\displaystyle t^{3}+y^{3}+1=d\cdot x\cdot y} .

Это означает, что скрученные кривые Гессе бирационально эквивалентны эллиптическим кривым в форме Вейерштрасса .

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

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

Пусть P = ( x 1 , y 1 ) — точка; тогда ее обратная точка — − P = ( x 1 / y 1 , 1/ y 1 ) на плоскости. В проективных координатах пусть P = ( X  : Y  : Z ) — точка; тогда − P = ( X 1 / Y 1  : 1/ Y 1  : Z ) — ее обратная точка. Кроме того, нейтральный элемент в аффинной плоскости — θ = (0, −1) , а в проективных координатах — θ = (0 : −1 : 1) .

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

Формулы сложения

Пусть P = ( x 1 , y 1 ) и Q = ( x 2 , y 2 ) ; тогда R = P + Q = ( x 3 , y 3 ) , где

х 3 = х 1 − у 1 2 ⋅ х 2 ⋅ у 2 а ⋅ х 1 ⋅ у 1 ⋅ х 2 2 − у 2 {\displaystyle x_{3}={\frac {x_{1}-y_{1}^{2}\cdot x_{2}\cdot y_{2}}{a\cdot x_{1}\cdot y_{1}\cdot x_{2}^{2}-y_{2}}}}

у 3 = у 1 ⋅ у 2 2 − а ⋅ х 1 2 ⋅ х 2 а ⋅ х 1 ⋅ у 1 ⋅ х 2 2 − у 2 {\displaystyle y_{3}={\frac {y_{1}\cdot y_{2}^{2}-a\cdot x_{1}^{2}\cdot x_{2}}{a\cdot x_{1}\cdot y_{1}\cdot x_{2}^{2}-y_{2}}}}

Формулы удвоения

Пусть P = ( x , y ) ; тогда [2] P = ( x 1 , y 1 ) , где

х 1 = х − у 3 ⋅ х а ⋅ у ⋅ х 3 − у {\displaystyle x_{1}={\frac {xy^{3}\cdot x}{a\cdot y\cdot x^{3}-y}}}

у 1 = у 3 − а ⋅ х 3 а ⋅ у ⋅ х 3 − у {\displaystyle y_{1}={\frac {y^{3}-a\cdot x^{3}}{a\cdot y\cdot x^{3}-y}}}

Алгоритмы и примеры

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

Добавление

А = Х 1 ⋅ З 2 {\displaystyle A=X_{1}\cdot Z_{2}}

Б = З 1 ⋅ З 2 {\displaystyle B=Z_{1}\cdot Z_{2}}

С = И 1 Х 2 {\displaystyle C=Y_{1}X_{2}}

Д = И 1 ⋅ И 2 {\displaystyle D=Y_{1}\cdot Y_{2}}

Э = З 1 ⋅ И 2 {\displaystyle E=Z_{1}\cdot Y_{2}}

Ф = а ⋅ Х 1 ⋅ Х 2 {\displaystyle F=a\cdot X_{1}\cdot X_{2}}

Х 3 = А ⋅ Б − С ⋅ Д {\displaystyle X_{3}=A\cdot BC\cdot D}

И 3 = Д ⋅ Э − Ф ⋅ А {\displaystyle Y_{3}=D\cdot EF\cdot A}

З 3 = Ф ⋅ С − Б ⋅ Э {\displaystyle Z_{3}=F\cdot CB\cdot E}

Стоимость этого алгоритма составляет 12 умножений, одно умножение на константу и 3 сложения.

Пример:

Пусть P 1 = (1 : −1 : 1) и P 2 = (−2 : 1 : 1) — точки на скрученной кривой Гессе с ( a , d ) = (2, −2) . Тогда R = P 1 + P 2 определяется как:

А = − 1 ; Б = − 1 ; С = − 1 ; Д = − 1 ; Э = 1 ; Ф = 2 ; {\displaystyle A=-1;B=-1;C=-1;D=-1;E=1;F=2;}

х 3 = 0 {\displaystyle x_{3}=0}
у 3 = − 3 {\displaystyle y_{3}=-3}
з 3 = − 3 {\displaystyle z_{3}=-3}

То есть, R = (0 : −3 : −3) .

Удвоение

Д = Х 1 3 {\displaystyle D=X_{1}^{3}}

Э = И 1 3 {\displaystyle E=Y_{1}^{3}}

Ф = З 1 3 {\displaystyle F=Z_{1}^{3}}

Г = а ⋅ Д {\displaystyle G=a\cdot D}

Х 3 = Х 1 ⋅ ( Э − Ф ) {\displaystyle X_{3}=X_{1}\cdot (EF)}

И 3 = З 1 ⋅ ( Г − Э ) {\displaystyle Y_{3}=Z_{1}\cdot (GE)}

З 3 = И 1 ⋅ ( Ф − Г ) {\displaystyle Z_{3}=Y_{1}\cdot (FG)}

Стоимость этого алгоритма составляет 3 умножения, одно умножение на константу, 3 сложения и 3 возведения в куб. Это лучший результат, полученный для этой кривой.

Пример:

Пусть P = (1 : −1 : 1) — точка на кривой, определяемая уравнением ( a , d ) = (2, −2) , как указано выше; тогда R = [2] P = ( x3 , y3 , z3 ) определяется по формуле:

Д = 1 ; Э = − 1 ; Ф = 1 ; Г = − 4 ; {\displaystyle D=1;E=-1;F=1;G=-4;}

х 3 = − 2 {\displaystyle x_{3}=-2}
у 3 = − 3 {\displaystyle y_{3}=-3}
з 3 = − 5 {\displaystyle z_{3}=-5}

То есть, R = (−2 : −3 : 5) .

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

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

Ссылки

  1. ^ "Скрученные кривые Гессе" . Получено 28 февраля 2010 г.
  • http://hyperelliptic.org/EFD/g1p/auto-twistedhessian.html
Взято с "https://en.wikipedia.org/w/index.php?title=Скрученные_кривые_Гессиана&oldid=1249843296"