Кривая якоби - Jacobian curve

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

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

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

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

Эллиптическая кривая E, через поле K можно поместить в Форма Вейерштрасса у² = Икс³ + топор + б, с а, б в K. Что будет важно позже: по порядку ведения заседания 2, то есть п на E такие, что [2]п = О. Если п = (п, 0) - точка на E, то он имеет порядок 2; в более общем смысле точки порядка 2 соответствуют корням многочлен f (x) = Икс³ + топор + б.

С этого момента мы будем использовать E_{а, б} для обозначения эллиптической кривой с формой Вейерштрасса у² = Икс³ + топор + б.

Если E_{а, б} таков, что кубический многочлен Икс³ + топор + б имеет три различных корня в K мы можем написать E_{а, б} в Нормальная форма Лежандра:

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

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

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

Эллиптическая кривая в п³(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_{а, б} - эллиптическая кривая в форме Вейерштрасса, применим следующее карта к нему:

${\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] соответствует следующему пересечению поверхности в п³(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), то есть образ О = (0: 1: 0) при ψ.

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

Данный п₁ = (Икс₁, Y₁, Z₁, Т₁) и п₂ = (Икс₂, Y₂, Z₂, Т₂), две точки на S1, то координаты по делу п₃ = п₁ + п₂ находятся:

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

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

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

${\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]п₁ можно получить, добавив п₁ с [2]п₁ со стоимостью 7 умножений для [2]п₁ и 16 для п₁ + [2]п₁^[2]

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

Позволять K = р или же C и рассмотрим случай:

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

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

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

${\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)}$.

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

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

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

Отрицание

Учитывая точку п₁ = (Икс₁, Y₁, Z₁, Т₁) в S1, это отрицание это -п₁ = (−Икс₁, Y₁, Z₁, Т₁)

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

Учитывая две аффинные точки п₁ = (Икс₁, у₁, z₁) и п₂ = (Икс₂, у₂, z₂) их сумма равна точке п₃ с координатами:

${\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})}}}$

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

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

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

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

то расширенные координаты описать точку п = (х, у, г) с переменными 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

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

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

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

f: E_{а, б} → 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]

Применение ж к E_{а, б}, получается кривая в 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}$,

где часто е = 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-(x_{1}x_{2})^{2}}}}$

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

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

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

Учитывая два очка п₁ = (Икс₁: Y₁: Z₁) и п₂ = (Икс₂: Y₂: Z₂) в C ′, координаты точки п₃ = (Икс₃: Y₃: Z₃), куда п₃ = п₁ + п₂, даны в терминах п₁ и п₂ по формулам:

${\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}-2dX_{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}}$

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

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

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

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

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

Рассмотрим эллиптическую кривую E_4,0, в этом есть смысл п порядка 2: п = (п, 0) = (0, 0). Следовательно, а = 4, б = п = 0, поэтому мы имеем е = 1 и d = 1 и ассоциированная форма квартики Якоби:

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

Выбор двух точек ${\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)}$.

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

${\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)}$.

Отрицание

Отрицание точки п₁ = (Икс₁: Y₁: Z₁) это: -п₁ = (−Икс₁: Y₁: Z₁)

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

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

Учитывая аффинную квартику Якоби

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

то Ориентированный на удвоение XXYZZ координаты ввести дополнительный параметр кривой c удовлетворение а² + c² = 1 и они представляют собой точку (х, у) в качестве (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 координаты, при том же дополнительном предположении (а² + c² = 1), представляют собой точку (х, у) с (X, Y, Z) удовлетворяющие следующим уравнениям:

${\displaystyle x=X/Z}$

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

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

${\displaystyle x=X/Z}$

${\displaystyle y=Y/ZZ}$

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

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

в то время как Координаты XXYZZR представлять (х, у) в качестве (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, Z), с:

${\displaystyle x=X/Z}$

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

Смотрите также

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

Примечания

1. Оливье Билле, Модель Якоби эллиптической кривой и анализ боковых каналов
2. П. Ю. Лиардет, Н. П. Смарт, Предотвращение SPA / DPA в системах ECC с помощью формы Якоби, стр. 397
3. Оливье Билле и Марк Джой, Модель Якоби эллиптической кривой и анализ боковых каналов, стр. 37-38
4. Сильвен Дюкен, Улучшение арифметики эллиптических кривых в модели Якоби-I3M, (UMR CNRS 5149) и Lirmm, (UMR CNRS 5506), Университет Монпелье II

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

• Оливье Билле, Марк Джой (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.
• http://hyperelliptic.org/EFD/index.html

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

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