shamirs_three-step_protocol.tex

\section[Трёхэтапный протокол Шамира]{Трёхэтапный протокол Шамира на коммутативных шифрах}
\selectlanguage{russian}

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

Для решения этой задачи используют трёхэтапный протокол Шамира с тремя <<замками>>. \emph{Протокол Шамира}\index{протокол!Шамира} построен на \emph{коммутативных} функциях шифрования, для которых выполняется условие:
    \[ E_{K_{B}} (E_{K_{A}}(K))=E_{K_{A}} (E_{K_{B}}(K)). \]

Протокол предполагает следующие процедуры.
\begin{enumerate}
    \item $A$ создаёт секретный ключ $K$, шифрует его своей системой шифрования с помощью своего ключа $K_A$ и посылает сообщение стороне $B$:
        \[ A \rightarrow B: ~ E_{K_A}(K). \]
    \item $B$ получает это сообщение, шифрует его с помощью своего ключа $K_B$ и посылает сообщение стороне $A$:
        \[ A \leftarrow B: ~ E_{K_B}( E_{K_A}( K)). \]
    \item Сторона $A$, получив сообщение $E_{K_B}(E_{K_A}(K))$, использует свой секретный ключ $K_A$ для расшифрования:
            \[ D_{K_A}(E_{K_B} (E_{K_A}(K))) = E_{K_B}(K). \]
        Сторона $A$ передаёт стороне $B$ сообщение:
        \[ A \rightarrow B: ~ E_{K_B}(K). \]
    \item Сторона $B$, получив сообщение $E_{K_B}(K)$, использует свой секретный ключ $K_B$ для расшифрования:
            \[ D_{K_B}(E_{K_B}(K)) = K. \]
        В результате стороны получают общий секретный ключ $K$.
\end{enumerate}

Приведём пример неудачного шифрования с использованием коммутативных функций.

\begin{enumerate}
    \item $A$ имеет функцию шифрования совершенной секретности $E_{K_A}(K) = K \oplus K_A$, где $K_A$ -- двоичная последовательность с равномерным распределением символов. $A$ посылает это сообщение стороне $B$:
            \[ A \rightarrow B: ~ E_{K_A}(K) = K \oplus K_A. \]
    \item $B$ использует такую же функцию шифрования совершенной секретности с ключом $K_B$ (двоичная последовательность с равномерным распределением символов). $B$ шифрует полученное сообщение и отправляет $A$:
            \[ A \leftarrow B: ~ E_{K_A}(K) \oplus K_B = K \oplus K_A \oplus K_B. \]
    \item Сторона $A$, получив сообщение $K \oplus K_A \oplus K_B$, выполняет расшифрование:
            \[ K \oplus K_A \oplus K_B \oplus K_A = K \oplus K_B. \]
        Сторона $A$ передаёт стороне $B$ сообщение:
            \[ A \rightarrow B: ~ K \oplus K_B. \]
    \item Сторона $B$, получив сообщение $K \oplus K_B$, выполняет расшифрование:
            \[ K \oplus K_B \oplus K_B = K. \]
        Обе стороны получают общий секретный ключ $K$.
\end{enumerate}

Предложенный выбор коммутативной функции шифрования совершенной секретности был назван неудачным, так как существуют ситуации, при которых криптоаналитик может определить ключ $K$. Предположим, что криптоаналитик перехватил все три сообщения:
    \[ K \oplus K_A, ~~ K \oplus K_A \oplus K_B, ~~ K \oplus K_B. \]
Сложение по модулю 2 всех трёх сообщений даёт ключ $K$. Поэтому такая система шифрования не применяется.

Теперь приведём протокол надёжной передачи секретного ключа, основанный на экспоненциальной (коммутативной) функции шифрования. Стойкость этого протокола связана с трудностью задачи вычисления дискретного логарифма: известны значения $y, g, p$, найти $x$ в уравнении $y = g^x \mod p$.

\textbf{Протокол Шамира распространения ключей}

Выбирают большое простое\index{число!простое} число $p\sim 2^{1024}$ и используют его как открытый ключ.

\begin{enumerate}
    \item Сторона $A$ задаёт общий секретный ключ $K <p$ и выбирает целое число $a$, взаимно простое с $p-1$. $A$ вычисляет и посылает сообщение стороне $B$:
            \[ A \rightarrow B: ~ K^a \mod p. \]
        Существует число $c$ такое, что $a c =1 \mod (p-1)$, то есть $a c = 1 + l (p-1)$, где $l$ -- целое число. Число $c$ будет использовано стороной $A$ на следующем этапе.
    \item Сторона $B$ выбирает целое число $b$, взаимно простое с $p-1$. Используя полученное сообщение, вычисляет и посылает сообщение стороне $A$:
            \[ A \leftarrow B: ~ (K^a)^b \mod p. \]
    \item Сторона $A$, получив сообщение, вычисляет
        \[ \left( K^{ab} \right)^c = K^{(1 + l (p-1)) b} = K^b \cdot K^{l (p-1) b} = K^b \mod p. \]
        Здесь применена малая теорема Ферма\index{теорема!Ферма малая}: $K^{p-1} = 1 \mod p$, поэтому $\left( K^{p-1} \right)^{lb} = 1 \mod p$.
        $A$ посылает $B$ сообщение:
            \[ A \rightarrow B: ~ K^b \mod p. \]
    \item Сторона $B$, получив сообщение $K^{b}\mod p$, вычисляет
        \[ (K^b \mod p)^d = K^{bd} \mod p = K, \]
        где $d$ найдено из $b d =1 \mod (p-1)$.
\end{enumerate}

Теперь проверим криптостойкость этого протокола. Предположим, что криптоаналитик перехватил три сообщения:
\[ \begin{array}{l}
    y_1 = K^a \mod p, \\
    y_2 = K^{ab} \mod p, \\
    y_3 = K^b \mod p. \\
\end{array} \]
Чтобы найти ключ $K$, надо решить систему из этих трёх уравнений, что имеет очень большую вычислительную сложность, неприемлемую с практической точки зрения, если все три числа $a, b, ab$ достаточно велики. Предположим, что $a$ (или $b$) мало. Тогда, вычисляя последовательные степени $y_3$ (или $y_1$), можно найти $a$ (или $b$), сравнивая результат с $y_2$. Зная $a$, легко найти $a^{-1}\mod(p-1)$ и $K=(y_1)^{a^{-1}}\mod p$.

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