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

история алгоритм появился благодаря трем людям бла бла в 1975 году и внезапно решил проблему распределения ключей. в основе алгоритма лежит чистая математика, а точнее теория чисел. благодаря теореме ферма бла бла

Как это работает:

1. Алиса и Боб договариваются об односторонней функции вида \(y^x\mod{p}\): генерируют большое простое число \(p\) и подбирают подходящий базовый элемент \(g\) - генератор.
2. Алиса и Боб выбирают случайные натуральные числа \(a\) и \(b\) из множества {1,…,p-2} - закрытые ключи.
3. Вычисляют значения односторонних функций: \(A=g^a\mod{p}\) и \(B=g^b\mod{p}\).
4. Обмениваются полученными значениями \(A\) и \(B\).
5. Вычисляют итоговый общий секретный ключ: \(K = A^b\mod{p} = B^a\mod{p}\).

В реальных приложениях обеспечение безопасности частично делегировано серверу - он отвечает за генерацию большого случайного \(p\) и подбор генератора \(g\).

graph LR
  client["<b>Сервер</b><br>a, g, p<br>A = gᵃ mod p<br>K = Bᵃ mod p"]
  server["<b>Клиент</b><br>b<br>B = gᵇ mod p<br>K = Aᵇ mod p"]

  client -- "g, p, A" --> server
  server -- "B" --> client

Базовый элемент (он же генератор)

рассказать простыми словами что такое базовый элемент

Функция НайтиГенератор(p):
    если p не простое:
        вернуть НИЧЕГО

    q_list ← ПростыеДелители(p - 1)  // без повторов

    для g от 2 до p - 2:
        если для всех q из q_list:
            g^((p - 1) / q) mod p ≠ 1
        тогда:
            вернуть g  // g — генератор

    вернуть НИЧЕГО  // генераторов почти всегда много, так что странно, если не нашёл

Уязвимости

Данный алгоритм подвержен атаке “человек посередине”. Когда атакующий (Ева) выступает в роли посредника при передаче сообщений между Алисой и Бобом. В таком случае он может выработать 2 независимых секретных ключа с Алисой и Бобом.

PKI используются цифровые подписи потому что челвоек по середине это не снежный человек и он существует.

Цифровая подпись

PKI (Public Key Infrastructure)