el-gamal.tex

\section{Системы Эль-Гамаля}
\selectlanguage{russian}

\subsection[Шифрование]{Система шифрования Эль-Гамаля}

Эта система шифрования с открытым ключом опубликована Эль-Гамалем (El-Gamal) в 1985 году. Рассмотрим принципы ее построения.

Пусть имеется мультипликативная группа $\Z_p^* = \{1, 2, \dots, p-1\}$, где $p$ -- большое простое число, содержащее 1024 двоичных разряда. Существует целое число $g$, называемое примитивным элементом, который порождает все ненулевые числа группы, причем $1 < g < p-1$.

    \[ g\mod p, ~~ g^2\mod p, ~~ \dots, ~~ g^{p-1} = 1\mod p \]

Выберем целое число $x$ в интервале $1 \le x \le p-1$. Вычислим
    \[ y = g^x \mod p. \]
Известно, что в конечном поле функция $y(x)$ -- вычислительно однонаправленная.

Задачей \textbf{дискретного логарифмирования}\index{задача!дискретного логарифмирования} в мультипликативной группе $\Gr$ называется нахождение $x$ по заданным элементам $a,b \in \Gr, ~ b = a^x$. Для групп большого размера $2^{150}$--$2^{1000}$ при выборе элемента $a$ генератором группы или подгруппы большого порядка дискретный логарифм известными алгоритмами не вычислим за доступное время, все известные алгоритмы -- неполиномиальные.

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

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


\subsubsection{Пример системы}

\begin{enumerate}
    \item Генерирование параметров.
        \begin{enumerate}
            \item Выберем $p=41$.
            \item Группа $\Z_p^*$ циклическая, найдем генератор (примитивный элемент). Порядок группы
                \[ |\Z_p^*| = \phi(p) = p-1 = 40. \]
                Делители 40: 2, 4, 5, 8, 10, 20. Элемент группы является примитивным, если все его степени, соответствующие делителям порядка группы, не сравнимы с 1. Из табл. \ref{tab:elgamal-generator-search} видно, что число $g = 6$ является генератором всей группы.
                \begin{table}[h!]
                    \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}
                                & 2   & 4   & 5   & 8  & 10 & 20 & 40 & \\
                        \hline
                        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 [1, 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 = (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}


\subsection[Электронная цифровая подпись]{Электронная цифровая подпись \protect\\ Эль-Гамаля}

Криптосистема Эль-Гамаля, как и криптосистема RSA,  может быть использована для создания ЭЦП.

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

Пусть $A$ имеет секретный ключ $\SK = (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} \]

\subsubsection{Пример системы}

\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 = (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}


\subsection[Криптостойкость]{Криптостойкость систем \protect\\ Эль-Гамаля}

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

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

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

Представим искомое число $x$   в следующем виде

\begin{equation}
    x=x_{1} S+x_{2},
    \label{S}
\end{equation}

где $x_{1}$ и $x_{2}$ -- целые неотрицательные числа,
    \[ x_{1} \le S-1, ~ x_{2} \le 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} был предложен Шенксом (Shanks)и Хеллманом (Hellman). В англоязычной технической литературе он получил название алгоритма Шенкcа.

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

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