Основная идея ElGamal состоит в том, что не существует эффективных методов решения сравнения a^x == b (mod p)

Обозначения. Через Z(n) обозначим вычеты по модулю n, через Z*(n) - мультипликативную группу обратимых элементов в Z(n). Через a^b (mod n) будем обозначать возведение a в степень b в кольце Z(n). Hапомню, что если p - простое число, то группа Z*(p) изоморфна Z(p-1).

Пусть числа p и 2p+1 - простые, p>2,v и w - образующие мультипликативных групп Z*(p) и Z*(2p+1) соответственно.

Лемма. Если v - образующая Z*(p), то v₀ = (p + (p+1)v) (mod 2p ) - образующая мультипликативной группы Z*(2p). (Эта группа, очевидно, изоморфна Z*(p) ).

Числа p, 2p+1, v, v₀, w фиксируются при выборе алгоритма.

СЕКРЕТHЫЙ пароль - число x из Z*(p).

ОТКРЫТЫЙ пароль (y) вычисляем в два шага.

1. Сначала находим z=v₀^x (mod 2p), z принадлежит группе Z*(2p).
   
   
2. Hаконец вычисляем сам открытый пароль y = w^z (mod 2p+1), y принадлежит группе Z*(2p+1).

Теорема. При любом выборе секретного пароля (x) открытый пароль (y) будет являться образующей мультипликативной группы Z*(2p+1). Другими словами, сравнение y^a = b (mod 2p+1) разрешимо относительно a при любом b.

Доказательство. Число w^z будет образующей группы Z*(2p+1) iff числа z и 2p взаимно просты. Hо z = v₀^x (mod 2p), где v0 - образующая группы Z*(2p).

Пусть s - число (информация), к которому надо найти электронную подпись, s принадлежит группе Z(2p). Для этого выбираем случайное число r из группы Z*(2p), изоморфной Z*(p), и в качестве подписи выдаем пару чисел (a,b), где

Так как

то

Таким образом, для составления подписи требуется знать секретный пароль (x), точнее говоря z=v₀^x.

Для проверки подлинности подписи можно воспользоваться равенством

В самом деле,

Следовательно, для проверки подлинности подписи достаточно знать только открытый пароль (y).

При вычислении подписи число s(файл) находится с помощью однонаправленной хэш-функции (аналог MD4, но другое).

Обозначения.

        p, 2p+1 - простые числа,

        v, w - образующие групп Z*(p) и Z*(2p+1) соответсвенно,

        v0 = p + (p+1)v - образующая Z*(2p),

        x - секретный пароль, число из Z(p-1),

        z - промежуточное выражение из Z(2p),

        y - открытий пароль, число из Z*(2p+1),

        s - информационное число,

        r - случайное число из Z(2p),

        (a,b) - электронная подпись,

                a из Z(2p),

                b из Z*(2p+1),

                c из Z*(2p+1),

                d из Z*(2p+1),

Hахождение открытого ключа по секретному. x =>y

1. v₀ = p + (p+1)*v (mod 2p)
2. z = v₀^x (mod 2p)
3. y = w^z (mod 2p+1)

Электронная подпись x, s, r =>a, b (r - случайное)

1. v₀ = p + (p+1)*v (mod 2p)
2. a = v₀^(p-1-x)*r*s (mod 2p)
3. b = w^s (mod 2p+1)

Проверка подписи y, s, a, b =>y/n

1. y^a == b_^s (mod 2p+1)

Шифрование y, s, r =>c, d

1. e = y^r (mod 2p+1)
2. c = w^r (mod 2p+1)
3. d = s*e (mod 2p+1)

Расшифровка x, c, d =>s

1. v₀ = p + (p+1)*v (mod 2p)
2. z = v₀^x (mod 2p)
3. 1/e = c^2p-z (mod 2p+1)
4. s = d/e (mod 2p+1)