Протокол электронной цифровой подписи

Пользователь А публикует эллиптическую кривую (*), в том числе простое число p, точку и простое число q, которое является порядком этой точки в группе . А выбирает свой секретный ключ , и публикует свой открытый ключ из . Пусть вычет – хэш – значение подписываемого сообщения. Чтобы получить подпись для m, А выполняет следующие шаги.

1) А выбирает случайный секретный вычет , где , вычисляет точку = , где представитель класса вычетов выбирается из фиксированного интервала .

2) А вычисляет . Если , то перейти к шагу 1. В противном случае вычислить

.

Если , то перейти к шагу 1. В противном случае пара чисел c, d, где есть подпись для m.

Чтобы проверить подпись А под сообщением m (хэш – значением сообщения), Б выполняет следующие шаги.

1) Б вычисляет и вычеты , .

2) Б вычисляет точку , .

3) Если , то подпись принимается, в противном случае – отвергается.

Замечание. 1) Легко показать, что подпись А не будет отвергнута Б. Действительно, видим, что

,

так как . Поэтому и следовательно . Значит . Из этих рассуждений также следует, что Р является аффинной точкой, то есть и имеет вид .

2) Объем хранимой информации можно уменьшить, если вместо точек G, W хранить их x – координаты.