Крипто шоу: Особенности протокола Диффи-Хеллмана-Меркла(DH)

Перевод статьи Dave Cridland: "Crypto Show And Tell: The Wonders of Diffie-Hellman-Merkle"

Я практически ничего не знаю о криптографии, хотя пользуюсь ею постоянно, достаточно сведущ в свойствах RSA и прочих и даже проектировал механизмы аутентификации. Но как это работает?

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

Шаг первый

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

Он построен вокруг Коммутативных Групп, математического определения множества, в котором любые два значения могут быть скомбинированы при помощи некой операции, результат которой всегда принадлежит третьему множеству. В Диффи-Хеллмане можно использовать любую Коммутативную Группу, у которой операцию трудно определить по результату.

Далее будем использовать Python, так как описание математическими формулами получается слишком сложным. Язык поддерживает "большие" числа, и, хотя код будет почти готов к реализации DH в боевой системе, вряд ли стоит его использовать - проще будет взять намного меньшие числа, для наглядности.

Для классического DH определим константы-параметры. Нам нужны: G (обычно это небольшая величина, вроде 2 или 5) и P (простое число достаточной длины, вроде 2048 или 4096 бит). Эти значения нет нужды держать в секрете - они передаются по сети на первом шаге.

G = 2 # Это нормально
P = 13 # Это НАМНОГО больше

Для начала - неплохо, осталось ввести определение случайного числа:

def gen_key():
  '''Generate a random integral number from 1 to P-1 inclusive.'''
  global P
  import random
  return random.randrange(1, P)

Функцию назовём gen_key и будем генерировать ею приватный ключ. Теперь - сама операция.

def op(a):
  global P
  global G
  return (G ** a) % P

Отлично! Возводим G в степень a, затем берем остаток от деления результата на P. Теперь приватный ключ можно получить как Ka = gen_key(), а соответствующий ему публичный ключ - как Pa = op(Ka). Легко.

Итак, что с этим можно сделать? Немного, потому как функцию op() хорошо бы улучшить - иногда ведь хочется использовать параметр, отличный от G.

def op(a, b=None):
  global P
  global G
  e = b if b is not None else G
  return (e ** a) % P

Вот тут начинается магия. Допустим, Алисе надо найти согласие с Бобом. Алисе нужны ключи, приватный и публичный.

Ka = gen_key()
Pa = op(Ka)

У Боба тоже есть подобная пара:

Kb = gen_key()
Pb = op(Kb)

Алиса шлёт свой публичный ключ, взамен - получает такой же от Боба. Алиса вычисляет результат:

result = op(Ka, Pb)

Боб - вычисляет обратный:

result = op(Kb, Pa)

Теперь результат идентичен у обоих.

Математика тут довольно проста, никакого волшебства.

У Алисы получилось:

((G ** Kb) % P) ** Ka) % P

Что аналогично:

((G ** Kb) ** Ka) % P

Или просто:

(G ** (Ka * Kb)) % P

Потому как именно так и работает степенная функция. Ka*Kb равнозначно Kb*Ka, то есть, вычисления Боба - идентичны, это всего лишь операнд публичного ключа в обоих случаях.

Шаг второй: Поездка на летние каникулы.

Хорошо, теперь и Алиса и Боб могут найти ключ. (Я имею ввиду, если они действительно разговаривают друг с другом, а не через посредника, но это уже совсем другая проблема).

Но, что если Алиса уезжает на праздники и хочет перенаправить свои сообщения Кэрол? Конечно, она могла бы дать Кэрол свой приватный ключ. Но это не комильфо, так что она решает дать Кэрол только часть своего ключа, оставив другую часть на сервере.

Теперь всё становится немного запутаннее.

Значит, имеется публичный ключ Алисы, который видит Боб. Далее, у Алисы есть свой приватный ключ, у Кэрол тоже появился приватный ключ для почты Алисы, а на сервере - лежит ключ перекодировки для доступа Кэрол-как-Алисы.

Ka = gen_key()       # Приватный, есть только у Алисы
Pa = op(Ka)          # Публичный, - у всех
Kca = gen_key() % Ka # закреплённый за Ka, который Кэрол получает от Алисы
Rca = Ka - Kca # Да, просто разбиваем его и держим на сервере
Kb = gen_key() # Приватный, только у Боба
Pb = op(Ka)    # Публичный

Вот и весь набор. Теперь Боб хочет отправить Алисе сообщение и генерирует ключ, как и ранее:

result = op(Kb, Pa)

Алиса легко получает тот же результат. Но сервер перед отправкой Кэрол делает следующую операцию:

half_result = op(Rca, Pb)

А Кэрол делает остальное:

result = (op(Kca, Pb) * half_result) % P

И, как ни странно, результат одинаков в обоих случаях, хотя ни на сервере, ни у Кэрол нет приватного ключа Алисы. Зоркий глаз заметит, конечно, что совсем нетрудно договориться и получить их - это ничуть не совершенная схема для шифрующего прокси, вовсе нет.

Шаг третий: Десктор, ноутбук, планшет, смартфон, часы.

В наши дни количество девайсов неуклонно растёт. У меня действительно есть все из вышеперечисленных, и они используются для реальных задач.

Традиционный способ обмена ключами подразумевает, что Алиса и Боб обмениваются публичными ключами для всех своих девайсов (плохо), или - что по всем распределяется одна и та же пара ключей (ещё хуже), или - что на сервере хранятся приватные ключи (тоже не айс).

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

То есть, у Алисы есть единственная пара ключей для всех устройств, но приватный хранится только на самом доверенном устройстве - вплоть до смарт-карты или подобном. Публичный ключ размещается на сервере.

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

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

Шаг четвёртый: Итог

Ничто из этого не покрыто патентами, насколько мне известно, но утверждать это с абсолютной уверенностью я не могу. Если же хочется использовать этот алгоритм в реальной системе, надо помнить:

Следует использовать ГРОМАДНЫЕ простые числа. В пакете OpenSSL есть утилиты для поиска подходящих параметров для алгоритма.

Возможно, следует приглядеться к ECDH, вариант алгоритма DH на эллиптических кривых. Как на нём построить шифрующий прокси - неясно, скорей всего - так же просто.