Для определения схемы цифровой подписи необходимо описать базовые математические объекты, используемые в процессах ее формирования и проверки. В данном разделе установлены основные математические определения и требования, накладываемые на параметры схемы цифровой подписи.

5.1 Математические определения

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

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

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

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

. (3)

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

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

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

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

. (4)

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

. (5)

В случае, когда выполнено условие и сумму точек и будем называть нулевой точкой О, не определяя ее х- и у-координаты. В этом случае точка называется отрицанием точки . Для нулевой точки О выполнены равенства

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

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

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

5.2 Параметры цифровой подписи

Параметрами схемы цифровой подписи являются:

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

- эллиптическая кривая Е, задаваемая своим инвариантом J(E) или коэффициентами а, b ;

- целое число m - порядок группы точек эллиптической кривой Е;

- простое число q - порядок циклической подгруппы группы точек эллиптической кривой Е, для которого выполнены следующие условия:

- точка эллиптической кривой Е, с координатами , удовлетворяющая равенству qP = 0;

- хэш-функция , отображающая сообщения, представленные в виде двоичных векторов произвольной конечной длины, в двоичные вектора длины 256 бит. Хэш-функция определена в ГОСТ Р 34.11.

Каждый пользователь схемы цифровой подписи должен обладать личными ключами:

- ключом подписи - целым числом d, удовлетворяющим неравенству ;

- ключом проверки - точкой эллиптической кривой Q с координатами , удовлетворяющей равенству dP = Q.

На приведенные выше параметры схемы цифровой подписи накладываются следующие требования:

- должно быть выполнено условие , для всех целых t = 1, 2, ... В, где В удовлетворяет неравенству ;

- должно быть выполнено неравенство ;

- инвариант кривой должен удовлетворять условию или 1728.

5.3 Двоичные векторы

Для определения процессов формирования и проверки цифровой подписи необходимо установить соответствие между целыми числами и двоичными векторами длины 256 бит.

Рассмотрим следующий двоичный вектор длиной 256 бит, в котором младшие биты расположены справа, а старшие - слева.

где равно либо 1, либо 0. Будем считать, что число соответствует двоичному вектору , если выполнено равенство

Для двух двоичных векторов и , соответствующих целым числам и , определим операцию конкатенации (объединения) следующим образом. Пусть

, (12)

,

тогда их объединение имеет вид