Алгоритм Эль-Гамаля

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

История и предпосылки

В 1976 году Уитфилд Диффи и Мартин Хеллман опубликовали концепцию криптографии с открытым ключом, предложив протокол обмена ключами (протокол Диффи — Хеллмана). Этот протокол позволял двум сторонам получить общий секретный ключ по незащищённому каналу, но не обеспечивал непосредственного шифрования сообщений.

Тахер Эль-Гамаль, работавший в то время в компании Hewlett-Packard, в 1985 году опубликовал работу «A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms». В ней он описал метод, который на основе протокола Диффи — Хеллмана позволял не только обмениваться ключами, но и шифровать произвольные сообщения, а также создавать цифровые подписи. Алгоритм получил имя автора.

Первоначально алгоритм был запатентован в США (патент № 4,995,082), но срок действия патента истёк в 2007 году, после чего он перешёл в общественное достояние.

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

Безопасность алгоритма Эль-Гамаля базируется на предположении, что задача дискретного логарифмирования является вычислительно неразрешимой для достаточно больших чисел. Формально это означает, что для большого простого числа \( p \) и целого числа \( g \) (образующего элемента мультипликативной группы поля \( \mathbb{Z}_p^* \)) нахождение \( x \) по известным \( g \) и \( g^x \mod p \) требует экспоненциального времени относительно размера \( p \).

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

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

1. Выбирается большое простое число \( p \). Размер \( p \) обычно составляет от 1024 до 4096 бит для обеспечения современного уровня безопасности.
2. Выбирается целое число \( g \), которое является генератором мультипликативной группы \( \mathbb{Z}_p^* \). Это означает, что степени \( g \) по модулю \( p \) порождают все числа от 1 до \( p-1 \).
3. Выбирается случайное число \( x \), такое что \( 1 < x < p-1 \). Это число является закрытым ключом.
4. Вычисляется \( y = g^x \mod p \). Это число является открытым ключом.

Открытый ключ состоит из трёх чисел: \( (p, g, y) \). Закрытый ключ — это число \( x \). Все операции шифрования и дешифрования выполняются в поле целых чисел по модулю \( p \).

Шифрование и дешифрование

Шифрование

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

1. Получает открытый ключ получателя \( (p, g, y) \).
2. Генерирует случайное число \( k \), такое что \( 1 < k < p-1 \). Это число называется эфемерным ключом (ephemeral key) и используется только для одного сеанса шифрования.
3. Вычисляет первую часть шифротекста: \( c_1 = g^k \mod p \).
4. Вычисляет общий секретный элемент: \( s = y^k \mod p \).
5. Вычисляет вторую часть шифротекста: \( c_2 = M \cdot s \mod p \).

Результирующий шифротекст представляет собой пару чисел: \( (c_1, c_2) \).

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

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

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

Корректность дешифрования следует из того, что \( c_2 \cdot s^{-1} = (M \cdot s) \cdot s^{-1} = M \mod p \).

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

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

Создание подписи

Для подписи сообщения \( M \) владелец закрытого ключа \( x \) выполняет:

1. Вычисляет хеш сообщения \( h = H(M) \), где \( H \) — криптографическая хеш-функция.
2. Выбирает случайное число \( k \), взаимно простое с \( p-1 \).
3. Вычисляет \( r = g^k \mod p \).
4. Вычисляет \( s = (h - x \cdot r) \cdot k^{-1} \mod (p-1) \).

Подписью является пара \( (r, s) \).

Проверка подписи

Любой обладатель открытого ключа \( (p, g, y) \) может проверить подпись:

1. Вычисляет хеш сообщения \( h = H(M) \).
2. Проверяет выполнение равенства: \( y^r \cdot r^s \equiv g^h \pmod{p} \).

Если равенство выполняется, подпись считается действительной.

Безопасность и криптостойкость

Криптостойкость алгоритма Эль-Гамаля напрямую зависит от размера простого числа \( p \). Рекомендуемая длина ключа в 2020-е годы составляет не менее 2048 бит. Основные угрозы безопасности:

• Задача дискретного логарифмирования: Если злоумышленник сможет решить задачу дискретного логарифмирования для выбранного \( p \), он вычислит закрытый ключ \( x \) из открытого ключа \( y \). Для чисел длиной 1024 бита и более в настоящее время не существует эффективных алгоритмов решения этой задачи на классических компьютерах.
• Атака на эфемерный ключ: Если случайное число \( k \) будет скомпрометировано или предсказуемо, злоумышленник сможет вычислить общий секретный элемент \( s \) и расшифровать сообщение. Поэтому генерация \( k \) должна быть криптографически стойкой.
• Атака по известному открытому тексту: Алгоритм Эль-Гамаля не является детерминированным — один и тот же открытый текст при разных \( k \) даёт разные шифротексты. Однако если злоумышленник знает открытый текст и соответствующий ему шифротекст, он может вычислить \( s \), но это не раскрывает закрытый ключ.
• Уязвимость к квантовым компьютерам: Как и RSA, алгоритм Эль-Гамаля уязвим для атак с использованием квантовых компьютеров (алгоритм Шора), которые могут решить задачу дискретного логарифмирования за полиномиальное время. В связи с этим ведётся разработка постквантовых криптосистем.

Применение

Алгоритм Эль-Гамаля нашёл применение в нескольких областях:

• Стандарты цифровой подписи: Модифицированная версия алгоритма Эль-Гамаля лежит в основе стандарта цифровой подписи DSA (Digital Signature Algorithm), принятого в США (FIPS 186). В России аналогом является стандарт ГОСТ Р 34.10-2012, который также основан на задаче дискретного логарифмирования, но использует эллиптические кривые.
• Шифрование в программных пакетах: Алгоритм используется в некоторых реализациях криптографических библиотек, таких как GnuPG (GNU Privacy Guard), где он применяется для шифрования ключей сессии.
• Протоколы аутентификации: Схема Эль-Гамаля может быть адаптирована для протоколов аутентификации и подтверждения подлинности.
• Криптовалюты: Некоторые криптовалюты (например, ранние версии Bitcoin) использовали модификации алгоритмов на основе дискретного логарифмирования для создания цифровых подписей, хотя в основном применяется ECDSA (на эллиптических кривых).

Сравнение с RSA

Алгоритм Эль-Гамаля и RSA — два основных асимметричных криптоалгоритма. Их сравнение:

Критика и ограничения

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

Кроме того, алгоритм требует генерации нового случайного числа \( k \) для каждого сообщения. Повторное использование \( k \) приводит к компрометации закрытого ключа.

Источники

1. ElGamal, T. (1985). A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31(4), 469-472.
2. Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press.
3. Schneier, B. (1996). Applied Cryptography: Protocols, Algorithms, and Source Code in C (2nd ed.). John Wiley & Sons.
4. Федеральный стандарт цифровой подписи США — FIPS PUB 186-5 (Digital Signature Standard).