Содержание
Схема цифровой подписи Эль-Гамаля
В процессе подписания две функции создают две подписи. На стороне подтверждения обрабатывают выходы двух функций и сравнивают между собой для проверки. Обратите внимание, что одна и та же функция применяется и для подписания, и для проверки, но использует различные входы. Рисунок показывает входы каждой функции. Сообщение — часть входа, для обеспечения функционирования при подписании; оно же — часть входа к функции 1 при подтверждении. Обратите внимание, что вычисления в функциях 1 и 3 проводятся по модулю p, а функции 2 — по модулю p — 1.
Процедура генерации ключей здесь точно такая же, как та, которая используется в криптографической системе. Выберем достаточно большое простое число p, чтобы в поле Z p* проблема дискретного логарифма была достаточно трудной. Пусть e1 — простой элемент в Z p*. Алиса выбирает свой секретный ключ d, чтобы он был меньше, чем p — 1. Она вычисляет e2 = e1d. Открытый ключ Алисы — кортеж (e1, e2, p) ; секретный ключ Алисы — d.
Рисунок 3.10 показывает схему цифровой подписи Эль-Гамаля.
- Алиса выбирает секретное случайное число r. Обратите внимание, что хотя открытые и секретные ключи могут использоваться неоднократно, Алиса каждый раз нуждается в новом r, когда она подписывает новое сообщение.
- Алиса вычисляет первую подпись S1 = er mod p.
- Алиса вычисляет вторую подпись S2 = (М — d x S1) x r-1 mod (p — 1),где r — мультипликативная инверсия r по модулю p — 1.
- Алиса передает М, S1 и S2 Бобу.
- Боб проверяет, что 0 < S1 < p.
- Боб проверяет, что 0 < S2 < p — 1.
- Боб вычисляет V1 = e1M mod p.
- Боб вычисляет V2 = e2S1 x e2S2 mod p.
- Если V1 является конгруэнтным V2, сообщение принято; иначе оно будет отклонено. Мы можем доказать правильность этого критерия проверки, используя e2 = e1d и S1 = e1r:
Мы имеем
Поскольку e1 — первообразный корень, может быть доказано, что вышеупомянутое сравнение справедливо тогда и только тогда, когда , и результат сравнения есть тот же самый S2, с которого мы начали процесс подписания.
Ниже приводится тривиальный пример. Алиса выбрала p = 3119, e1 = 2, d = 127 и вычислила e2 = 2127 mod 3119 = 1702. Она выбрала r равным 307. Она объявила e1, e2 и p ; она сохранила в тайне d. Далее показано, как Алиса может подписать сообщение.
Поскольку V1 и V2 являются конгруэнтными, Боб принимает сообщение, и он предполагает, что сообщение было подписано Алисой, потому что никто, кроме нее, не имеет секретного ключа Алисы d.
Теперь вообразите, что Алиса хочет передать другое сообщение, М = 3000, Тэду. Она выбирает новое r = 107. Алиса передает М., S1 и S2 Тэду. Тэд использует общедоступные ключи, чтобы вычислить V1 и V2.
Подделка цифровой подписи в схеме Эль-Гамаля
Подделка только ключа. В этом типе подделки Ева имеет доступ только к открытому ключу. Возможны два варианта:
Подделка при известном сообщении. Если Ева перехватила сообщение М и его две подписи S1 и S2, она может найти другое сообщение М’, с той же самой парой подписей S1 и S2. Однако обратите внимание, что это — экзистенциальная подделка, которая не помогает Еве.
Источник