Математические основы защиты информации. Ишмухаметов Ш.Т - 76 стр.

Методы, основанные на задаче дискретного логарифмирования                77

  2. Вычисляет открытый ключ по формуле y = g x mod p,

2. Шифрование сообщения M :

  1. Сначала генерируется случайное число k, 1 < k < p, взаимно-простое
     с p − 1, т.е. Н.О.Д(p − 1, k) = 1,

  2. Вычисляем a = g k mod p,

  3. Вычисляем b = y k · M mod p.

      Пара ⟨a, b⟩ является шифром сообщения M .

III. Расшифровка кода ⟨a, b⟩:

Вычисляем исходное сообщение M по формуле:

                            M = b · a−x mod p

      Отметим, что поскольку ap−1 mod p = 1, то чтобы не вычислять
обратные элементы в поле Fp , можно использовать прямое вычисление M
по формуле:
                           M = b · ap−1−x mod p.

      Пример. Выберем p = 11, g = 2, секретный ключ x = 8. Вычисляем
y = g x mod p = 3 . Начальные параметры шифрования подготовлены.
      Пусть cообщение M = 5. Выбираем случайное число k = 9. Убедимся,
что Н.О.Д.(k, p − 1)= Н.О.Д.(9, 10) = 1.
      Вычисляем пару (a, b):

 a = g k mod p = 29 mod 11 = 3,      b = y k · M mod p = 39 · 5 mod 11 = 9.

      Получена шифрограмма (a, b) = (6, 9) для сообщения M = 9.

      Расшифровки сообщения (a, b):

  M = b · ap−1−x mod p = M = 9 · 611−1−8 mod 11 = 9 · 36 mod 11 = 5