Схема цифровой подписи Шнорра

Проблема схемы цифровой подписи Эль — Гамаля в том, что p должно быть очень большим, чтобы сделать трудной проблему дискретного логарифма Zp*. Рекомендуется длина p по крайней мере 1024 битов. Можно сделать подпись размером 2048 бит. Чтобы уменьшить размер подписи, Шнорр предложил новую схему, основанную на схеме Эль-Гамаля, но с уменьшенным размером подписи.

Генерация ключей: Перед подписанием сообщения Алиса должна генерировать ключи и объявить всем общедоступные ключи.

• 1. Алиса выбирает простое число p, которое обычно равно по длине 1024 битам.
• 2. Алиса выбирает другое простое число q, которое имеет тот же самый размер, что и хэш, созданный функцией криптографического хэширования (?160). q | (p — 1), другими словами, (p — 1) = 0 mod q.
• 3. Алиса выбирает e₁, q-тый корень которого был бы равен 1 mod p. Чтобы сделать это, Алиса выбирает примитивный элемент в Zp, e₀ и вычисляет e₁ = e₀^(p-1)/q mod p.
• 4. Алиса выбирает целое число d, как свой секретный ключ.
• 5. Алиса вычисляет e₂ = e₁^d mod p.

Общедоступный ключ Алисы — (e_1, e₂, p, q), ее секретный ключ — (d).

Подписание:

• 1. Алиса выбирает случайное число r. (меняется каждый раз при новом сообщении) такое что 1 < r < q.
• 2. Алиса вычисляет первую подпись S₁ = h (M | e₁^r mod p). Сообщение присоединяется спереди к значению e₁^r mod p, затем применяется хэш-функция, чтобы создать хэш. хэш-функция непосредственно не применяется к сообщению, но вместо этого она получается из последовательного соединения М и e₁^r mod p.
• 3. Алиса вычисляет вторую подпись S₂ = r + d * S₁ mod q.
• 4. Алиса передает М, S₁ и S₂.

Проверка: Приемник, например Боб, получает М, S₁ и S₂.

• 1. Боб вычисляет V = h (М | e₁^S2 * e₂^-S1 mod p).
• 2. Если S₂ сравнимо с V по модулю p, сообщение принято; иначе оно отклоняется.