Кривые Эдвардса уравнения x2 + y2 = 1 − d ·x2·y2 над полем действительных чисел с параметрами d = 300 (красный), d = √8 (желтый) и d = −0.9 (синий)
Кривые Эдвардса — семейство эллиптических кривых, изученных профессором математик Гарольдом Эдвардсом в 2007 году[1]. Концепция эллиптических кривых над конечными полями широко используется в эллиптической криптографии. Первыми, кто исследовал преимущества эллиптической кривой в форме Эдвардса перед эллиптической кривой в форме Вейерштрасса, были Даниэль Бернстайн и Тани Ланге: они доработали оригинальную кривую Эдвардса, введя новый параметр кривой, и получили закон сложения точек для модифицированной кривой.[2]
Эта модификация и называется эллиптической кривой в форме Эдвардса, или проще кривой Эдвардса.
Кривая Эдвардса изоморфна (бирационально эквивалентна) эллиптической кривой в форме Монтгомери и, следовательно, допускает наличие алгебраической группы при выборе нейтрального элемента. Если поле K конечно, то значительная часть эллиптических кривых над эти полем может быть записана в форме Эдвардса.
Подстановкой в исходное уравнение кривой Эдвардса можно получить изоморфную кривую в форме Эдвардса вида:
Выбор параметра с = 1 не умаляет общности, поэтому далее при рассмотрении кривых Эдвардса параметр с предполагается равным единице.
Для любой эллиптической кривой сумма двух точек представляется рациональным выражением от координат этих точек, хотя в общем случае могут понадобиться несколько дополнительных формул для покрытия всех частных случаев. Для кривых Эдвардса, беря в качестве нейтрального элемента точку (0, 1), сумма точек и представляется формулой:
Вывод формулы для сложения двух точек
Утверждение
Пусть и -- точки кривой Эдвардса и выполняются равенства . Пусть . Тогда .
Доказательство
Не умаляя общности примем (иначе замена переменных )
Рассмотрим полином , который после раскрытия скобок и приведений соответствующих слагаемых принимает следующий вид: .
Из определения точек кривой в общем случае имеем:
.
Умножая второе равенство на и вычитая результат из первого, получаем:
Аналогично,
Отсюда получаем
Согласно условию точка выражается через . Это позволяет нам получить следующее равенство:
.
Обратная точка определяется как . Любая Кривая Эдвардса имеет единственную точку 2-го порядка и ровно 2 точки 4-го порядка с координатами в поле K.
Если d не является квадратичным вычетом в K и , тогда кривая не имеет особых точек: в знаменателе и . Это свойство принято называть полнотой закона сложения для кривых Эдвардса. Оно выполняется, когда d не является квадратичным вычетом в поле K. Другими словами, выражения для суммы двух точек справедливы для любых пар точек кривой Эдвардса над полем K.[2]
Доказательство свойства полноты
Утверждение
Для любых пар точек кривой Эдвардса знаменатели закона сложения не обращаются в нуль:
Доказательство
Пусть точки принадлежат одной кривой и пусть .
От противного: пусть (Возьмем равной 1). Тогда и .
.
Аналогично,
.
Так как не является квадратичным вычетом, то оба равенства выполняются лишь тогда, когда одновременно и . Следовательно, , но кривая Эдвардса не содержит такой точки. Противоречие.
Если d является квадратичным вычетом в K, то существуют особые точки, то есть может быть пара точек для которых один из знаменателей обращается в ноль: или .
Изоморфное отображение между кривой Эдвардса и соответствующей эллиптической кривой отображает прямые линии в конические сечения[5]. Другими словами, для кривой Эдвардса три точки , и лежат на гиперболе.
Для двух различных точек , коэффициенты квадратичной формы:
,
,
В случае удвоения точки обратный элемент лежит на конусе, который касается кривой в точке . Коэффициенты квадратичной формы, определяющей конус:
Самой трудоемкой операцией арифметики эллиптических кривых является операция взятия обратного элемента в поле (инверсия). Чтобы от нее избавиться переходят от аффинных двумерных координат к 3-х и 4-хмерным координатом, среди которых распространены проективные координаты.
Проективные координаты позволяют избежать 2-х инверсий в законе сложения. Ввод третьей переменней дает возможность заменить операцию инверсии другими операциями. Введем третью координату как общий знаменатель в законе сложения. Обозначим , тогда исходное уравнение кривой Эдвардса примет вид:
Нейтральный элемент в проективных координатах:
Нахождение обратной точки
В проективных координатах сумма двух точек записывается как . С учетом подстановок получается:
Обозначим:
Тогда
Всего получается 10 умножений в поле, одно возведение в квадрат и одно умножение на параметр кривой , не считая простые операции сложения (вычитания).
Удвоение может быть произведено с помощью тех же выражений, что и для закона сложения. Удвоение является частным случаем сложения двух одинаковых точек
Удвоение точки на кривой Эдвардса с d = −30
Удвоение точки :
Знаменатели были упрощены согласно уравнению кривой . Дальнейшая оптимизация достигается путем подсчета как . Это сокращает стоимость удвоения в гомоморфных координатах до 3M + 4S + 3C + 6a, в то время как обычное сложение стоит 10M + 1S + 1C + 1D + 7a. Здесь M — умножение в поле, S — возведение в квадрат в поле, D — стоимость умножение на параметр кривой d,a — сложение в поле.
В проективных координатах закон удвоения принимает вид:
Обозначим:
Тогда
Всего получается 3 возведения в квадрат и 4 умножения в поле.
Кривые Эдвардса над конечными полями используются в криптографических приложениях, а также для факторизации целых чисел. Общая идея этих приложений заключается в том, что берется известный алгоритм, использующий свойства определенных конечных абелевых групп, и переписывается для использования групп рациональных точек кривых Эдвардса. Подробнее см. также
EdDSA — схема цифровой подписи с использованием кривых Эдвардса
ECDH — протокол Ди́ффи-Хе́ллмана на эллиптических кривых
↑Edwards, H.M. A normal form for elliptic curves. — Bulletin of the American Mathematical Society, July 2007. — P. 393—422.
↑ 123Bernstein, 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.