Главная » Информационные системы » Информационная безопасность и защита информации » Криптографическая система Эль Гамаля.

Криптографическая система Эль Гамаля.

Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе бывших стандартов электронной цифровой подписи в США (DSA) и России (ГОСТ Р 34.10-94).

Генерируется случайное простое число $~p$ длины $~n$ битов.
Выбирается случайный примитивный элемент $~g$ поля $\mathbb$ .
Выбирается случайное целое число $~x$ такое, что $~1$ .
Вычисляется $~y$ .
Открытым ключом является тройка $\left($ , закрытым ключом — число $~x$ .

Шифросистема Эль-Гамаля является фактически одним из способов выработки открытых ключей Диффи — Хеллмана. Шифрование по схеме Эль-Гамаля не следует путать с алгоритмом цифровой подписи по схеме Эль-Гамаля.

Сообщение $~M$ шифруется следующим образом:

Выбирается сессионный ключ — случайное целое число $~k$ такое, что $~1$
Вычисляются числа $a$ и $b$ .
Пара чисел $\left($ является шифротекстом.

Нетрудно видеть, что длина шифротекста в схеме Эль-Гамаля длиннее исходного сообщения $M$ вдвое.

Зная закрытый ключ $~x$ , исходное сообщение можно вычислить из шифротекста $\left($ по формуле:

$M$

При этом нетрудно проверить, что

$~(a^x)^{-1}\equiv$

и поэтому

$~b(a^x)^{-1}\equiv$ .

Для практических вычислений больше подходит следующая формула:

$M$

Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.

Поделиться

Дисциплины