el-gamal.tex

\section{Криптосистема Эль-Гамаля}\index{криптосистема!Эль-Гамаля|(}
\selectlanguage{russian}

Эта система шифрования с открытым ключом опубликована в 1985 году Эль-Гамалем (\langen{Taher El Gamal}, \cite{ElGamal:1985}). Рассмотрим принципы её построения.

Пусть имеется мультипликативная группа $\Z_p^* = \{1, 2, \dots, p-1\}$, где $p$ -- большое простое\index{число!простое} число, содержащее не менее 1024 двоичных разрядов. В группе $\Z_p^*$ существует $\varphi( \varphi( p ) ) = \varphi( p - 1 )$ элементов, которые порождают все элементы группы. Такие элементы называются генераторами\footnote{Подробнее см. раздел~\ref{section-groups} в приложении.}.

Выберем один из таких генераторов $g$ и целое число $x$ в интервале $1 \leq x \leq p-1$. Вычислим:
    \[ y = g^x \mod p. \]

Хотя элементы $x$ и $y$ группы $\Z_p^*$ задают друг друга однозначно, найти $y$, зная $x$, просто, а вот эффективный алгоритм для получения $x$ по заданному $y$ неизвестен. Говорят, что задача вычисления дискретного логарифма
	\[ x = \log_g y \mod p \]
является вычислительно сложной. На сложности вычисления дискретного логарифма для больших простых $p$ основывается криптосистема Эль-Гамаля.

\subsection{Шифрование}\index{шифр!Эль-Гамаля|(}

Процедура шифрования в криптосистеме Эль-Гамаля состоит из следующих операций.

\begin{enumerate}
    \item \textbf{Создание пары из закрытого и открытого ключей стороной $A$.}
        \begin{enumerate}
            \item $A$ выбирает простое\index{число!простое} случайное число $p$.
            \item Выбирает генератор $g$ (в программных реализациях алгоритма генератор часто выбирается малым числом, например, $g = 2 \mod p$).
            \item Выбирает $x \in [0, p - 1]$ с помощью генератора случайных чисел.
            \item Вычисляет $y=g^{x}\mod p$.
            \item Создаёт закрытый и открытый ключи $\SK$ и $\PK$:
                \[ \SK = (p, g, x), ~ \PK = (p, g, y). \]
                Криптостойкость задаётся битовой длиной параметра $p$.
        \end{enumerate}
    \item \textbf{Шифрование на открытом ключе стороной $B$.}
        \begin{enumerate}
            \item Стороне $B$ известен открытый ключ $\text{PK} = (p, g, y)$ стороны $A$.
            \item Сообщение представляется числом $m \in [0, p-1]$.
            \item Сторона $B$ выбирает случайное число $r \in [1, p-1]$ и вычисляет:
                \[ \begin{array}{l}
                    a = g^r \mod p, \\
                    b = m \cdot y^r \mod p.
                \end{array} \]
            \item Создаёт шифрованное сообщение в виде
                \[ c = (a, b) \]
                и посылает стороне $A$.
        \end{enumerate}
    \item \textbf{Расшифрование на закрытом ключе стороной $A$.}

	Получив сообщение $(a, b)$ и владея закрытым ключом $\text{SK} = (p, g, x)$, $A$ вычисляет:
                \[ m = \frac{b}{a^x} \mod p. \]
\end{enumerate}

Шифрование корректно, так как 
\[ \begin{array}{l}
    m' = \frac{b}{a^x} = \frac{m y^r}{g^{rx}} = m \mod p, \\
    m' \equiv m \mod p.
\end{array} \]

Чтобы криптоаналитику получить исходное сообщение $m$ из шифртекста $(a, b)$, зная только открытый ключ получателя $\text{PK} = (p, g, y)$, нужно вычислить значение $m = b \cdot y^{-r} \mod p$. Для этого криптоаналитику нужно найти случайный параметр $r = \log_g a \mod p$, то есть вычислить дискретный логарифм. Такая задача является вычислительно сложной.

\example Создание ключей, шифрование и расшифрование в криптосистеме Эль-Гамаля.

\begin{enumerate}
    \item Генерация параметров.
        \begin{enumerate}
            \item Выберем $p=41$.
            \item Группа $\Z_p^*$ циклическая, найдём генератор (примитивный элемент). Порядок группы
                \[ |\Z_p^*| = \varphi(p) = p-1 = 40. \]
                Делители 40: 1, 2, 4, 5, 8, 10, 20. Элемент группы является примитивным, если все его степени, соответствующие делителям порядка группы, не сравнимы с 1. Из таблицы~\ref{tab:elgamal-generator-search} видно, что число $g = 6$ является генератором всей группы.
                \begin{table}[!ht]
                    \centering
                    \caption{Поиск генератора в циклической группе $\Z_{41}^*$. Элемент 6 -- генератор\label{tab:elgamal-generator-search}}
                    \resizebox{\textwidth}{!}{ \begin{tabular}{|c|c|c|c|c|c|c|c|c|}
                        \hline
                        \multirow{2}{*}{Элемент} & \multicolumn{7}{|c|}{Степени} & \multirow{2}{*}{Порядок элемента} \\
                        \cline{2-8}
                        \rule{0pt}{2.5ex}        & $2$   & $4$   & $5$   & $8$  & $10$ & $20$ & $40$ & \\
                        \hline
                        \rule{0pt}{2.5ex}$2$       & $4$   & $16$  & $-9$  & $10$ & $-1$ & $1$  &    & $20$ \\
                        $3 $      & $9$   & $-1$  & $-3$  & $1$  &    &    &    & $8$ \\
                        $5 $      & $-16$ & $10$  & $9$   & $18$ & $-1$ & $1$  &    & $20$ \\
                       $ 6 $      & $-5$  & $-16$ & $-14$ & $10$ & $-9$ & $-1$ & $1$  & $40$ \\
                        \hline
                    \end{tabular} }
                \end{table}
            \item Выберем случайное $x = 19 \in [0, p-1]$.
            \item Вычислим
                \[ \begin{array}{ll}
                    y & = g^x \mod p = \\
                    & = 6^{19} \mod 41 = \\
                    & = 6^{1 + 2 + 4 \cdot 0 + 8 \cdot 0 + 16} \mod 41 = \\
                    & = 6^1 \cdot 6^2 \cdot 6^{4 \cdot 0} \cdot 6^{8 \cdot 0} \cdot 6^{16} \mod 41 = \\
                    & = 6 \cdot (-5) \cdot (-16)^0 \cdot 10^0 \cdot 18 \mod 41 = \\
                    & = -7 \mod 41.
                \end{array} \]
            \item Открытый и закрытый ключи:
                \[ \PK = (p:41, g:6, y:-7), ~ \SK = (p:41, g:6, x:19). \]
        \end{enumerate}
    \item Шифрование.
        \begin{enumerate}
            \item Пусть сообщением является число $m = 3 \in \Z_p^*$.
            \item Выберем случайное число $r = 25 \in [1, p-1]$.
            \item Вычислим
                \[ \begin{array}{l}
                    a = g^r \mod p = 6^{25} \mod 41 = 14 \mod 41, \\
                    b = m y^r \mod p = 3 \cdot (-7)^{25} \mod 41 = -9 \mod 41.
                \end{array} \]
            \item Шифртекстом является пара чисел
                \[ c = (a:14, ~ b:-9). \]
        \end{enumerate}
    \item Расшифрование.
        \begin{enumerate}
            \item Пусть получен шифртекст
                \[ c = (a:14, ~ b:-9). \]
            \item Вычислим открытый текст как
                \[ \begin{array}{ll}
                    m & = \frac{b}{a^x} \mod p = \\
                    & = -9 \cdot (14^{-1})^{19} \mod 41 = \\
                    & = -9 \cdot 3^{19} \mod 41 = \\
                    & = -9 \cdot (-14) \mod 41 = \\
                    & = 3 \mod 41. \\
                \end{array} \]
        \end{enumerate}
\end{enumerate}

\exampleend
\index{шифр!Эль-Гамаля|)}

\subsection{Электронная подпись}\index{электронная подпись!Эль-Гамаля|(}

Криптосистема Эль-Гамаля, как и криптосистема RSA\index{криптосистема!RSA}, может быть использована для создания электронной подписи.

По-прежнему имеются два пользователя $A$ и $B$ и незащищённый канал связи между ними. Пользователь $A$ хочет подписать своё открытое сообщение $m$ для того, чтобы пользователь $B$ мог убедиться, что именно $A$ подписал сообщение.

Пусть $A$ имеет закрытый ключ $\SK = (p, g, x)$, открытый ключ $\PK = (p, g, y)$ (полученные так же, как и в системе шифрования Эль-Гамаля) и хочет подписать открытое сообщение. Обозначим подпись $S(m)$.

Для создания подписи $S(m)$ пользователь $A$ выполняет следующие операции:
\begin{itemize}
    \item вычисляет значение криптографической хэш-функции $h(m) \in [0,p-2]$ от своего открытого сообщения $m$;
    \item выбирает случайное число $r: ~ \gcd(r, p-1)=1$;
    \item используя закрытый ключ, вычисляет:
        \[ \begin{array}{l}
            a = g^r \mod p, \\
            b = \frac{h(m) - xa}{r} \mod (p-1); \\
        \end{array} \]
    \item создаёт подпись в виде двух чисел
        \[ S(m) = (a, b) \]
        и посылает сообщение с подписью $(m, S(m))$.
\end{itemize}

Получив сообщение, $B$ осуществляет проверку подписи, выполняя следующие операции:
\begin{itemize}
    \item по известному сообщению $m$ вычисляет значение хэш-функции $h(m)$;
    \item вычисляет:
        \[ \begin{array}{l}
            f_1 = g^{h(m)} \mod p, \\
            f_2 = y^a a^b \mod p; \\
        \end{array} \]
    \item сравнивает значения $f_1$ и $f_2$; если
        \[ f_1 = f_2, \]
        то подпись подлинная, в противном случае -- фальсифицированная (или случайно испорченная).
\end{itemize}

Покажем, что проверка подписи корректна. По малой теореме Ферма получаем
\[ \begin{array}{ll}
    f_1 & = g^{h(m)} \mod p = \\
    & \\
    & = g^{h(m) \mod (p-1)} \mod p; \\
\end{array} \] \[ \begin{array}{ll}
    f_2 & = y^a a^b \mod p = \\
    & = \underbrace{\left( g^x \right)^a}_{y^a} \cdot
        \underbrace{\left( g^r \mod p \right)^{\frac{h(m) - xa}{r} \mod (p-1)}}_{a^b} \mod p = \\
    & \\
    & = g^{xa \mod (p-1)} ~\cdot~ g^{h(m) - xa \mod (p-1)} \mod p = \\
    & = g^{h(m) \mod (p-1)} \mod p = \\
    & = f_1.
\end{array} \]

\example Создание и валидация электронной подписи в криптосистеме Эль-Гамаля.

\begin{enumerate}
    \item Генерирование параметров.
        \begin{enumerate}
            \item Выберем $p=41$.
            \item Выберем генератор $g=6$ в группе $\Z_{41}^*$.
            \item Выберем случайное $x = 19 \in [1, p-1]$.%, ~ \gcd(x, p-1) = 1$.
            \item Вычислим
                \[ \begin{array}{ll}
                    y & = g^x \mod p = \\
                    & = 6^{19} \mod 41 = \\
                    & = 6^{1 + 2 + 4 \cdot 0 + 8 \cdot 0 + 16} \mod 41 = \\
                    & = 6 \cdot (-5) \cdot (-16)^0 \cdot 10^0 \cdot 18 \mod 41 = \\
                    & = -7 \mod 41. \\
                \end{array} \]
            \item Открытый и закрытый ключи:
                \[ \PK = (p:41, g:6, y:-7), ~ \SK = (p:41, g:6, x:19). \]
        \end{enumerate}
    \item Подписание.
        \begin{enumerate}
            \item От сообщения $m$ вычисляется хэш $h = H(m)$. Пусть хэш $h  = 3 \in [0, p-2]$.
            \item Выберем случайное $r = 9 \in [1, p-2]$: \\
                $\gcd(r=9, p-1 = 40) = 1$.
            \item Вычислим
                \[ \begin{array}{ll}
                    a & = g^r \mod p = \\
                      & = 6^9 \mod 41 = 19 \mod 41, \\
                    b & = \frac{h - xa}{r} \mod (p-1) = \\
                      & = (3 - 19 \cdot 19) \cdot 9^{-1} \mod 40 = \\
                      & = 2 \cdot 9 \mod 40 = 18 \mod 40. \\
                \end{array} \]
            \item Подпись
                \[ s = (a:19, b:18). \]
        \end{enumerate}
    \item Проверка подписи.
        \begin{enumerate}
            \item Для полученного сообщения находится хэш $h = H(m) = 3$. Пусть полученная подпись к нему имеет вид
                \[ s = (a:19, b:18). \]
            \item Вычислим
                \[ \begin{array}{ll}
                    f_1 & = g^h \mod p = \\
                        & = 6^3 \mod 41 = 11 \mod 41, \\
                    f_2 & = y^a a^b \mod p = \\
                        & = (-7)^{19} \cdot 19^{18} \mod 41 = 11 \mod 41. \\
                \end{array} \]
            \item Проверим равенство $f_1$ и $f_2$. Подпись верна, так как
                \[ f_1 = f_2 = 11. \]
        \end{enumerate}
\end{enumerate}

\exampleend
\index{электронная подпись!Эль-Гамаля|)}

\subsection{Криптостойкость}

Пусть дано уравнение $y=g^{x} \mod p$, требуется определить $x$ в интервале $0 < x < p-1$. Задача называется \emph{дискретным логарифмированием}\index{задача!дискретного логарифмирования}.

Рассмотрим возможные способы нахождения неизвестного числа $x$. Начнём с перебора различных значений $x$ из интервала $0<x<p-1$ и проверки равенства $y=g^{x} \mod p$. Число попыток в среднем равно $\frac{p}{2}$, при $p=2^{1024}$ это число равно $2^{1023}$, что на практике неосуществимо.

\index{алгоритм!Гельфонда~---~Шенкса|(}Другой подход предложен советским математиком Гельфондом в 1962 году безотносительно к криптографии. Он состоит в следующем.
Вычислим $S=\left\lceil\sqrt{p-1}\right\rceil $, где скобки означают наименьшее целое, которое не меньше $\sqrt{p-1} $.

Представим искомое число $x$ в следующем виде:
\begin{equation}
    x=x_{1} S+x_{2},
    \label{S}
\end{equation}

где $x_{1}$ и $x_{2}$ -- целые неотрицательные числа,
    \[ x_{1} \leq S-1, ~ x_{2} \leq S-1. \]

Такое представление является однозначным.

Вычислим и занесём в таблицу следующие $S$ чисел:
    \[ g^{0} \mod p, ~~ g^{1} \mod p, ~~ g^{2} \mod p, ~~ \dots, ~~ g^{S-1} \mod p. \]
Вычислим $g^{-S} \mod p$ и также занесём в таблицу.

\begin{center} \begin{tabular}{|l|c|c|c|c|c|c|}
    \hline
    $\lambda $ & 0 & 1 & 2 & \dots & $S-1$ & $-S$ \\
    \hline
    $g^{\lambda} \mod p$ & $g^{0}$ & $g^{1}$ & $g^{2}$ & \dots & $g^{S-1}$ & $g^{-S}$ \\
    \hline
\end{tabular} \end{center}

Для решения уравнения~\ref{S} используем перебор значений $x_{1}$.
\begin{enumerate}
    \item Предположим, что $x_{1} = 0$. Тогда $x = x_{2}$. Если число $y = g^{x_{2}} \mod p$ содержится в таблице, то находим его и выдаём результат: $x=x_{2} $. Задача решена. В противном случае переходим к пункту 2.
    \item Предположим, что $x_{1} =1$. Тогда $x=S+x_{2} $ и $y=g^{S+x_{2}} \mod p$. Вычисляем $yg^{-S} \mod p=g^{x_{2}} \mod p$. Задача сведена к предыдущей: если $g^{x_{2} } \mod p$ содержится в таблице, то в таблице находим число $x_{2} $ и выдаём результат $x$: $x=S+x_{2} $.
    \item Предположим, что $x_{1} =2$. Тогда $x=2S+x_{2} $ и $y=g^{2S+x_{2} } \mod p$. Если число $yg^{-2S} \mod p=g^{x_{2} } \mod p$ содержится в таблице, то находим число $x_{2}$ и выдаём результат: $x = 2S + x_{2}$.
     \item Пробегая все возможные значения, доберёмся в худшем случае до $x_{1} =S-1$. Тогда $x=(S-1)S+x_{2} $ и $y = g^{(S-1)S+x_{2} } \mod p$. Если число $yg^{-(S-1)S} \mod p=g^{x_{2}} \mod p$ содержится в таблице, то находим его и выдаём результат: $x=(S-1)S+x_{2}$.
\end{enumerate}

Легко убедиться в том, что с помощью построенной таблицы мы проверили все возможные значения $x$. Максимальное число умножений равно $2S \approx 2\sqrt{p-1} =2\times 2^{512} $, что для практики очень велико. Тем самым проблему достаточной криптостойкости этой системы можно было бы считать решённой. Однако это неверно, так как числа $p-1$ являются составными. Если $p-1$ можно разложить на маленькие множители, то криптоаналитик может применить процедуру, подобную процедуре Гельфонда, по взаимно простым делителям $p-1$ и найти секрет. Пусть $p-1=st$. Тогда элемент $g^s$ образует подгруппу порядка $t$ и наоборот. Теперь, решая уравнение $y^s=(g^s)^a\mod p$, находим вычет $x=a\mod t$. Поступая аналогично, находим $x=b\mod s$ и по Китайской теореме об остатках находим $x$.

Несколько позже подобный метод ускоренного решения уравнения~\ref{S} был предложен американским математиком Шенксом (\langen{Daniel Shanks}, \cite{Shanks:1971}). Оба алгоритма в литературе можно встретить под названиями: алгоритм Гельфонда, алгоритм Шенкса или алгоритм Гельфонда~---~Шенкса.

Пусть $k = \lceil \log_2 p \rceil$ -- битовая длина числа $p$. Алгоритм Гельфонда имеет экспоненциальную сложность (число двоичных операций):
    \[ O\left(\sqrt{p}\right) = O\left(e^{\frac{1}{2} \frac{1}{\log_2 e} k}\right). \]
\index{алгоритм!Гельфонда~---~Шенкса|)}

Наилучшие из известных алгоритмов решения задачи дискретного логарифмирования имеют экспоненциальную сложность порядка
    \[ O\left(e^{\sqrt{k}}\right). \]

\index{криптосистема!Эль-Гамаля|)}