» » »

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

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

Генерация ключей

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

Работа в режиме шифрования

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

Шифрование

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

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

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

Расшифрование

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

M

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

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

и поэтому

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

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

M

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

Поделиться

Оплаченная реклама

Дисциплины