\documentclass[a4paper,oneside]{article}

\usepackage[utf8]{inputenc}
\usepackage[T2A]{fontenc}
\usepackage[english,russian]{babel}

\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{amsfonts}
\usepackage{enumitem}
\usepackage{amsthm}
\usepackage{minted}
\setminted{fontsize=\small, breaklines=true, style=emacs, linenos}
\usepackage{graphicx}
\graphicspath{ {./images/} }
\usepackage{float}
\usepackage{algorithm}
\floatname{algorithm}{Алгоритм}

\newcommand{\Z}{\mathbb{Z}}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}

\newtheorem{theorem}{Теорема}
\newtheorem*{theorem*}{Теорема}

% --- Определение --- %
\theoremstyle{definition}
\newtheorem{definition}{Определение}
\newtheorem*{definition*}{Определение}
% ------------------- %

\theoremstyle{definition}
\newtheorem*{example}{Пример}


\title{{Криптографические методы защиты информации}\\{Лабораторная работа №5}}
\author{Гущин Андрей, 431 группа, 1 подгруппа, 2 вариант}
\date{\the\year{} г.}

\begin{document}
\maketitle

\section{Схема}

Рассмотрим следующее упрощение схемы Эль-Гамаля. Пусть $p$ --- простое число,
$g$ --- порождающий элемент мультипликативной группы $Z^\cdot_p$. Эти данные
открыты.

Пользователь выбирает секретное число $1 \leq a \leq p - 1$ и открывает значение
$y = g^a \pmod{p}$.

К сообщению $m \in \{ 0, 1 \}^*$ применяется известная хэш-функция, дающая
значение $h = h(m) \in Z_p$.

Допустим, что $\gcd(h, p - 1) = 1$. Этого можно добиться, внеся необходимые
коррективы в случае невыполнения.

При генерации подписи пользователь вычисляет значение
\begin{equation}
  z = h^{-1} a \pmod{(p - 1)}
  \label{eq:zpow}
\end{equation}

В качестве подписи под документом $m$ предлагается использовать $g^z$.

Проверка правильности подписи элементарна:
\begin{equation}
  (g^z)^h = g^{h^{-1} h a} = g^a \pmod{p}
  \label{eq:check}
\end{equation}

Подпись принимается, если полученное значение совпадает с $y$.

Необходимо объяснить почему упомянутая схема неприемлема.


\section{Взлом схемы}

Будем считать схему подписи \emph{неприемлемой}, если имеется возможность
создать подпись для произвольного сообщения не имея при этом секретного ключа.

Рассмотрим выражение \ref{eq:check}. Можно заметить, что $(g^z)^h = y$. Также
можем получить 
\begin{equation*}
  \left( \left( g^z \right)^h \right)^{h^{-1}} = y^{h^{-1}}
\end{equation*}

То есть
\begin{equation*}
  g^z = y^{h^{-1}}
\end{equation*}

Но значение $y$ является частью открытого ключа, а $h^{-1}$ вычисляется из
публично известной хэш-функции для произвольного сообщения.

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


\section{Непроверяемость подписи}

Заметим, что в выражении \ref{eq:check} подразумевается, что значения $z$
и $h$ находятся в одном кольце и поэтому можно написать $z \cdot h =
h^{-1} \cdot a \cdot h = h^{-1} \cdot h \cdot a = a$.

Но, также можно заметить, что при вычислении $z$ в выражении \ref{eq:zpow}
умножаемые значения берутся по модулю $(p - 1)$. То есть, значение $z$
является элементом мультипликативной группы $Z^\cdot_{(p - 1)}$. При этом
значение $h$ является элементом группы $Z^\cdot_p$ по условию.

В общем случае мы можем сказать, что
\begin{equation*}
  z \cdot h 
  = (h^{-1} \cdot a \pmod{(p - 1)}) \cdot h
  \neq h^{-1} \cdot a \cdot h
\end{equation*}

Например, пусть $p = 31, a = 19, h = 11$. При этом $h^{-1} = 17$, где обратное
берётся в группе $Z^\cdot_p$.

\begin{align*}
  z &= 17 \cdot 19 \pmod{30} = 23 \\
  z \cdot h &= 23 \cdot 11 \pmod{31} = 5 \\
  h^{-1} \cdot a \cdot h &= 17 \cdot 19 \cdot 11 \pmod{31} = 19
\end{align*}

Получаем
\begin{equation*}
  z \cdot h = 5 \neq 19 = h^{-1} \cdot a \cdot h
\end{equation*}

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

\end{document}