Криптосистема Эль-Гамаля

Данная система является альтернативой RSA и при равном значении ключа обеспечивает ту же криптостойкость. Однако общего мнения по поводу предпочтительности того или иного метода нет.

В отличие от RSA метод Эль-Гамаля основан на проблеме дискретного логарифма. Этим он похож на алго р итм Диффи-Хелмана. Если возводить число в степень в конечном поле достаточно легко, то восстановить аргумент по значению (то есть найти логарифм в множестве целых чисел) довольно трудно.

Основу системы составляют параметры p и g - числа, первое из ко­торых p — простое, а второе (g Î Z_p) — целое. Данные параметры не явля­ются секретными и могут быть общими для группы пользователей. В ре­альных схемах шифрования необходимо использовать в качестве модуля большое целое простое число, имеющее в двоичном представлении длину 512...1024 бит.

Cекретный ключ x Î Z_p-1 генерируетcя случайным образом, а открытый ключ y вычисляется по формуле

y = g^x mod p.

Для шифрования сообщения m сначала выбира­ется случайное число k, взаимно простое с p-1, которое называют также сеансовым ключом.

Шифртекстом является пара чисел (a,b), вычисляемая по формулам:

a = g^k mod p и

b = y^k m mod p.

Таким образом, шифртекст в два раза длиннее открытого текста.

Для дешифрования вычисляется

m =  mod p.

Преобразование обратимо, так как

а^x = g^kx mod p

и  mod p.

Число k называют также рандомизатором. Его использование означает, что здесь реализован мнозначный шифр замены. При этом для зашифрования различных блоков (чисел) открытого текста необходимо использовать различные значения рандомизатора. При использовании одного и того же значения соответсвующие шифртексты (a, b) и (a ´, b ´), полученные для блоков открытых текстов m и m ´, связаны соотношением

b (b ´) ^–1= m (m ´) ^–1

и текст m ´можно вычислить, если известен текст m.

Стойкость криптосистемы Эль Гамаля основана на сложности зада­чи логарифмирования в мультипликативной группе конечного простого поля. Эта криптосистема может быть обобщена для применения в любой конечной циклической группе. В качестве такой группы, помимо рассмот­ренной Z^*_p, чаще всего используется мультипликативная группа конечного поля GF (2 ^m) и группа точек на эллиптической кривой над конечным полем (см. приложение П.8).

Алгоритм не запатентован, но попадает под действие патента на метод экспо­ненциального ключевого обмена Диффи-Хеллмана, рассмот­ренный ниже. Преоб­разование шифрования/дешифрова­ния Эль Гамаля по сути то же самое, что ключевой обмен по Диффи-Хеллману, за исключени­ем того, что y – это часть ключа, а при шифровании сообщение умножается на y^k. Алгоритм цифровой подписи DSA, разработанный NIST (National Institute of Standard and Technology USA) и являющийся частью стандарта DSS частично опирается на рассмотренный метод.