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

история алгоритм появился благодаря трем людям бла бла в 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)