кривая Якоби

Эта статья может содержать избыточные или нерелевантные примеры . Пожалуйста, помогите улучшить статью, добавив описательный текст и удалив менее релевантные примеры . ( Апрель 2022 г. )

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Jacobian curve" – news · newspapers · books · scholar · JSTOR (December 2009) (Learn how and when to remove this message)

В математике кривая Якоби — это представление эллиптической кривой, отличное от обычной, определяемой уравнением Вейерштрасса . Иногда она используется в криптографии вместо формы Вейерштрасса, поскольку может обеспечить защиту от атак в стиле простого и дифференциального анализа мощности (SPA); действительно, возможно использовать общую формулу сложения также для удвоения точки на эллиптической кривой этой формы: таким образом, две операции становятся неотличимыми от некоторой информации по побочным каналам. ^[1] Кривая Якоби также предлагает более быструю арифметику по сравнению с кривой Вейерштрасса.

Кривая Якоби может быть двух типов: пересечение Якоби , которое задается пересечением двух поверхностей, и квартика Якоби .

Если задана эллиптическая кривая, можно выполнять некоторые «операции» между ее точками: например, можно сложить две точки P и Q, получив точку P + Q , принадлежащую кривой; если задана точка P на эллиптической кривой, можно «удвоить» P, что означает найти [2] P = P + P (квадратные скобки используются для обозначения [n]P , точки P , добавленной n раз), а также найти отрицание P , что означает найти – P. Таким образом, точки эллиптической кривой образуют группу . Обратите внимание, что единичный элемент групповой операции не является точкой на аффинной плоскости, он появляется только в проективных координатах: тогда O = (0: 1: 0) является «точкой на бесконечности», то есть нейтральным элементом в групповом законе . Формулы сложения и удвоения также полезны для вычисления [n]P , n -го кратного точки P на эллиптической кривой: эта операция считается наиболее часто используемой в криптографии эллиптических кривых .

Эллиптическая кривая E над полем K может быть представлена ​​в форме Вейерштрасса y ² = x ³ + ax + b , где a , b находятся в K . Позже будут важны точки порядка 2 , то есть P на E такие, что [2] P = O и P ≠ O . Если P = ( p , 0) — точка на E , то она имеет порядок 2; в более общем случае точки порядка 2 соответствуют корням многочлена f (x) = x ³ + ax + b .

С этого момента мы будем использовать E _a,b для обозначения эллиптической кривой с формой Вейерштрасса y ² = x ³ + ax + b .

Если E _a,b таков, что кубический многочлен x ³ + ax + b имеет три различных корня в K и b = 0, мы можем записать E _a,b в нормальной форме Лежандра :

E _a,b : y ² = x(x + 1)(x + j)

В этом случае у нас есть три точки второго порядка: (0, 0), (–1, 0), (– j , 0). В этом случае мы используем обозначение E[j] . Обратите внимание, что j можно выразить через a , b .

Эллиптическая кривая в P ³ ( K ) может быть представлена ​​как пересечение двух квадратичных поверхностей :

${\displaystyle Q:\{Q_{1}(X_{0},X_{1},X_{2},X_{3})=0\}\cap \{Q_{2}(X_{0},X_{1},X_{2},X_{3})=0\}}$

Можно определить форму Якоби эллиптической кривой как пересечение двух квадрик. Пусть E _a,b — эллиптическая кривая в форме Вейерштрасса, применим к ней следующее отображение :

${\displaystyle \Phi :(x,y)\mapsto (X,Y,Z,T)=(x,y,1,x^{2})}$

Мы видим, что справедлива следующая система уравнений :

${\displaystyle \mathbf {S} :{\begin{cases}X^{2}-TZ=0\\Y^{2}-aXZ-bZ^{2}-TX=0\end{cases}}}$

Кривая E[j] соответствует следующему пересечению поверхностей в P ³ ( K ):

${\displaystyle \mathbf {S} 1:{\begin{cases}X^{2}+Y^{2}-T^{2}=0\\kX^{2}+Z^{2}-T^{2}=0\end{cases}}}$.

«Особый случай», E[0] , эллиптическая кривая имеет двойную точку и, таким образом, является сингулярной .

S1 получается путем применения к E[j ] преобразования :

ψ: E[j] → S1

${\displaystyle (x,y)\mapsto (X,Y,Z,T)=(-2y,x^{2}-j,x^{2}+2jx+j,x^{2}+2x+j)}$

${\displaystyle O=(0:1:0)\mapsto (0,1,1,1)}$

Для S1 нейтральным элементом группы является точка (0, 1, 1, 1), то есть образ O = (0: 1: 0) при ψ.

Даны две точки на S1 : P ₁ = ( X ₁ , Y ₁ , Z ₁ , T ₁ ) и P ₂ = ( X ₂ , Y ₂ , Z ₂ , T _{2 ),} координаты точки P ₃ = P ₁ + P ₂ равны:

${\displaystyle X_{3}=T_{1}Y_{2}X_{1}Z_{2}+Z_{1}X_{2}Y_{1}T_{2}}$

${\displaystyle Y_{3}=T_{1}Y_{2}Y_{1}T_{2}-Z_{1}X_{2}X_{1}Z_{2}}$

${\displaystyle Z_{3}=T_{1}Z_{1}T_{2}Z_{2}-kX_{1}Y_{1}X_{2}Y_{2}}$

${\displaystyle T_{3}=(T_{1}Y_{2})^{2}+(Z_{1}X_{2})^{2}}$

Эти формулы также действительны для удвоения: достаточно, чтобы P ₁ = P _2. Таким образом, добавление или удвоение точек в S1 — это операции, которые требуют 16 умножений плюс одно умножение на константу ( k ).

Также можно использовать следующие формулы для удвоения точки P ₁ и найти P ₃ = [2] P ₁ :

${\displaystyle X_{3}=2Y_{1}T_{1}Z_{1}X_{1}}$

${\displaystyle Y_{3}=(T_{1}Y_{1})^{2}-(T_{1}Z_{1})^{2}+(Z_{1}Y_{1})^{2}}$

${\displaystyle Z_{3}=(T_{1}Z_{1})^{2}-(T_{1}Y_{1})^{2}+(Z_{1}Y_{1})^{2}}$

${\displaystyle T_{3}=(T_{1}Z_{1})^{2}+(T_{1}Y_{1})^{2}-(Z_{1}Y_{1})^{2}}$

Используя эти формулы, для удвоения точки требуется 8 умножений. Однако существуют еще более эффективные «стратегии» удвоения, которые требуют всего 7 умножений. ^[2] Таким образом, можно утроить точку с помощью 23 умножений; действительно, [3] P ₁ можно получить, сложив P ₁ с [2] P ₁ со стоимостью 7 умножений для [2] P ₁ и 16 для P ₁ + [2] P ₁ ^[2]

Пусть K = R или C и рассмотрим случай:

${\displaystyle \mathbf {S} 1:{\begin{cases}X^{2}+Y^{2}-T^{2}=0\\4X^{2}+Z^{2}-T^{2}=0\end{cases}}}$

Рассмотрим точки и : легко проверить, что P ₁ и P ₂ принадлежат S1 (достаточно убедиться, что эти точки удовлетворяют обоим уравнениям системы S1 ) .${\displaystyle P_{1}=(1,{\sqrt {3}},0,2)}$${\displaystyle P_{2}=(1,2,1,{\sqrt {5}})}$

Используя приведенные выше формулы для сложения двух точек, координаты для P ₃ , где P ₃ = P ₁ + P _{2 ,} равны:

${\displaystyle X_{3}=T_{1}Y_{2}X_{1}Z_{2}+Z_{1}X_{2}Y_{1}T_{2}=4}$

${\displaystyle Y_{3}=T_{1}Y_{2}Y_{1}T_{2}-Z_{1}X_{2}X_{1}Z_{2}=4{\sqrt {15}}}$

${\displaystyle Z_{3}=T_{1}Z_{1}T_{2}Z_{2}-kX_{1}Y_{1}X_{2}Y_{2}=-8{\sqrt {3}}}$

${\displaystyle T_{3}=(T_{1}Y_{2})^{2}+(Z_{1}X_{2})^{2}=16}$

Полученная точка — .${\displaystyle P_{3}=(4,4{\sqrt {15}},-8{\sqrt {3}},16)}$

Используя приведенные выше формулы удвоения, можно найти точку P ₃ = [2] P ₁ :

${\displaystyle X_{3}=2Y_{1}T_{1}Z_{1}X_{1}=0}$

${\displaystyle Y_{3}=(T_{1}Y_{1})^{2}-(T_{1}Z_{1})^{2}+(Z_{1}Y_{1})^{2}=12}$

${\displaystyle Z_{3}=(T_{1}Z_{1})^{2}-(T_{1}Y_{1})^{2}+(Z_{1}Y_{1})^{2}=-12}$

${\displaystyle T_{3}=(T_{1}Z_{1})^{2}+(T_{1}Y_{1})^{2}-(Z_{1}Y_{1})^{2}=12}$

Итак, в этом случае P ₃ = [2] P ₁ = (0, 12, –12, 12).

Если задана точка P ₁ = ( X ₁ , Y ₁ , Z ₁ , T ₁ ) в S1 , то ее отрицание равно − P ₁ = (− X ₁ , Y ₁ , Z ₁ , T ₁ )

Если заданы две аффинные точки P ₁ = ( x ₁ , y ₁ , z ₁ ) и P ₂ = ( x ₂ , y ₂ , z ₂ ), их сумма представляет собой точку P ₃ с координатами:

${\displaystyle x_{3}={\frac {y_{2}x_{1}z_{2}+z_{1}x_{2}y_{1}}{(y_{2}^{2}+(z_{1}x_{2})^{2})}}}$

${\displaystyle y_{3}={\frac {y_{2}y_{1}-z_{1}x_{2}x_{1}z_{2}}{(y_{2}^{2}+(z_{1}x_{2})^{2})}}}$

${\displaystyle z_{3}={\frac {z_{1}z_{2}-ax_{1}y_{1}x_{2}y_{2}}{(y_{2}^{2}+(z_{1}x_{2})^{2})}}}$

Эти формулы справедливы также для удвоения при условии P ₁ = P ₂ .

Существует другой вид системы координат, с помощью которой можно представить точку в пересечении Якоби. Дана следующая эллиптическая кривая в форме пересечения Якоби:

${\displaystyle \mathbf {S} 1:{\begin{cases}x^{2}+y^{2}=1\\kx^{2}+z^{2}=1\end{cases}}}$

расширенные координаты описывают точку P = (x, y, z) с переменными X, Y, Z, T, XY, ZT , где:

${\displaystyle x=X/T}$

${\displaystyle y=Y/T}$

${\displaystyle z=Z/T}$

${\displaystyle XY=X\cdot Y}$

${\displaystyle ZT=Z\cdot T}$

Иногда эти координаты используются, так как они более удобны (с точки зрения времени-стоимости) в некоторых конкретных ситуациях. Для получения дополнительной информации об операциях, основанных на использовании этих координат, см. http://hyperelliptic.org/EFD/g1p/auto-jintersect-extended.html

Эллиптическая кривая в форме Якоби четвертого порядка может быть получена из кривой E _a,b в форме Вейерштрасса с хотя бы одной точкой порядка 2. Следующее преобразование f переводит каждую точку E _a,b в точку в координатах Якоби, где (X: Y: Z) = (sX: s ² Y: sZ) .

ж: Е _{а, б} → J

${\displaystyle (p,0)\mapsto (0:-1:1)}$

${\displaystyle (x,y)\neq (p,0)\mapsto (2(x-p):(2x+p)(x-p)^{2}-y^{2}:y)}$

${\displaystyle O\mapsto (0:1:1)}$^[3]

Применяя f к E _a,b , получаем кривую в J следующего вида:

${\displaystyle C:\ Y^{2}=eX^{4}-2dX^{2}Z^{2}+Z^{4}}$^[3]

где:

${\displaystyle e={\frac {-(3p^{2}+4a)}{16}},\ \ d={\frac {3p}{4}}}$.

являются элементами в K. C представляет собой эллиптическую кривую в форме Якоби четвертого порядка в координатах Якоби.

Общая форма кривой четвертого порядка Якоби в аффинных координатах имеет вид:

${\displaystyle y^{2}=ex^{4}+2ax^{2}+1}$,

где часто предполагается e = 1.

Нейтральным элементом группового закона C является проективная точка (0:1:1).

Если даны две аффинные точки и , их сумма представляет собой точку , такую, что:${\displaystyle P_{1}=(x_{1},y_{1})}$${\displaystyle P_{2}=(x_{2},y_{2})}$${\displaystyle P_{3}=(x_{3},y_{3})}$

${\displaystyle x_{3}={\frac {x_{1}y_{2}+y_{1}x_{2}}{1-e(x_{1}x_{2})^{2}}}}$

${\displaystyle y_{3}={\frac {((1+e(x_{1}x_{2})^{2})(y_{1}y_{2}+2ax_{1}x_{2})+2ex_{1}x_{2}({x_{1}}^{2}+{x_{2}}^{2}))}{(1-e(x_{1}x_{2})^{2})^{2}}}}$

Как и в пересечениях Якоби, в этом случае также можно использовать эту формулу для удвоения.

Даны две точки P ₁ = ( X ₁ : Y ₁ : Z ₁ ) и P ₂ = ( X ₂ : Y ₂ : Z ₂ ) в C′ , координаты точки P ₃ = ( X ₃ : Y ₃ : Z ₃ ), где P ₃ = P ₁ + P ₂ , задаются через P ₁ и P ₂ по формулам:

${\displaystyle X_{3}=X_{1}Z_{1}Y_{2}+Y_{1}X_{2}Z_{2}}$

${\displaystyle Y_{3}=\left(Z_{1}^{2}Z_{2}^{2}+eX_{1}^{2}X_{2}^{2}\right)\left(Y_{1}Y_{2}-2aX_{1}X_{2}Z_{1}Z_{2}\right)\ +\ 2eX_{1}X_{2}Z_{1}Z_{2}\left(X_{1}^{2}Z_{2}^{2}+Z_{1}^{2}X_{2}^{2}\right)}$

${\displaystyle Z_{3}=Z_{1}^{2}Z_{2}^{2}-eX_{1}^{2}X_{2}^{2}}$

Эту формулу можно использовать и для удвоения, при условии, что P ₂ = P ₁ : таким образом получается точка P ₃ = P ₁ + P ₁ = [2] P _{1 .}

Число умножений, необходимое для сложения двух точек, равно 13 плюс 3 умножения на константы: в частности, имеется два умножения на константу e и одно на константу a .

Существуют некоторые «стратегии» для сокращения операций, необходимых для сложения и удвоения точек: количество умножений можно уменьшить до 11 плюс 3 умножения на константы ( более подробную информацию см. в ^{[4], раздел 3).}

Число умножений можно сократить, работая над константами e и d : эллиптическую кривую в форме Якоби можно модифицировать, чтобы иметь меньшее число операций сложения и удвоения. Так, например, если константа d в ​​C значительно мала, умножение на d можно отменить; однако лучшим вариантом будет уменьшить e : если она мала, то не только одно, но и два умножения игнорируются.

Рассмотрим эллиптическую кривую E _4,0 , она имеет точку P порядка 2: P = ( p , 0) = (0, 0). Следовательно, a = 4, b = p = 0, так что мы имеем e = 1 и d = 1, а соответствующая форма Якоби четвертой степени имеет вид:

${\displaystyle C:\ Y^{2}=X^{4}+Z^{4}}$

Выбрав две точки и , можно найти их сумму P ₃ = P ₁ + P _{2 ,} используя формулы сложения, приведенные выше:${\displaystyle P_{1}=(1:{\sqrt {2}}:1)}$${\displaystyle P_{2}=(2:{\sqrt {17}}:1)}$

${\displaystyle X_{3}=1\cdot 1\cdot {\sqrt {17}}+{\sqrt {2}}\cdot 2\cdot 1={\sqrt {17}}+2{\sqrt {2}}}$

${\displaystyle Y_{3}=\left(1^{2}\cdot 1^{2}+1\cdot 1^{2}\cdot 2^{2}\right)\left({\sqrt {2}}\cdot {\sqrt {17}}-2\cdot 0\cdot 1\cdot 2\cdot 1\cdot 1\right)+2\cdot 1\cdot 1\cdot 2\cdot 1\cdot 1\left(1^{2}\cdot 1^{2}+1^{2}\cdot 2^{2}\right)=5{\sqrt {34}}+20}$

${\displaystyle Z_{3}=1^{2}\cdot 1^{2}-1\cdot 1^{2}\cdot 2^{2}=-3}$.

Так

${\displaystyle P_{3}=({\sqrt {17}}+2{\sqrt {2}}:5{\sqrt {34}}+20:-3)}$.

Используя те же формулы, получаем точку P ₄ = [2] P _{1 :}

${\displaystyle X_{3}=1\cdot 1\cdot {\sqrt {2}}+{\sqrt {2}}\cdot 1\cdot 1=2{\sqrt {2}}}$

${\displaystyle Y_{3}=\left(1+1\cdot 1\right)\left({\sqrt {2}}\cdot {\sqrt {2}}-2\cdot 0\cdot 1\cdot 1\cdot 1\cdot 1\right)+2\cdot 1\left(1^{2}\cdot 1^{2}+1^{2}\cdot 1^{2}\right)=8}$

${\displaystyle Z_{3}=1^{2}\cdot 1^{2}-1\cdot 1^{2}\cdot 1^{2}=0}$

Так

${\displaystyle P_{4}=(2{\sqrt {2}}:8:0)}$.

Отрицание точки P ₁ = ( X ₁ : Y ₁ : Z ₁ ) равно: − P ₁ = (− X ₁ : Y ₁ : Z ₁ )

Существуют и другие системы координат, которые можно использовать для представления точки в квартике Якоби: они используются для получения быстрых вычислений в определенных случаях. Для получения дополнительной информации о временных затратах, требуемых для операций с этими координатами, см. http://hyperelliptic.org/EFD/g1p/auto-jquartic.html

Дана аффинная квартика Якоби

${\displaystyle y^{2}=x^{4}+2ax^{2}+1}$

Координаты XXYZZ , ориентированные на удвоение, вводят дополнительный параметр кривой c, удовлетворяющий условию a ² + c ² = 1, и они представляют точку (x, y) как (X, XX, Y, Z, ZZ, R) , так что:

${\displaystyle x=X/Z}$

${\displaystyle y=Y/ZZ}$

${\displaystyle XX=X^{2}}$

${\displaystyle ZZ=Z^{2}}$

${\displaystyle R=2\cdot X\cdot Z}$

Координаты XYZ , ориентированные на удвоение , с тем же дополнительным предположением ( a ² + c ² = 1), представляют точку (x, y) с (X, Y, Z), удовлетворяющую следующим уравнениям:

${\displaystyle x=X/Z}$

${\displaystyle y=Y/Z^{2}}$

При использовании координат XXYZZ нет никаких дополнительных предположений, и они представляют точку (x, y) как (X, XX, Y, Z, ZZ) таким образом, что:

${\displaystyle x=X/Z}$

${\displaystyle y=Y/ZZ}$

${\displaystyle XX=X^{2}}$

${\displaystyle ZZ=Z^{2}}$

в то время как координаты XXYZZR представляют (x, y) как (X, XX, Y, Z, ZZ, R), так что:

${\displaystyle x=X/Z}$

${\displaystyle y=Y/ZZ}$

${\displaystyle XX=X^{2}}$

${\displaystyle ZZ=Z^{2}}$

${\displaystyle R=2\cdot X\cdot Z}$

с координатами XYZ точка (x, y) задается как (X, Y, Z) , где:

${\displaystyle x=X/Z}$

${\displaystyle y=Y/Z^{2}}$.

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

• Оливье Билле, Марк Джой (2003). "Модель Якоби эллиптической кривой и анализ боковых каналов". Модель Якоби эллиптической кривой и анализ боковых каналов . Конспект лекций по информатике. Том 2643. Springer-Verlag Berlin Heidelberg 2003. стр. 34–42. doi :10.1007/3-540-44828-4_5. ISBN 978-3-540-40111-7.
• PY Liardet, NP Smart (2001). «Предотвращение SPA/DPA в системах ECC с использованием формы Якоби». Криптографическое оборудование и встроенные системы — CHES 2001. Конспект лекций по информатике. Том 2162. Springer-Verlag Berlin Heidelberg 2001. стр. 391–401. doi :10.1007/3-540-44709-1_32. ISBN 978-3-540-42521-2. S2CID  32648481.
• http://hyperelliptic.org/EFD/index.html

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