Главная | Обратная связь

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

В данной системе исправлен недостаток RSA по однозначному шифрованию. В самой схеме заложено присутствие случайного элемента – эфемерного сеансового ключа k, передаваемого в сообщении неявным образом. Кроме того, система позволяет использовать общие для всех абонентов параметры, аналогичные протоколу Диффи-Хеллмана – простое число P и примитивный элемент G.

Каждый абонент системы генерирует секретный ключ

Открытый ключ Y вычисляют как:

Абонент, желающий зашифровать сообщение m выбирает сеансовый ключ

Обязательность соблюдения условий

и аналогична протоколу Диффи-Хеллмана.

Особенностью (и недостатком) шифрования является то, что сообщение при шифровании удваивается по длине и представляет собой пару:

- первая часть сообщения, не зависящая от открытого текста. C₁ служит для неявной передачи эфемерного ключа и, ввиду независимости от шифруемого сообщения, может быть выработано заранее в фоновом режиме.

- вторая часть сообщения, служащая собственно для передачи m.

Расшифрование сообщения m’ производится как:

Ниже приведено краткое доказательство работоспособности, в котором для удобства опущены операции приведения по модулю:

Недостатком системы также является необходимость помимо возведения в степень при расшифровании также применить обобщенный алгоритм Евклида, что отрицательно сказывается на скорости вычислений.

Задача 3.4. Для заданного простого числа P и открытого текста m, определить самостоятельно минимальный порождающий элемент G и остальные параметры шифрсистемы Эль-Гамаля и осуществить зашифрование и расшифрование. Проверить совпадение исходного m и полученного m’ значений открытого текста.

Пример решения

Дано: P = 131 m = 59	Решение:
Найти: Gmin, x, Y, k, C1, C2, m’ Проверить: m’ = m