В математике , то кривая Витая Гессиан представляет собой обобщение Мешковины кривых ; он был введен в криптографию на основе эллиптических кривых, чтобы ускорить сложение и удвоение формул и иметь сильно унифицированную арифметику. В некоторых операциях (см. Последние разделы) он близок по скорости к кривым Эдвардса .
Определение [ править ]
Пусть K - поле . Согласно [1] скрученные кривые Гессе были введены Бернштейном , Ланге и Кохелем.
Скрученная форма Гессе в аффинных координатах имеет вид:
и в проективных координатах :
где и и , d в K
Обратите внимание , что эти кривые бирациональны для Мешковины кривых .
Кривая Гессе - это просто частный случай скрученной кривой Гессе с a = 1.
Рассматривая уравнение a · x 3 + y 3 + 1 = d · x · y , обратите внимание, что:
если имеет корень куба в K , существует единственное б такое , что а = Ь 3 .otherwise, необходимо рассмотреть поле расширения в К (например, К ( 1/3 )). Тогда, поскольку b 3 · x 3 = bx 3 , определяя t = b · x , для преобразования необходимо следующее уравнение (в форме Гессе):
.
Это означает, что скрученные кривые Гессе бирационально эквивалентны эллиптической кривой в форме Вейерштрасса .
Групповой закон [ править ]
Интересно проанализировать групповой закон эллиптической кривой, определяя формулы сложения и удвоения (поскольку атаки простого анализа мощности и дифференциального анализа мощности основаны на времени выполнения этих операций). В общем случае групповой закон определяется следующим образом: если три точки лежат на одной прямой, то сумма их равна нулю. Таким образом, по этому свойству явные формулы группового закона зависят от формы кривой.
Пусть 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 ) - это обратная точка P.
Кроме того, нейтральный элемент (в аффинной плоскости) равен: θ = (0, −1), а в проективных координатах: θ = (0: −1: 1).
В некоторых применениях эллиптической кривой криптографии и эллиптического метода кривого целочисленной факторизации ( ECM ) необходимо вычислить скалярные умножения из Р , скажем , [п] Р для некоторого целого числа п , и они основаны на двойном и добавлении метод; поэтому необходимы формулы сложения и удвоения.
Формулы сложения и удвоения для этой эллиптической кривой могут быть определены с использованием аффинных координат для упрощения записи:
Формулы сложения [ править ]
Пусть p = ( x 1 , y 1 ) и Q = ( x 2 , y 2 ); тогда R = P + Q = ( x 3 , y 3 ) определяется следующими уравнениями:
Формулы удвоения [ править ]
Пусть P = ( x , y ); тогда [2] P = ( x 1 , y 1 ) определяется следующими уравнениями:
Алгоритмы и примеры [ править ]
Здесь приведены некоторые действенные алгоритмы закона сложения и удвоения; они могут быть важны в криптографических вычислениях, и для этой цели используются проективные координаты.
Дополнение [ править ]
Стоимость этого алгоритма - 12 умножений, одно умножение на (константа) и 3 сложения.
Пример:
пусть P 1 = (1: −1: 1) и P 2 = (−2: 1: 1) - точки над скрученной кривой Гессе с a = 2 и d = -2, тогда R = P 1 + P 2 равно предоставлено:
То есть R = (0: −3: −3).
Удвоение [ править ]
Стоимость этого алгоритма - 3 умножения, одно умножение на константу, 3 сложения и 3 степени куба. Это лучший результат, полученный для данной кривой.
Пример:
пусть P = (1: −1: 1) будет точкой над кривой, определенной как a = 2 и d = -2, как указано выше, тогда дано R = [2] P = ( x 3 : y 3 : z 3 ) от:
То есть R = (−2: −3: 5).
См. Также [ править ]
Внешние ссылки [ править ]
- http://hyperelliptic.org/EFD/g1p/index.html
Ссылки [ править ]
- ^ "Скрученные кривые Гессе" . Проверено 28 февраля 2010 года . CS1 maint: discouraged parameter (link)
- http://hyperelliptic.org/EFD/g1p/auto-twistedhessian.html