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

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

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

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

¨ эллиптическая кривая в конечном поле 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 бит алгоритма.