Кривые Эдвардса (Tjnfdy |;fgj;vg)

Перейти к навигации Перейти к поиску
Кривые Эдвардса уравнения x2 + y2 = 1 − d ·x2·y2 над полем действительных чисел с параметрами d = 300 (красный), d = √8 (желтый) и d = −0.9 (синий)

Кривые Эдвардса — семейство эллиптических кривых, изученных профессором математик Гарольдом Эдвардсом в 2007 году[1]. Концепция эллиптических кривых над конечными полями широко используется в эллиптической криптографии. Первыми, кто исследовал преимущества эллиптической кривой в форме Эдвардса перед эллиптической кривой в форме Вейерштрасса, были Даниэль Бернстайн и Тани Ланге: они доработали оригинальную кривую Эдвардса, введя новый параметр кривой, и получили закон сложения точек для модифицированной кривой.[2]

Определение

[править | править код]

Оригинальной кривой Эдвардса над полем K, не имеющим характеристики 2, называется уравнение вида

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

Поэтому Даниэлем Бернстайнем и Тани Ланге была предложена модификация кривой Эдвардса с ведением параметра d, не являющимся квадратичным вычетов в поле :[2]

, , , где символ Лежандра, ,  — характеристика поля,

Эта модификация и называется эллиптической кривой в форме Эдвардса, или проще кривой Эдвардса.

Кривая Эдвардса изоморфна (бирационально эквивалентна) эллиптической кривой в форме Монтгомери и, следовательно, допускает наличие алгебраической группы при выборе нейтрального элемента. Если поле K конечно, то значительная часть эллиптических кривых над эти полем может быть записана в форме Эдвардса.

Подстановкой в исходное уравнение кривой Эдвардса можно получить изоморфную кривую в форме Эдвардса вида:

Выбор параметра с = 1 не умаляет общности, поэтому далее при рассмотрении кривых Эдвардса параметр с предполагается равным единице.

Групповой закон

[править | править код]

(См. также групповой закон эллиптической кривой в форме Вейерштрасса)

Любая кривая Эдвардса вида над полем K с характеристикой изоморфна эллиптической кривой в форме Монтгомери над тем же полем:

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

Закон сложения для кривых Эдвардса

[править | править код]

Для любой эллиптической кривой сумма двух точек представляется рациональным выражением от координат этих точек, хотя в общем случае могут понадобиться несколько дополнительных формул для покрытия всех частных случаев. Для кривых Эдвардса, беря в качестве нейтрального элемента точку (0, 1), сумма точек и представляется формулой:

[3]

Обратная точка определяется как . Любая Кривая Эдвардса имеет единственную точку 2-го порядка и ровно 2 точки 4-го порядка с координатами в поле K.

Если d не является квадратичным вычетом в K и , тогда кривая не имеет особых точек: в знаменателе и . Это свойство принято называть полнотой закона сложения для кривых Эдвардса. Оно выполняется, когда d не является квадратичным вычетом в поле K. Другими словами, выражения для суммы двух точек справедливы для любых пар точек кривой Эдвардса над полем K.[2]

[4]

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

Пример закона сложения

[править | править код]

Рассмотрим эллиптическую кривую в форме Эдвардса с параметром d = 2

и точкой на ней.

Покажем, что сумма и нейтрального элемента дает снова . Действительно, используя выражения для закона сложения, получаем координаты точки суммы:

Геометрическая интерпретация

[править | править код]
Сложение углов на единичной окружности

Для лучшего понимания можно рассмотреть геометрическую интерпретацию закона сложения:

Возьмем окружность радиуса 1:

и рассмотрим точки . Пусть и углы такие, что:

Сумма и будет «суммой их углов». То есть точка это точка на круге такая, что:

Таким образом, формула сложения для точек на окружности радиуса 1:

.
Сумма двух точек на кривой Эдвардса с d = −30

Закон сложения на кривых Эдвардса

[править | править код]

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

Изоморфное отображение между кривой Эдвардса и соответствующей эллиптической кривой отображает прямые линии в конические сечения[5] . Другими словами, для кривой Эдвардса три точки , и лежат на гиперболе.

Для двух различных точек , коэффициенты квадратичной формы:

,

,

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

,

,

Проективные однородные координаты

[править | править код]

(См. также проективные однородные координаты)

Самой трудоемкой операцией арифметики эллиптических кривых является операция взятия обратного элемента в поле (инверсия). Чтобы от нее избавиться переходят от аффинных двумерных координат к 3-х и 4-хмерным координатом, среди которых распространены проективные координаты.

Проективные координаты позволяют избежать 2-х инверсий в законе сложения. Ввод третьей переменней дает возможность заменить операцию инверсии другими операциями. Введем третью координату как общий знаменатель в законе сложения. Обозначим , тогда исходное уравнение кривой Эдвардса примет вид:

Нейтральный элемент в проективных координатах:

Нахождение обратной точки

В проективных координатах сумма двух точек записывается как . С учетом подстановок получается:

Обозначим:

Тогда

Всего получается 10 умножений в поле, одно возведение в квадрат и одно умножение на параметр кривой , не считая простые операции сложения (вычитания).

Закон удвоения

[править | править код]

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

Удвоение точки на кривой Эдвардса с d = −30

Удвоение точки :

Знаменатели были упрощены согласно уравнению кривой . Дальнейшая оптимизация достигается путем подсчета как . Это сокращает стоимость удвоения в гомоморфных координатах до 3M + 4S + 3C + 6a, в то время как обычное сложение стоит 10M + 1S + 1C + 1D + 7a. Здесь M — умножение в поле, S — возведение в квадрат в поле, D — стоимость умножение на параметр кривой d, a — сложение в поле.

В проективных координатах закон удвоения принимает вид:

Обозначим:

Тогда

Всего получается 3 возведения в квадрат и 4 умножения в поле.

Пример удвоения

[править | править код]

Как и примере с законом сложения, рассмотри кривую Эдвардса с параметром d=2:

и точку . Координаты точки :

Точка, полученная удвоением P, имеет координаты .

Применение

[править | править код]

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

  • EdDSA — схема цифровой подписи с использованием кривых Эдвардса
  • ECDH — протокол Ди́ффи-Хе́ллмана на эллиптических кривых
  • ECQMV — протокол распределения общего ключа
  • ECIES — протокол направленного шифрования
  • Twisted Edwards curve — скрученные кривые Эдвардса, альтернативная форма представления кривых.
  1. Edwards, H.M. A normal form for elliptic curves. — Bulletin of the American Mathematical Society, July 2007. — P. 393—422.
  2. 1 2 3 Bernstein, D.J. Faster Addition and Doubling on Elliptic Curves / D.J. Bernstein, T. Lange. — Advancesin Cryptology—ASIACRYPT’20077 (Proc. 13th Int. Conf. On the Theory and Applicationof Cryptology and Information Security. Kuching, Malaysia. December 2–6, 2007), 2007.
  3. M.R. Dam. Edwards Elliptic Curves (Bachelor Thesis Mathematics). — 2012. — С. 11. Архивировано 13 декабря 2022 года.
  4. Бессалов А.В. Эллиптические кривые в форме Эдвардса и криптография. — Киев: Політехніка, 2017. — С. 20. Архивировано 11 декабря 2022 года.
  5. Christophe Arene, Tanja Lange, Michael Naehrig, Christophe Ritzenthaler. Faster Computation of the Tate Pairing. Архивировано 11 декабря 2022 года.