4.2 Криптосистема Эль-Гамаля

Разработана в 1985 году. Названа по фамилии автора - Эль-Гамаль. Данная система является альтернативой RSA и при равном значении ключа обеспечивает ту же криптостойкость. (Однако общего мнения по поводу предпочтительности того или иного метода нет).

В отличие от RSA метод Эль-Гамаля основан на проблеме дискретного логарифма. Этим он похож на алгоритм Диффи-Хелмана. Если возводить число в степень в конечном поле достаточно легко, то восстановить аргумент по значению (то есть найти логарифм) довольно трудно.

Рассмотрим систему шифрования и цифровой подписи, носящую имя ее изобретателя Эль-Гамаля и основанную на схеме формирования открытых и секретных ключей Диффи-Хеллмана. Пусть мы имеем большое простое число p , такое, что разложение числа p-1 содержит по крайней мере один большой простой множитель, и первообразный корень a по модулю p.

Механизм подписывания состоит в следующем. Некоторый абонент A выбирает секретный ключ x_A , по которому формирует открытый ключ y_A = Подписью абонента A под документом M (подписываемое сообщение должно иметь длину меньше простого модуля p , т.е. M < p) служит пара чисел (r, s) (где 0 £ r < p-1 и 0 £ s <p-1 ), которое удовлетворяет уравнению

(a^M) = y^r_Ar^S (mod p).

Данное уравнение служит для проверки того факта, что документ подписан абонентом A. (Значение y_A = является открытым ключом абонента A и доступно для всех пользователей, что позволяет каждому убедиться в том, что данное сообщение действительно подписано абонентом A.)

Данная система электронной цифровой подписи основана на том, что только действительный владелец секретного ключа a может выработать пару чисел (r, s), удовлетворяющую уравнению проверки подписи. Используя значение a , абонент A вырабатывает подпись по следующему алгоритму:

1. Сгенерировать случайное число k, удовлетворяющее условию: 0 < k < p-1 и НОД(k, p-1) = 1.

2. Вычислить: r = a^k (mod p).

3. Вычислить s из уравнения

M = x_Ar + ks (mod (p-1)).

Из теории чисел известно, что последнее уравнение имеет решение для s, если НОД(k, p-1) = 1. Это уравнение получается путем подстановки в уравнение проверки подписи значения r = a^k (mod p):

Из двух последних формул видно, что владелец секретного ключа может подписать документ, а его подпись может быть проверена по его открытому ключу. Нахождение пары чисел (r, s), без знания секретного ключа вычислительно сложно. Различных подписей, соответствующих данному документу, может быть чрезвычайно много (заметим, что k может иметь разные значения), но выработать правильную подпись может только владелец секретного ключа. Множество возможных подписей отличаются значением r , но для данного r найти соответствующее значение s без знания секретного ключа практически невозможно. Для вычисления секретного ключа по открытому необходимо решить задачу дискретного логарифмирования, которая является вычислительно сложной.

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

Алгоритм цифровой подписи DSA, разработанный NIST (National Institute of Standard and Technology) и являющийся частью стандарта DSS частично опирается на рассмотренный метод.

Выше были рассмотрены механизмы двухключевой криптографии, которые дают возможность подписывать сообщения ограниченной длины (порядка 10³ бит). Если сообщение имеет большой размер, то при прямолинейном использовании таких механизмов потребуется разбить исходное сообщение на большое число блоков меньшего размера и выработать столько подписей, сколько блоков будет содержаться в сообщении. Это сильно усложняет проблему хранения подписей и самих подписанных сообщений и организации баз данных, содержащих большое число подписанных документов. Для упрощения этой проблемы подписывается не сам документ, а некоторый его цифровой образ небольшого размера, полученный по специальным криптографическим процедурам, называемым хэшированием.

Алгоритм хэширования должен быть таким, чтобы обеспечить вычислительную неосуществимость нахождения двух сообщений с одинаковым значением цифрого образа (значением хэш-функции от сообщения). В настоящее время разработаны алгоритмы, которые удовлетворяют этому условию и позволяют легко вычислить значение хэш-функции от данного документа. Вместо подписывания большого числа отдельных частей электронного документа в реальных системах цифровой подписи осуществляется вычисление хэш-функции от документа и подписывание хэш-функции. Если хэш-функция подписана, то документ считается подписанным.