Современная прикладная криптография (стр. 32 )

Эллиптической кривой над полем К называется неособая (гладкая) кривая, заданная в длинной форме Вейерштрасса

y+a xy+ a = x+ a x +a x + a,

при условии, что все коэффициенты лежат в поле К [БССШ03].

Через E(K) обозначается множество, состоящее из точек (x, y) из А(К), удовлетворяющих этому уравнению, и «бесконечно удаленной» точки О.

Следует еще раз отметить на встречающиеся различные определения эллиптической кривой. Например, во многих работах [K87, B03, ГОСТ 34.10-2001, FIPS 186-2] эллиптической кривой называется именно множество точек Е(К), удовлетворяющих соотношению y+a xy+ a = x+ a x +a x + a или y = x+ a x +b, со специально выбранными коэффициентами для гладкости, причем «бесконечно удаленную» точку О не всегда включают в множество Е(К) [ГОСТ 34.10 - 2001].

Условие гладкости кривой означает, что в множестве E(K) , где К –алгебраическое замыкание поля К, не существует точек, в которых одновременно обращались бы в нуль частные производные d f(x, y)/dx и d f(x, y)/d y,

где f(x, y)= y+axy+ ay - x- a x - a x - a.

Иными словами, система уравнений

d f(x, y)/dx = ay-3x - 2a x - a = 0

d f(x, y)/d y = 2y+a x+a = 0

не имеет решений в E(K). Условие гладкости необходимо для задания на точках кривой структуры абелевой группы. Проверка гладкости кривой достаточно проста.

Если характеристика поля char K не равна 2, то линейной заменой переменных

y à y –(ax+ a)/2 кривая приводится к виду

y= x+a x +a x + a.

Конечно, в последнем выражении значения коэффициентов a, a, a другие, чем в исходном.

Если характеристика поля char K не равна 2 и 3, то линейной заменой переменных x àx – 1/3 a2, эллиптическая кривая примет вид

y = x + a x +b,

где a, b из поля К. Этот вид задания эллиптической кривой называется короткой формой Вейерштрасса.

Условие гладкости кривой в этом случае означает, что кубический многочлен

x+a x+b не имеет кратных корней. Это выполняется тогда и только тогда, когда дискриминант этого многочлена, равный - (4 a + 27 b), отличен от нуля.

Как правило, в многочисленных криптографических приложениях эллиптические кривые задаются именно в этой короткой форме Вейерштрасса [K87, B03, ГОСТ 34.10-2001, FIPS 186-2], а в качестве поля выбираются конечные поля вида F и F.

Сложение точек эллиптической кривой.

Сначала заметим, что на некоторых плоских кривых существуют естественные законы сложения, такие, что относительно этой операции точки кривых образуют алгебраическую группу. Простейшими примерами таких кривых являются прямая и окружность [ПС97]. Например, суммой двух точек (r cos a, r sin a) и (r cos b, r sin b) , окружности x+y = r будем считать точку (r cos (a+b), r sin (a+b)).

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

Определим операцию сложения точек P и Q на кривой E отправляясь от графического изображения кривой [K87, БССШ03]. Проведем через точки P и Q прямую. В общем случае эта прямая пересечет кривую еще в третьей точке. Отразим эту точку относительно оси Ох и назовем полученную точку суммой P + Q точек P и Q. Не всегда прямая, проходящая через две точки, пересекает кривую Е в третьей точке, например, этого не происходит с вертикальной прямой. Этот случай рассмотрим далее подробно.

Заметим, что определить сумму P + Q точек P и Q можно не только таким образом, но именно такое определение наделяет множество точек эллиптической кривой структурой абелевой группы. Проиллюстрируем описание операции на рисунке.

Покажем, что относительно этой операции точки кривой образуют абелеву группу.

Очевидно, что так определенная операция коммутативна, так как для вычисления Q+P используется та же самая прямая, что и для P+Q.

Займемся существованием нейтрального по сложению элемента – нуля. Это такая точка O на кривой, что Р+О = Р для любой точки Р кривой. Мы хотим найти нечто такое, что, если провести прямую через Р и это нечто, пересечь получившуюся прямую с кривой и потом отразить точку пересечения от оси Ох, то вновь получится точка Р. Обозначим через Р` точку, симметричную Р относительно оси Ох. Из сказанного вытекает, что прямая должна проходить через точки Р и Р`, то есть должна быть вертикальной. Следовательно, если имеется точка О, для которой Р+О = Р для всех Р, то эта точка должна лежать и на кривой и на любой вертикальной прямой. Разумеется в плоскости (xOy) такой точки нет. Поэтому добавим ее к плоскости и кривой и назовем ее бесконечно удаленной точкой или точкой в бесконечности. Каким требованиям она должна удовлетворять? Любая вертикальная прямая стремится к бесконечности сверху и снизу. Потребуем, чтобы все эти точки в бесконечности были одной и той же точкой О, то есть будем считать, что точка О есть точка пересечения всех вертикальных прямых. Для того, чтобы точно понять, что это значит, рассмотрим проективное дополнение аффинной плоскости и кривой на ней. Рассмотрим проективную плоскость Р(K) с однородными координатами (X:Y:Z), причем будем считать, что координаты на исходной аффинной плоскости имеют вид

x = X/Z, y = Y/Z.

Тогда уравнение, соответствующее эллиптической кривой

y = x + a x +b,