9.2. Криптосистема Эль-Гамаля

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

Пусть имеется мультипликативная группа ${{\mathbb{Z}}}_p^* = \{1, 2, \dots, p-1\}$, где $p$ – большое простое число

, содержащее не менее 1024 двоичных разрядов. В группе ${{\mathbb{Z}}}_p^*$ существует $\varphi( \varphi( p ) ) = \varphi( p - 1 )$ элементов, которые порождают все элементы группы. Такие элементы называются генераторами

.

Выберем один из таких генераторов $g$ и целое число $x$ в интервале $1 < x < p-1$. Вычислим:

Хотя элементы $x$ и $y$ группы ${{\mathbb{Z}}}_p^*$ задают друг друга однозначно, найти $y$, зная $x$, просто, а вот эффективный алгоритм для получения $x$ по заданному $y$ неизвестен. Говорят, что задача вычисления дискретного логарифма

является вычислительно сложной. На сложности вычисления дискретного логарифма для больших простых $p$ основывается криптосистема Эль-Гамаля.

9.2.1. Шифрование

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

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

Шифрование корректно, так как

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

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

1. Генерация параметров.
   1. Выберем $p=41$.
   2. Группа ${{\mathbb{Z}}}_p^*$ циклическая, найдём генератор (примитивный элемент). Порядок группы
      $$ |{{\mathbb{Z}}}_p^*| = \varphi(p) = p-1 = 40. $$
      Делители 40: 1, 2, 4, 5, 8, 10, 20. Элемент группы является примитивным, если все его степени, соответствующие делителям порядка группы, не сравнимы с 1. Из таблицы [tab:elgamal-generator-search] видно, что число $g = 6$ является генератором всей группы.

      Элемент	Степени							Порядок элемента
      	$2$	$5$	$8$	$10$	$20$	$40$
      0pt2.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$

   3. Выберем случайное $x = 19 \in [0, p-1]$.
   4. Вычислим
      $$ \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} $$
   5. Открытый и закрытый ключи:
      $$ {\textrm{PK}}= (p:41, g:6, y:-7), ~ {\textrm{SK}}= (p:41, g:6, x:19). $$
2. Шифрование.
   1. Пусть сообщением является число $m = 3 \in {{\mathbb{Z}}}_p^*$.
   2. Выберем случайное число $r = 25 \in (1, p-1)$.
   3. Вычислим
      $$ \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} $$
   4. Шифртекстом является пара чисел
      $$ c = (a:14, ~ b:-9). $$
3. Расшифрование.
   1. Пусть получен шифртекст
      $$ c = (a:14, ~ b:-9). $$
   2. Вычислим открытый текст как
      $$ \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} $$

9.2.2. Электронная подпись

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

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

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

Для создания подписи $S(m)$ пользователь $A$ выполняет следующие операции:

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

Получив сообщение, $B$ осуществляет проверку подписи, выполняя следующие операции:

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

Покажем, что проверка подписи корректна. По малой теореме Ферма получаем

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

1. Генерирование параметров.
   1. Выберем $p=41$.
   2. Выберем генератор $g=6$ в группе ${{\mathbb{Z}}}_{41}^*$.
   3. Выберем случайное $x = 19 \in (1, p-1)$.
   4. Вычислим
      $$ \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} $$
   5. Открытый и закрытый ключи:
      $$ {\textrm{PK}}= (p:41, g:6, y:-7), ~ {\textrm{SK}}= (p:41, g:6, x:19). $$
2. Подписание.
   1. От сообщения $m$ вычисляется хеш $h = H(m)$. Пусть хеш $h = 3 \in [0, p-2]$.
   2. Выберем случайное $r = 9 \in [1, p-2]$: $\gcd(r=9, p-1 = 40) = 1$.
   3. Вычислим
      $$ \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} $$
   4. Подпись
      $$ s = (a:19, b:18). $$
3. Проверка подписи.
   1. Для полученного сообщения находится хеш $h = H(m) = 3$. Пусть полученная подпись к нему имеет вид
      $$ s = (a:19, b:18). $$
   2. Вычислим
      $$ \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} $$
   3. Проверим равенство $f_1$ и $f_2$. Подпись верна, так как
      $$ f_1 = f_2 = 11. $$

9.2.3. Криптостойкость

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

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

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

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

где $x_{1}$ и $x_{2}$ – целые неотрицательные числа,

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

Вычислим и занесём в таблицу следующие $S$ чисел:

Вычислим $g^{-S} \mod p$ и также занесём в таблицу.

Для решения уравнения [S] используем перебор значений $x_{1}$.

1. Предположим, что $x_{1} = 0$. Тогда $x = x_{2}$. Если число $y = g^{x_{2}} \mod p$ содержится в таблице, то находим его и выдаём результат: $x=x_{2} $. Задача решена. В противном случае переходим к пункту 2.
2. Предположим, что $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} $.
3. Предположим, что $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}$.
4. Пробегая все возможные значения, доберёмся в худшем случае до $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}$.

Легко убедиться в том, что с помощью построенной таблицы мы проверили все возможные значения $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$.

Несколько позже подобный метод ускоренного решения уравнения [S] был предложен американским математиком Шенксом (англ. Daniel Shanks, [94]). Оба алгоритма в литературе можно встретить под названиями: алгоритм Гельфонда, алгоритм Шенкса или алгоритм Гельфонда — Шенкса.

Пусть $k = \lceil \log_2 p \rceil$ – битовая длина числа $p$. Алгоритм Гельфонда имеет экспоненциальную сложность (число двоичных операций):

Наилучшие из известных алгоритмов решения задачи дискретного логарифмирования имеют экспоненциальную сложность порядка