Схема Эль-Гамаля. 
Криптографические методы защиты информации

Предложенная в 1984 году схема электронной подписи ЭльГамаля является наиболее распространенной и лежит в основе стандартов Российской Федерации, Германии, Соединенных Штатов Америки и еще целого ряда стран.

Стойкость данной схемы основывается на решении задачи дискретного логарифмирования в некоторой абелевой группе. В качестве такой группы, как правило, выступает либо мультипликативная группа конечного простого поля, либо группа точек эллиптической кривой. Основная привлекательность схемы Эль-Гамаля заключается в том, что она представляет собой семейство схем, которые могут быть оптимизированы в зависимости от потребностей субъекта, использующего данную схему.

Вначале мы дадим краткое описание общей схемы Эль-Гамаля применительно к мультипликативной группе поля, а далее приведем примеры конкретных схем, реализованных в группе точек эллиптической кривой.

Пусть р — большое простое число, q — простое число, для которого выполнено условие qp— 1. Рассмотрим вычет a G F* такой, что ordp а — q, то есть число q является показателем вычета а по модулю р, см. определение 9.9.

Также мы зафиксируем бесключевую функцию хеширования Н: F|° —> F₂^!, отображающую сообщения произвольной длины в двоичные векторы длины п. Дополнительно будем считать, что выполнено неравенство q < 2^п.

Поскольку каждый двоичный вектор (h,…, h_n) может быть естественным образом представлен в виде целого числа.

то далее мы будем использовать отображение Н: Flf -" ?_q, определяемое равенством.

Будем считать, то абонент, подписывающий сообщения, обладает секретным ключом электронной подписи Ад, представленным в виде вычета Ад € F*, и открытым ключом подписи к_е, представленным в виде вычета к_е € F* и удовлетворяющим равенству.

Для выработки электронной подписи с под сообщением s в обобщенной схеме Эль-Гамаля абонент должен выполнить следующие шаги.

Алгоритм 11.1 (Алгоритм выработки электронной подписи) Вход: Открытые параметры схемы р, q, а, отображение Я, а также сообщение s, под которым вычисляется подпись.

Выход: Электронная подпись с под сообщением s, представляющая собой пару вычетов по модулю q.

• 1. Определить образ сообщения s — величину h = H (s).
• 2. Вычислить случайное число к е {1,… <7 — 1}.
• 3. Определить вычет г = и^к (mod р).
• 4. Определить значение t, удовлетворяющее сравнению

где знаки ± должны быть выбраны заранее и фиксированы.

5. Определить в качестве электронной подписи пару (г (mod q), t).? тому, что в 2001 году была принята новая редакция данного стандарта, предписывающая производить вычисления в группе точек эллиптической кривой, определенной над конечным простым нолем.