В основу безопасности российского стандарта электронной цифровой подписи ГОСТ Р 34.10-2001 на
эллиптической кривой E(Fp) над простым конечным полем из p элементов и его американского аналога
ECDSS положена задача дискретного логарифмирования на эллиптической кривой. Эллиптическая кривая
E(Fp) в форме Вейерштрасса задается уравнением
y2 = f(x) ( mod p ),
где кубический многочлен f(x) не имеет кратных корней в поле Fp.
В основу протокола электронной цифровой подписи ГОСТ Р 34.10-2001
положен протокол Эль-Гамаля. Этот протокол обладает вычислимыми морфизмами, позволяющими
на основании одного подписанного сообщения создавать произвольное число формально правильных пар
сообщение-подпись, поэтому подпись вычисляется для значения хэш-функции от сообщения.
Пусть m - подписываемое сообщение, h - хэш-функция по ГОСТ Р 34.11-94, {E(Fp), Q, P} - открытый
ключ, число l, - секретный ключ, при этом P = lQ.
Для формирования подписи выполняются следующие действия:
вычисляется хэш-функция e = h(m) ( mod r ), причем e неравно 0;
вырабатывается случайный показатель k, 0 < k < r, и вычисляется точка R = (xR, yR) = kQ,
причем xR неравно 0 ( mod r );
вычисляется часть подписи
s = (lxR + ke) ( mod r ),
причем s неравно 0.
Подписанное сообщение представляет собой тройку (m, xR ( mod r ), s).
Для проверки подписи выполняются следующие действия:
проверяются условия 0 < xR ( mod r ) < r и 0 < s < r;
вычисляется e = h(m) ( mod r ) и если e = 0, то считается e = 1;
вычисляется точка R' = (se-1 ( mod r ))Q - (xRe -1 ( mod r ))Q;
проверяется сравнение xR' = xR ( mod r ).
Если сравнение выполняется, то подпись верна.
Для обеспечения высокой сложности задачи дискретного логарифмирования на эллиптической кривой
необходимо выполнение следующих условий, предусмотренных ГОСТ Р 34.10-2001:
p - простое число длины 256 бит;
многочлен f(x) не имеет кратных корней (дискриминант многочлена f
отличен от нуля);
многочлен f(x) не должен задаваться неполным уравнением;
число точек |E(Fp)|
имеет простой делитель r длины от 254 до 256 бит;
порядок группы E(Fp) |E(Fp)| неравен p;
pk неравно 1 ( mod r ) для k = 1,... , 30.
Безопасность протокола подписи непосредственно зависит от сложности обращения хэш-функции и
сложности вычисления коллизий хэш-функции, так как в первом случае можно вычислить сообщение
для имеющейся подписи, а во втором — заготовить пару сообщений с одинаковыми значениями e,
подписать одно из них, а потом заменить одно сообщение другим.