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

Криптосистема Эль-Гамаля — это асимметричный алгоритм шифрования с открытым ключом, основанный на вычислительной сложности задачи дискретного логарифмирования в конечных полях. Разработана египетским криптографом Тахером Эль-Гамалем в 1985 году. Является одной из классических криптосистем, наряду с RSA, и широко применяется в протоколах электронной подписи (например, DSA — Digital Signature Algorithm, стандарт США) и гибридных схемах шифрования.

История

Криптосистема была предложена Тахером Эль-Гамалем в 1985 году в статье «A public key cryptosystem and a signature scheme based on discrete logarithms», опубликованной в журнале IEEE Transactions on Information Theory. Работа Эль-Гамаля развивала идеи, заложенные в криптосистеме Диффи — Хеллмана (1976), которая впервые предложила концепцию открытого ключа. В отличие от RSA, чья стойкость основана на сложности факторизации больших чисел, стойкость схемы Эль-Гамаля опирается на сложность обратного преобразования — дискретного логарифмирования в мультипликативной группе конечного поля.

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

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

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

Стойкость криптосистемы базируется на предположении, что в мультипликативной группе **Z_p^*** (где \( p \) — большое простое число) вычисление дискретного логарифма является вычислительно трудной задачей для классических компьютеров. Формально: для заданных простого числа \( p \), образующего элемента \( g \) группы и значения \( y = g^x \mod p \), найти \( x \) (дискретный логарифм \( y \) по основанию \( g \)) за полиномиальное время невозможно.

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

1. Выбирается большое простое число \( p \) и образующий элемент \( g \) мультипликативной группы **Z_p^*** (обычно \( g \) — примитивный корень по модулю \( p \)).
2. Случайным образом выбирается секретный ключ \( x \in \{1, 2, \dots, p-2\} \).
3. Вычисляется открытый ключ: \( y = g^x \mod p \).

Открытый ключ — это тройка \( (p, g, y) \); секретный ключ — \( x \).

Процедура шифрования и дешифрования

Шифрование

Для шифрования сообщения \( m \), представленного в виде числа из интервала \( 0 \leq m < p \), отправитель:

1. Генерирует случайное число \( k \in \{1, 2, \dots, p-2\} \) (это сессионный ключ, одноразовый для каждого сообщения).
2. Вычисляет:

• \( c_1 = g^k \mod p \)
• \( c_2 = m \cdot y^k \mod p \)

1. Шифротекст — пара \( (c_1, c_2) \).

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

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

1. Вычисляет общий секрет: \( s = c_1^x \mod p \)
2. Находит обратный элемент к \( s \) по модулю \( p \): \( s^{-1} \mod p \)
3. Восстанавливает сообщение: \( m = c_2 \cdot s^{-1} \mod p \)

Корректность следует из того, что \( s = c_1^x = (g^k)^x = g^{xk} = (g^x)^k = y^k \), поэтому \( c_2 \cdot s^{-1} = m \cdot y^k \cdot (y^k)^{-1} = m \mod p \).

Особенности

• Шифрование вероятностное: одно и то же сообщение \( m \) при разных \( k \) даёт разные шифротексты. Это свойство называется семантической стойкостью (при условии, что задача дискретного логарифмирования трудна).
• Длина шифротекста в два раза больше длины открытого текста (для одного блока).
• Сессионный ключ \( k \) должен быть уникальным для каждого сообщения; повторное использование \( k \) позволяет восстановить секретный ключ \( x \).

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

Стойкость к атакам

Криптосистема Эль-Гамаля является семантически стойкой (IND-CPA — неотличимость шифротекстов при атаке с выбором открытого текста) в предположении, что задача Диффи — Хеллмана (CDH — Computational Diffie-Hellman) вычислительно трудна. Это означает, что противник, знающий открытый ключ, не может отличить шифротекст одного сообщения от шифротекста другого, даже если он может выбирать открытые тексты.

Однако схема не является стойкой к атаке с выбором шифротекста (CCA) в своей базовой форме: противник, имеющий доступ к оракулу дешифрования, может модифицировать шифротекст и получить информацию о сообщении. Для защиты от CCA-атак используются модифицированные версии, например, схема Cramer-Shoup (1998) или гибридные схемы с хешированием.

Стойкость к квантовым атакам

Как и RSA, криптосистема Эль-Гамаля уязвима для атак с использованием квантового компьютера, работающего по алгоритму Шора (1994). Алгоритм Шора позволяет эффективно решать задачу дискретного логарифмирования в конечных полях, что полностью разрушает стойкость схемы. Поэтому в постквантовой криптографии (например, на основе решёток или кодов) схемы Эль-Гамаля не применяются.

Применение

Цифровая подпись

Вариант схемы Эль-Гамаля используется для создания цифровых подписей. Наиболее известный пример — алгоритм DSA (Digital Signature Algorithm), стандартизированный NIST в 1991 году. В DSA подпись состоит из двух чисел \( (r, s) \), где \( r = (g^k \mod p) \mod q \), а \( s \) вычисляется из хеша сообщения, секретного ключа и \( k \). В России аналогичный подход реализован в ГОСТ Р 34.10-2012, но на эллиптических кривых (ECDSA).

Гибридное шифрование

Из-за того, что шифрование Эль-Гамаля увеличивает размер данных в два раза, его редко используют для шифрования больших объёмов информации напрямую. Вместо этого применяют гибридные схемы: с помощью криптосистемы Эль-Гамаля шифруется сессионный ключ (например, для AES), а само сообщение шифруется симметричным алгоритмом. Пример — протоколы PGP (Pretty Good Privacy) и OpenPGP, где используется вариант Эль-Гамаля для шифрования ключей.

Криптографические протоколы

• Протокол Диффи — Хеллмана (предшественник): Эль-Гамаль фактически является расширением этого протокола на шифрование.
• Схема Cramer-Shoup (1998): модификация, обеспечивающая стойкость к CCA-атакам.
• Эллиптические кривые: аналог криптосистемы Эль-Гамаля на эллиптических кривых (EC-ElGamal) используется в некоторых протоколах, например, в стандарте ECIES (Elliptic Curve Integrated Encryption Scheme).

Сравнение с RSA

Интересные факты

• Тахер Эль-Гамаль получил степень доктора философии (PhD) в Стэнфордском университете в 1984 году под руководством Мартина Хеллмана — одного из создателей криптографии с открытым ключом.
• В 1994 году Эль-Гамаль стал сооснователем компании Certicom, специализирующейся на криптографии на эллиптических кривых.
• Схема Эль-Гамаля является гомоморфной по умножению: если перемножить шифротексты двух сообщений, то после дешифрования получится произведение исходных сообщений. Это свойство используется в некоторых протоколах конфиденциального вычисления.

Критика

Основные недостатки криптосистемы Эль-Гамаля:

• Увеличение размера данных: шифротекст в два раза длиннее открытого текста, что неэффективно для больших сообщений.
• Отсутствие стойкости к CCA-атакам в базовой версии: требуется использование дополнительных механизмов (например, хеширование или схемы Cramer-Shoup).
• Зависимость от случайности: качество генерации случайных чисел \( k \) критически важно; плохой генератор может привести к компрометации ключа.
• Уязвимость к квантовым атакам: как и большинство классических асимметричных схем, не устойчива к квантовым компьютерам.

Источники

• ElGamal, T. (1985). «A public key cryptosystem and a signature scheme based on discrete logarithms». IEEE Transactions on Information Theory, 31(4), 469–472.
• Menezes, A., van Oorschot, P., Vanstone, S. (1996). «Handbook of Applied Cryptography». CRC Press.
• Schneier, B. (1996). «Applied Cryptography: Protocols, Algorithms, and Source Code in C». John Wiley & Sons.
• Goldreich, O. (2001). «Foundations of Cryptography: Volume 1, Basic Tools». Cambridge University Press.
• Cramer, R., Shoup, V. (1998). «A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack». Advances in Cryptology — CRYPTO '98.