Для того чтобы генерировать пару ключей (открытый ключ - секретный ключ), сначала выбирают некоторое большое простое число Р и большое целое число G, причем G < Р. Числа Р и G могут быть распространены среди группы пользователей.

Затем выбирают случайное целое число X, причем Х<Р. Число Х является секретным ключом и должно храниться в секрете.

Для того чтобы зашифровать сообщение М, выбирают случайное целое число К, 1<К<Р -1, такое, что числа К и (Р-1) являются взаимно простыми.

Затем вычисляют числа

a=G^KmodP,

Пара чисел (а,Ь) является шифртекстом. Заметим, что длина шифртекста вдвое больше длины исходного открытого текста М.

Для того чтобы расшифровать шифртекст (а,b), вычисляют

Поскольку

то соотношение (*) справедливо.

Пример. Выберем Р = 11, G = 2, секретный ключ X = 8. Вычисляем

Итак, открытый ключ Y = 3.

Пусть сообщение М = 5. Выберем некоторое случайное число К = 9. Убедимся, что НОД (К,Р-1)=1. Действительно, НОД (9,10)=1. Вычисляем пару чисел а и Ь:

Получим шифртекст (а, b) = (6, 9).

Выполним расшифрование этого шифртекста. Вычисляем сообщение М, используя секретный ключ X:

или

Решая данное сравнение, находим М = 5.

В реальных схемах шифрования необходимо использовать в качестве модуля Р большое целое простое число, имеющее в двоичном представлении длину 512... 1024 бит.

При программной реализации схемы Эль Гамаля скорость ее работы (на SPARC-II) в режимах шифрования и рас-шифрования при 160-битовом показателе степени для различных длин модуля Р определяется значениями, приведенными в табл.2.

Таблица 2 Скорости работы схемы Эль Гамаля