Атаки на эллиптические кривые

• Название: Атаки на эллиптические кривые
• Дата: 06.03.2022
• Размер: 191.67 Kb.
• Имя файла: Referat (1).docx
• Тип: Реферат; #384804
• страница: 11 из 19

Алгоритм шифрования Деффи-Хеллмана

При работе алгоритма каждая сторона:

1. 
   Пользователь 1 генерирует случайное число a, которое является закрытым ключом
   
2. 
   Совместно с удалённой стороной устанавливает открытые параметры p и g такие, что:
   
   1. 
      p является случайным простым числом.
      
   2. 
      (p-1)/2 также должно быть случайным простым
      
   3. 
      g является обратным числом по модулю p
      
3. 
   Вычисляет открытый ключ A по формуле (3.3)
   

𝐴 = 𝑔 ∗ 𝑎 𝑚𝑜𝑑 𝑝 (3.3)

4. 
   Пользователи обмениваются ключами
   
5. 
   Вычисляет общий секретный ключ K по формуле (3.4)
   

𝐾 = 𝐵 ∗ 𝑎 𝑚𝑜𝑑 𝑝 (3.4)
Общий секретный ключ будет равным для обоих пользователей так как:
𝐵 ∗ 𝑎 𝑚𝑜𝑑 𝑝 = ⁽𝑔^𝑏 𝑚𝑜𝑑 𝑝⁾𝑎 𝑚𝑜𝑑 𝑝 = 𝑔^𝑎𝑏 𝑚𝑜𝑑 𝑝 = ⁽𝑔^𝑎 𝑚𝑜𝑑 𝑝⁾𝑏 𝑚𝑜𝑑 𝑝 =

𝐴 ∗ 𝑏 𝑚𝑜𝑑 𝑝 (3.5)
Формула (3.5) доказывает, что с помощью секретных ключей разных пользователей можно вычислить общий секретный ключ.

6. Шифрование с помощью алгоритма Диффи-Хеллмана

Главная проблема алгоритм заключается в том, чтобы зашифровать сообщение М, которое может быть представлено на ЭК в виде точки

𝑃𝑚 (𝑥, 𝑦).[15]
В шифровании и дешифровании сообщения, как и в случае передачи ключей по каналу связи, в качестве параметров выбирается эллиптическая кривая 𝐸𝑝 (𝑎, 𝑏) и точка пораждающая точка G которая принадлежит данной кривой. Пользователь 1 выбирает закрытый ключ 𝑛𝐵 и вычисляет открытый ключ путем перемножения закрытого ключа на точку G. Чтобы зашифровать сообщение 𝑃𝑚 используется открытый ключ пользователя 2 (P_B). Пользователь 1 выбирает случайное целое положительное число k и вычисляет зашифрованное сообщение 𝐶𝑚, являющееся точкой на эллиптической кривой.

𝐶𝑚 = (𝑘 × 𝐺, 𝑃𝑚 + 𝑘 × 𝑃𝐵) (3.6)
Для того, чтобы расшифровать сообщение (3.6), пользователь 2 умножает первую координату точки на свой закрытый ключ и получает результат из второй координаты по формуле (3.7):
𝑃𝑚 + 𝑘 × 𝑃𝐵 − 𝑛𝐵 × ⁽𝑘 × 𝐺⁾ = 𝑃𝑚 + 𝑘 × ⁽𝑛𝐵 × 𝐺⁾ − 𝑛𝐵 × ⁽𝑘 × 𝐺⁾ = 𝑃𝑚 (3.7)
Пользователь 1 зашифровал сообщение P_m добавлением к нему 𝑘 ∗ 𝑃𝐵. Никто не знает значения k, следовательно, хотя P_B и является открытым ключом, никто не знает k × P_B. Человеку, который пытается взломать алгоритм придется вычислить k, зная G и k × G. Эта операция довольно сложная.
Получатель также не знает k, но ему в качестве подсказки посылается k ×

G. [16] Умножив k × G на свой закрытый ключ, получатель вычислит значение, которое было добавлено отправителем к исходному сообщению. [17] Тем самым получатель, не зная k, но имея свой закрытый ключ, может восстановить незашифрованное сообщение. [18]