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

Схема Эль-Гамаля — это криптографическая система с открытым ключом, основанная на вычислительной сложности задачи дискретного логарифмирования в конечных полях. Предложена Тахером Эль-Гамалем в 1985 году. Является одной из классических асимметричных криптосистем, наряду с RSA, и служит основой для многих современных протоколов, включая цифровую подпись (DSA, ГОСТ Р 34.10-2012) и шифрование.

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

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

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

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

Схема Эль-Гамаля базируется на следующих математических понятиях:

• Конечное поле \( \mathbb{Z}_p^* \) — мультипликативная группа целых чисел по модулю простого числа \( p \).
• Задача дискретного логарифмирования (DLP) — для заданных \( g \) (генератор группы) и \( y = g^x \mod p \) вычислить \( x \) при больших \( p \) (обычно 1024–3072 бита) практически невозможно.
• Генератор группы \( g \) — элемент, степени которого порождают все ненулевые элементы группы.

Безопасность схемы напрямую зависит от размера \( p \) и качества генератора \( g \). Для обеспечения стойкости на современном уровне рекомендуется использовать простые числа длиной не менее 2048 бит.

Описание алгоритма

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

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

Шифрование

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

1. Отправитель генерирует случайное число \( k \) (сеансовый ключ), взаимно простое с \( p-1 \).
2. Вычисляет:

• \( a = g^k \mod p \)
• \( b = M \cdot y^k \mod p \)

1. Шифротекст — это пара \( (a, b) \). Длина шифротекста вдвое превышает длину открытого текста.

Расшифрование

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

1. Вычисляет \( a^{-x} \mod p \) (или \( a^{p-1-x} \mod p \)).
2. Вычисляет \( M = b \cdot a^{-x} \mod p \).

Обоснование: \( b \cdot a^{-x} = M \cdot y^k \cdot (g^k)^{-x} = M \cdot g^{xk} \cdot g^{-xk} = M \mod p \).

Свойства и особенности

• Вероятностный характер: Одно и то же сообщение при каждом шифровании даёт разные шифротексты (из-за случайного \( k \)). Это обеспечивает семантическую безопасность.
• Размер шифротекста: Вдвое больше размера открытого текста. Это является недостатком по сравнению с RSA.
• Скорость: Шифрование и расшифрование медленнее симметричных алгоритмов, но быстрее RSA при одинаковой длине ключа.
• Стойкость: Стойкость к атаке на основе подобранного открытого текста (IND-CPA) при условии, что DLP труднорешаема. Однако схема не является стойкой к атаке на основе подобранного шифротекста (IND-CCA) без дополнительных модификаций (например, схемы Фуджисаки — Окамото).

Применение

Шифрование

Схема Эль-Гамаля используется в гибридных криптосистемах, где асимметричный алгоритм шифрует сеансовый ключ для симметричного шифрования (например, AES). Примеры:

• PGP (Pretty Good Privacy) — в некоторых версиях используется для шифрования сеансовых ключей.
• GnuPG — поддерживает шифрование по схеме Эль-Гамаля.
• Стандарт IEEE P1363 — включает схему Эль-Гамаля для шифрования.

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

На основе схемы Эль-Гамаля построен ряд стандартов цифровой подписи:

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

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

• Протоколы доказательства с нулевым разглашением (например, протокол Шнорра).
• Схемы разделения секрета.
• Гомоморфное шифрование (свойство мультипликативной гомоморфности: \( E(M_1) \cdot E(M_2) = E(M_1 \cdot M_2) \)).

Варианты и модификации

• Эль-Гамаль на эллиптических кривых (EC-ElGamal): Использует группу точек эллиптической кривой вместо мультипликативной группы поля. Позволяет достичь той же стойкости при меньших размерах ключей (например, 256 бит вместо 3072 бит).
• Схема Фуджисаки — Окамото: Модификация, обеспечивающая стойкость к атаке на основе подобранного шифротекста (IND-CCA).
• Схема Эль-Гамаля с использованием хеш-функций: Применяется для подписи с восстановлением сообщения.

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

• Уязвимость к атаке на основе подобранного шифротекста: Без дополнительных мер (например, использования схемы «оптимальное асимметричное шифрование с дополнением» — OAEP) злоумышленник может модифицировать шифротекст и получить информацию об открытом тексте.
• Размер шифротекста: Удвоение длины делает схему неэффективной для передачи больших объёмов данных напрямую.
• Зависимость от качества генератора случайных чисел: Если \( k \) предсказуемо или повторяется, секретный ключ может быть восстановлен.
• Отсутствие аутентификации: Сама по себе схема не обеспечивает аутентификацию отправителя, что требует дополнительных механизмов (например, цифровой подписи).

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

• Тахер Эль-Гамаль также известен как один из создателей протокола SSL 3.0 и соавтор стандарта TLS.
• Схема Эль-Гамаля является основой для криптосистемы, используемой в некоторых версиях криптовалюты Bitcoin (для подписи транзакций используется ECDSA, вариант DSA на эллиптических кривых).
• В 2007 году была предложена атака на основе квантового компьютера на DLP (алгоритм Шора), что делает схему Эль-Гамаля потенциально уязвимой в постквантовую эпоху. Однако для классических компьютеров она остаётся стойкой при правильном выборе параметров.

Источники

• 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. J., van Oorschot, P. C., & Vanstone, S. A. (1996). «Handbook of Applied Cryptography». CRC Press.
• Schneier, B. (1996). «Applied Cryptography: Protocols, Algorithms, and Source Code in C». John Wiley & Sons.
• ГОСТ Р 34.10-2012. «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи».
• NIST FIPS PUB 186-4. «Digital Signature Standard (DSS)».