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

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

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

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

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

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

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

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

Eа, б: у2 = х (х + 1) (х + j)

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

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

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

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

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

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

.

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

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

ψ: E [j]S1

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

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

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

Данный п1 = (Икс1, Y1, Z1, Т1) и п2 = (Икс2, Y2, Z2, Т2), две точки на S1, то координаты по делу п3 = п1 + п2 находятся:

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

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

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

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

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

Рассмотрим точки и : легко проверить, что п1 и п2 принадлежать S1 (достаточно увидеть, что эти точки удовлетворяют обоим уравнениям система S1).

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

Результирующая точка .

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

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

Отрицание

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

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

Учитывая две аффинные точки п1 = (Икс1, у1, z1) и п2 = (Икс2, у2, z2) их сумма равна точке п3 с координатами:

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

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

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

то расширенные координаты описать точку п = (х, у, г) с переменными X, Y, Z, T, XY, ZT, куда:

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

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

Якобиевская квартика уравнение

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

f: Eа, бJ
[3]

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

[3]

куда:

.

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

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

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

,

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

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

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

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

Учитывая две аффинные точки и , их сумма равна баллу , такое, что:

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

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

Учитывая два очка п1 = (Икс1: Y1: Z1) и п2 = (Икс2: Y2: Z2) в C ′, координаты точки п3 = (Икс3: Y3: Z3), куда п3 = п1 + п2, даны в терминах п1 и п2 по формулам:

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

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

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

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

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

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

Выбор двух точек и , можно найти их сумму п3 = п1 + п2 используя формулы для добавления, указанные выше:

.

Так

.

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

Так

.

Отрицание

Отрицание точки п1 = (Икс1: Y1: Z1) это: -п1 = (−Икс1: Y1: Z1)

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

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

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

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

то Ориентированный на удвоение XYZ координаты, при том же дополнительном предположении (а2 + c2 = 1), представляют собой точку (х, у) с (X, Y, Z) удовлетворяющие следующим уравнениям:

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

в то время как Координаты XXYZZR представлять (х, у) в качестве (X, XX, Y, Z, ZZ, R) такой, что:

с Координаты XYZ смысл (х, у) дан кем-то (X, Y, Z), с:

.

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

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

Примечания

  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

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