В основу безопасности российского стандарта электронной цифровой подписи ГОСТ Р 34.10-2001 на эллиптической кривой E(F_p) над простым конечным полем из p элементов и его американского аналога ECDSS положена задача дискретного логарифмирования на эллиптической кривой. Эллиптическая кривая E(F_p) в форме Вейерштрасса задается уравнением

y² = f(x) ( mod p ),

где кубический многочлен f(x) не имеет кратных корней в поле F_p.

В основу протокола электронной цифровой подписи ГОСТ Р 34.10-2001 положен протокол Эль-Гамаля. Этот протокол обладает вычислимыми морфизмами, позволяющими на основании одного подписанного сообщения создавать произвольное число формально правильных пар сообщение-подпись, поэтому подпись вычисляется для значения хэш-функции от сообщения. Пусть m - подписываемое сообщение, h - хэш-функция по ГОСТ Р 34.11-94, {E(F_p), Q, P} - открытый ключ, число l, - секретный ключ, при этом P = lQ. Для формирования подписи выполняются следующие действия:

• вычисляется хэш-функция e = h(m) ( mod r ), причем e неравно 0;
• вырабатывается случайный показатель k, 0 < k < r, и вычисляется точка R = (x_R, y_R) = k_Q, причем x_R неравно 0 ( mod r );
• вычисляется часть подписи
  s = (lx_R + ke) ( mod r ),
  причем s неравно 0.

Подписанное сообщение представляет собой тройку (m, x_R ( mod r ), s). Для проверки подписи выполняются следующие действия:

• проверяются условия 0 < x_R ( mod r ) < r и 0 < s < r;
• вычисляется e = h(m) ( mod r ) и если e = 0, то считается e = 1;
• вычисляется точка R' = (se^-1 ( mod r ))Q - (x_Re ^-1 ( mod r ))Q;
• проверяется сравнение xR' = x_R ( mod r ).

Если сравнение выполняется, то подпись верна.

Для обеспечения высокой сложности задачи дискретного логарифмирования на эллиптической кривой необходимо выполнение следующих условий, предусмотренных ГОСТ Р 34.10-2001:

• p - простое число длины 256 бит;
• многочлен f(x) не имеет кратных корней (дискриминант многочлена f отличен от нуля);
• многочлен f(x) не должен задаваться неполным уравнением;
• число точек |E(F_p)| имеет простой делитель r длины от 254 до 256 бит;
• порядок группы E(F_p) |E(F_p)| неравен p;
• p^k неравно 1 ( mod r ) для k = 1,... , 30.

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