Рассказывает Сеид Садат Назрул. Днём он ловит киберпреступников с помощью машинного обучения, а по ночам ведёт блоги 🙂
Обмен ключами с помощью протокола Диффи-Хеллмана (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
Сравнивая их:
Заметили что-нибудь интересное? Мы оба получили одинаковые полные ключи, равные 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. Если вы хотите закрепить полученные знания, будет полезно посмотреть это видео:
Перевод статьи «Diffie-Hellman Key Exchange explained (Python)»,
Варвара Николаева
