Схема подписи Эль-Гамаля: формулы и проверка подписи

Схема подписи Эль-Гамаля (ElGamal) - одна из первых асимметричных схем цифровой подписи, предложенная Тахером Эль-Гамалем в 1985 году. Её стойкость опирается на сложность задачи дискретного логарифма в конечном поле: зная открытый ключ, подделать подпись без секретного показателя практически невозможно. Именно эта конструкция легла в основу стандарта DSA и идейно близка к подписи на эллиптических кривых. Разберём, как устроены генерация ключей, формирование и проверка подписи, какую роль играет случайное число и где студенты чаще всего ошибаются в расчётах.

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

Что лежит в основе схемы

Схема Эль-Гамаля работает в мультипликативной группе вычетов по модулю простого числа $p$. Все вычисления идут по модулю $p$ (для самой подписи) и по модулю $p-1$ (для показателей). Безопасность держится на том, что операция возведения в степень по модулю легко вычисляется в одну сторону, но обратная задача - найти показатель по результату - вычислительно неподъёмна для больших $p$.

Эта обратная задача и называется задачей дискретного логарифма: по известным $g$, $p$ и значению $y = g^x \bmod p$ найти $x$. Для простого числа из нескольких сотен десятичных цифр такая задача не решается за разумное время. На том же фундаменте стоит алгоритм Диффи-Хеллмана обмена ключами, поэтому схему Эль-Гамаля часто изучают сразу после него.

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

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

Подготовка ключевой пары состоит из нескольких шагов:

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

$$y = g^x \bmod p$$

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

Формирование подписи

Чтобы подписать сообщение $m$, подписывающий сначала вычисляет его хэш $H(m)$ - короткое числовое представление сообщения. Затем выполняются шаги:

1. Выбирается случайное сессионное число $k$, взаимно простое с $p-1$, то есть $\gcd(k, p-1) = 1$.
2. Вычисляется первая часть подписи:

$$r = g^k \bmod p$$

1. Вычисляется вторая часть подписи через обратный элемент $k^{-1}$ по модулю $p-1$:

$$s = (H(m) - x \cdot r) \cdot k^{-1} \bmod (p-1)$$

Подписью сообщения становится пара $(r, s)$. Если на каком-то шаге $s = 0$, число $k$ выбирают заново. Обратите внимание: показатели считаются по модулю $p-1$, а не $p$ - это следствие малой теоремы Ферма, по которой порядок группы равен $p-1$.

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

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

Получатель знает открытые параметры $(p, g, y)$, само сообщение $m$ и подпись $(r, s)$. Сначала он проверяет, что $0 < r < p$ и $0 < s < p-1$ - иначе подпись сразу отвергается. Затем вычисляет хэш $H(m)$ и сравнивает два значения:

$$g^{H(m)} \bmod p \quad \overset{?}{=} \quad y^{r} \cdot r^{s} \bmod p$$

Если равенство выполняется - подпись подлинна. Корректность проверки следует из подстановки: поскольку $H(m) = x \cdot r + k \cdot s \pmod{p-1}$, то

$$y^{r} \cdot r^{s} = g^{x r} \cdot g^{k s} = g^{x r + k s} = g^{H(m)} \pmod{p}$$

Равенство показателей по модулю $p-1$ гарантирует равенство самих степеней по модулю $p$ - на этом и строится вся проверка.

Роль случайного числа k

Сессионное число $k$ - самое уязвимое место схемы. Оно должно быть:

• случайным - выбираться заново для каждой подписи;
• секретным - никогда не раскрываться;
• уникальным - не повторяться на разных сообщениях.

Нарушение любого из этих условий ведёт к катастрофе. Если $k$ становится известно злоумышленнику, секретный ключ восстанавливается напрямую из формулы:

$$x = (H(m) - k \cdot s) \cdot r^{-1} \bmod (p-1)$$

Ещё опаснее повтор: если одно и то же $k$ использовано для двух разных сообщений, значение $r$ у обеих подписей совпадёт, и из системы двух уравнений противник вычислит сначала $k$, а затем и $x$. Именно из-за этой проблемы в современных реализациях $k$ генерируют детерминированно по RFC 6979, исключая ошибки генератора случайных чисел. Та же уязвимость есть и в подписи ECDSA, унаследовавшей конструкцию от Эль-Гамаля.

Разбор на учебном примере

Чтобы формулы стали наглядными, проследим короткий расчёт с маленькими числами. Пусть $p = 23$, генератор $g = 5$, секретный ключ $x = 6$. Тогда открытый ключ $y = 5^6 \bmod 23 = 8$. Публикуется тройка $(23, 5, 8)$.

Подписываем сообщение с хэшем $H(m) = 10$. Выбираем $k = 3$ - оно взаимно просто с $p-1 = 22$. Считаем первую часть: $r = 5^3 \bmod 23 = 10$. Находим обратное $k^{-1} = 3^{-1} \bmod 22 = 15$ (так как $3 \cdot 15 = 45 = 2 \cdot 22 + 1$). Тогда вторая часть:

$$s = (10 - 6 \cdot 10) \cdot 15 \bmod 22 = (-50) \cdot 15 \bmod 22 = 0$$

Получили $s = 0$ - такой случай запрещён, поэтому $k$ нужно перевыбрать. Возьмём $k = 5$: тогда $r = 5^5 \bmod 23 = 20$, $k^{-1} = 5^{-1} \bmod 22 = 9$, и $s = (10 - 6 \cdot 20) \cdot 9 \bmod 22 = (-110) \cdot 9 \bmod 22$. Этот пример показывает, почему проверка $s \ne 0$ и перевыбор $k$ - обязательные шаги алгоритма, а не формальность.

Чем схема отличается от RSA

И RSA, и Эль-Гамаль - асимметричные схемы, но их математическая основа и поведение различаются:

• Основа стойкости. RSA опирается на сложность факторизации больших чисел; Эль-Гамаль - на задачу дискретного логарифма.
• Детерминированность. Подпись RSA для одного сообщения всегда одна и та же. Подпись Эль-Гамаля вероятностная: из-за случайного $k$ одно сообщение даёт разные подписи при каждом подписании.
• Размер подписи. Подпись Эль-Гамаля состоит из двух чисел $(r, s)$, каждое порядка $p$, поэтому она примерно вдвое длиннее модуля. У RSA подпись - одно число.
• Связь с хэшем. Без хэш-функции схема Эль-Гамаля уязвима к экзистенциальной подделке, поэтому подписывают всегда $H(m)$, а не сам текст. Требования к хэшу разобраны в материале про хэш-функции.

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

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

• Считать показатели по модулю $p$ вместо $p-1$. Значение $s$ и обратный элемент $k^{-1}$ берутся по модулю $p-1$ - порядка группы, а не самого модуля.
• Брать $k$, не взаимно простое с $p-1$. Тогда обратного $k^{-1}$ не существует и подпись посчитать нельзя; $k$ нужно перевыбрать.
• Подписывать сам текст вместо хэша. Без $H(m)$ схема допускает подделку; в формулах участвует именно хэш сообщения.
• Повторно использовать одно $k$. Это раскрывает секретный ключ - самая известная практическая атака на схему.
• Путать $r$ и $s$ при проверке. В равенстве $y^{r} \cdot r^{s}$ показателем при $y$ стоит $r$, а $r$ возводится в степень $s$ - перестановка ломает проверку.

FAQ

Чем подпись Эль-Гамаля отличается от шифрования Эль-Гамаля? Это две разные схемы одного автора на общей математической основе. Шифрование скрывает сообщение и использует открытый ключ получателя; подпись подтверждает авторство и использует секретный ключ отправителя. Формулы и роли ключей у них разные.

Почему подпись каждый раз получается другой? Из-за случайного сессионного числа $k$: оно входит в обе части подписи $(r, s)$, и при новом $k$ обе части меняются. Это свойство вероятностных схем - в отличие от детерминированной RSA.

Как связаны схема Эль-Гамаля и DSA? DSA - это оптимизированный вариант схемы Эль-Гамаля. Подпись вычисляется в подгруппе простого порядка $q$, делящего $p-1$, что заметно сокращает длину подписи при той же стойкости относительно дискретного логарифма.

Коротко

Схема подписи Эль-Гамаля строит цифровую подпись как пару $(r, s)$ на основе случайного сессионного числа $k$, секретного ключа $x$ и хэша сообщения; проверка сводится к сравнению $g^{H(m)}$ с $y^{r} r^{s}$ по модулю $p$. Стойкость обеспечивает задача дискретного логарифма, а главная практическая опасность - повтор или утечка $k$, раскрывающие секретный ключ. Из этой конструкции выросли DSA и подписи на эллиптических кривых.