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

 

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

Криптосистемы на базе эллиптических кривых имеют более высокую производительность и позволяют использовать ключи существенно меньшего размера при сохранении требуемого уровня безопасности.

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

¨ эллиптическая кривая в конечном поле F_p, где р – простое число, р > 3;

¨ эллиптическая кривая в конечном поле .

 

Эллиптическая кривая в конечном поле F _p. Пусть задано простое число р > 3. Тогда эллиптической кривой Е, определенной над конечным простым полем F_p, называется множество пар чисел (х, у), х Î F_p, у Î F_p, удовлетворяющих тождеству

 

, (4.18)

 

где а, b Î F_p и не сравнимо с нулем по модулю p.

Инвариантом эллиптической кривой называется величина , удовлетворяющая тождеству

 

. (4.19)

 

Коэффициенты a, b эллиптической кривой Е по известному инварианту определяются следующим образом:

. (4.20)

 

Пары (х, у), удовлетворяющие тождеству (4.18), называются точками эллиптической кривой Е; х и у – соответственно х и y -координатами точки.

Точки эллиптической кривой будем обозначать Q (х, у) или просто Q. Две точки эллиптической кривой равны, если равны их соответствующие х - и y -координаты.

На множестве всех точек эллиптической кривой Е введем операцию сложения, которую обозначим знаком +. Для двух произвольных точек и эллиптической кривой Е рассмотрим несколько вариантов.

Пусть координаты точек Q ₁ и Q ₂ удовлетворяют условию . В этом случае их суммой будем называть точку , координаты которой определяются сравнениями

 

(4.21)

 

Если выполнены равенства и , то координаты точки Q ₃ определяются следующий образом:

 

(4.22)

 

В случае когда выполнено условие и , сумму точек Q ₁ и Q ₂ называют нулевой точкой , не определяя ее х - и y -координаты. В этом случае точка Q ₂ называется отрицанием точки Q _1. Для нулевой точки выполняются равенства

 

, (4.23)

 

где Q – произвольная точка эллиптической кривой Е.

Относительно введенной операции сложения множество всех точек эллиптической кривой Е вместе с нулевой точкой образуют конечную абелеву (коммутативную) группу порядка m, для которого выполнено неравенство

 

(4.24)

 

Точка Q называется точкой кратности k, или кратной точкой эллиптической кривой Е, если для некоторой точки Р выполнено равенство

 

(4.25)

 

Эллиптическая кривая в конечном поле определяется соотношением

 

 

при нулевом b.

 

Эллиптической кривой является группа решений , , приведенного выше соотношения при определенных значениях а и b, а также нулевая точка .

Аналогично группе эллиптической кривой , множество всех точек эллиптической кривой вместе с нулевой точкой образуют конечную абелеву группу.

С помощью описанных выше правил сложения можно вычислить точку kP для любого целого числа k и любой точки Р эллиптической кривой.

Однако решение обратной задачи – нахождение числа k по известным точкам Р и kP – является трудноразрешимой проблемой. Данную задачу называют проблемой дискретного логарифма эллиптической кривой ECDLP (Elliptic Curve Discrete Logarithm Problem). Решение проблемы ECDLP является значительно более сложным, чем проблемы дискретного логарифмирования (нахождение числа х по заданному числу при известных основании g и модуле p), на которой базируются RSA-подобные асимметричные криптосистемы.

Сложность решения проблемы ECDLP обусловлена ресурсоемкостью операций сложения и дублирования точек, с помощью которых вычисляется kP. Отсюда следует возможность применения более коротких ключей. Например, ключу размером 1024 бит алгоритма DSA соответствует по криптостойкости ключ размером 160 бит алгоритма.