Кривая Монтгомери - Википедия - Montgomery curve

В математика в Кривая Монтгомери это форма эллиптическая кривая, отличается от обычного Форма Вейерштрасса, представлен Питер Л. Монтгомери в 1987 г.[1] Он используется для определенных вычислений, в частности в различных криптография Приложения.

Определение

Кривая Монтгомери уравнения

Кривая Монтгомери над поле K определяется уравнение

для некоторых А, BK и с B(А2 − 4) ≠ 0.

Обычно это изгиб рассматривается над конечное поле K (например, над конечным полем q элементы, K = Fq) с характеристика отличается от 2 и с А ≠ ±2 и B ≠ 0, но они также рассматриваются рациональные с такими же ограничениями для А и B.

Арифметика Монтгомери

Можно проделать некоторые «операции» между точки эллиптической кривой: «складываем» две точки состоит из поиска третьего такой, что ; "удвоение" точки состоит из вычисления (Для получения дополнительной информации об операциях см. Групповой закон ) и ниже.

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

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

Теперь, учитывая два момента и : их сумма дается точкой чей координаты находятся:

Если , тогда операция становится «удвоением»; координаты даются следующими уравнениями:

Первая рассмотренная выше операция (добавление ) имеет временные затраты 3M+2S, куда M обозначает умножение двух общих элементы поля, на котором задана эллиптическая кривая, а S обозначает возведение в квадрат генерального элемента поля.

Вторая операция (удвоение) требует затрат времени 2.M + 2S + 1D, куда D обозначает умножение общего элемента на постоянный; обратите внимание, что константа , так можно выбрать, чтобы иметь небольшойD.

Алгоритм и пример

Следующий алгоритм представляет собой удвоение точки. на эллиптической кривой в форме Монтгомери.

Предполагается, что . Стоимость этой реализации составляет 1M + 2S + 1 * A + 3add + 1 * 4. Здесь M обозначает необходимое умножение, S указывает квадраты, а a относится к умножению на A.

Пример

Позволять быть точкой на кривой .В координатах , с , .

Потом:

Результат - это точка такой, что .

Добавление

Учитывая два очка , на кривой Монтгомери в аффинных координатах точка представляет, геометрически третья точка пересечения между и линия, проходящая через и . Есть возможность найти координаты из , следующим образом:

1) рассмотрим общую линию в аффинной плоскости и пропустить и (наложим условие), таким образом получим и ;

2) пересечь прямую с кривой , заменяя переменная в уравнении кривой с ; следующее уравнение третьей степени получается:

Как уже отмечалось ранее, это уравнение имеет три решения, которые соответствуют координаты , и . В частности, это уравнение можно переписать как:

3) Сравнивая коэффициенты двух идентичных уравнений, приведенных выше, в частности коэффициенты членов второй степени, получаем:

.

Так, можно записать в терминах , , , , в качестве:

4) Найти координата точки достаточно подставить значение в соответствии . Обратите внимание, что это не даст смысла напрямую. Действительно, этим методом находятся координаты точки такой, что , но если нужна итоговая точка суммы между и , то необходимо заметить, что: если и только если . Итак, учитывая суть , необходимо найти , но это легко сделать, изменив знак на координата . Другими словами, необходимо будет изменить знак координата, полученная подстановкой значения в уравнении линии.

Итак, координаты точки , находятся:

Удвоение

Учитывая точку на кривой Монтгомери , смысл геометрически представляет собой третью точку пересечения между кривой и прямой, касательной к ; Итак, чтобы найти координаты точки достаточно следовать тому же методу, который указан в формуле сложения; однако в этом случае строка у = лк + м должен касаться кривой в точке , так что если с

тогда значение л, который представляет собой склон линии, определяется как:

посредством теорема о неявной функции.

Так и координаты точки , находятся:

Эквивалентность скрученным кривым Эдвардса

Позволять - поле с характеристикой, отличной от 2.

Позволять - эллиптическая кривая в форме Монтгомери:

с ,

и разреши - эллиптическая кривая в скрученной форме Эдвардса:

с

Следующая теорема показывает бирациональная эквивалентность между кривыми Монтгомери и искривленная кривая Эдвардса:[2]

Теорема (i) Всякая скрученная кривая Эдвардса бирационально эквивалентна кривой Монтгомери над В частности, закрученная кривая Эдвардса бирационально эквивалентна кривой Монтгомери куда , и .

В карта:

является бирациональной эквивалентностью из к , с инверсией:

:

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

Эквивалентность кривым Вейерштрасса

Любую эллиптическую кривую можно записать в форме Вейерштрасса. В частности, эллиптическая кривая в форме Монтгомери

:

можно преобразовать следующим образом: разделите каждый член уравнения на к , и подставим переменные Икс и у, с и соответственно, чтобы получить уравнение

Чтобы получить отсюда краткую форму Вейерштрасса, достаточно заменить ты с переменной :

наконец, это дает уравнение:

Следовательно, отображение задается как

:

Напротив, эллиптическая кривая над базовым полем в форме Вейерштрасса

:

можно преобразовать в форму Монтгомери тогда и только тогда, когда имеет порядок, кратный четырем, и удовлетворяет следующим условиям:[3]

  1. имеет хотя бы один корень ; и
  2. является квадратичным вычетом в .

Когда эти условия выполнены, то при у нас есть отображение

:
.

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

Примечания

  1. ^ Питер Л. Монтгомери (1987). "Ускорение методов факторизации Полларда и эллиптических кривых". Математика вычислений. 48 (177): 243–264. Дои:10.2307/2007888. JSTOR  2007888.
  2. ^ Дэниел Дж. Бернштейн, Питер Биркнер, Марк Джой, Таня Ланге и Кристиан Петерс (2008). «Скрученные кривые Эдвардса». Прогресс в криптологии - AFRICACRYPT 2008. Конспект лекций по информатике. 5023. Springer-Verlag Berlin Heidelberg. С. 389–405. Дои:10.1007/978-3-540-68164-9_26. ISBN  978-3-540-68159-5.CS1 maint: несколько имен: список авторов (связь)
  3. ^ Кацуюки Окея, Хироюки Куруматани и Коичи Сакураи (2000). Эллиптические кривые с формой Монтгомери и их криптографические приложения. Криптография с открытым ключом (PKC2000). Дои:10.1007/978-3-540-46588-1_17.CS1 maint: несколько имен: список авторов (связь)

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

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