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

Рис. 3.9 дает общую идею схемы цифровой подписи Эль-Гамаля.

Рис. 3.9. Общая идея схемы цифровой подписи Эль-Гамаля

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

Генерация ключей

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

В схеме цифровой подписи Эль-Гамаля (e1, e2, p) - открытый ключ Алисы; d -секретный ключ Алисы.

Подтверждение и проверка

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

Рис. 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₂ Бобу.

Проверка. Объект, например Боб, получает М, 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₂, с которого мы начали процесс подписания.

Пример 3.2

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

M = 320S₁ = e₁^r = 2³⁰⁷ = mod3119S₂ = (M - d x S₁) x r^-1 = (320 - 127 x 2083) x 307^-1 = 2105 mod 3118

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

V₁ = e₁^M = 2³²⁰ = 3006 mod 3119V₂ = d^S1 x S₂^S1 = 1702²⁰⁸³ x 2083²¹⁰⁵ = 3006 mod 3119

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

Пример 3.3

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

M = 3000S₁ = e₁^r = 2¹⁰⁷ = 2732mod3119S₂ = (M - d x S₁) x r^-1 = (3000 - 127 x 2083) x 107^-1 = 2526 mod 3118V₁ = e₁^M = 2³⁰⁰⁰ = 704 mod 3119V₂ = d^S1 x S₁^S2 = 1702²⁷³² x 2083²⁵²⁶ = 704 mod 3119

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