В математике , то кривая Якоби является представление эллиптической кривой , отличной от обычной ( уравнение Вейерштрасса ). Иногда он используется в криптографии вместо формы Вейерштрасса, потому что он может обеспечить защиту от атак простого и дифференциального стиля анализа мощности (SPA); Действительно, можно использовать общую формулу сложения также для удвоения точки на эллиптической кривой этой формы: таким образом, две операции становятся неотличимыми от некоторой информации побочного канала. [1] Кривая Якоби также предлагает более быстрые вычисления по сравнению с кривой Вейерштрасса.
Кривая Якоби может быть двух типов: пересечение Якоби , которое задается пересечением двух поверхностей, и квартика Якоби .
Эллиптические кривые: основы
Для эллиптической кривой можно выполнять некоторые «операции» между ее точками: например, можно сложить две точки P и Q, получив точку P + Q, которая принадлежит кривой; учитывая точку P на эллиптической кривой, можно «удвоить» P, что означает найти [2] P = P + P (квадратные скобки используются для обозначения [n] P , точка P складывается n раз), а также найти отрицание Р , что означает найти - P . Таким образом, точки эллиптической кривой образуют группу . Обратите внимание, что единичный элемент групповой операции не является точкой на аффинной плоскости, он появляется только в проективных координатах: тогда O = (0: 1: 0) - это «бесконечно удаленная точка», то есть нейтральный элемент в групповой закон . Формулы сложения и удвоения полезны также для вычисления [n] P , n-го кратного точки P на эллиптической кривой: эта операция считается наиболее распространенной в криптографии на основе эллиптических кривых .
Эллиптической кривой Е , над полем K можно положить в вейерштрассовой форме у 2 = х 3 + ах + б , с , б , в K . Что будет иметь значение позже являются точкой 2 - го порядка , то есть P на E такое , что [2] P = O . Если P = ( p , 0) - точка на E , то она имеет порядок 2; в более общем случае точки порядка 2 соответствуют корням многочлена f (x) = x 3 + ax + b .
С этого момента мы будем использовать E a, b для обозначения эллиптической кривой с формой Вейерштрасса y 2 = x 3 + ax + b .
Если E a, b таково, что кубический многочлен x 3 + ax + b имеет три различных корня в K, мы можем записать E a, b в нормальной форме Лежандра :
- E a, b : y 2 = x (x + 1) (x + j).
В этом случае мы имеем три точки второго порядка: (0, 0), (–1, 0), (- j , 0). В этом случае мы используем обозначение E [j] . Обратите внимание, что j можно выразить через a , b .
Определение: пересечение Якоби
Эллиптическая кривая в P 3 ( K ) может быть представлена как пересечение двух квадратичных поверхностей :
Можно определить форму Якоби эллиптической кривой как пересечение двух квадрик. Пусть E a, b - эллиптическая кривая в форме Вейерштрасса, применим к ней следующее отображение :
Мы видим, что справедлива следующая система уравнений :
Кривая E [j] соответствует следующему пересечению поверхностей в P 3 ( K ):
- .
«Частный случай», E [0] , эллиптическая кривая имеет двойную точку и, следовательно, сингулярна .
S1 , получается путем применения к E [J] в преобразовании :
- ψ: E [j] → S1
Групповое право
Для S1 , то нейтральный элемент группы является точка (0, 1, 1, 1), то есть изображение O = (0: 1: 0) в ф.
Сложение и удвоение
Даны P 1 = ( X 1 , Y 1 , Z 1 , T 1 ) и P 2 = ( X 2 , Y 2 , Z 2 , T 2 ), две точки на S1 , координаты точки P 3 = P 1 + P 2 :
Эти формулы справедливы и для удвоения: достаточно, чтобы P 1 = P 2 . Таким образом, сложение или удвоение точек в S1 - это операции, которые требуют 16 умножений плюс одно умножение на константу ( k ).
Также можно использовать следующие формулы для удвоения точки P 1 и найти P 3 = [2] P 1 :
Используя эти формулы, необходимо 8 умножений, чтобы удвоить очко. Однако есть еще более эффективные «стратегии» удвоения, требующие всего 7 умножений. [2] Таким образом можно утроить точку с 23 умножениями; действительно [3] P 1 может быть получено путем сложения P 1 с [2] P 1 с затратами 7 умножений для [2] P 1 и 16 для P 1 + [2] P 1 [2]
Пример сложения и удвоения
Пусть K = R или C и рассмотрим случай:
Рассмотрим точки а также : легко проверить, что P 1 и P 2 принадлежат S1 (достаточно увидеть, что эти точки удовлетворяют обоим уравнениям системы S1 ).
Используя приведенные выше формулы для сложения двух точек, координаты точки P 3 , где P 3 = P 1 + P 2, равны:
Результирующая точка .
С помощью приведенных выше формул для удвоения можно найти точку P 3 = [2] P 1 :
Итак, в этом случае P 3 = [2] P 1 = (0, 12, –12, 12).
Отрицание
Учитывая точку P 1 = ( X 1 , Y 1 , Z 1 , T 1 ) в S1 , ее отрицание будет - P 1 = (- X 1 , Y 1 , Z 1 , T 1 )
Сложение и удвоение в аффинных координатах
Для двух аффинных точек P 1 = ( x 1 , y 1 , z 1 ) и P 2 = ( x 2 , y 2 , z 2 ) их сумма представляет собой точку P 3 с координатами:
Эти формулы верны также для удвоения с условием P 1 = P 2 .
Расширенные координаты
Есть еще одна система координат, с помощью которой можно представить точку пересечения Якоби. Дана следующая эллиптическая кривая в форме пересечения Якоби:
эти расширенные координаты описывают точку Р = (х, у, г) с переменным X, Y, Z, T, XY, ZT , где:
Иногда используются эти координаты, потому что они более удобны (с точки зрения затрат времени) в некоторых конкретных ситуациях. Для получения дополнительной информации об операциях, основанных на использовании этих координат, см. Http://hyperelliptic.org/EFD/g1p/auto-jintersect-extended.html.
Определение: квартика Якоби
Эллиптическая кривая в форме Якоби квартики может быть получена из кривой E a, b в форме Вейерштрасса по крайней мере с одной точкой порядка 2. Следующее преобразование f переводит каждую точку E a, b в точку в координатах Якоби, где (X: Y: Z) = (sX: s 2 Y: sZ) .
- f: E a, b → J
- [3]
Применяя f к E a, b , получаем кривую в J следующего вида:
где:
- .
являются элементами K . C представляет собой эллиптическую кривую в форме квартики Якоби в координатах Якоби.
Квартика Якоби в аффинных координатах
Общий вид кривой Якоби квартики в аффинных координатах:
- ,
где часто предполагается e = 1.
Групповое право
Нейтральным элементом группового закона C является проективная точка (0: 1: 1).
Сложение и удвоение в аффинных координатах
Учитывая две аффинные точки а также , их сумма равна баллу , такое, что:
Как и в случае пересечений Якоби, в этом случае также можно использовать эту формулу для удвоения.
Сложение и удвоение в проективных координатах
Для двух точек P 1 = ( X 1 : Y 1 : Z 1 ) и P 2 = ( X 2 : Y 2 : Z 2 ) в C ′ координаты точки P 3 = ( X 3 : Y 3 : Z 3 ), где P 3 = P 1 + P 2 , задаются через P 1 и P 2 формулами:
Эту формулу можно использовать также для удвоения при условии, что P 2 = P 1 : таким образом получается точка P 3 = P 1 + P 1 = [2] P 1 .
Количество умножений, необходимых для сложения двух точек, составляет 13 плюс 3 умножения на константы: в частности, есть два умножения на константу e и одно на константу d .
Есть несколько «стратегий» для сокращения операций, необходимых для сложения и удвоения точек: количество умножений может быть уменьшено до 11 плюс 3 умножения на константы (подробнее см. [4] раздел 3).
Количество умножений можно уменьшить, работая с константами e и d : эллиптическая кривая в форме Якоби может быть изменена, чтобы иметь меньшее количество операций сложения и удвоения. Так, например, если константа d в C значительно мала, умножение на d можно отменить; однако лучше всего уменьшить е : если оно мало, не учитывается не только одно, но и два умножения.
Пример сложения и удвоения
Рассмотрим эллиптическую кривую E 4,0 , у нее есть точка P порядка 2: P = ( p , 0) = (0, 0). Следовательно, a = 4, b = p = 0, поэтому мы имеем e = 1 и d = 1, и соответствующая форма Якоби квартики имеет следующий вид:
Выбор двух точек а также , можно найти их сумму P 3 = P 1 + P 2, используя формулы сложения, приведенные выше:
- .
Так
- .
По тем же формулам получается точка P 4 = [2] P 1 :
Так
- .
Отрицание
Отрицание точки P 1 = ( X 1 : Y 1 : Z 1 ) составляет: - P 1 = (- X 1 : Y 1 : Z 1 )
Альтернативные координаты квартики Якоби
Существуют и другие системы координат, которые можно использовать для представления точки в квартике Якоби: они используются для получения быстрых вычислений в определенных случаях. Для получения дополнительной информации о временных затратах, необходимых для операций с этими координатами, см. Http://hyperelliptic.org/EFD/g1p/auto-jquartic.html.
Учитывая аффинную квартику Якоби
в удвоении-ориентированное XXYZZ координаты ввести дополнительный параметр кривого с , удовлетворяющие на 2 + гр 2 = 1 , и они представляют собой точку (х, у) , как (X, XX, Y, Z, ZZ, R) , такие , что:
Ориентированные на удвоение координаты XYZ с тем же дополнительным предположением ( a 2 + c 2 = 1) представляют точку (x, y) с (X, Y, Z), удовлетворяющую следующим уравнениям:
Использование координат XXYZZ не требует дополнительных предположений, и они представляют точку (x, y) как (X, XX, Y, Z, ZZ) , так что:
в то время как координаты XXYZZR представляют (x, y) как (X, XX, Y, Z, ZZ, R) , так что:
с координатами XYZ точка (x, y) задается как (X, Y, Z) с:
- .
Смотрите также
Для получения дополнительной информации о времени выполнения, необходимом в конкретном случае, см. Таблицу затрат на операции в эллиптических кривых .
Заметки
- ^ Оливье Билле, Модель Якоби эллиптической кривой и анализ боковых каналов
- ^ a b П.Я. Лиардет и NPSmart, Предотвращение SPA / DPA в системах ECC с использованием формы Якоби , стр. 397
- ^ a b Оливье Билле и Марк Джой, Модель Якоби эллиптической кривой и анализ боковых каналов , стр. 37-38
- ^ Сильвен Дюкен, Улучшение арифметики эллиптических кривых в модели Якоби -I3M, (UMR CNRS 5149) и Lirmm, (UMR CNRS 5506), Университет Монпелье II
Рекомендации
- Оливье Билле, Марк Джой (2003). "Модель Якоби эллиптической кривой и анализ боковых каналов". Модель Якоби эллиптической кривой и анализ боковых каналов . Конспект лекций по информатике. 2643 . Springer-Verlag Berlin Heidelberg 2003. С. 34–42. DOI : 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. DOI : 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