Нуралиев Д.С.

Евразийский Национальный университет им. Л.Н.Гумилева, Казахстан

Математические понятия эллиптических кривых

В общем случае уравнение эллиптической кривой Е имеет вид:

y² + axy + by = x³ + cx² + dx + e

В качестве примера рассмотрим эллиптическую кривую   Е, уравнение которой имеет вид: y² + y = x³ - x²

Рис. 1. Пример эллиптической кривой с четырьмя точками

На этой кривой лежат только четыре точки, координаты которых являются целыми числами. Это точки А (0, 0), В (1, -1), С (1, 0) и D (0, -1)

Для определения операции сложения для точек на эллиптической кривой сделаем следующие предположения:

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

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

Введем следующие правила сложения точек на эллиптической кривой:

• Точка 0 выступает в роли нулевого элемента. Так, 0 = -0 и для любой точки Р на эллиптической кривой Р + 0 = Р.
• Вертикальная линия пересекает кривую в двух точках с одной и той же координатой х-скажем, S=(x,y) и T=(x,-y). Эта прямая пересекает кривую и в бесконечно удаленной точке. Поэтому Р₁ + Р₂ + 0 = 0 и Р₁ = -Р₂.
• Чтобы сложить две точки P и Q с разными координатами х, следует провести через эти точки прямую и найти точку пересечения ее с эллиптической кривой. Если прямая не является касательной к кривой в точках P или Q, то существует только одна такая точка, обозначим ее S. Согласно нашему предположению P + Q + S = 0

Следовательно, P + Q = -S или P + Q = T

Если прямая является касательной к кривой в какой-либо из точек P или Q, то в этом случае следует положить S = P или S = Q соответственно.

• Чтобы удвоить точку Q, следует провести касательную в точке Q и найти другую точку пересечения S с эллиптической кривой. Тогда Q + Q = 2 × Q = -S.

Введенная таким образом операция сложения подчиняется всем обычным правилам сложения, в частности коммутативному и ассоциативному законам. Умножение точки Р эллиптической кривой на положительное число k определяется как сумма k точек Р.

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

y²  x³ + ax + b (mod p)

Такую кривую будем обозначать E_p (a,b). При этом числа а и b должны быть меньше р и должны удовлетворять условию 4a³ + 27b² (mod p)  0. Множество точек на эллиптической кривой вычисляется следующим образом.

1. Для каждого такого значения х, что 0  х  р, вычисляется x³ + ax + b (mod p).

2. Для каждого из полученных на предыдущем шаге значений выясняется, имеет ли это значение квадратный корень по модулю р. Если нет, то в E_p(a,b) нет точек с этим значением х. Если корень существует, имеется два значения y, соответствующих операции извлечения квадратного корня (исключением является случай, когда единственным значением оказывается y = 0). Эти значения (x,y) и будут точками E_p (a,b).

Множество точек E_p (a,b) обладает следующими свойствами:

1. Р + 0 = Р

2. Если Р = (x,y), то Р + (x,-y) = 0. Точка (x,-y) является отрицательным значением точки Р и обозначается -Р. Заметим, что (x,-y) лежит наэллиптической кривой и принадлежит E_p (a,b).

3. Если Р = (x₁,y₁) и Q = (x₂,y₂), где P  Q, то P + Q = (x₃,y₃) определяется по следующим формулам:

4. x₃ λ² - x₁ - x₂ (mod p)

5. y₃ λ (x₁ - x₃) - y₁ (mod p)

где

(y₂ - y₁)/(x₂ - x₁) , если P Q

λ = {

(3x₁² + a)/2y₁ , если P = Q

Число λ есть угловой коэффициент секущей, проведенной через точки P = (x₁, y₁) и Q = (x₂, y₂). При P = Q секущая превращается в касательную, чем и объясняется наличие двух формул для вычисления λ.

Задача, которую должен решить в этом случае атакующий, есть своего рода задача "дискретного логарифмирования на эллиптической кривой", и формулируется она следующим образом. Даны точки P и Q на эллиптической кривой   E_p (a,b). Необходимо найти коэффициент k < p такой, что P = k × Q

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

Литература:

1. Библиотека MSDN Library for Visual Studio 2008

2. Интернет-Университет Информационных Технологий, http://www.intuit.ru

3. Сергей Панасенко, “Алгоритмы шифрования”, Санкт-Петербург - 2009