Эль гамаля схема

Схема Эль-Гамаля. Схема была предложена Тахером Эль-Гамалем в 1985 году. Алгоритм Эль-Гамаля базируется на трудности вычисления дискретного логарифма. Первый этап алгоритма Эль-Гамаля заключается в генерации ключей. Этот этап включает следующую последовательность действий: Генерируется случайное простое число p длины n бит. Выбирается произвольное целое число a , являющееся первообразным (примитивным) корнем по модулю p . Выбирается случайное число x из интервала (1,p) , взаимно простое с p-1 . Вычисляется y = a x (mod p) . Открытым ключом является тройка (a, p ,y) , закрытым ключом — число x . Второй этап алгоритма включает шифрование . Сообщение М шифруется следующим образом: Выбирается случайное секретное число k , взаимно простое с p − 1 . Вычисляется γ = a k (mod p) , δ = M * y k (mod p) , где M — исходное сообщение. Пара чисел (γ,δ) является шифртекстом . Нетрудно заметить, что длина шифртекста в схеме Эль-Гамаля длиннее исходного сообщения M вдвое. Заключительный этап схемы Эль-Гамаля – это расшифрование . Зная закрытый ключ x и учитывая тот факт, что M = (δ * γ p-1-x )(mod p) , исходное сообщение M можно вычислить из шифртекста (γ,δ) по формуле: M = γ -x * δ (mod p) На рисунке 3 приведена схема работы алгоритма шифрования Эль-Гамаля. Ввиду того, что число k является произвольным, то такую схему еще называют схемой вероятностного шифрования. Вероятностный характер шифрования является преимуществом для схемы Эль-Гамаля, т.к. у схем вероятностного шифрования наблюдается большая стойкость по сравнению со схемами с определенным процессом шифрования. Недостатком схемы шифрования Эль-Гамаля является удвоение длины зашифрованного текста по сравнению с начальным текстом. Для схемы вероятностного шифрования само сообщение M и ключ не определяют шифртекст однозначно. В схеме Эль-Гамаля необходимо использовать различные значения случайной величины k для шифровки различных сообщений M и M' . Если использовать одинаковые k , то для соответствующих шифртекстов (γ,δ) и (γ',δ') выполняется соотношение δ * (δ') -1 = M * (M') -1 (mod p) . Из этого выражения можно легко вычислить M , если известно M' .