Кривая Якобиана

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

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

Эллиптические кривые: основы

Учитывая эллиптическую кривую, можно выполнять некоторые «операции» между ее точками: например, можно добавить две точки 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 ² = х ³ + топор + b с a , b в K. , Что будет иметь значение позже, так это точка порядка 2 , то есть P на E такая, что [2] P = O и P ≠ O . Если P = ( p , 0) — точка на E , то она имеет порядок 2; в более общем смысле точки порядка 2 соответствуют корням многочлена f (x) = x ³ + топор + б .

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

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

Е _{а, б} : у ² = х(х + 1)(х + j)

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

Определение: пересечение Якоби.

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

$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 — эллиптическая кривая в форме Вейерштрасса, применим к ней следующее отображение :

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

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

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

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

$\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

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

$O=(0:1:0)\mapsto (0,1,1,1)$

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

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

Сложение и удвоение

Учитывая P ₁ = ( X ₁ , Y ₁ , Z ₁ , T ₁ ) и P ₂ = ( X ₂ , Y ₂ , Z ₂ , T ₂ ), две точки на S1 , координаты точки P ₃ = P ₁ + П ₂ это:

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

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

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

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

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

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

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

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

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

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

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

Пример сложения и удвоения

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

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

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

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

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

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

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

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

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

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

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

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

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

$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 ₃ с координатами:

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

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

$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 ₂ .

Расширенные координаты

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

$\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 , где:

$x=X/T$

$y=Y/T$

$z=Z/T$

$XY=X\cdot Y$

$ZT=Z\cdot T$

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

Определение: квартика Якоби.

Квартика Якоби уравнения $y^{2}=x^{4}-1.9x^{2}+1$

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

f: Пусть _a,b → J

$(p,0)\mapsto (0:-1:1)$

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

$O\mapsto (0:1:1)$

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

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

где:

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

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

Квартика Якоби в аффинных координатах

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

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

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

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

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

Сложение и удвоение в аффинных координатах

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

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

$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 ₂ по формулам:

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

$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)$

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

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

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

Существуют некоторые «стратегии», позволяющие сократить количество операций, необходимых для сложения и удвоения точек: количество умножений можно уменьшить до 11 плюс 3 умножения на константы (см. раздел 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, а соответствующая квартическая форма Якоби:

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

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

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

$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$

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

Так

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

точка P ₄ = [2] P ₁ По тем же формулам получается :

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

$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$

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

Так

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

Отрицание

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

Альтернативные координаты квартики Якоби

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

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

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

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

$x=X/Z$

$y=Y/ZZ$

$XX=X^{2}$

$ZZ=Z^{2}$

$R=2\cdot X\cdot Z$

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

$x=X/Z$

$y=Y/Z^{2}$

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

$x=X/Z$

$y=Y/ZZ$

$XX=X^{2}$

$ZZ=Z^{2}$

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

$x=X/Z$

$y=Y/ZZ$

$XX=X^{2}$

$ZZ=Z^{2}$

$R=2\cdot X\cdot Z$

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

$x=X/Z$

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

См. также

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

Ссылки

• Оливье Билле, Марк Джой (2003). «Модель Якоби эллиптической кривой и анализ боковых каналов». Модель Якоби эллиптической кривой и анализ боковых каналов . Конспекты лекций по информатике. Том. 2643. Springer-Verlag Berlin Heidelberg 2003. стр. 34–42. дои : 10.1007/3-540-44828-4_5 . ISBN  978-3-540-40111-7 .
• П. Я. Лиардет, Н. П. Смарт (2001). «Предотвращение SPA/DPA в системах ECC с использованием формы Якоби». Криптографическое оборудование и встроенные системы — CHES 2001 . Конспекты лекций по информатике. Том. 2162. Springer-Verlag Berlin Heidelberg 2001. стр. 391–401. дои : 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