Диффи хеллмана алгоритм

Основы шифрования (часть 1) — Алгоритм Диффи-Хеллмана

Malarkey

Некоторое время назад я проводил исследование, чтобы лучше понять, как устроены криптографические алгоритмы. Сфера применения подобных алгоритмов весьма обширна. Мы защищаем информацию, хранящуюся на дисках или передаваемую через интернет. Мы проводим верификацию отсылаемых сообщений. В некоторых платежных системах шифрование является неотъемлемой частью. Тема криптографии настолько глубока и сложна, что неподготовленному человеку легко запутаться и наделать непоправимых ошибок, и поэтому весь приведенный ниже код не следует использовать в реальных задачах. Основная цель – ознакомиться с базовыми концепциями. Если вы хотите узнать историю вопроса, рекомендую почитать книгу The Code Book. Более детально различные аспекты криптографии описаны в книге Cryptography Engineering. Изучив вышеуказанную литературу, вы сможете лучше понимать, о чем я буду говорить в этой статье.

Суть проблемы

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

Алгоритм Диффи-Хеллмана

Рассмотрим схему обмена секретными ключами при помощи алгоритма Диффи-Хеллмана (Diffie-Hellman Key Exchange, DHKE). Более подробно с этой темой можно ознакомиться в русскоязычной и англоязычной Википедии. Ниже показана наглядная схема обмена между двумя пользователями. Алиса и Боб хотят использовать общий ключ для шифрования переписки. Рассмотрим детально этот процесс, используя краски вместо чисел:

  1. Алиса и Боб выбрали общую краску.
  2. Алиса и Боб выбрали по одной секретной краске.
  3. Алиса и Боб смешали общую и секретную краску.
  4. Алиса и Боб обменялись получившимися смешанными красками.
  5. Алиса смешала полученную смешанную краску от Боба со своей секретной краской.
  6. Боб смешал полученную смешанную краску от Алисы со своей секретной краской.
  7. Теперь у Алисы и Боба есть общая секретная краска.

(Алиса и Боб будут периодически встречаться в наших рассуждениях, так что привыкайте).

Рисунок 1: Наглядная схема получения общего секретного ключа (из Википедии)

Рабочий пример

Схема обмена секретным ключом реализована мной в коде. Ниже показан результат работы утилиты (для большей наглядности используются дополнительные флаги).

Рисунок 2: Результаты работы скрипта, реализующего алгоритм Диффи-Хеллмана

Небольшие пояснения к Рисунку 2:

  • «x -> y» означает, что «x» отсылает сообщение «y»
  • «Internal» означает, что действие происходит локально на машине одного из оппонентов

Вначале Алиса выбирает простое базовое число (5) и передает через Еву информацию Бобу. Затем Алиса выбирает еще одно простое число (23), которое будет использоваться при вычислениях, и опять передает через Еву информацию Бобу. Далее Алиса и Боб выбирают секретные числа и производят математические вычисления с использованием чисел 5 и 23. Затем Алиса и Боб через Еву обмениваются полученными сведениями. Далее каждый из оппонентов вычисляет секретный ключ.

Математическая сторона вопроса

«Как же работает этот алгоритм?», — спросите вы. Здесь нам на помощь приходит модулярная арифметика. Рассмотрим выражение g^x mod p. Числа g и p являются эквивалентом общей краски (см. схему выше). Существуют некоторые ограничения относительного того, какие числа можно использовать в качестве g и x (рассмотрим ниже). Число p – простое. Алиса и Боб будут выбирать секретные числа или секретные краски (a и b соответственно). Эти числа могут быть любыми. Затем каждый вычисляет выражение g^x mod p и рассказывает своему оппоненту конечный результат (смешанная краска). Теперь у Алисы есть значение B = g^b mod p, полученное от Боба, а у Боба есть значение A = g^a mod p, полученное от Алисы. Затем оппоненты вычисляют секретный ключ. Алиса вычисляет выражение B^a mod p, а Боб — A^b mod p.

Подождите, B^a mod p и A^b mod p – это и есть секретные ключи? Тогда мы должны быть уверены, что оба выражения дают одинаковый результат. Рассмотрим еще раз весь алгоритм по шагам.

  1. Алиса и Боб выбирают два числа g и p.
  2. Алиса и Боб выбирают секретные числа (a и b соответственно)
  3. Алиса и Боб вычисляют g ^ x mod p, где x – секретное число.
  4. Алиса и Боб обмениваются полученными данными (числа A и B соответственно).
  5. Алиса и Боб используют полученное число и секретное число для вычисления общего ключа.

В шаге 5 имеем следующее:

У Алисы: B^a mod p = (g^b mod p) ^ a mod p = g^ab mod p.

У Боба: A^b mod p = (g^a mod p) ^ b mod p = g^ab mod p.

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

Когда вы вычисляете выражение y mod z, на самом деле вычисляется остаток от деления y / z (или y % z, как принято в большинстве языков программирования). Если y < z, тогда y % z = y. Когда y > z выражение работает наподобие часов. По мере увеличения числа y выражение y % z будет равняться значениям в диапазоне от 0 до z – 1. Как только y станет кратно z, отсчет начинается сначала. Выясняется, что операция возведения в степень в модулярной арифметике имеет свойство транзитивности. То есть (a ^ b) ^ c mod d = (a ^ c) ^ b mod d = a^ (b ^ c) mod d. Алиса вычисляет выражение (g^b mod p) ^ a mod p, которое эквивалентно (g^b)^a mod p. В конечном счете, мы получаем выражение g^ab mod p.

Как было сказано ранее, на числа g и p накладываются определенные ограничения. Для выражения a ^ b mod c итоговый результат зависит от выбранных чисел. Рассмотрим выражение: a ^ b mod 7.

2 ^ 1 mod 7 = 2 mod 7 = 2

2 ^ 2 mod 7 = 4 mod 7 = 4

2 ^ 3 mod 7 = 8 mod 7 = 1

2 ^ 4 mod 7 = 16 mod 7 = 2

2 ^ 5 mod 7 = 32 mod 7 = 4

2^ 6 mod 7 = 64 mod 7 = 1

Понимаете, в чем дело? В результате мы имеет только 3 различных числа, и количество секретных ключей лишь половина всех чисел, которые меньше 7 (а ограниченное количество ключей напрямую влияет на уровень безопасности).

Вместо 2 возьмем 3:

3 ^ 1 mod 7 = 3 mod 7 = 3

3 ^ 2 mod 7 = 9 mod 7 = 2

3 ^ 3 mod 7 = 27 mod 7 = 6

3 ^ 4 mod 7 = 81 mod 7 = 4

3 ^ 5 mod 7 = 243 mod 7 = 5

3^ 6 mod 7 = 729 mod 7 = 1

….

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

Преимущества алгоритма

Алисе и Бобу удалось сгенерировать одинаковый ключ, но насколько решена наша проблема? Рассмотрим ситуацию с позиции Евы (курьера, который передает информацию).

Рисунок 3: Информация, которую видит курьер

Если скрипт запущен без флагов, на выходе показывается информацию, которую видит Ева. В примере выше Ева видит числа g и p, а также A и B. Чтобы вычислить секретный ключ, Еве нужно определить значения числа a (или b), используя выражение A = g^a mod p. Найти решение этого уравнения, которое часто называют секретно вычисляемой функцией (trap door function), довольно сложно. Подобные выражения легко вычисляются в одну сторону, но тяжело в другую (через некоторые двери вы не можете вернуться обратно). Если хотите копнуть глубже, ознакомьтесь со статьей, где описана проблема дискретного логарифмирования.

В итоге Алиса и Боб обменялись секретным ключом и могут пересылать друг другу зашифрованные сообщения. Чтобы еще больше усилить безопасность, мы можем генерировать новые ключи для каждого сеанса связи, и даже если ключ будет вычислен, пострадает только одна сессия.

Во второй части мы рассмотрим алгоритм RSA.

Ссылки

Протокол MQV — старый добрый Диффи-Хеллман, но не совсем

Вот уже более 30 лет протокол распределения ключей Диффи-Хеллмана радует глаз простого криптомана своей простотой и надежностью. Для тех, кто эти последние 30 лет провел за занятиями более веселыми, нежели изучение криптографических протоколов, поясняю.
Протокол Диффи-Хеллмана был опубликован в 1976 году и послужил началом эры асимметричной криптографии. Суть его до гениального проста: Алиса и Боб хотят получить общий ключ для симметричной криптосистемы. Для этого они, договорившись, выбирают два больших числа g и p. Эти числа известны им обоим и держать их в секрете не имеет никакого смысла. Затем Алиса в тайне генерирует большое секретное число a, а Боб — большое число b. А далее за дело берется простая арифметика. Алиса посылает Бобу число
.
Боб в свою очередь высылает Алисе
.
Теперь, чтобы получить общий ключ Алиса вычисляет , а Боб находит .
Нетрудно проверить, что , т.к.
.
Гениальность идеи заключается в том, что для получения ключа K Алисе и Бобу не понадобится много времени, в то время, как злоумышленнику, чтобы найти K нужно уметь решать задачу дискретного логарифмирования.
Боясь утомить читателя общеизвестными фактами, перехожу сразу к сути дела. А что если абстрагироваться от теории и перейти к практике? То получим следующее.
Протокол Диффи-Хеллмана отлично противостоит пассивному нападению, но в случае реализации атаки «человек посередине» он не устоит. В самом деле, в протоколе ни Алиса, ни Боб не могут достоверно определить, кем является их собеседник, поэтому вполне возможно представить следующую ситуацию, при которой Боб и Алиса установили связь с Меллори, который Алисе выдает себя за Боба, а Бобу представляется Алисой. И тогда вместо протокола Диффи-Хеллмана получаем, что-то похожее на следующее:

Шаг Алиса Меллори Боб
1
2

3
4

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

ЭЦП в качестве защиты

Как бороться с такой уязвимостью? Самый логичный и простой ответ: нужна взаимная аутентификация. И тут на помощь приходит ЭЦП.
Если у Боба имеется открытый ключ Алисы, и он уверен на сто процентов, что это действительно ключ Алисы, то тогда для защиты от атаки «человек посередине» Алисе достаточно подписать своим закрытым ключом число на шаге 1. Теперь Меллори может сколько угодно пытаться выдать себя за Алису, но подделать ее подпись он не сможет, а Боба сразу начнут терзать «смутные сомненья».
Казалось бы решение найдено, протокол доработан, уязвимость устранена. Но… Как всегда есть одно но. И в данном случае в роли такового выступает чрезмерное увеличение размера сообщений за счет добавления подписи. Наглядно этот эффект демонстрирует следующая таблица:

Алгоритмы Размер сообщения Размер подписи Общий размер
Диффи-Хеллман + DSA-подпись 1024 бит 320 бит 1344 бит
Диффи-Хеллман + RSA-подпись 1024 1024 2048
Диффи-Хеллман(на эллиптических кривых) + RSA-подпись 160 1024 1184
Диффи-Хеллман(на эллиптических кривых) + DSA-подпись(на эллиптических кривых) 160 320 480

Как видно из этой таблицы размер сообщений увеличивается в разы. Казалось бы, да и бог же с ними с этими лишними 320 битами, кому от них вред то будет? Но в криптографии не терпят полумер. Вот потому и был придуман протокол MQV, избавляющий Диффи-Хеллман от уязвимости и при этом не использующий ЭЦП.

Протокол MQV

Итак, протокол MQV – протокол распределения ключей, поддерживающий взаимную аутентификацию сторон и тем самым устраняющий уязвимость к атаке «человек посередине», присущей классическому Диффи-Хеллману. Помимо прочего, для аутентификации пользователей не используется никакая вспомогательная информация, наподобие ЭЦП, что позволяет существенно сократить размер передаваемых сообщений.

Протокол Размер сообщения
MQV 1024 бит
MQV(на эллиптических кривых) 160 бит

Теперь о самом протоколе.
Алиса и Боб имеют каждый свою ключевую пару, состоящие из открытых и закрытых ключей:и. Разумеется, Бобу известен открытый ключ Алисы, а той в свою очередь известен открытый ключ Боба.
Далее, Алиса и Боб генерируют сеансовую пару ключей:и.
Затем происходит обмен как в классическом протоколе Диффи-Хеллмана:
Алиса к Бобу:
Боб к Алисе:
Теперь Алиса знает: A, B, C, D, a,.
А Бобу известны: A, B, C, D, b,.
Чтобы получить общий ключ K они должны проделать следующие операции.
Алиса:
Выбирает число l, равное размеру сообщения в битах деленному на 2. Так если используется EC-MQV и длина сообщения равна 160 бит, то l=80.

1. Задает
2. Находит
3. Задает
4. Вычисляет
5. Находит
6. Вычисляет
Боб проделывает те же действия, но со своими закрытыми ключами:
1. Задает
2. Находит
3. Задает
4. Вычисляет
5. Находит
6. Вычисляет
Получившиеся в результате вычислений числаи есть общий секретный ключ. Убедимся в этом:
, т.к.и;
, т.к.;
, т.к.и;
, т.к.;
.
Обратите внимание, что в преобразованиях используются секретные ключи как Алисы, так и Боба. Т.е. любой пользователь протокола может быть уверен, что кроме того человека, с которым он хочет установить соединение, получить общий ключ не удастся никому.
Несмотря на кажущуюся сложность, в скорости протокол MQV ничего не теряет по сравнению со схемой использующей ЭЦП, ведь и там и там используется одна и та же операция возведения в степень по модулю простого числа. Выгода же от использования протокола заключается в следующем. Это, во-первых, устойчивость к атаке «человек посередине», во-вторых, небольшой размер сообщений, а, в-третьих, удобная реализация протокола, избавляющая пользователя от необходимости подписывать каждое отправляемое сообщение.

Синопсис

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

Немного теории

Метод Диффи-Хеллмана позволяет всем участникам общения получить общий секретный ключ (участников может быть два и более) в незащищенной от прослушивания среде. После того как все участники получили свои ключи, каждый из них, используя этот ключ, шифрует свое сообщения используя симметричный алгоритм шифрования для дальнейшего обмена в незащищенном от прослушивания канале. Алгоритм называется симметричным потому что каждый из участников общения использует для шифрования своего сообщения один и тот же ключ. Алгоритм Диффи-Хеллмана позволяет с генерировать этот секретный ключ каждому из участника общения на своей стороне не обмениваясь им через не защищенный канал, однако обмениваться некоторыми исходными параметрами на базе которых секретный ключ будет генерироваться все же придется, поэтому эти исходные параметры не скрываются и передаются в открытом виде, и могут быть доступны шпиону. Так вот, метод Диффи-Хеллмана используется для того, чтоб участники общения А и Б получили один и тот же ключ не обмениваясь им, ведь шпион хочет завладеть именно этим ключом чтобы потом применив его дешифровать перехваченное сообщение. Теперь рассмотрим все по порядку.
Для того чтобы участники А и Б с генерировали одинаковый ключ им должны быть известны исходные параметры на базе которых будет создан секретный ключ. Первые два параметра которые будут известны двум участникам общения А и Б это простые случайные числа p и g. Эти параметры не представляют из себя никакой секретной информации, поэтому они могут передаваться через не защищенный от прослушивания канал в открытом виде, и понято, что они будут известны шпиону.

История

Передача ключа по открытым каналам была большой проблемой криптографии XX века. Но эту проблему удалось решить после появления алгоритма Диффи — Хеллмана. Данный алгоритм позволил дать ответ на главный вопрос: «Как при обмене зашифрованными посланиями уйти от необходимости передачи секретного кода расшифровки, который, как правило, не меньше самого послания?» Открытое распространение ключей Диффи — Хеллмана позволяет паре пользователей системы выработать общий секретный ключ, не обмениваясь секретными данными.

Основы криптографии с открытыми ключами были выдвинуты Уитфилдом Диффи (Whitfield Diffie) и Мартином Хеллманом (Martin Hellman), а также независимо от них Ральфом Мерклом (Ralph Merkle).

Их вкладом в криптографию было убеждение, что ключи можно использовать парами — ключ зашифрования и ключ расшифрования — при условии, что исключается возможность определения содержимого ключа для расшифрования исходя из содержимого открыто передаваемого ключа для зашифрования. Диффи и Хеллман впервые представили эту идею на Национальной компьютерной конференции 1976 года, а через несколько месяцев была опубликована их основополагающая работа «New Directions in Cryptography» («Новые направления в криптографии»).

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

В 2002 году Мартин Хеллман писал:

Эта система … с тех пор известна под названием алгоритма Диффи — Хеллмана. Однако, когда система была впервые описана на бумаге Диффи и мной, это была система распространения открытых ключей, концепция которой была выработана Мерклом, и поэтому она должна называться „алгоритмом Диффи — Хеллмана — Меркла“, если её связывают с именами. Я надеюсь, что это небольшое изменение поможет признанию равного вклада Меркла в изобретение криптографии с открытыми ключами.

В уже истёкшем патенте U.S. Patent 4 200 770 в качестве создателей данного алгоритма указано три автора — Хеллман, Диффи и Меркл.

Только в декабре 1997 года появилась обновлённая информация о том, что Малькольм Вильямсон уже в 1974 году изобрёл математический алгоритм, основанный на коммутативности показателей при последовательном возведении в степень ( ( b x ) y = ( b y ) x = b x y {\displaystyle (b^{x})^{y}=(b^{y})^{x}=b^{xy}} ). Данный метод можно назвать аналогом алгоритма Диффи — Хеллмана.

Описание алгоритма

Предположим, существует два абонента: Алиса и Боб. Обоим абонентам известны некоторые два числа g {\displaystyle g} и p {\displaystyle p} , которые не являются секретными и могут быть известны также другим заинтересованным лицам. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют большие случайные числа: Алиса — число a {\displaystyle a} , Боб — число b {\displaystyle b} . Затем Алиса вычисляет остаток от деления (1):

A = g a mod p {\displaystyle A=g^{a}{\bmod {p}}} (1)

и пересылает его Бобу, а Боб вычисляет остаток от деления (2):

B = g b mod p {\displaystyle B=g^{b}{\bmod {p}}} (2)

и передаёт Алисе. Предполагается, что злоумышленник может получить оба этих значения, но не модифицировать их (то есть, у него нет возможности вмешаться в процесс передачи).

На втором этапе Алиса на основе имеющегося у неё a {\displaystyle a} и полученного по сети B {\displaystyle B} вычисляет значение (3):

B a mod p = g a b mod p {\displaystyle B^{a}{\bmod {p}}=g^{ab}{\bmod {p}}} (3)

Боб на основе имеющегося у него b {\displaystyle b} и полученного по сети A {\displaystyle A} вычисляет значение (4):

A b mod p = g a b mod p {\displaystyle A^{b}{\bmod {p}}=g^{ab}{\bmod {p}}} (4)

Как нетрудно видеть, у Алисы и Боба получилось одно и то же число (5):

K = g a b mod p {\displaystyle K=g^{ab}{\bmod {p}}} (5)

Его они и могут использовать в качестве секретного ключа, поскольку здесь злоумышленник встретится с практически неразрешимой (за разумное время) проблемой вычисления (3) или (4) по перехваченным g a mod p {\displaystyle g^{a}{\bmod {p}}} и g b mod p {\displaystyle g^{b}{\bmod {p}}} , если числа p {\displaystyle p} , a {\displaystyle a} , b {\displaystyle b} выбраны достаточно большими. Работа алгоритма показана на рисунке.

Алгоритм Диффи — Хеллмана, где K — итоговый общий секретный ключ

При работе алгоритма каждая сторона:

  1. генерирует случайное натуральное число a — закрытый ключ
  2. совместно с удалённой стороной устанавливает открытые параметры p и g (обычно значения p и g генерируются на одной стороне и передаются другой), где p является случайным простым числом (p-1)/2 также должно быть случайным простым числом (для повышения безопасности) g является первообразным корнем по модулю p (также является простым числом)
  3. вычисляет открытый ключ A, используя преобразование над закрытым ключом A = ga mod p
  4. обменивается открытыми ключами с удалённой стороной
  5. вычисляет общий секретный ключ K, используя открытый ключ удаленной стороны B и свой закрытый ключ a K = Ba mod p К получается равным с обеих сторон, потому что: Ba mod p = (gb mod p)a mod p = gab mod p = (ga mod p)b mod p = Ab mod p

В практических реализациях для a и b используются числа порядка 10100 и p порядка 10300. Число g не обязано быть большим и обычно имеет значение в пределах первого десятка.

Пример

Ева — криптоаналитик. Она читает пересылку Боба и Алисы, но не изменяет содержимого их сообщений.

  • s = секретный ключ. s = 2
  • g = первообразный корень по модулю р. g = 5
  • p = открытое простое число. p = 23
  • a = секретный ключ Алисы. a = 6
  • A = открытый ключ Алисы. A = ga mod p = 8
  • b = секретный ключ Боба. b = 15
  • B = открытый ключ Боба. B = gb mod p = 19

Алгоритм Диффи — Хеллмана с тремя и более участниками

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

Все вычисления производятся по модулю p

  1. Стороны договариваются о параметрах алгоритма p и g
  2. Стороны, Алиса, Боб и Кэрол генерируют свои ключи — a, b и c соответственно.
  3. Алиса вычисляет ga и посылает его Бобу
  4. Боб вычисляет (ga)b = gab и посылает его Кэрол
  5. Кэрол вычисляет (gab)c = gabc и получает тем самым общий секретный ключ
  6. Боб вычисляет gb и посылает его Кэрол
  7. Кэрол вычисляет (gb)c = gbc и посылает его Алисе
  8. Алиса вычисляет (gbc)a = gbca = gabc — общий секретный ключ
  9. Кэрол вычисляет gc и посылает его Алисе
  10. Алиса вычисляет (gc)a = gca и посылает его Бобу
  11. Боб вычисляет (gca)b = gcab = gabc и также получает общий секретный ключ

Если кто-то будет прослушивать канал связи, то он сможет увидеть ga, gb, gc, gab, gac, и gbc, но при этом не сможет воспроизвести gabc используя любые комбинации этих чисел.

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

  • Передача ключа должна начинаться с «пустого» ключа g. Весь секрет состоит в повышении текущего значения показателя каждого участника один раз;
  • Любое промежуточное значение может быть раскрыто публично, но окончательное значение представляет из себя секретный ключ, который никогда не должен быть публично раскрыт. Таким образом, каждый пользователь получает свою копию тайного ключа.

Криптографическая стойкость

Криптографическая стойкость алгоритма Диффи — Хеллмана (то есть сложность вычисления K = g a b mod p {\displaystyle K=g^{ab}{\bmod {p}}} по известным p, g, A = g a mod p {\displaystyle A=g^{a}{\bmod {p}}} и B = g b mod p {\displaystyle B=g^{b}{\bmod {p}}} ) основана на предполагаемой сложности задачи дискретного логарифмирования.

Протокол Диффи — Хеллмана отлично противостоит пассивному нападению, но в случае реализации атаки «человек посередине» он не устоит. В самом деле, в протоколе ни Алиса, ни Боб не могут достоверно определить, кем является их собеседник, поэтому вполне возможно представить случай, при котором Боб и Алиса установили связь с Меллори, который Алисе выдает себя за Боба, а Бобу представляется Алисой. И тогда вместо протокола Диффи — Хеллмана получаем что-то похожее на следующее:

Шаг Алиса Меллори Боб
1 ga→ ga
2 gn← gn
gan gan
3 gm→ gm
4 gb← gb
gmb gmb

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

Задача Диффи — Хеллмана и задача дискретного логарифмирования

Стойкость разделенного ключа в протоколе Диффи — Хеллмана обеспечивается вычислением значения g a b mod p {\displaystyle g^{ab}{\bmod {p}}} по заданным числам g a {\displaystyle g^{a}} и g b {\displaystyle g^{b}} . Эта задача называется вычислительной задачей Диффи — Хеллмана.

Вычислительная задача Диффи — Хеллмана (в конечном поле)

ИСХОДНЫЕ ДАННЫЕ: desq F q {\displaystyle F_{q}}: описание конечного поля F q {\displaystyle F_{q}}; g∈ F q ∗ {\displaystyle F_{q}^{*}}— порождающий элемент группы F q ∗ {\displaystyle F_{q}^{*}}; g a {\displaystyle g_{a}}, g b {\displaystyle g_{b}}∈ F q ∗ {\displaystyle F_{q}^{*}}, где 0 < a, b < q. РЕЗУЛЬТАТ: g a b {\displaystyle g^{ab}}

Такая формулировка представляет собой общую постановку задачи в конечном поле F q {\displaystyle F_{q}} представляет общий случай, для Диффи — Хеллмана используется специальный случай. Если бы задачу Диффи — Хеллмана было легко решить, то значение g a b mod p {\displaystyle g^{ab}{\bmod {p}}} можно было бы найти, зная числа p {\displaystyle p} , g {\displaystyle g} , g a {\displaystyle g^{a}} и g b {\displaystyle g^{b}} , которые являются частью протокола. Предполагая, что противник обладает возможностями перехвата информации, следует предположить, что эти числа не являются для него секретом. Задача Диффи — Хеллмана опирается на сложность вычисления дискретного логарифма.

Задача дискретного логарифмирования (в конечном поле)

ИСХОДНЫЕ ДАННЫЕ: desq F q {\displaystyle F_{q}}: описание конечного поля F q {\displaystyle F_{q}}; g∈ F q ∗ {\displaystyle F_{q}^{*}}— порождающий элемент группы F q ∗ {\displaystyle F_{q}^{*}}

; h ∈ U {\displaystyle {}_{U}}F q ∗ {\displaystyle F_{q}^{*}}РЕЗУЛЬТАТ: Уникальное число a < q, удовлетворяющее условию h = g a {\displaystyle g^{a}}. Целое число a обозначается как l o g g {\displaystyle log_{g}}h.

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

Как уже стало понятным, в основе современной криптографии лежит теория вычислительной сложности. Это значит, что стойкость криптосистем с открытым ключом является условной и зависит от сложности решения некоторых задач. Все это приводит к тому, что задача Диффи — Хеллмана и задача дискретного логарифмирования считаются трудноразрешимыми.

Интуитивно ясно, что сложность решения этих задач зависит как от размера поля Fq, так и от выбора параметров (открытого параметра g и секретных чисел a и b). Очевидно, что небольшие варианты этих задач являются разрешимыми. Полученные сведения позволяют сформулировать точные предположения о неразрешимости задачи Диффи — Хеллмана и задачи дискретного логарифмирования.

Предположение 1 — Условия неразрешимости задачи Диффи — Хеллмана

Алгоритмом решения задачи Диффи — Хеллмана называется вероятностный полиномиальный алгоритм A с преимуществом ε > 0:

где входные данные А указаны в определении (Вычислительная задача Диффи — Хеллмана) (в конечном поле).

Пусть IG — генератор вариантов, получающий на вход число 1 k {\displaystyle 1^{k}} , время работы которого является полиномом от параметра k, а результатом — 1) desq( F q {\displaystyle F_{q}} ), где |q| = k, и 2) порождающий элемент g ∈ F q ∗ {\displaystyle F_{q}^{*}} .

Будем говорить, что генератор IG удовлетворяет условиям неразрешимости задачи Диффи — Хеллмана, если для вариантов IG( 1 k {\displaystyle 1^{k}} ) не существует алгоритма решения с преимуществом ε> 0, которое не является пренебрежимо малым по сравнению со всеми достаточно большими числами k.

Предположение 2 — Условия неразрешимости задачи дискретного логарифмирования

Алгоритмом решения задачи дискретного логарифмирования называется вероятностный полиномиальный алгоритм A с преимуществом ε > 0:

ε = Prob

где входные данные А указаны в определении (Вычислительная задача Диффи — Хеллмана) (в конечном поле).

Пусть IG — генератор вариантов, получающий на вход число 1 k {\displaystyle 1^{k}} , время работы которого является полиномом от параметра k, а результатом — 1) desq( F q {\displaystyle F_{q}} ), где |q| = k, и 2) порождающий элемент g ∈ F q ∗ {\displaystyle F_{q}^{*}} и 3) элемент h ∈ F q ∗ {\displaystyle F_{q}^{*}}

Будем говорить, что генератор IG удовлетворяет условиям неразрешимости задачи Диффи — Хеллмана, если для вариантов IG( 1 k {\displaystyle 1^{k}} ) не существует алгоритма решения с преимуществом ε> 0, которое не является пренебрежимо малым по сравнению со всеми достаточно большими числами k.

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

Примечания

  1. 1 2 Diffie W., Hellman M. E. New Directions in Cryptography // IEEE Trans. Inf. Theory / F. Kschischang — IEEE, 1976. — Vol. 22, Iss. 6. — P. 644–654. — ISSN 0018-9448 — doi:10.1109/TIT.1976.1055638
  2. Intellect. Как работает асимметричное шифрование понятным языком. 20 мая 2012.
  3. 1 2 Брюс Шнаер «Прикладная Криптография»
  4. 1 2 3 Шифрование-асимметричные методы Глава 8 («Шифрование с открытым ключом», «Обмен ключом без обмена ключом», «Криптографическая стойкость», «Задача Диффи — Хеллмана и задача дискретного логарифмирования»)
  5. Брюс Шнаер «Прикладная криптография» Глава 22 пункт 22.1
  6. Cryptographic apparatus and method Martin E. Hellman, Bailey W. Diffie, and Ralph C. Merkle, U.S. Patent #4,200,770, 29 April 1980)
  7. Summary of ANSI X9.42: Agreement of Symmetric Keys Using Discrete Logarithm Cryptography (64K PDF file) (Description of ANSI 9 Standards)
  8. Diffie-Hellman Key Exchange — A Non-Mathematician’s Explanation by Keith Palmgren
  9. NSA could put undetectable “trapdoors” in millions of crypto keys. Technique allows attackers to passively decrypt Diffie-Hellman protected data. (англ.), ARS Technica (OCT 11, 2016). Дата обращения 13 октября 2016.
  10. Joshua Fried; Pierrick Gaudry, Nadia Heninger, Emmanuel Thomé. A kilobit hidden SNFS discrete logarithm computation (англ.). Eprint IACR (2016). Дата обращения 13 октября 2016.