Криптосистема открытого шифрования Эль-Гамаля

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 21:14, 22 мая 2016.

Процесс шифрования

  • большое простое число (для которого сложно решить задачу DLP (дискретного логарифмирования))
  • первообразный корень, порождающий
  • открытый текст, число из интервала
  • - долговременный секретный ключ пользователя (выбор случайный)
  • - открытый ключ пользователя , помещается в справочнике: (или любой другой ключ для другого абонента).

УЦ (удостоверяющий центр) хранит эти ключи в виде сертификата на стандарте X.509

Последовательность действий:

  1. разовый, сеансовый ключ, выбираем его.
  2. Вычисляется ключ для шифрования
  3. - шифрованый текст.

Прим. Шифрованый текст в 2 раза больше открытого текста.

Трудоемкость получения шифротекста сравнима с 2 возведениями в степень и это действие по схеме Горнера имеет трудоемкость

Процесс расшифрования

На В происходит расшифрование:

- необходим ключ.

Восстанавливаем

Еще

Замечание 1 Это пример вероятностного шифрования - probabilistic encryption - т.е. из одного и того же ОТ при шифровании может получиться совершенно произвольный ШТ.

Замечание 2 Ключ k называется разовым; можно было бы использовать его повторно, но что будет, если использовать его 2 раза?

ШТ1 (шифротекст):

ШТ2:

Если противник перехватывает оба ШЦ, то получается соотношение, из которого можно достать кое-какие вычисления:

+ по статистике можно определить, что используется повторно один и тот же ключ. Ситуация, как и в шифре Вернама.

Это все очень похоже на Диффи-Хеллмана.

Эту схему модифицировали и результатом стала Схема открытого шифрования Дамгарда

См. также

Схема открытого шифрования Дамгарда