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

Преимущество подхода на основе эллиптических кривых в сравнении с задачей факторизации числа, используемой в 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.