Математические основы

Кривая третьего порядка Е, задаваемая уравнением вида

Е: Y² = X³ + аХ + b, (1)

называется эллиптической кривой.

Поскольку Y = ± Ö Х³ + аХ + b, график кривой симметричен от­носительно оси абсцисс. Чтобы найти точки его пересечения с осью абсцисс, необходимо решить кубическое уравнение

X³ + аХ + b = 0, (2)

используя известные формулы Кардано. Дискриминант этого уравне­ния

(3)

a) D < 0; б) D = 0; в) D > 0.

Рис. 1. Эллиптическая кривая:

Кривая на рис. б) называется сингулярной. В ее точке сингулярности (β,0) имеются две касательные. Сингулярные кривые мы будем исключать из нашего рассмотрения. Поэтому при за­дании кривой с помощью параметров а и b потребуем выполнения условия

4 a ³ + 27 b ² ≠ 0. (4)

Определим операцию компози­ции точек на кривой.

Возьмем какие-либо две точки Р = (x₁, y₁), Q = (x₂, y₂) Î Е и проведем через них наклонную прямую (рис. 2). Эта прямая обязательно пересечет кривую в третьей точке, которую обозначим через R'.

Рис. 2. Композиция точек R = Р + Q

Точку R = (х_з, у_з) получим путем измене­ния знака ординаты точки R'. Будем обозначать описанную операцию композиции точек следующим образом: R = Р + Q.

Пусть точка Р Î Е имеет координаты (х, у). Тогда точку с ко­ординатами (х, - у), будем обозначать - Р. Будем считать, что вер­тикальная прямая, проходящая через Р и - Р, пересекает кривую в бесконечно удаленной точке О, т.е. Р + (-Р) = O. По соглашению Р + О = О + Р = Р. Т очка О будет играть роль нуля в операциях на эллиптической кривой.

Теперь представим, что точки Р и Q (рис. 2) сближаются друг с другом и, наконец, сливаются в одну точку Р = Q = (x₁, y₁). Тогда композиция R = (х_з,y_з) = Р + Q = Р + Р будет получена путем проведения касательной в точке Р и отражения ее второго пересечения с кривой R' относительно оси абсцисс (рис. 3). Будем использовать следующее обозначение: R =

Р + Р = [2]Р. Композицию точек часто называют сложением точек. Удобно ввести следующие обозначения.

[m]P = Р + Р+…+ Р (m слагаемых),

[0]Р = О,

[-т]Р = - (Р + Р+…+ Р) (m слагаемых).

Рис. 3. Удвоение точки R = Р + Р = [2]Р

Обозначим через k угловой коэффициент прямой.

. (5)

Тогда формулы для вычисления координат точки R:

x ₃ = k ² – x ₁ – x ₂, (6)

y₃ = k (x₁ – x₃ ) – y₁, (7)

(8)

В криптографии используется кривая

Е_р(a,b): Y ² = X ³ + аХ + b (mod p).(9)

В уравнении (9) переменные X, Y и коэффициенты a, b, где a, b < р, принимают целочисленные значения, а все вычисления выполняются по модулю р. В соответствии с (4) на a, b накладывается ограничение

(4 а ³ + 27 b ²) mod р ≠ 0. (10)

Количе­ство точек в будем обозначать #Е_р(а, b).