Российский стандарт ЭЦП основан на криптосистеме типа Эль-Гамаль.

В качестве группы используется группа точек на эллиптической кривой над конечным полем(группа должна быть порядка $2^{255}$ элементов).

Пусть имеются две стороны $A$ и $B$ и между ними канал связи. Пусть сторона $A$ желает передать сообщение $M$ стороне $B$ и подписать его. Сторона $B$ должна проверить правильность подписки, то есть аутентифицировать сторону $A$ .

Формирование пары открытого и закрытого ключей

Выбрать простое число $p>2^{255}$ ,
Записать уравнение эллиптической кривой

$E:~y^2=x^3+ax+b~\bmod~p$ ,

которое определяет группу точек эллиптической кривой $E(\mathbb{Z})$ .

Для того, чтобы выбрать группу, Alice задает два случайныx числа $0<a,b<p-1$ , либо эллиптический инвариант $J(E)$ в интервале $0<J(E)<1728$ :

$J(E)=1728\frac{4a^3}{4a^3+27b^2}~\bmod~p$ ,

и для нахождения $a,b$ вычисляется

$K=\frac{J(E)}{1728-J(E)},~~a=3K~\bmod~p,~~b=2K~\bmod~p$ .

подобрать числа натуральное $n$ и простое $q$ такие, что

$m=nq,~2^{254}<q<2^{256},~n\geqslant 1$ ,

где $m$ - порядок группы точек эллиптической кривой $E(\mathbb{Z}_p)$ , а $q$ - делитель этого порядка.

Выбрать точку в циклической подгруппе порядка $q$ - точку $P$ .

$P\in\mathbb{E}(\mathbb{Z}_p): qP\equiv 0$ .

Случайно выбирать число $d$ и вычислить точку

$Q=dP$ ,

Сформировать секретный ключ: $SK=\{d\}$
Сформировать открытый ключ: $PK=\{E,p,q,P,Q\}$

Процесс подписи сообщения

Вычисляет число $e=h(M)~\bmod~q$ .
Случайно выбирает число $r$ и вычисляет точку
$C=rP=(x_c,y_c)$ ,
если такая точка не существует, то выбирает другое число $r$ .
Вычисляет число $a=x_c~\bmod~q$ .
Вычисляет число $b=re+ad~\bmod~q$ .
Формирует подпись

$S(M)=\{a,b\}$ .

Процесс проверки подписи

Проверить условия
$a<q,~a<b$ .
Если эти условия не выполняются, то подпись отвергается. Если условия выполняются, то процедура продолжается.
Вычислить число