Список обозначений

Протокол Диффи—Хеллмана

diffie-Hellman protocol

Протокол Диффи – Хеллмана является наиболее известным протоколом распределения ключей. Мы опишем его в более общем виде, чем в пионерской работе [1].

Пусть $(G_i\,|\, i\in I)$, где $I\subseteq\{0,1\}^*$, — полиномиально вычислимое семейство конечных групп. Пусть также $(\mathfrak I_n\,|\, n\in\mathbb N)$ и $(\mathfrak G_i\,|\, i\in I)$ — полиномиально конструируемые семейства распределений вероятностей такие, что $\mathop{\mathrm{supp}}\mathfrak I_n\subseteq I$ для всех $n\in\mathbb N$ и $\mathop{\mathrm{supp}}\mathfrak G_i\subseteq G_i$ для всех $i\in I$. Кроме того, предположим, что определены полиномиально вычислимые функции $\alpha$ и $\beta$, определенные на всех парах вида $(i,g)$, где $i\in I$ и $g\in G_i$, и принимающие целочисленные значения, причем $\alpha(i,g)\leqslant\beta(i,g)$ для всех пар $(i,g)$ указанного вида. Для произвольного $n\in\mathbb N$ определим распределение вероятностей $\mathfrak D_n$ как распределение на множестве всех пар $(i,g)$, где $i\leftarrow\mathfrak I_n$ и $g\leftarrow\mathfrak G_i$. Очевидно, что семейство распределений вероятностей $(\mathfrak D_n\,|\, n\in\mathbb N)$ полиномиально конструируемо. Тогда протокол Диффи – Хеллмана (с двумя участниками A и B) определяется следующим образом.

Общий вход: $(1^n,i,g)$, где $i\in\mathop{\mathrm{supp}}\mathfrak I_n$ и $g\in\mathop{\mathrm{supp}}\mathfrak G_i$ ($n\in\mathbb N$).
  1. Участник A выбирает $x\in_{\mathfrak U}\{\alpha(i,g),\dots,\beta(i,g)\}$, вычисляет $a=g^x$ и посылает $a$ участнику B.
  2. Участник B выбирает $y\in_{\mathfrak U}\{\alpha(i,g),\dots,\beta(i,g)\}$, вычисляет $b=g^y$ и посылает $b$ участнику A.
  3. Участник A вычисляет общий секретный ключ, равный $g^{xy}$, как $b^x$.
  4. Участник B вычисляет общий секретный ключ, равный $g^{xy}$, как $a^y$.

Очевидно, что протокол Диффи – Хеллмана удовлетворяет условию 1 определения протокола распределения ключей (см. определение 1 из одноименной статьи). В то же время доказать выполнение условия 2 этого определения удалось лишь для некоторых частных случаев протокола Диффи – Хеллмана и лишь при некоторых предположениях.

Пусть $n\in\mathbb N$, $i\in\mathop{\mathrm{supp}}\mathfrak I_n$, $g\in\mathop{\mathrm{supp}}\mathfrak G_i$, а $x$, $y$ и $z$ — целые числа. Под вычислительной задачей Диффи – Хеллмана (называемой также просто задачей Диффи – Хеллмана) понимают задачу вычисления по $(1^n,i,g,g^x,g^y)$ элемента $g^{xy}$. Распознавательная задача Диффи – Хеллмана заключается в проверке по $(1^n,i,g,g^x,g^y,g^z)$ истинности равенства $g^{xy}=g^z$. Очевидно, что распознавательная задача Диффи – Хеллмана сводится к вычислительной. Условие 2 определения протокола распределения ключей (см. определение 1 из одноименной статьи) означает, что вычислительная задача Диффи – Хеллмана трудна в среднем, т. е. что произвольный полиномиальный вероятностный алгоритм может найти $g^{xy}$ по $(1^n,i,g,g^x,g^y)$, где $i\leftarrow\mathfrak I_n$, $g\leftarrow\mathfrak G_i$ и $x,y\in_{\mathfrak U}\{\alpha(i,g),\dots,\beta(i,g)\}$, лишь с пренебрежимо малой (от $n$) вероятностью. Трудность в среднем распознавательной задачи Диффи – Хеллмана формализуется как вычислительная неотличимость семейств распределений вероятностей (индексированных $n\in\mathbb N$) на наборах $(i,g,g^x,g^y,g^{xy})$ и $(i,g,g^x,g^y,g^z)$, где $i\leftarrow\mathfrak I_n$, $g\leftarrow\mathfrak G_i$ и $x,y,z\in_{\mathfrak U}\{\alpha(i,g),\dots,\beta(i,g)\}$. Условие трудности в среднем распознавательной задачи Диффи – Хеллмана является формализацией того, что внешний пассивный полиномиально ограниченный противник не может получить по открытой информации и транскрипции диалога никакой информации об общем секретном ключе.

Пусть $\operatorname{num}(i)$ для любого $i\in I$ является произведением двух различных простых чисел. Для каждого $i\in I$ в качестве группы $G_i$ выбирается $\mathbb Z^{\star}_{\operatorname{num}(i)}$. Предположим, что семейство $(\mathfrak I_n\,|\, n\in\mathbb N)$ распределений вероятностей выбрано так, что задача факторизации чисел $\operatorname{num}(i)$, где $i\leftarrow\mathfrak I_n$, трудна. Формально это означает, что для любого полиномиального вероятностного алгоритма $\mathcal F$ величина $\Pr(\mathcal F(1^n,pq)=\{p,q\})$, где $i\leftarrow\mathfrak I_n$ и $pq=\operatorname{num}(i)$ ($p$ и $q$ — различные простые числа), пренебрежимо мала как функция от $n\in\mathbb N$. При этом предположении в работах [2], [3], [4] было доказано, что некоторые частные случаи протокола Диффи – Хеллмана с параметрами указанного вида удовлетворяют условию 2 определения протокола распределения ключей (т. е. для этих частных случаев вычислительная задача Диффи – Хеллмана трудна в среднем). Однако в работах [2] и [3] для этого требуется, чтобы простые числа, произведениями которых являются $\operatorname{num}(i)$, имели некоторый специальный вид, тогда как в [4] эти простые числа могут быть произвольными. Мы приведем результат работы [4] (в несколько модифицированном виде), из которого следует вышеуказанное утверждение о трудности в среднем вычислительной задачи Диффи – Хеллмана для соответствующего частного случая.

Теорема 1
Пусть $M$ — множество всех чисел, являющихся произведениями двух различных простых чисел. Предположим, что для каждого $m\in M$ определен вероятностный оракул $D_m$, который в ответ на произвольный запрос вида $(g,f,h)$, где $g,f,h\in\mathbb Z^{\star}_m$, возвращает некоторый элемент $\mathbb Z^{\star}_m$. Обозначим через $\delta(m)$ вероятность того, что $D_m$ в ответ на запрос $(g,g^x\bmod m,g^y\bmod m)$, где $g$ — случайный элемент нечетного порядка группы $\mathbb Z^{\star}_m$, выбранный равновероятно среди всех таких элементов, а $x,y\in_{\mathfrak U}\mathbb Z_m$, возвращает $g^{xy}\bmod m$ ($m\in M$). Тогда существует полиномиальный вероятностный алгоритм $\mathcal F$ такой, что \[ \Pr\left(\mathcal F^{D_m}(m)=\{p,q\}\right) =\Omega(\delta(m)) \] для любого $m\in M$, где $p$ и $q$ — простые множители числа $m$.

Отметим, что распределение вероятностей $\mathfrak G_i$ в работе [3] сосредоточено на $16$, а в [2], как и в [4], оно является равномерным на множестве всех элементов нечетного порядка группы $\mathbb Z^{\star}_{\operatorname{num}(i)}$.

Другое направление исследований состоит в том, чтобы попытаться доказать условие 2 определения протокола распределения ключей (см. определение 1 из одноименной статьи) в предположении сложности задачи дискретного логарифмирования. Это удалось сделать лишь при сильных дополнительных предположениях (см. [5], [6], [7], [8], [9], [10], [11], [12]). О сложности распознавательной задачи Диффи – Хеллмана известно гораздо меньше, чем о сложности вычислительной задачи Диффи – Хеллмана (см. [13], [14], [9], [12]).

Литература

  • [1] Diffie, W. and Hellman, M. E. «New directions in cryptography» 1976
  • [2] Shmuely, Z. «Composite Diffie-Hellman public-key generating systems are hard to break» 1985
  • [3] McCurley, K. S. «A key distribution system equivalent to factoring» 1988
  • [4] Anokhin, M. I. «A provably secure composite Diffie–Hellman scheme» 1996
  • [5] den Boer, B. «Diffie-Hellman is as strong as discrete log for certain primes» 1989
  • [6] Maurer, U. M. «Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms» 1994
  • [7] Maurer, U. and Wolf, S. «Diffie-Hellman Oracles» 1996
  • [8] Maurer, U. and Wolf, S. «On the complexity of breaking the Diffie-Hellman protocol» 1996
  • [9] Maurer, U. and Wolf, S. «Diffie-Hellman, decision Diffie-Hellman, and discrete logarithms» 1998
  • [10] Maurer, U. and Wolf, S. «Lower bounds on generic algorithms in groups» 1998
  • [11] Maurer, U. and Wolf, S. «The relationship between breaking the Diffie-Hellman protocol and computing discrete logarithms» 1999
  • [12] Maurer, U. and Wolf, S. «The Diffie-Hellman protocol» 2000
  • [13] Boneh, D. «The decision Diffie—Hellman problem» 1998
  • [14] Maurer, U. and Wolf, S. «On the hardness of the Diffie—Hellman decision problem» 1998

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна