Share This
Связаться со мной
Крути в низ
Categories
//Как работает обмен ключами в протоколе Диффи-Хеллмана

Как работает обмен ключами в протоколе Диффи-Хеллмана

20.09.2020Category : Python

Перевод статьи «Diffie-Hellman Key Exchange explained (Python)»,
Варвара Николаева

Обмен ключами с помощью протокола Диффи-Хеллмана (DH) — это метод безопасного обмена криптографическими ключами по общедоступному каналу. Это один из первых протоколов с открытым ключом, который изначально был концептуализирован Ральфом Мерклем и назван в честь Уитфилда Диффи и Мартина Хеллмана. DH является одним из первых практических примеров обмена открытыми ключами. Сегодня DH используется для многих приложений, таких как, например, Proton Mail, SSH, GPG и так далее. В статье мы рассмотрим принципы работы этого протокола и проблемы, которые он решает.

 

Проблема в сквозном шифровании

Давайте возьмём простейшую ситуацию. Представьте, Майкл и я решили обменяться информацией. А хакер по имени Мистер Робот пытается перехватить наше сообщение.

kak rabotaet obmen kljuchami v protokole diffi hellmana f47db4b - Как работает обмен ключами в протоколе Диффи-Хеллмана

Логичный способ помешать Мистеру Роботу прочитать наше сообщение — шифрование. Предполагается, что даже если способ шифрования известен, сообщение не может быть расшифровано без ключа. Поэтому, пока мы с Майклом используем один и тот же метод шифрования и одинаковый ключ, мы можем общаться конфиденциально! Однако есть одна проблема…

kak rabotaet obmen kljuchami v protokole diffi hellmana ab0b166 - Как работает обмен ключами в протоколе Диффи-Хеллмана

Чтобы расшифровать сообщение Майкла, мне нужно, чтобы он отправил мне ключ по сети. Проблема в том, что Мистер Робот следит за перепиской и обязательно увидит ключ. Получив ключ, он легко сможет расшифровать все наши сообщения! Эта проблема обмена ключами решается с помощью алгоритма Диффи-Хеллмана.

Эволюция криптографии: от математики до физикиtproger.ru

Как Диффи-Хеллман решает проблему?

Диффи-Хеллман работает по принципу неполного обмена ключом шифрования по сети. У каждой стороны есть открытый ключ (который может видеть каждый, включая Мистера Робота) и закрытый ключ (его может видеть только пользователь компьютера). У меня нет доступа к личному ключу Майкла. У Майкла — к моему.

kak rabotaet obmen kljuchami v protokole diffi hellmana 4ebdbfe - Как работает обмен ключами в протоколе Диффи-Хеллмана

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

Создание базового класса

Ниже приведён предварительный базовый класс одной стороны, использующей шифрование DH. Пока не беспокойтесь о деталях, так как мы подробно рассмотрим каждую функцию!

class DH_Endpoint():    def __init__(self, public_key1, public_key2, private_key):        self.public_key1 = public_key1        self.public_key2 = public_key2        self.private_key = private_key        self.full_key = None           def generate_partial_key(self):        partial_key = self.public_key1 ** self.private_key        partial_key = partial_key % self.public_key2        return partial_key       def generate_full_key(self, partial_key_r):        full_key = partial_key_r ** self.private_key        full_key = full_key % self.public_key2        self.full_key = full_key        return full_key       def encrypt_message(self, message):        encrypted_message = ""        key = self.full_key        for c in message:            encrypted_message += chr(ord(c) + key)        return encrypted_message       def decrypt_message(self, encrypted_message):        decrypted_message = ""        key = self.full_key        for c in encrypted_message:            decrypted_message += chr(ord(c) — key)        return decrypted_message 

Давайте определим секретное сообщение, которое Майкл планирует отправить мне, а также наши закрытые и открытые ключи, установленные на компьютерах. В реальной жизни обычно используются большие простые числа, здесь мы будем использовать небольшие значения для простого отображения математической части.

message = "This is a very secret message!!!" s_public = 197 s_private = 199 m_public = 151 m_private = 157 Sadat = DH_Endpoint(s_public, m_public, s_private) Michael = DH_Endpoint(s_public, m_public, m_private) 

Частичный обмен ключами

Давайте предположим, что мы ничего не видим внутри сервера Майкла (включая его личный ключ).

kak rabotaet obmen kljuchami v protokole diffi hellmana 3858775 - Как работает обмен ключами в протоколе Диффи-Хеллмана

Теперь мне нужно создать частичный ключ шифрования, используя 3 доступные единицы информации: мой закрытый и открытый ключи и открытый ключ Майкла. Алгоритмически мы согласились использовать мой открытый ключ в качестве базы и его открытый ключ в качестве модуля.

kak rabotaet obmen kljuchami v protokole diffi hellmana 4903170 - Как работает обмен ключами в протоколе Диффи-Хеллмана

Если мы посмотрим на нашу функцию для генерации частичного ключа, то она именно эти вычисления и делает:

def generate_partial_key(self):        partial_key = self.public_key1 ** self.private_key        partial_key = partial_key % self.public_key2        return partial_key

Теперь давайте сгенерируем этот частичный ключ и отправим его Майклу по сети.

s_partial = Sadat.generate_partial_key() print(s_partial) # 147

Таким же образом Майкл посылает мне свой частичный ключ по сети.

m_partial = Michael.generate_partial_key() print(m_partial) # 66

Сравнение обоих вычислений частичного ключа:

kak rabotaet obmen kljuchami v protokole diffi hellmana 3e82b6b - Как работает обмен ключами в протоколе Диффи-Хеллмана

Мистер Робот, естественно, увидел обмен частичными ключами. Он также знает оба открытых ключа. Теперь ему нужно взломать наши соответствующие закрытые ключи.

kak rabotaet obmen kljuchami v protokole diffi hellmana aed9015 - Как работает обмен ключами в протоколе Диффи-Хеллмана

Всё, что знает Мистер Робот, — это частичные ключи и соответствующие открытые ключи, а также формула, используемая для получения частичных ключей. Особенность вычисления по модулю в том, что функция заставляет значение циклически изменяться. Если у вас есть модуль 151, значение будет между 0 и 151-1.

kak rabotaet obmen kljuchami v protokole diffi hellmana 9c943d7 - Как работает обмен ключами в протоколе Диффи-Хеллмана

Существует бесконечное число возможных значений, которые по модулю 151 будут равны либо 66, либо 147. В результате информации для получения закрытых ключей пользователей недостаточно (если не считать грубый перебор безумно большого числа всевозможных вариантов). Кроме того, в примере используются небольшие числа для закрытых и открытых ключей, что делает подбор реальным. В реальной жизни это было бы почти невозможно!

Генерация полного ключа

kak rabotaet obmen kljuchami v protokole diffi hellmana 398a30c - Как работает обмен ключами в протоколе Диффи-Хеллмана

Теперь, когда мы успешно обменялись частичными ключами, давайте снова применим операторы степени и деления с остатком к частичному ключу другого человека, используя наши собственные закрытые ключи следующим образом:

kak rabotaet obmen kljuchami v protokole diffi hellmana f84f54e - Как работает обмен ключами в протоколе Диффи-Хеллмана

Реализация этого в Python:

def generate_full_key(self, partial_key_r):        full_key = partial_key_r ** self.private_key        full_key = full_key % self.public_key2        self.full_key = full_key        return full_key

Код с моей стороны:

s_full = Sadat.generate_full_key(m_partial) print(s_full) # 75

И то же самое для Майкла, использующего мой частичный ключ:

m_full=Michael.generate_full_key(s_partial) print(m_full) # 75 

Сравнивая их:

kak rabotaet obmen kljuchami v protokole diffi hellmana 80a634a - Как работает обмен ключами в протоколе Диффи-Хеллмана

Заметили что-нибудь интересное? Мы оба получили одинаковые полные ключи, равные 75! Причина заключается в следующем математическом соотношении:

kak rabotaet obmen kljuchami v protokole diffi hellmana 5d4a723 - Как работает обмен ключами в протоколе Диффи-Хеллмана

Здесь a и b — закрытые ключи, а g и p — открытые. Нам удалось обменяться друг с другом по сети достаточным количеством информации, чтобы сгенерировать общий ключ шифрования, не ставя под угрозу наши закрытые ключи.

Время шифрования!

Теперь, когда у нас есть общий ключ шифрования, пришло время начать обмен сообщениями! Как объяснялось в начале этого раздела, Майкл хочет отправить мне зашифрованное сообщение. Вот простой алгоритм, который я написал для шифрования сообщения Майкла:

def encrypt_message(self, message):        encrypted_message = ""        key = self.full_key        for c in message:            encrypted_message += chr(ord(c) + key)        return encrypted_message 

Ничего особенного. Каждый символ кодируется в целое число, значение ключа добавляется, а затем целое число преобразуется обратно в символ. Этот процесс повторяется для каждого символа в сообщении. Первоначальное сообщение, которым хотел поделиться Майкл: «This is a very secret message!!!». Давайте добавим его в алгоритм с нашим новым ключом шифрования.

Прим. пер.: это шифр простой замены, которым в реальной жизни пользоваться не стоит. Взламывается чуть сложнее классического, но всё равно достаточно быстро.

m_encrypted = Michael.encrypt_message(message) print(m_encrypted) # 'x9f³´¾k´¾k¬kÁ°½Äk¾°®½°¿k¸°¾¾¬²°lll'

Зашифрованное сообщение — «x9f³´¾k´¾k¬kÁ°½Äk¾°®½°¿k¸°¾¾¬²°lll», что при чтении выглядит как бессвязный набор символов. Мистер Робот понятия не имеет, чем Майкл делится со мной по сети.

Теперь пришло время расшифровать сообщение с моей стороны.

def decrypt_message(self, encrypted_message):        decrypted_message = ""        key = self.full_key        for c in encrypted_message:            decrypted_message += chr(ord(c) — key)        return decrypted_message

Эта функция делает обратное преобразование. На этапе шифрования было добавлено значение ключа, на этапе расшифровки будет вычтено то же самое значение.

message = Sadat.decrypt_message(m_encrypted) print(message) # 'This is a very secret message!!!'

Получил сообщение! Хорошая попытка, Мистер Робот. Нам удалось обмениваться зашифрованными сообщениями, не поставив под угрозу наши ключи шифрования.

kak rabotaet obmen kljuchami v protokole diffi hellmana 885c343 - Как работает обмен ключами в протоколе Диффи-Хеллмана

kak rabotaet obmen kljuchami v protokole diffi hellmana f05f6e0 - Как работает обмен ключами в протоколе Диффи-Хеллмана

Удачи с Evil Corp!

Аналитик-тестировщик

«МойОфис», Санкт-Петербург

tproger.ru Вакансии на tproger.ru

Мы рассмотрели механику работы алгоритма Диффи-Хеллмана на примерах с цифрами и кодом на Python. Если вы хотите закрепить полученные знания, будет полезно посмотреть это видео:

 

Хинт для программистов: если зарегистрируетесь на соревнования Huawei Honor Cup, бесплатно получите доступ к онлайн-школе для участников. Можно прокачаться по разным навыкам и выиграть призы в самом соревновании.

Перейти к регистрации

  • 24 views
  • 0 Comment

Leave a Reply

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.

Связаться со мной
Close