Эль-Гамаля шифрование

Эль-Гамаля шифрование — это криптографическая система с открытым ключом, основанная на вычислительной сложности задачи дискретного логарифмирования в конечных полях. Предложена Тахером Эль-Гамалем в 1985 году как альтернатива системе RSA, обладающая свойством вероятностного шифрования: один и тот же открытый текст при каждом шифровании даёт разные шифротексты.

История

Схема была разработана египетским криптографом Тахером Эль-Гамалем в 1985 году в рамках его докторской диссертации в Стэнфордском университете. Работа была опубликована в журнале IEEE Transactions on Information Theory. Эль-Гамаль предложил использовать математический аппарат, лежащий в основе протокола обмена ключами Диффи — Хеллмана (1976), для построения полноценной асимметричной системы шифрования. В отличие от RSA, которая опирается на сложность факторизации больших чисел, стойкость схемы Эль-Гамаля базируется на сложности дискретного логарифмирования.

В 1991 году алгоритм был включён в стандарт цифровой подписи США (DSA — Digital Signature Algorithm), который является модификацией схемы Эль-Гамаля. Впоследствии система нашла применение в протоколах шифрования электронной почты (PGP, GPG) и в криптографических библиотеках.

Математические основы

Задача дискретного логарифмирования

Безопасность схемы основана на предположении, что в мультипликативной группе Zₚ\* (где p — большое простое число) вычисление дискретного логарифма является вычислительно неосуществимым. Для заданных чисел g (образующая группа) и y = gˣ mod p нахождение x при достаточно больших p (рекомендуется 2048 бит и более) считается трудоёмкой задачей.

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

Процесс создания ключей включает следующие шаги:

1. Выбирается большое простое число p и образующая g мультипликативной группы Zₚ\*.
2. Случайным образом выбирается секретный ключ x — целое число из интервала 1 < x < p-1.
3. Вычисляется открытый ключ y = gˣ mod p.

Таким образом, открытый ключ состоит из тройки (p, g, y), а закрытый — из числа x.

Алгоритм шифрования и дешифрования

Шифрование

Для отправки сообщения M (представленного в виде числа, меньшего p) получателю с открытым ключом (p, g, y) отправитель выполняет:

1. Генерирует случайное эфемерное число k (сеансовый ключ), такое что 1 < k < p-1 и k взаимно просто с p-1.
2. Вычисляет первую часть шифротекста: c₁ = gᵏ mod p.
3. Вычисляет общий секретный элемент: s = yᵏ mod p.
4. Вычисляет вторую часть шифротекста: c₂ = M × s mod p.

Шифротекст представляет собой пару (c₁, c₂). Длина шифротекста вдвое превышает длину открытого текста.

Дешифрование

Получатель, зная свой закрытый ключ x, восстанавливает сообщение:

1. Вычисляет общий секретный элемент: s = c₁ˣ mod p (поскольку c₁ˣ = gᵏˣ = yᵏ).
2. Находит обратный элемент s⁻¹ mod p.
3. Восстанавливает сообщение: M = c₂ × s⁻¹ mod p.

Свойства

Вероятностный характер

Ключевое отличие от детерминированных схем (например, RSA в базовой реализации) — использование случайного сеансового ключа k. Одно и то же сообщение при каждом шифровании даёт разные пары (c₁, c₂), что предотвращает атаки по словарю и затрудняет статистический анализ.

Гомоморфизм

Схема Эль-Гамаля обладает свойством мультипликативного гомоморфизма: произведение зашифрованных сообщений соответствует шифротексту произведения открытых текстов. Формально: если E(M₁) = (c₁₁, c₂₁) и E(M₂) = (c₁₂, c₂₂), то E(M₁ × M₂) = (c₁₁ × c₁₂ mod p, c₂₁ × c₂₂ mod p). Это свойство используется в некоторых протоколах электронного голосования и облачных вычислений.

Размер шифротекста

Шифротекст в два раза длиннее открытого текста (по модулю p). Это делает схему менее эффективной по пропускной способности по сравнению с RSA, где шифротекст имеет ту же длину, что и модуль.

Применение

Цифровые подписи

Вариант схемы Эль-Гамаля лёг в основу алгоритма цифровой подписи DSA (Digital Signature Algorithm), принятого в 1991 году Национальным институтом стандартов и технологий США (NIST). В России аналогом является ГОСТ Р 34.10-2012, также основанный на задаче дискретного логарифмирования в группах точек эллиптических кривых.

Шифрование данных

Схема используется в программном обеспечении для шифрования электронной почты (GnuPG, PGP) и в криптографических библиотеках (OpenSSL, libgcrypt). В протоколе GPG (GNU Privacy Guard) алгоритм Эль-Гамаля применяется для шифрования сеансовых ключей симметричных шифров.

Протоколы с нулевым разглашением

Гомоморфные свойства схемы позволяют строить доказательства с нулевым разглашением и протоколы для электронного голосования, где требуется проверять корректность подсчёта голосов без раскрытия их содержимого.

Криптостойкость

Выбор параметров

Стойкость схемы напрямую зависит от размера модуля p. По состоянию на 2024 год рекомендуемая длина p составляет не менее 2048 бит для долговременной защиты. Использование коротких ключей (менее 1024 бит) делает систему уязвимой для атак с использованием решета числового поля (NFS).

Уязвимости

• Повторное использование сеансового ключа k: Если одно и то же значение k используется для шифрования двух разных сообщений, злоумышленник может восстановить оба сообщения.
• Атака на основе подобранного шифротекста: Схема не является стойкой к атакам с выбором шифротекста (CCA) в базовой реализации. Для защиты требуется применение схем преобразования, таких как OAEP (Optimal Asymmetric Encryption Padding).
• Квантовая уязвимость: Как и RSA, алгоритм Эль-Гамаля нестоек к атакам с использованием квантового компьютера, работающего по алгоритму Шора. Для постквантовой защиты рассматриваются альтернативы на основе решёток или хэш-функций.

Сравнение с RSA

Реализации

Алгоритм реализован в большинстве современных криптографических библиотек:

• OpenSSL — поддержка через функции EVP_PKEY (алгоритм id-ecPublicKey для эллиптических кривых).
• GnuPG — используется для шифрования сеансовых ключей.
• libsodium — реализация на эллиптических кривых (X25519) как аналог схемы Эль-Гамаля.
• Java Cryptography Extension (JCE) — поддержка через класс ElGamal в Bouncy Castle.

Источники

• ElGamal, T. «A public key cryptosystem and a signature scheme based on discrete logarithms». IEEE Transactions on Information Theory, 1985.
• Menezes, A., van Oorschot, P., Vanstone, S. «Handbook of Applied Cryptography». CRC Press, 1996.
• Шнайер, Б. «Прикладная криптография». Вильямс, 2003.
• NIST FIPS 186-5: Digital Signature Standard (DSS), 2023.
• ГОСТ Р 34.10-2012: Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи.