Схема Эль-Гамаля: шифрование на дискретном логарифме

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

Зачем нужна схема Эль-Гамаля

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

Схема Эль-Гамаля строится поверх протокола Диффи - Хеллмана и добавляет к нему полноценное шифрование сообщения. Её ключевое свойство - вероятностность: одно и то же сообщение при повторном шифровании даёт разный шифртекст, потому что на каждом шаге выбирается новое случайное число. Это сильно затрудняет атаки на основе анализа повторяющихся блоков.

Математическая основа: дискретный логарифм

Вся стойкость держится на одной задаче. Пусть дано простое число $p$, первообразный корень (генератор) $g$ по модулю $p$ и значение $y = g^x \bmod p$. Зная $p$, $g$ и $y$, найти показатель $x$ - это и есть задача дискретного логарифмирования.

Возвести $g$ в степень $x$ по модулю легко даже для огромных чисел (быстрое возведение в степень работает за $O(\log x)$ умножений). А вот обратное действие - восстановить $x$ - для больших $p$ вычислительно неподъёмно: лучшие известные алгоритмы работают субэкспоненциально. Именно эта асимметрия «легко в одну сторону, тяжело в обратную» делает схему рабочей.

Рассчитать для своей задачи

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

Получатель сообщения (назовём его Боб) готовит свою пару ключей один раз:

1. Выбирает большое простое число $p$.
2. Выбирает первообразный корень $g$ по модулю $p$ (генератор мультипликативной группы).
3. Случайно выбирает закрытый ключ $x$, где $1 < x < p - 1$.
4. Вычисляет открытую часть: $y = g^x \bmod p$.

Открытый ключ - это тройка $(p, g, y)$, её можно публиковать. Закрытый ключ - число $x$, его Боб никому не сообщает. Восстановить $x$ из $(p, g, y)$ означало бы решить задачу дискретного логарифма - на то и расчёт.

Шифрование сообщения

Отправитель (Алиса) хочет передать сообщение $m$, где $0 \le m < p$. Она берёт открытый ключ Боба $(p, g, y)$ и действует так:

1. Выбирает случайный сеансовый ключ $k$, где $1 < k < p - 1$, взаимно простой с $p - 1$.
2. Вычисляет первую компоненту: $a = g^k \bmod p$.
3. Вычисляет вторую компоненту: $b = y^k \cdot m \bmod p$.

Шифртекст - это пара $(a, b)$. Заметьте: длина шифртекста вдвое больше длины открытого текста, это плата за вероятностность. Число $k$ Алиса после отправки уничтожает и больше нигде не использует.

$$\begin{aligned} a &= g^{k} \bmod p, \\ b &= y^{k} \cdot m \bmod p. \end{aligned}$$

Расшифровка

Боб получает пару $(a, b)$ и применяет свой закрытый ключ $x$:

$$m = b \cdot \left(a^{x}\right)^{-1} \bmod p.$$

Здесь $(a^x)^{-1}$ - мультипликативный обратный элемент к $a^x$ по модулю $p$, его находят расширенным алгоритмом Евклида (или как $a^{x(p-1-1)}$ по малой теореме Ферма, то есть $a^{p-1-x}$).

Почему это работает? Подставим $a = g^k$ и $b = y^k m = (g^x)^k m$:

$$b \cdot (a^x)^{-1} = g^{xk} \cdot m \cdot (g^{kx})^{-1} = m \cdot g^{xk - kx} = m \bmod p.$$

Показатели взаимно сокращаются, и остаётся исходное сообщение. Ключевой момент: Боб никогда не узнаёт $k$, но ему это и не нужно - секрет $x$ позволяет восстановить общий маскирующий множитель $g^{xk}$.

Рассчитать для своей задачи

Пример с маленькими числами

Возьмём учебные параметры. Пусть $p = 23$, $g = 5$, закрытый ключ Боба $x = 6$. Тогда открытая часть:

$$y = g^{x} \bmod p = 5^{6} \bmod 23 = 8.$$

Открытый ключ Боба - $(23, 5, 8)$. Алиса шифрует сообщение $m = 10$, выбрав случайный $k = 3$:

$$\begin{aligned} a &= 5^{3} \bmod 23 = 10, \\ b &= 8^{3} \cdot 10 \bmod 23 = 512 \cdot 10 \bmod 23 = 19. \end{aligned}$$

Шифртекст - пара $(10, 19)$. Боб расшифровывает, вычислив $a^x = 10^6 \bmod 23 = 4$, затем обратный к нему по модулю 23 - это 6 (так как $4 \cdot 6 = 24 \equiv 1$). Итог: $m = 19 \cdot 6 \bmod 23 = 114 \bmod 23 = 10$. Исходное сообщение восстановлено.

Цифровая подпись Эль-Гамаля

Ту же математику можно повернуть наоборот - для подписи. Здесь секрет $x$ принадлежит подписывающему, а проверяет любой по открытому ключу. Чтобы подписать сообщение $m$, выбирают случайный $k$, взаимно простой с $p - 1$, и считают:

$$\begin{aligned} r &= g^{k} \bmod p, \\ s &= (m - x r) \cdot k^{-1} \bmod (p - 1). \end{aligned}$$

Подпись - пара $(r, s)$. Проверка считает $g^m \bmod p$ и сравнивает его с $y^{r} \cdot r^{s} \bmod p$: при верной подписи они равны. Именно из этой конструкции вырос алгоритм DSA, входящий в государственные стандарты. О базовом протоколе, поверх которого надстроена схема, - в разборе про обмен ключами Диффи - Хеллмана.

Стойкость и сравнение с RSA

Безопасность Эль-Гамаля эквивалентна сложности задачи Диффи - Хеллмана, которая не сложнее дискретного логарифма. На практике это значит:

• Длина ключа. Для сопоставимой с RSA стойкости нужен модуль $p$ примерно той же битности (2048+ бит для серьёзных применений).
• Расширение шифртекста. Шифртекст вдвое длиннее открытого текста - у RSA такого удвоения нет.
• Вероятностность из коробки. RSA в «учебном» виде детерминирован и требует отдельного дополнения (OAEP); Эль-Гамаль рандомизирован самой схемой.
• Скорость. Шифрование медленнее RSA из-за двух возведений в степень, зато подпись и проверка хорошо ложатся на эллиптические кривые (ECElGamal, EdDSA).

Частые ошибки

• Повторное использование $k$. Самая опасная ошибка: один и тот же сеансовый ключ для разных сообщений раскрывает закрытый ключ. $k$ должен быть свежим и случайным каждый раз.
• Сообщение $m \ge p$. Открытый текст обязан помещаться в группу, $0 \le m < p$. Длинные данные шифруют поблочно или гибридно (Эль-Гамалем шифруют только симметричный ключ).
• $g$ не первообразный корень. Если генератор имеет малый порядок, пространство шифртекстов схлопывается и схема становится уязвимой.
• Забыли про обратный по модулю $p - 1$ в подписи. В подписи деление идёт по модулю $p - 1$, а не $p$ - путаница модулей ломает проверку.
• Смешивание шифрования и подписи на одном ключе. Использовать одну пару и для конфиденциальности, и для подписи без разделения доменов небезопасно.

FAQ

Чем схема Эль-Гамаля отличается от протокола Диффи - Хеллмана? Диффи - Хеллман - это протокол выработки общего секрета, он сам по себе ничего не шифрует. Эль-Гамаль надстраивает над ним шаг маскирования сообщения множителем $y^k$, превращая обмен ключами в полноценное асимметричное шифрование.

Почему шифртекст в два раза длиннее сообщения? Потому что он состоит из пары чисел $(a, b)$: первое переносит «открытую часть» сеансового ключа $g^k$, второе - замаскированное сообщение. Это структурная плата за вероятностность и невозможность повтора.

Используется ли схема Эль-Гамаля на практике сегодня? В исходном виде над $\mathbb{Z}_p$ редко, но её идея живёт в DSA, в шифровании PGP/GnuPG и особенно в варианте на эллиптических кривых, где она компактна и быстра.

Коротко

Схема Эль-Гамаля - асимметричный алгоритм на основе сложности дискретного логарифма. Получатель публикует открытый ключ $(p, g, y)$ с $y = g^x \bmod p$ и хранит секрет $x$. Отправитель выбирает случайный $k$ и шлёт пару $(a, b) = (g^k, y^k m)$; получатель снимает маску через $m = b \cdot (a^x)^{-1} \bmod p$. Та же конструкция в обратную сторону даёт цифровую подпись (основу DSA). Главные подводные камни - повторное использование сеансового ключа $k$ и удвоение длины шифртекста.