Кривая Доче – Икарта – Кохеля, ориентированная на утроение - 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 (x,y)}$. «Точка в бесконечности» представляет собой нейтральный элемент для группового закона, и он записан в проективные координаты как 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{aligned}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{aligned}}}$

Удвоение

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

${\displaystyle {\begin{aligned}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{aligned}}}$

Отрицание

Учитывая точку ${\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 P=(x,y)}$ на ${\displaystyle T_{a}}$ записывается в новых якобианских координатах как ${\displaystyle P=(X:Y:Z:Z^{2})}$, куда ${\displaystyle x=X/Z^{2}}$ и ${\displaystyle y=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 y^{2}=x^{3}+3(x+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 C=3(A+B)}$

${\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 y^{2}=x^{3}+3(x+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}}$.

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

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

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

Примечания

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

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

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

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

• Кристоф Доче; Томас Икарт и Дэвид Р. Кохель (2006). Эффективное скалярное умножение с помощью разложения изогении (PDF). появился на PKC 2006 г., часть тома 3958 LNCS (серии лекций по информатике). Springer Verlag. С. 285–352.
• Дэниел Дж. Бернштейн, Таня Ланге (2007). Анализ и оптимизация односкалярного умножения эллиптических кривых (PDF). появился в G.L. Mullen, D. Panario, I.E. Шпарлински (ред.), Конечные поля и приложения (Материалы 8-й Международной конференции, Fq8, Мельбурн, Австралия, 9–13 июля 2007 г.). Классификация предметов математики.
• Д. Дж. Бернштейн, П. Биркнер, Т. Ланге и К. Питерс (2007). Оптимизация односкалярного умножения на эллиптической кривой с двойной базой (PDF). появился у К. Сринатана, К. Панду Ранган, М. Юнг (ред.), Труды 8-й Международной конференции по криптологии в Индии: прогресс в криптологии (Indocrypt 2007), 9–13 декабря 2007 г., Ченнаи, Индия. Springer.
• http://hyperelliptic.org/EFD/g1p/auto-3dik-standard.html