Создатель ключа А выбирает

• произвольное достаточно большое простое число $ p_{} $;
• произвольный первообразный корень $ \Lambda_{} $ по основанию $ p_{} $;
• произвольное число $ a_{} $ и вычисляет $ Q=\Lambda^a \pmod{p} $.

Открытый (публичный) ключ шифрования состоит из трех чисел $ p,\Lambda, Q $. Секретный ключ дешифрования — число $ a_{} $, т.е. индекс (дискретный логарифм) $ \operatorname{ind}_{_{\Lambda}} Q $ числа $ Q_{} $ по модулю $ p_{} $ и основанию $ \Lambda $.

Корреспондент Б , желающий послать создателю ключа А открытый текст $ x_{} $, зашифрованный этим ключом, предпринимает следующие действия:

• выбирает случайное число $ k \in \{ 1,2,\dots, p-2 \} $;
• вычисляет $ \gamma=\Lambda^k \pmod{p} $;
• вычисляет $ c=xQ^k \pmod{p} $

и посылает А два числа $ c_{} $ и $ \gamma_{} $.

Получив эти числа, создатель ключа А для восстановления открытого текста $ x_{} $ должен прозвести следующие действия: выразить $ x_{} $ из $ c=xQ^k \pmod{p} $ по формуле $$x=cQ^{-k} \pmod{p}=$$ (но он не знает $ k_{} $, зато знает, что $ Q=\Lambda^a \pmod{p} $): $$=c\left(\Lambda^a \right)^{-k} \pmod{p} = c\left(\Lambda^k \right)^{-a} \pmod{p}= $$ (число $ \Lambda^k $ ему сообщено корреспондентом Б ) $$ =c \gamma^{-a} \pmod{p}\equiv c \gamma^{p-1-a} \pmod{p} \ . $$ (последнее сравнение следует из теоремы Ферма ). Поскольку все числа в этом выражении ему известны, то он получает искомый текст $ x_{} $.

1. В отличие от алгоритма RSA, шифрование по ЭльГамалю дает удлинение шифротекста почти в два раза по сравнению с текстом открытым: вместо $ x_{} $ посылается пара чисел $ (c,\gamma) $, каждое из которых — практически того же размера, что и $ x_{} $.

2. Для шифрования каждого нового текста надо подбирать новое $ k_{} $.

3. Участники переписки могут образовать закрытую для постороннего контроля группу «внутренней рассылки», договорившись использовать одинаковые для участников группы числа $ p_{} $ и $ \Lambda_{} $ (но разные секретные $ a_{} $). При этом числа $ p_{} $ и $ \Lambda_{} $ тоже секретятся, и тем самым усложняется задача криптоанализа переписки внутри группы.

Пример.

$$p=276359384326756927539349639753936254367560234574543725346534764354257629,\ \Lambda=2, $$ $$ Q=267913333839598359953082878808980288593658415295490235452780248871637093 \ .$$