diffie-hellman.tex

\subsection{Протокол Диффи~---~Хеллмана}
\selectlanguage{russian}

Алгоритм с открытым ключом впервые был предложен У.~Диффи (W.~Diffie) и М.~Хеллманом (M.E.~Hellman) в работе 1976 года <<Новые направления в криптографии>>\index{протокол!Диффи~---~Хеллмана}.

Рассмотрим \textbf{протокол Диффи~---~Хеллмана} обмена информацией  двух сторон $A$ и $B$. Задача состоит в том, чтобы создать общий сеансовый ключ.

Пусть $p$ -- большое простое число, $g$ -- примитивный элемент группы $\Z_p^*$, ~ $y = g^x \mod p$, причем $p,y,g$ -- известны заранее. Функцию $y=g^{x} \mod p$ считаем однонаправленной, т.е. вычисление функции при известном значении аргумента является легкой задачей, а ее обращение (нахождение аргумента) при известном значении функции -- является трудной задачей.

Протокол обмена состоит из следующих действий.
\begin{enumerate}
    \item Сторона $A$ выбирает случайное число $x, ~ 2 \leq x \leq (p-1)$, вычисляет и передает стороне $B$ сообщение:
        \[ A \rightarrow B: ~ g^x \mod p. \]
    \item Сторона $B$ выбирает случайное число $y, ~ 2\leq y \leq (p-1)$, вычисляет и передает стороне $A$:
        \[ A \leftarrow B: ~ g^y \mod p. \]
    \item Сторона $A$, используя известные ей значения $x,g^{y} \mod p$, вычисляет ключ
        \[ K_{A} =(g^{y})^{x}\mod p=g^{xy} \mod p. \]
    \item Сторона $B$, используя известные ей значения $y,g^{x} \mod p$, вычисляет ключ
        \[ K_{B} =(g^{x})^{y}\mod p=g^{xy}\mod p. \]
        В результате получаем равенство  $K_A = K_B = K$.
\end{enumerate}

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

Рассмотрим протокол Диффи~---~Хеллмана в ситуации, когда имеются три легальных пользователя $A,B,C$.

Каждая из сторон $A,B,C$ вырабатывает случайные числа $x,y,z$ соответственно и держит их в секрете.

\begin{enumerate}
    \item Первый этап обмена информацией аналогичен вышеописанному обмену информацией между двумя сторонами:
        \begin{enumerate}
            \item $A \rightarrow B: ~ g^x \mod p$.
            \item $B \rightarrow C: ~ g^y \mod p$.
            \item $C \rightarrow A: ~ g^z \mod p$.
        \end{enumerate}
    \item Второй этап состоит из передач сообщений:
        \begin{enumerate}
            \item $A \rightarrow B: ~ (g^z)^x = g^{zx} \mod p$.
            \item $B \rightarrow C: ~ (g^x)^y = g^{xy} \mod p$.
            \item $C \rightarrow A: ~ (g^y)^z = g^{yz} \mod p$.
        \end{enumerate}
    \item На завершающем третьем этапе стороны вычисляют:
        \begin{enumerate}
            \item $A: ~ K_A = (g^{yz})^x = g^{xyz} \mod p$.
            \item $B: ~ K_A = (g^{zx})^y = g^{xyz} \mod p$.
            \item $C: ~ K_A = (g^{xy})^z = g^{xyz} \mod p$.
        \end{enumerate}
\end{enumerate}

Как видно из произведенных действий, выработанные сторонами $A, B, C$ ключи совпадают: $K_A = K_B = K_C = K$. Следовательно, создан общий секретный сеансовый ключ $K$ для трех участников.

Таким же образом можно построить протокол Диффи~---~Хеллмана для любого числа легальных пользователей.

Рассмотрим этот двусторонний протокол с точки зрения криптоаналитика, желающего узнать ключ $K$. Предположим, ему удалось перехватить сообщения $g^{x}\mod p$ и $g^{y}\mod p $. Используя заранее известные данные $g,p $ и эти сообщения, криптоаналитик старается найти  хотя бы одно из чисел $(x,y)$, то есть решить задачу дискретного логарифма. В настоящее время эта задача  считается вычислительно трудной при обычно выбираемых значениях $p\sim 2^{1024}$.

Существует атака криптоаналитика, названная \textbf{<<человек посредине>>} (man-in-the-middle). Пусть имеются две легальные стороны $A$ и $B$ и нелегальная сторона $E$, криптоаналитик, который имеет возможность перехватывать сообщения как от $A$, так и от $B$:
    \[ A \leftrightsquigarrow E \leftrightsquigarrow B. \]
    %\[ A \leftrightarrow E \leftrightarrow B. \]

\begin{enumerate}
    \item Подмена ключей.
        \begin{enumerate}
            \item Сторона $A$ передает стороне $B$ сообщение:
                \[ A \overset{E}{\nrightarrow} B: ~ g^x \mod p. \]
            \item Сторона $E$ перехватывает сообщение $g^x \mod p$, сохраняет его и, зная $g$, передает стороне $B$ свое сообщение:
                \[ E \rightarrow B: ~ g^z \mod p. \]
            \item Сторона $B$ передает стороне $A$ сообщение:
                \[ A \overset{E}{\nleftarrow} B: ~ g^y \mod p. \]
            \item Сторона $E$ перехватывает сообщение $g^y \mod p$, сохраняет его и передает стороне $A$ свое сообщение
                \[ A \leftarrow E: ~ g^z \mod p \]
                или какое-то другое.
            \item Таким образом между сторонами $A$ и $E$ образуется общий секретный ключ $K_{AE}$, между $B$ и $E$ -- ключ $K_{BE}$, причем $A$ и $B$ не знают, что у них ключи со стороной $E$, а не с друг другом
                \[ \begin{array} {l}
                    K_{AE} = g^{xz} \mod p, \\
                    K_{BE} = g^{yz} \mod p. \\
                \end{array} \]

        \end{enumerate}
    \item Подмена сообщений.
        \begin{enumerate}
            \item Сторона $A$ посылает $B$ сообщение $m$, зашифрованное на ключе $K_{AE}$:
                % \rightsquigarrow
                \[ A \overset{E}{\nrightarrow} B: ~ E_{K_{AE}}(m). \]
            \item Сторона $E$ перехватывает сообщение, расшифровывает с ключом $K_{AE}$, возможно, подменяет на $m'$, зашифровывает с ключом $K_{BE}$ и посылает $B$:
                \[ E \rightarrow B: ~ E_{K_{BE}}(m'). \]
            \item То же самое происходит при обратной передаче от $B$ к $A$.
        \end{enumerate}
\end{enumerate}

Криптоаналитик $E$ перехватывает все сообщения и может их подменять. Если по тексту письма нельзя обнаружить участие криптоаналитика в обмене информацией, то атака <<человек-посередине>>\index{криптоатака!человек-посередине} успешна.

Существует несколько протоколов для преодоления атаки этого типа.