Схема Эль-Гамаля

---

Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе бывших стандартов электронной цифровой подписи в США (DSA) и России (ГОСТ Р 34.10-94).

Схема была предложена Тахером Эль-Гамалем в 1985 году^[1]. Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA, алгоритм Эль-Гамаля не был запатентован и поэтому стал более дешёвой альтернативой, так как не требовалось оплаты взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана.

Шифросистема Эль-Гамаля является фактически одним из способов выработки открытых ключей Диффи — Хеллмана.^{[источник не указан 881 день]} Шифрование по схеме Эль-Гамаля не следует путать с алгоритмом цифровой подписи по схеме Эль-Гамаля.

Сообщение ${\displaystyle M}$ должно быть меньше числа ${\displaystyle p}$. Сообщение шифруется следующим образом:

Нетрудно заметить, что длина шифротекста в схеме Эль-Гамаля вдвое больше исходного сообщения ${\displaystyle M}$.

Зная закрытый ключ ${\displaystyle x}$, исходное сообщение можно вычислить из шифротекста ${\displaystyle (a,b)}$ по формуле:

---