Алгоритм Диффи-Хелмана: безопасный обмен ключами в интернете
Я задумал написать статью о безопасных способах передачи данных в Интернете. В первую очередь я задался вопросом "Как работает протокол SSH?". Исследования затянулись, я выяснил много нового и все оказалось совсем не так как представляют большинство. Но прежде чем изучать как работает протокол SSH, необходимо разобраться как работает алгоритм Диффи-Хелмана. Дело в том, что этот алгоритм используется и в протоколе SSH, и при настройке шифрования HTTPS, а так же в других протоколах передачи данных. Тема довольно обширная так, что я решил вынести это в отдельную статью и ссылаться на нее по необходимости.
В статье я расскажу историю алгоритма, его основной принцип работы, рассмотрим реализации данного алгоритма и попробуем реализовать алгоритм на практике.
Алгоритм Диффи-Хелмана (Diffie–Hellman key exchange) - это криптографический протокол, который позволяет двум пользователям безопасно обмениваться секретными ключами через небезопасный канал связи.
Этот алгоритм (так же его называют протокол, метод) был разработан Уитфилдом Диффи и Мартином Хелманом в 1976 году. В то время они работали в лаборатории исследования компьютерных наук в Стэндфордском университете и занимались проблемой безопасного обмена ключами для шифрования данных.
Ранее для обмена ключами использовались алгоритмы, основанные на секретных ключах, которые должны были быть заранее распределены между пользователями. Но это было неудобно и небезопасно, так как ключи могли быть украдены или перехвачены злоумышленниками.
Диффи и Хелман предложили новый метод обмена ключами, который не требовал заранее распределенных секретных ключей. Они основали свой алгоритм на математической проблеме вычисления дискретного логарифма, которая считалась трудной для решения на тот момент.
Алгоритм Диффи-Хелмана (зачастую просто сокращают до аббревиатуры DH) стал первым протоколом, который позволял безопасно обмениваться ключами через небезопасный канал связи. Он стал основой для многих современных систем шифрования и используется во многих областях, включая интернет-банкинг, электронную почту и защиту данных в облаке.
Как же он работает? Давайте разбираться вместе.
Симметричное шифрование
Перед тем как разбирать сам алгоритм, давайте разберем термин Симметричное шифрование, он нам понадобится позднее.
Симметричное шифрование - это метод шифрования данных, при котором используется один и тот же ключ для шифрования и дешифрования информации. Это означает, что отправитель и получатель должны иметь доступ к одному и тому же ключу, чтобы зашифровать и расшифровать сообщение. Симметричное шифрование является быстрым и эффективным методом шифрования, но требует безопасного обмена ключами между отправителем и получателем.
Принцип работы алгоритма Диффи-Хелмана
Задача. Имеется Клиент и Сервер, которые хотят обмениваться сообщениями и не допустить утечки информации третьим лицам. Клиентом может быть как ваш браузер, так и клиент SSH, а возможно два сервера общаются между собой. Сейчас мы изучаем только алгоритм, а не конкретную его реализацию.
1) Этап первый
Клиент и Сервер договариваются о двух секретных числах:
p = 29, g = 3
Числа генерируются случайным образом, каждый раз новые, при каждом новом соединении. Данные числа иногда называют "публичными ключами".
Конечно же эти цифры являются публичными и могут передаваться в открытом виде. Поэтому злоумышленник так же может получить эти значения. На изображениях числа отмеченные зеленым могут передаваться по открытому каналу связи.
2) Этап второй
Клиент и Сервер генерируют свое собственное секретное число. Эти случайные числа уже нельзя передавать по открытым каналам связи. На изображениях я отмечу их красным цветом.
3) Этап третий
Клиент выполняет специальную операцию:
Число g, в нашем случае 3, возводит в число которое клиент выбрал случайным образом, в нашем случае это 5, и берется остаток от деления на число p, в нашем случае это 29. Получается число 11. Это число можно передавать по открытым каналам связи. Клиент передает это число на сервер.
4) Этап четвертый
Сервер выполнят такой же расчет, но только со своим секретным случайным числом. В нашем случае 3 в степени 8 и берем остаток от деления на 29, равно 7.
Сервер пересылает получившиеся число клиенту.
Да, эти получившиеся числа клиента и сервера может перехватить злоумышленник, но он не может узнать какие секретные числа были использованы для генерации этих публичных чисел.
5) Этап пятый - Генерация симметричного ключа
Теперь клиент и сервер снова производят похожие операции.
Клиент выполняет ту же функцию, что и выше, но только с числом полученным от сервера, в нашем случае это 7.
7 в степени 5 и остаток от деления на 29, равно 16.
Сервер производит то же самое, но с числом полученным от клиента, у нас это было число 11.
11 в степени 8 и остаток от деления на 29, равно 16.
Получившиеся число 16 и будет считаться секретным ключом для симметричного шифрования. Данный ключ (разделяемый ключ, симметричный ключ), никогда не передается по сети.
Как же получилось так, что клиент и сервер смогли вычислить одинаковое число? Все совсем не сложно. Дело в том, что и клиент и сервер выполняли одни и те же вычисления, но в разном порядке.
(3^5 mod 29)^8 mod 29 = (3^8 mod 29)^5 mod 29
Благодаря тому, что данные вычисления являются коммутативными, клиент и сервер получают одни и те же результаты вычисления.
Название "коммутативный" происходит от латинского слова "commutare", что означает "менять местами". В математике это означает, что порядок операндов не влияет на результат операции. Например, операция сложения является коммутативной, так как порядок слагаемых можно менять местами, и результат останется тем же.
Да, хакер перехватил начальные числа p и g, так же он смог перехватить сгенерированные публичные ключи 11 и 7, но этого будет недостаточно, чтобы рассчитать общий симметричный ключ. Да, злоумышленник, все еще может выдать себя за сервер, или представиться серверу клиентом, но это уже другая история. Существуют множество способов провести аутентификацию пользователя, но к алгоритму Диффи-Хелмана это не имеет отношения. Разбираемый алгоритм служит именно для генерации секретного, симметричного ключа.
Теперь, клиент и сервер могут шифровать и расшифровывать сообщения с помощью симметричного ключа. Считаем, что безопасный канал связи настроен.
Условия работы алгоритма
Пример выше, был заведомо упрощен для понимания. В реальности условия для реализации алгоритма Диффи-Хелмана отличаются. Сгенерированные случайные числа должны отвечать определенным требованиям:
p - большое простое число минимум 2024 бита.
g - небольшое целое число (первообразный корень по модулю p).
Если эти условия соблюдаются, полученный ключ невозможно вычислить даже на современных суперкомпьютерах.
Секретные ключ клиента и сервера так же выбираются не обычной случайностью, но как именно мне выяснить не удалось. Вообще эта тема довольно сложная, оставим ее математикам.
Так же алгоритм обеспечивает Совершенную прямую секретность (Perfect forward secrecy). Если злоумышленник записал данные, которыми мы обменивались в течении соединения, а затем получил доступ к серверу, он не сможет их расшифровать. Почему? Просто, ни клиент, ни сервер не хранят симметричный ключ, он используется только в периоде соединения. Этот ключ не может быть восстановлен из переданных данных, поэтому злоумышленник не может узнать его, даже если он перехватит все сообщения, передаваемые по каналу связи. Таким образом, мы можем быть уверены в том, что в будущем никто не сможет расшифровать наши сообщения.
Так же стоит заметить, что базовый алгоритм Диффи-Хелмана редко используется на практике. Существуют различные вариации этого алгоритма и наиболее популярным является алгоритм Диффи-Хелмана на эллиптических кривых. Принцип работы довольно схож, но разберем мы его в другой раз. Для понимания принципа работы алгоритма, данного материала достаточно.
Практика
Ниже пример вышеописанного алгоритма на языке JavaScript. Поменяйте числа, и вы убедитесь, что для правильной работы алгоритма подходят не любые случайные числа.
const p = 29
const g = 3
console.log('Публичное случайное число p: ', p);
console.log('Публичное число g: ', g);
const clientSecretNumber = 5
const serverSecretNumber = 8
console.log('Случайное секретное число клиента: ', clientSecretNumber);
console.log('Случайное секретное число сервера: ', serverSecretNumber);
function specialCalculation(g, n, p) {
return Math.pow(g, n) % p
}
console.log('Клиент производит вычисление...');
const publicClientKey = specialCalculation(g, clientSecretNumber, p);
console.log('Публичный ключ клиента: ', publicClientKey);
console.log('Сервер производит вычисление...');
const serverClientKey = specialCalculation(g, serverSecretNumber, p);
console.log('Публичный ключ сервера: ', serverClientKey);
console.log('Клиент и сервер обмениваются публичными ключами...');
console.log('Клиент и сервер производят вычисление симметричного ключа...');
const clientSymmetricKey = specialCalculation(serverClientKey, clientSecretNumber, p);
console.log('Вычисленный симметричный ключ клиента: ', clientSymmetricKey);
const serverSymmetricKey = specialCalculation(publicClientKey, serverSecretNumber, p);
console.log('Вычисленный симметричный ключ сервера: ', serverSymmetricKey);
Применение алгоритма Диффи-Хелмана.
Алгоритм Диффи-Хеллмана применяется во многих криптографических протоколах и стандартах, включая:
1. TLS/SSL: Протоколы передачи данных, обеспечивающие защищенное соединение между клиентом и сервером.
2. SSH: Протокол безопасной оболочки, используемый для безопасного удаленного доступа к серверам и обмена данными между ними.
3. IPSec: Протокол безопасности для защиты данных, передаваемых через сети, включая VPN-соединения.
Проблемы безопасности
В алгоритме Диффи-Хелмана существуют проблемы безопасности. Например, атака MITM (Man-in-the-Middle) может быть использована для перехвата и изменения передаваемых данных. Также возможна атака на основе подбора ключа, когда злоумышленник пытается угадать секретный ключ, используемый для шифрования данных. Для обеспечения безопасности протокола Диффи-Хелмана необходимо использовать надежные простые числа и другие меры защиты. Но все же данный алгоритм является одним из наиболее распространенных и широко используемых.
Заключение
Алгоритм Диффи-Хелмана является одним из самых важных алгоритмов криптографии. Он позволяет двум сторонам безопасно обмениваться секретными ключами через небезопасный канал связи. Алгоритм Диффи-Хелмана используется во многих протоколах безопасности, таких как SSL/TLS, SSH и VPN. Важно отметить, что алгоритм Диффи-Хелмана не обеспечивает аутентификацию сторон, поэтому он должен использоваться в сочетании с другими методами аутентификации, такими как цифровые сертификаты.
Да, соглашусь, что тема довольно сложная и если попробовать реализовать алгоритм самостоятельно, возникают новые вопросы и нюансы, но нам это и не нужно. Реализация уже есть. Главное уловить общий смысл. Понимание алгоритма понадобится, когда я буду писать о безопасном протоколе передачи данных SSH.
Если вам понравилась статья, не стесняйтесь поделиться ее в соц. сетях. Спасибо.
Материалы
Обьяснение алгоритма на примере смешивания цветов.
Андрей Созыкин - Шифрование в TLS/SSL | Защищенные сетевые протоколы