Подпись .

,

1) проверить m, что 0<s<q, 0<r’<q. Если хотя бы одно из неравенств нарушено, то подпись отвергается;

Вычислить ;

3) выбрать число е: ;

4) если е(mod q)=0, то е=1;

5) ;

6) , ;

7) ;

8) .

, => 0<r’<q и пункт 6);

=> 0<s<q и пункт 8);

;

Корректность: .

Проверим, что :

;

;

;

По малой теореме Ферма:

Из теоремы Эллера:

=> ;

;

;

=>

Стойкость:

1) Атака на закрытый ключ:

y=>x

=>можно решить задачу дискретного логарифмирования:

(если длина р=1024 бит);

если учесть, что 0<x₂₅₆<q=>метод Полларда;

(если длина q=256 бит).

2) Атака на неотказуемость:

Мошенник пытается отказаться от подписанного им сообщения.

m – сообщение, s – подпись.

(m₁,s₁) => получатель

(m₂,s₂) предъявляет как истинное (m₂,s₂) и отказывается от первого сообщения.

Можно: s₁=s₂.

,

Следовательно, противник формирует сообщение с одинаковой подписью (m₁,s), (m₂,s), посылает (m₁,s), предъявляет (m₂,s), отказывается от m₁.

;

;

, ;

одинаково для m₁,m₂.

Необходимо определить, совпадают ли следующие две формулы:

;

;

;

фиксируем х₁,k,e₂,e₁ => вычисляем x₂.

Для того чтобы противостоять этой атаки, противник не должен знать полное содержание сообщения m₁,m₂ в момент генерации ключа. Это реализуется путем добавления в подписываемое сообщение атрибутов сертификата открытого ключа, которое формируется удостоверяющим центром, а не самим пользователем.