Алгоритм Диффи-Хеллмана — это просто

Представь ситуацию: тебе нужно сообщить своему товарищу что-нибудь секретное, о чем никто больше знать не должен. Но, к сожалению, все доступные каналы связи прослушивают и о приватной беседе не может быть даже речи. На ум приходит шифрование — зашифруй сообщение и отправь. Задача тривиальна, казалось бы, но о пароле вы с товарищем заранее не договорились. А если отправить пароль вместе с зашифрованным посланием, то его вмиг расшифруют шпионы. Как же обеспечить приватность в таких условиях.

В 1976 году два американских криптографа Мартин Хеллман и Уитфилд Диффи нашли ответ на этот вопрос. Они придумали алгоритм обмена ключами через публичный канал связи, и первыми в мире ввели понятие публичного и приватного ключей.

Сейчас алгоритм Диффи-Хеллмана применяется чуть менее чем во всех системах, где нужно построить безопасный туннель от одного узла к другому, например, в протоколе SSL. Ну, и, разумеется, в мессенджерах, таких как Element, Telegram (секретные чаты), Signal и других.

Сам по себе алгоритм, как и всё гениальное, работает очень просто и содержит всего 2 формулы. Обменяться ключами настолько легко, что ты можешь прямо сейчас испытать в деле алгоритм и обменяться ключами со своими друзьями!

Алгоритм вычисления общего выглядит примерно так. Предположим, в обмене участвуют Алиса (А) и Боб (Б). У каждого из них есть по два ключа: приватный и публичный. Оба из них представляют собой случайно сгенерированные числа, но приватный знает только его владелец, а публичный знают все, это не секрет. Далее случается два этапа: сначала вычисляется частичный ключ, а затем полный, который благодаря магии алгебры будет совпадать у обеих сторон.

Теперь рассмотрим на примере. Если ты собираешься повторять с другом обмен ключами, то нужно четко определиться, кто будет Алисой, а кто Бобом. В реальности применяются огромнейшие числа, но для наглядности числа будем брать четырехзначные, а стало быть и ключ получится такой же длины. Итак, Алиса с Бобом сгенерировали свои ключи рандомно и поделились публичными ключами. 🔒 Приватные ключи каждый оставил при себе:

Теперь, каждый из них может вычислить частичный ключ (Kp, от слова partial), для этого публичный ключ Алисы возводим в степень своего приватного ключа и находим остаток от деления на публичный ключ Боба:

В основании степени у обоих участников будет публичный ключ Алисы, а публичный ключ Боба всегда будет после остатка от деления. mod — это нахождение остатка от деления. Есть не во всех калькуляторах, но вот в WolframAlpha, например, есть. Также можешь нажать F12 в браузере и использовать консоль как калькулятор, вместо mod тогда пиши %.

После нахождения частичных ключей, участники обмена сообщают их друг другу и вычисляют полный ключ (Kf, от слова full). Формула отличается от предыдущей только тем, что вместо ключа Алисы, в основании степени теперь стоит частичный ключ собеседника.

Вот и всё, обмен ключами совершен, ключи у обоих участников должны получиться одинаковыми. Теперь их можно использовать, чтобы, к примеру, поставить пароль на архив или просто зашифровать текст и безопасно передать информацию.

Данный способ обмена не подвержен replay-атакам, злоумышленник может невозбранно наблюдать со стороны процесс обмена ключами, а полный ключ всё равно не узнает. Всё это благодаря приватным ключам каждого из участников.

Однако, алгоритм уязвим к атаке человек посередине (MITM). Если хакер станет посредником и представится Бобу Алисой, а ей ‒ Бобом, то сможет расшифровать сообщение, прочитать его, зашифровать и отправить дальше. При том, такая дыра в безопасности будет незаметной долгое время.