Кривая Доче – Икарта – Кохеля, ориентированная на утроение - Википедия - Tripling-oriented Doche–Icart–Kohel curve

В кривая Доче – Икарта – Кохеля, ориентированная на утроение это форма эллиптическая кривая который использовался в последнее время в криптография; это особый тип Кривая Вейерштрасса. При определенных условиях некоторые операции, поскольку сложение, удвоение или утроение точек, быстрее вычислить с использованием этой формы. Кривая Доче – Икарта – Кохеля, ориентированная на утроение, часто называется с сокращением 3DIK был представлен Кристофом Доче, Томасом Икартом и Дэвидом Р. Кохелем в ^[1]

Определение

Ориентированная на утроение кривая Доша – Икарта – Кохеля уравнения

{ displaystyle y ^ {2} = x ^ {3} -3x ^ {2} -6x-3}

Позволять ${ displaystyle K}$ быть поле из характеристика разная форма 2 и 3.

Эллиптическая кривая в утроение ориентированной формы Доче – Икарта – Кохеля определяется уравнение:

{ displaystyle T_ {a} : y ^ {2} = x ^ {3} + 3a (x + 1) ^ {2}}

с ${ displaystyle a in K}$ .

Генерал точка п на ${ displaystyle T_ {a}}$ имеет аффинные координаты ${ Displaystyle (х, у)}$ . «Точка в бесконечности» представляет собой нейтральный элемент для группового закона, и он записан в проективные координаты как O = (0: 1: 0). Отрицание точки п = (Икс, у) относительно этого нейтрального элемента -п = (Икс, −у).

Групповой закон

Рассмотрим эллиптическую кривую в ориентированной на утроение форме Доче-Икарта-Кохеля в аффинные координаты:

{ displaystyle T_ {a}: quad y ^ {2} = x ^ {3} + 3a (x + 1) ^ {2}, qquad a neq 0, { tfrac {9} {4}} .}

Как и в других формах эллиптических кривых, между точками можно определить некоторые «операции», такие как добавление точек или удвоение (см. Также Групповой закон ). В следующих разделах приведены формулы для сложения, отрицания и удвоения. Формулы сложения и удвоения часто используются для других операций: с учетом точки п на эллиптической кривой можно вычислить [n] P, куда п является целое число, используя сложение и удвоение; вычисление кратных точек важно в криптография на основе эллиптических кривых И в Факторизация эллиптической кривой Ленстры.

Добавление

Данный ${ Displaystyle P_ {1} = (x_ {1}, y_ {1})}$ и ${ Displaystyle P_ {2} = (x_ {2}, y_ {2})}$ на ${ displaystyle T_ {a}}$ , смысл ${ Displaystyle P_ {3} = (x_ {3}, y_ {3}) = P_ {1} + P_ {2}}$ имеет координаты:

{ displaystyle { begin {align} x_ {3} & = { frac {1} {(x_ {2} -x_ {1}) ^ {2}}} left {- x_ {1} ^ { 3} + (x_ {2} -3a) x_ {1} ^ {2} + (x_ {2} ^ {2} + 6ax_ {2}) x_ {1} + (y_ {1} ^ {2} - 2y_ {2} y_ {1} + (- x_ {2} ^ {3} -3ax_ {2} ^ {2} + y_ {2} ^ {2})) right } y_ {3} & = { frac {1} {(x_ {2} -x_ {1}) ^ {3}}} left {(- y_ {1} + 2y_ {2}) x_ {1} ^ {3} + (-3ay_ {1} -3y_ {2} x_ {2} + 3ay_ {2}) x_ {1} ^ {2} + (3x_ {2} ^ {2} y_ {1} + 6ax_ {2} y_ { 1} -6ay_ {2} x_ {2}) x_ {1} right. & qquad qquad qquad qquad left. + (Y_ {1} ^ {3} -3y_ {2} y_ { 1} ^ {2} + (- 2x_ {2} ^ {3} -3ax_ {2} ^ {2} + 3y_ {2} ^ {2}) y_ {1} + (y_ {2} x_ {2} ^ {3} + 3ay_ {2} x_ {2} ^ {2} -y_ {2} ^ {3})) right } end {align}}}

Удвоение

Учитывая точку ${ Displaystyle P_ {1} = (x_ {1}, y_ {1})}$ на ${ displaystyle T_ {a}}$ , смысл ${ Displaystyle P_ {3} = (x_ {3}, y_ {3}) = 2P_ {1}}$ имеет координаты:

{ displaystyle { begin {align} x_ {3} & = { frac {9} {4y_ {1} ^ {2} x_ {1} ^ {4}}} + { frac {9} {y_ { 1} ^ {2} ax_ {1} ^ {3}}} + left ({ frac {9} {y_ {1} ^ {2} a ^ {2}}} + { frac {9} { y_ {1} ^ {2} a}} right) x_ {1} ^ {2} + left ({ frac {18} {y_ {1} ^ {2} a ^ {2}}} - 2 right) x_ {1} + { frac {9} {y_ {1} ^ {2} a ^ {2} -3a}} y_ {3} & = - { frac {27} {8y_ { 1} ^ {3} x_ {1} ^ {6}}} - { frac {81} {4y_ {1} ^ {3} ax_ {1} ^ {5}}} + left (- { frac {81} {2y_ {1} ^ {3} a ^ {2}}} - { frac {81} {4y_ {1} ^ {3} a}} right) x_ {1} ^ {4} + left (- { frac {27} {y_ {1} ^ {3} a ^ {3}}} - { frac {81} {y_ {1} ^ {3} a ^ {2}}} + { frac {9} {2y_ {1}}} right) x_ {1} ^ {3} + left (- { frac {81} {y_ {1} ^ {3} a ^ {3}} } - { frac {81} {2y_ {1} ^ {3}}} a ^ {2} + { frac {27} {2y_ {1} a}} right) x_ {1} ^ {2} & qquad qquad qquad qquad + left (- { frac {81} {y_ {1} ^ {3} a ^ {3}}} + { frac {9} {y_ {1}) a ^ {2}}} + { frac {9} {y_ {1} a}} right) x_ {1} + left (- { frac {27} {y_ {1} ^ {3} a ^ {3}}} + { frac {9} {y_ {1} a ^ {2}}} - y_ {1} right) end {выравнивается}}}

Отрицание

Учитывая точку ${ Displaystyle P_ {1} = (x_ {1}, y_ {1})}$ на ${ displaystyle T_ {a}}$ , это отрицание относительно нейтрального элемента ${ displaystyle (0: 1: 0)}$ является ${ displaystyle -P_ {1} = (x_ {1}, - y_ {1})}$ .

Есть и другие формулы, приведенные в ^[2] для ориентированных на утроение кривых Доче – Икарта – Кохеля для быстрой операции утроения и смешанного сложения.

Новые якобианские координаты

Для расчета на этих кривых точки обычно представлены в новые якобианские координаты (J^п):

точка в новых якобианских координатах имеет вид ${ Displaystyle P = (X: Y: Z: Z ^ {2})}$ ; более того:

{ Displaystyle P = (X: Y: Z: Z ^ {2}) = ( lambda ^ {2} X: lambda ^ {3} Y: lambda Z: lambda ^ {2} Z ^ {2 }),}

для любого ${ displaystyle lambda in K}$ .

Это означает, например, что точка ${ Displaystyle P = (X: Y: Z: Z ^ {2})}$ и точка ${ displaystyle Q = (4X: 8Y: 2Z: 4Z ^ {2})}$ (за ${ displaystyle lambda = 2}$ ) на самом деле одинаковы.

Итак, аффинная точка ${ Displaystyle Р = (х, у)}$ на ${ displaystyle T_ {a}}$ записывается в новых якобианских координатах как ${ Displaystyle P = (X: Y: Z: Z ^ {2})}$ , куда ${ Displaystyle х = Х / Z ^ {2}}$ и ${ Displaystyle у = Y / Z ^ {3}}$ ; таким образом, уравнение для ${ displaystyle T_ {a}}$ становится:

{ displaystyle T_ {a} : Y ^ {2} = X ^ {3} + 3aZ ^ {2} (X + Z ^ {2}) ^ {2}.}

Период, термин ${ displaystyle Z ^ {2}}$ точки на кривой делает смешанное добавление (это сложение двух точек в разных системы координат ) более эффективным.

В нейтральный элемент в новых якобианских координатах ${ displaystyle (1: 1: 0: 0)}$ .

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

Добавление

Следующий алгоритм представляет собой сумму двух точек. ${ displaystyle P_ {1}}$ и ${ displaystyle P_ {2}}$ на эллиптической кривой в форме Доче-Икарта-Кохеля, ориентированной на утроение. Результат - точка ${ displaystyle P_ {3} = (X_ {3}, Y_ {3}, Z_ {3}, ZZ_ {3})}$ .Предполагается, что ${ displaystyle Z_ {2} = 1}$ и это ${ displaystyle a_ {3} = 3a}$ Стоимость этой реализации составляет 7M + 4S + 1 * a3 + 10add + 3 * 2 + 1 * 4, где M указывает умножения, S квадраты, a3 указывает умножение на константу a.₃, add представляет необходимое количество добавлений.

${ displaystyle A = X_ {2} ZZ_ {1}}$

${ displaystyle B = Y_ {2} ZZ_ {1} Z_ {1}}$

${ displaystyle C = X_ {1} -A}$

${ displaystyle D = 2 (Y_ {1} -B)}$

${ displaystyle F = C ^ {2}}$

${ displaystyle F_ {4} = 4F}$

${ displaystyle Z_ {3} = (Z_ {1} + C) ^ {2} -ZZ_ {1} -F}$

${ displaystyle E = {Z_ {3}} ^ {2}}$

${ displaystyle G = CF_ {4}}$

${ displaystyle H = AF_ {4}}$

${ displaystyle X_ {3} = D ^ {2} -G-2H-a_ {3} E}$

${ displaystyle Y_ {3} = D (H-X_ {3}) - 2BG}$

${ displaystyle ZZ_ {3} = E}$

Пример

Позволять ${ displaystyle P_ {1} = (1, { sqrt {13}})}$ и ${ displaystyle P_ {2} = (0, { sqrt {3}})}$ аффинные точки на эллиптической кривой над ${ Displaystyle mathbb {R}}$ :

${ Displaystyle у ^ {2} = х ^ {3} +3 (х + 1) ^ {2}}$ .

Потом:

${ displaystyle A = X_ {2} ZZ_ {1} = 0}$

${ displaystyle B = Y_ {2} ZZ_ {1} Z_ {1} = { sqrt {3}}}$

${ displaystyle C = X_ {1} -A = 1}$

${ displaystyle D = 2 (Y_ {1} -B) = 2 ({ sqrt {13}} - { sqrt {3}})}$

${ Displaystyle F = C ^ {2} = 1}$

${ displaystyle F_ {4} = 4F = 4}$

${ Displaystyle Z_ {3} = (Z_ {1} + C) ^ {2} -ZZ_ {1} -F = 2}$

${ displaystyle E = {Z_ {3}} ^ {2} = 4}$

${ displaystyle G = CF_ {4} = 4}$

${ displaystyle H = AF_ {4} = 0}$

${ displaystyle X_ {3} = D ^ {2} -G-2H-a_ {3} E = 48-8 { sqrt {39}}}$

${ displaystyle Y_ {3} = D (H-X_ {3}) - 2BG = 296 { sqrt {3}} - 144 { sqrt {13}}}$

${ displaystyle ZZ_ {3} = E = 4}$

Обратите внимание, что в этом случае ${ Displaystyle Z_ {1} = Z_ {2} = 1}$ В результате получается точка ${ displaystyle P_ {3} = (X_ {3}, Y_ {3}, Z_ {3}, ZZ_ {3}) = (48-8 { sqrt {39}}, 296 { sqrt {3}} -144 { sqrt {13}}, 2,4)}$ , что в аффинных координатах равно ${ displaystyle P_ {3} = (12-2 { sqrt {39}}, 37 { sqrt {3}} - 18 { sqrt {13}})}$ .

Удвоение

Следующий алгоритм представляет собой удвоение точки. ${ displaystyle P_ {1}}$ на эллиптической кривой в ориентированной на утроение форме Доче-Икарта-Кохеля. Предполагается, что ${ displaystyle a_ {3} = 3a}$ , ${ displaystyle a_ {2} = 2a}$ Стоимость этой реализации составляет 2M + 7S + 1 * a2 + 1 * a3 + 12add + 2 * 2 + 1 * 3 + 1 * 8; здесь M представляет собой умножение, S квадрат, a2 и a3 указывает умножение на константы a₂ и₃ соответственно, а add указывает на дополнения.

${ displaystyle A = {X_ {1}} ^ {2}}$

${ displaystyle B = a_ {2} ZZ_ {1} (X_ {1} + ZZ_ {1})}$

${ Displaystyle С = 3 (А + В)}$

${ displaystyle D = {Y_ {1}} ^ {2}}$

${ displaystyle E = D ^ {2}}$

${ Displaystyle Z_ {3} = (Y_ {1} + Z_ {1}) ^ {2} -D-ZZ_ {1}}$

${ displaystyle ZZ_ {3} = Z_ {3} ^ {2}}$

${ Displaystyle F = 2 ((X_ {1} + D) ^ {2} -A-E)}$

${ displaystyle X_ {3} = C ^ {2} -a_ {3} ZZ_ {3} -2F}$

${ displaystyle Y_ {3} = C (F-X_ {3}) - 8E}$

Пример

Позволять ${ displaystyle P_ {1} = (0, { sqrt {3}})}$ быть точкой на ${ Displaystyle у ^ {2} = х ^ {3} +3 (х + 1) ^ {2}}$ .

Потом:

${ displaystyle A = {X_ {1}} ^ {2} = 0}$

${ displaystyle B = a_ {2} ZZ_ {1} (X_ {1} + ZZ_ {1}) = 2}$

${ Displaystyle C = 3 (A + B) = 6}$

${ displaystyle D = {Y_ {1}} ^ {2} = 3}$

${ Displaystyle E = D ^ {2} = 9}$

${ displaystyle Z_ {3} = (Y_ {1} + Z_ {1}) ^ {2} -D-ZZ_ {1} = 2 { sqrt {3}}}$

${ displaystyle ZZ_ {3} = Z_ {3} ^ {2} = 12}$

${ Displaystyle F = 2 ((X_ {1} + D) ^ {2} -A-E) = 0}$

${ displaystyle X_ {3} = C ^ {2} -a_ {3} ZZ_ {3} -2F = 0}$

${ displaystyle Y_ {3} = C (F-X_ {3}) - 8E = -72}$

Обратите внимание, что здесь точка находится в аффинных координатах, поэтому ${ displaystyle Z_ {1} = 1}$ В результате получается точка ${ displaystyle P_ {3} = (0, -72,2 { sqrt {3}}, 12)}$ , что в аффинных координатах равно ${ displaystyle P_ {3} = (0, - { sqrt {3}})}$ .

Эквивалентность форме Вейерштрасса

Любая эллиптическая кривая бирационально эквивалентный другому, написанному в форме Вейерштрасса.

Следующее скрученный кривая Доче-Икарта-Кохеля, ориентированная на утроение:

{ displaystyle T_ {a, lambda}: quad y ^ {2} = x ^ {3} +3 lambda a (x + lambda) ^ {2}}

можно преобразовать к форме Вейерштрасса с помощью карта:

{ displaystyle (x, y) mapsto (x- lambda a, y).}

Таким образом ${ displaystyle T_ {a, lambda}}$ становится:

{ displaystyle y ^ {2} = x ^ {3} -3 { lambda} ^ {2} a (a-2) x + { lambda} ^ {3} a (2a ^ {2} -6a + 3 )}

.

И наоборот, для эллиптической кривой в форме Вейерштрасса:

{ displaystyle E_ {c, d}: quad y ^ {2} = x ^ {3} + cx ^ {2} + d}

,

можно найти "соответствующую" ориентированную на утроение кривую Доче – Икарта – Кохеля, используя следующее соотношение:

{ displaystyle lambda = { frac {-3d (a-2)} {a (2a ^ {2} -6a + 3)}}}

куда $а$ это корень полинома

{ displaystyle 6912a (a-2) ^ {3} -j (4a-9),}

куда

{ displaystyle j = { frac {6912c ^ {3}} {4c ^ {3} + 27d ^ {2}}}}

это j-инвариантный эллиптической кривой ${ displaystyle E_ {c, d}}$ .

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

Внутренняя ссылка

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

Примечания

^ Кристоф Доче, Томас Икарт и Дэвид Р. Кохель, Эффективное скалярное умножение с помощью разложения изогении
^ Кристоф Доче, Томас Икарт и Дэвид Р. Кохель, Эффективное скалярное умножение с помощью разложения изогении, стр. 198-199

внешняя ссылка

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

Кривая Доче – Икарта – Кохеля, ориентированная на утроение - Википедия - Tripling-oriented Doche–Icart–Kohel curve

Содержание

Определение

Групповой закон

Добавление

Удвоение

Отрицание

Новые якобианские координаты

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

Добавление

Пример

Удвоение

Пример

Эквивалентность форме Вейерштрасса

Внутренняя ссылка

Примечания

внешняя ссылка

Рекомендации