Криптосистема на основе эллиптических кривых
Преимущество подхода на основе эллиптических кривых в сравнении с задачей факторизации числа, используемой в RSA, или задачей целочисленного логарифмирования, применяемой в алгоритме Диффи-Хеллмана, заключается в том, что в данном случае обеспечивается эквивалентная защита при меньшей длине ключа.
В общем случае уравнение эллиптической кривой имеет вид:
y2 + a×x×y + b×y = x3 + c×x2 + d×x + e.
В качестве примера рассмотрим эллиптическую кривую, уравнение которой имеет вид: y2 + y = x3 – x2. На рис. 4.1 изображен график этой кривой. На этой кривой лежат только четыре точки, координаты которых являются целыми числами. Это точки А (0, 0), В (1, –1), С (1, 0) и D (0, –1).
|
| Рис. 4.1. Пример эллиптической кривой с четырьмя точками. |
Для определения операции сложения для точек на эллиптической кривой используются следующие предположения:
· на плоскости существует бесконечно удаленная точка O, принадлежащая кривой, в которой сходятся все вертикальные прямые;
· считается, что касательная к кривой пересекает точку касания два раза;
· если три точки эллиптической кривой лежат на прямой линии, то их сумма есть O.
Введем следующие правила сложения точек на эллиптической кривой.
1. Точка O выступает в роли нулевого элемента: для любой точки Р на эллиптической кривой Р + O = Р.
2. Вертикальная линия пересекает кривую в двух точках с одной и той же координатой х – скажем, P1 = (x, y) и P2 = (x, –y) (эта прямая пересекает кривую и в бесконечно удаленной точке O), поэтому Р1 + Р2 = O и Р1 = –Р2.
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 точек Р.
В криптографии с использованием эллиптических кривых все значения вычисляются по модулю р, где р является простым числом. Элементами данной эллиптической кривой являются пары неотрицательных целых чисел, которые меньше р и удовлетворяют частному виду эллиптической кривой:
.
Такую кривую обычно обозначают Ep(a,b). При этом числа а и b должны быть меньше р и должны удовлетворять условию
.
Множество точек на эллиптической кривой вычисляется следующим образом. Для каждого такого значения х, что 0 £ х £ р, вычисляется 
. Далее, для каждого из полученных на предыдущем шаге значений выясняется, имеет ли это значение квадратный корень по модулю р. Если нет, то в Ep(a,b) нет точек с этим значением х. Если корень существует, имеется два значения y, соответствующих операции извлечения квадратного корня (исключением является случай, когда единственным значением оказывается y = 0). Эти значения (x,y) и будут точками Ep(a,b).
Множество точек Ep(a,b) обладает следующими свойствами:
1. Р + O = Р.
2. Если Р = (x,y), то Р + (x,–y) = O. Точка (x,–y) является отрицательным значением точки Р и обозначается –Р. Заметим, что (x,–y) лежит на эллиптической кривой и принадлежит Ep(a,b).
3. Если Р = (x1, y1) и Q = (x2, y2), где x1 ¹ x2, то P + Q = (x3, y3) определяется по следующим формулам:
,
,
где 
.
4. Если Р = (x1, y1) и Q = (x2, y2), где x1 = x2, y1 = y2 ¹ 0, то P + Q = (x3, y3) определяется по следующим формулам:
,
,
где 
.
Число λ есть угловой коэффициент секущей, проведенной через точки P = (x1, y1) и Q = (x2, y2). При P = Q секущая превращается в касательную, чем и объясняется наличие двух формул для вычисления λ.
Рассмотрим подход к шифрованию/расшифрованию с использованием эллиптических кривых. Задача состоит в том, чтобы зашифровать сообщение М, которое может быть представлено в виде точки на эллиптической кривой Pm(x,y). В качестве параметров алгоритма рассматривается эллиптическая кривая Ep(a,b) и точка G на ней.
Секретным ключом шифрования является некоторое случайное число n, открытый ключ Q вычисляется следующим образом Q = n × G.
Процедура шифрования осуществляется следующим образом: выбирается случайное целое положительное число k и вычисляется шифртекст Cm, являющийся точкой на эллиптической кривой:
.
Для расшифрования требуется умножить первую координату точки Cm на секретный ключ и вычесть полученный результат из второй координаты:
.
Если отправитель зашифровал сообщение Pm добавлением к нему k ´ Q, то никто не знает значения k, поэтому, хотя Q и является открытым ключом, никто не знает k ´ Q. Получатель также не знает k, но ему в качестве подсказки посылается k ´ G. Умножив k ´ G на свой закрытый ключ, получатель получит значение, которое было добавлено отправителем к незашифрованному сообщению. Тем самым получатель, не зная k, но имея свой закрытый ключ, может восстановить незашифрованное сообщение.
Злоумышленнику для восстановления сообщения придется вычислить k, зная G и k ´ G. Эта задача является рода задачей дискретного логарифмирования на эллиптической кривой, и формулируется следующим образом: даны точки P и Q на эллиптической кривой Ep(a, b), необходимо найти коэффициент k < p такой, что P = k ´ Q.