Эцп эль гамаля пример

Схема цифровой подписи Эль-Гамаля

В процессе подписания две функции создают две подписи. На стороне подтверждения обрабатывают выходы двух функций и сравнивают между собой для проверки. Обратите внимание, что одна и та же функция применяется и для подписания, и для проверки, но использует различные входы. Рисунок показывает входы каждой функции. Сообщение — часть входа, для обеспечения функционирования при подписании; оно же — часть входа к функции 1 при подтверждении. Обратите внимание, что вычисления в функциях 1 и 3 проводятся по модулю p, а функции 2 — по модулю p — 1.

Процедура генерации ключей здесь точно такая же, как та, которая используется в криптографической системе. Выберем достаточно большое простое число p, чтобы в поле Z _p* проблема дискретного логарифма была достаточно трудной. Пусть e₁ — простой элемент в Z _p*. Алиса выбирает свой секретный ключ d, чтобы он был меньше, чем p — 1. Она вычисляет e₂ = e₁^d. Открытый ключ Алисы — кортеж (e₁, e₂, p) ; секретный ключ Алисы — d.

Рисунок 3.10 показывает схему цифровой подписи Эль-Гамаля.

1. Алиса выбирает секретное случайное число r. Обратите внимание, что хотя открытые и секретные ключи могут использоваться неоднократно, Алиса каждый раз нуждается в новом r, когда она подписывает новое сообщение.
2. Алиса вычисляет первую подпись S₁ = e^r mod p.
3. Алиса вычисляет вторую подпись S₂ = (М — d x S₁) x r^-1 mod (p — 1),где r — мультипликативная инверсия r по модулю p — 1.
4. Алиса передает М, S₁ и S₂ Бобу.

1. Боб проверяет, что 0 < S₁ < p.
2. Боб проверяет, что 0 < S₂ < p — 1.
3. Боб вычисляет V₁ = e₁^M mod p.
4. Боб вычисляет V₂ = e₂^S1 x e₂^S2 mod p.
5. Если V₁ является конгруэнтным V₂, сообщение принято; иначе оно будет отклонено. Мы можем доказать правильность этого критерия проверки, используя e₂ = e₁^d и S₁ = e₁^r:

   
   Мы имеем

   
   
   
   

   
   Поскольку e₁ — первообразный корень, может быть доказано, что вышеупомянутое сравнение справедливо тогда и только тогда, когда , и результат сравнения есть тот же самый S₂, с которого мы начали процесс подписания.

Ниже приводится тривиальный пример. Алиса выбрала p = 3119, e₁ = 2, d = 127 и вычислила e₂ = 2¹²⁷ mod 3119 = 1702. Она выбрала r равным 307. Она объявила e₁, e₂ и p ; она сохранила в тайне d. Далее показано, как Алиса может подписать сообщение.

Поскольку V₁ и V₂ являются конгруэнтными, Боб принимает сообщение, и он предполагает, что сообщение было подписано Алисой, потому что никто, кроме нее, не имеет секретного ключа Алисы d.

Теперь вообразите, что Алиса хочет передать другое сообщение, М = 3000, Тэду. Она выбирает новое r = 107. Алиса передает М., S₁ и S₂ Тэду. Тэд использует общедоступные ключи, чтобы вычислить V₁ и V₂.

Подделка цифровой подписи в схеме Эль-Гамаля

Подделка только ключа. В этом типе подделки Ева имеет доступ только к открытому ключу. Возможны два варианта:

Подделка при известном сообщении. Если Ева перехватила сообщение М и его две подписи S₁ и S₂, она может найти другое сообщение М’, с той же самой парой подписей S₁ и S₂. Однако обратите внимание, что это — экзистенциальная подделка, которая не помогает Еве.

Источник

• http://www.intuit.ru/studies/higher_education/3406/courses/409/lecture/9379?page=4