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

Схема Эль-Гамаля (Elgamal) — криптосистема, предложенная в 1984 году. Схема Эль-Гамаля лежит в основе стандартов электронной цифровой подписи в США и России.

Содержание

Генерируется случайное простое число $p$ длины $n$ .
Выбирается произвольное целое число g, являющееся первообразным корнем по модулю p.
Выбирается случайное число $x$ из интервала (1,p), взаимно простое с p-1.
Вычисляется $y = g x mod p$ .
Открытым ключом является тройка $(p, g, y)$ , закрытым ключом — число $x$ .

Сообщение М шифруется так:

Нетрудно видеть, что длина шифротекста в схеме Эль-Гамаль длиннее исходного сообщения $M$ вдвое.

Зная закрытый ключ $x$ , исходное сообщение можно вычислить из шифротекста $(a, b)$ по формуле:

$M = b(a^x)^{-1}\,\bmod\,p.$

При этом нетрудно проверить, что

$a^x\equiv g^{kx}\pmod{p}$ и $\frac{b}{a^x}\equiv \frac{y^kM}{a^x}\equiv \frac{g^{xk}M}{g^{xk}}\equiv M \pmod{p}$ .

При работе в режиме подписи предполагается наличие фиксированной хеш-функции $h ()$ , значения которой лежат в интервале $(1, p - 1).$

Для подписи сообщения M выполняются следующие операции:

Вычисляется дайджест сообщения M: $m = h (M).$
Выбирается случайное число $1 < k < p - 1$ взаимно простое с p-1 и вычисляется $r = g^k\,\bmod\,p.$
С помощью расширенного алгоритма Евклида вычисляется число s, удовлетворяющее сравнению:

$m \equiv xr + ks\pmod{p-1}.$
Подписью сообщения M является пара (r,s).

Зная открытый ключ $(p, g, y)$ , подпись (r,s) сообщения M проверяется следующим образом:

Проверяется выполнимость условий: $0 < r < p$ и $0 < s < p - 1$ . Если хотя бы одно из них не выполняется, то подпись считается неверной.
Вычисляется дайджест $m = h (M).$
Подпись считается верной, если выполняется сравнение:

$y^r r^s \equiv g^m \pmod{p}.$

Криптостойкость данной схемы основана на вычислительной сложности проблемы дискретного логарифмирования, где по известным p, g и y требуется вычислить х, удовлетворяющий сравнению:

$y \equiv g^x \pmod{p}.$

RSA • DSA • Схема Эль-Гамаля • ГОСТ Р 34.10-2001

Это незавершённая статья по криптографии. Вы можете помочь проекту, исправив и дополнив её.