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

Рассказывает Сеид Садат Назрул. Днём он ловит киберпреступников с помощью машинного обучения, а по ночам ведёт блоги ?

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

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

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

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

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

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

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

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

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

Ниже приведён предварительный базовый класс одной стороны, использующей шифрование 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)
		

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

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

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

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

			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
		

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

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

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

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

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

Реализация этого в 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
		

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

Здесь 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!!!'
		

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

Удачи с Evil Corp!

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