Как работает обмен ключами в протоколе Диффи-Хеллмана
Перевод статьи «Diffie-Hellman Key Exchange explained (Python)»,
Варвара Николаева
Обмен ключами с помощью протокола Диффи-Хеллмана (DH) — это метод безопасного обмена криптографическими ключами по общедоступному каналу. Это один из первых протоколов с открытым ключом, который изначально был концептуализирован Ральфом Мерклем и назван в честь Уитфилда Диффи и Мартина Хеллмана. DH является одним из первых практических примеров обмена открытыми ключами. Сегодня DH используется для многих приложений, таких как, например, Proton Mail, SSH, GPG и так далее. В статье мы рассмотрим принципы работы этого протокола и проблемы, которые он решает.
Проблема в сквозном шифровании
Давайте возьмём простейшую ситуацию. Представьте, Майкл и я решили обменяться информацией. А хакер по имени Мистер Робот пытается перехватить наше сообщение.
Логичный способ помешать Мистеру Роботу прочитать наше сообщение — шифрование. Предполагается, что даже если способ шифрования известен, сообщение не может быть расшифровано без ключа. Поэтому, пока мы с Майклом используем один и тот же метод шифрования и одинаковый ключ, мы можем общаться конфиденциально! Однако есть одна проблема…
Чтобы расшифровать сообщение Майкла, мне нужно, чтобы он отправил мне ключ по сети. Проблема в том, что Мистер Робот следит за перепиской и обязательно увидит ключ. Получив ключ, он легко сможет расшифровать все наши сообщения! Эта проблема обмена ключами решается с помощью алгоритма Диффи-Хеллмана.
Эволюция криптографии: от математики до физикиtproger.ru
Как Диффи-Хеллман решает проблему?
Диффи-Хеллман работает по принципу неполного обмена ключом шифрования по сети. У каждой стороны есть открытый ключ (который может видеть каждый, включая Мистера Робота) и закрытый ключ (его может видеть только пользователь компьютера). У меня нет доступа к личному ключу Майкла. У Майкла — к моему.
Теперь давайте предположим, что мы оба используем общий алгоритм шифрования, и нам нужно каким-то образом восстановить общий ключ шифрования, не передавая слишком много информации через сеть.
Создание базового класса
Ниже приведён предварительный базовый класс одной стороны, использующей шифрование 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!
Аналитик-тестировщик
«МойОфис», Санкт-Петербург
tproger.ru Вакансии на tproger.ru
Мы рассмотрели механику работы алгоритма Диффи-Хеллмана на примерах с цифрами и кодом на Python. Если вы хотите закрепить полученные знания, будет полезно посмотреть это видео:
Хинт для программистов: если зарегистрируетесь на соревнования Huawei Honor Cup, бесплатно получите доступ к онлайн-школе для участников. Можно прокачаться по разным навыкам и выиграть призы в самом соревновании.
Перейти к регистрации
- 24 views
- 0 Comment