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

Преимущество подхода на основе эллиптических кривых в сравнении с задачей факторизации числа, используемой в RSA, или задачей целочисленного логарифмирования, применяемой в алгоритме Диффи-Хеллмана, заключается в том, что в данном случае обеспечивается эквивалентная защита при меньшей длине ключа.

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

y² + a × x × y + b × y = x ³ + c × x ² + d × x + e.

В качестве примера рассмотрим эллиптическую кривую, уравнение которой имеет вид: y ² + y = x ³ – x ². На рис. 4.1 изображен график этой кривой. На этой кривой лежат только четыре точки, координаты которых являются целыми числами. Это точки А (0, 0), В (1, –1), С (1, 0) и D (0, –1).

 

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

 

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

· на плоскости существует бесконечно удаленная точка O, принадлежащая кривой, в которой сходятся все вертикальные прямые;

· считается, что касательная к кривой пересекает точку касания два раза;

· если три точки эллиптической кривой лежат на прямой линии, то их сумма есть O.

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

1. Точка O выступает в роли нулевого элемента: для любой точки Р на эллиптической кривой Р + O = Р.

2. Вертикальная линия пересекает кривую в двух точках с одной и той же координатой х – скажем, P ₁ = (x, y) и P ₂ = (x, –y) (эта прямая пересекает кривую и в бесконечно удаленной точке O), поэтому Р ₁ + Р ₂ = O и Р ₁ = – Р ₂.

3. Чтобы сложить две точки P и Q (см. рис. 4.2) с разными координатами х, следует провести через эти точки прямую и найти точку пересечения ее с эллиптической кривой. Если прямая не является касательной к кривой в точках P или Q, то существует только одна такая точка, обозначим ее S. Согласно предположению P + Q + S = О, следовательно, P + Q = – S, или P + Q = T.

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

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

 

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

 

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

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

.

Такую кривую обычно обозначают E_p (a, b). При этом числа а и b должны быть меньше р и должны удовлетворять условию

.

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

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

1. Р + O = Р.

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

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

,

,

где .

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

,

,

где .

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

Рассмотрим подход к шифрованию/расшифрованию с использованием эллиптических кривых. Задача состоит в том, чтобы зашифровать сообщение М, которое может быть представлено в виде точки на эллиптической кривой P_m (x, y). В качестве параметров алгоритма рассматривается эллиптическая кривая E_p (a, b) и точка G на ней.

Секретным ключом шифрования является некоторое случайное число n, открытый ключ Q вычисляется следующим образом Q = n × G.

Процедура шифрования осуществляется следующим образом: выбирается случайное целое положительное число k и вычисляется шифртекст C_m, являющийся точкой на эллиптической кривой:

.

Для расшифрования требуется умножить первую координату точки C_m на секретный ключ и вычесть полученный результат из второй координаты:

.

Если отправитель зашифровал сообщение P_m добавлением к нему k ´ Q, то никто не знает значения k, поэтому, хотя Q и является открытым ключом, никто не знает k ´ Q. Получатель также не знает k, но ему в качестве подсказки посылается k ´ G. Умножив k ´ G на свой закрытый ключ, получатель получит значение, которое было добавлено отправителем к незашифрованному сообщению. Тем самым получатель, не зная k, но имея свой закрытый ключ, может восстановить незашифрованное сообщение.

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