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

\begin{document}
\maketitle

\begin{definition*}
  Функция Эйлера $\varphi (n)$ --- мультипликативная арифметическая функция,
  значение которой равно количеству натуральных чисел, меньших $n$ и взаимно
  простых с ним.
\end{definition*}

\begin{theorem}
  \label{thm:euler-mult}
  Для любых взаимно простых чисел $m$ и $n$:
  \begin{equation*}
    \varphi(mn) = \varphi(m) \varphi(n)
  \end{equation*}
\end{theorem}

Для простого $p$ значение функции Эйлера задаётся явной формулой: $\varphi(p)
= p - 1$, которая следует из определения. Таким образом, исходя из теоремы
\ref{thm:euler-mult}, функция Эйлера от числа $n = pq$, где $p, q$ --- простые
числа, равна $\varphi(n) = \varphi(p) \varphi(q) = (p - 1) \cdot (q - 1)$.

Рассмотрим алгоритм генерации ключей криптосистемы RSA:
\begin{algorithm}[H]
  \caption{Генерация ключей криптосистемы RSA}\label{alg:generate}
  \begin{enumerate}
    \item
      Выбираются два различных случайных простых числа $p$ и $q$ заданного
      размера;
    \item
      Вычисляется их произведение $n = p \cdot q$, которое называется
      \emph{модулем};
    \item
      Вычисляется значение функции Эйлера от числа $n$:
      $$\varphi(n) = (p - 1) \cdot (q - 1);$$
    \item
      Выбирается целое число $e$ (\emph{открытая экспонента}), удовлетворяющее
      $1 < e < \varphi(n)$, взаимно простое со значением функции $\varphi(n)$;
    \item
      Вычисляется число $d$ (\emph{секретная экспонента}), мультипликативно
      обратное к числу $e$ по модулю $\varphi(n)$, то есть число,
      удовлетворяющее сравнению:
      \begin{equation}
        d \cdot e \equiv 1 \pmod{\varphi(n)};
        \label{eq:d-calc}
      \end{equation}
    \item Пара $(e, n)$ публикуется в качестве открытого ключа RSA;
    \item Пара $(d, n)$ играет роль закрытого ключа RSA.
  \end{enumerate}
\end{algorithm}

\begin{algorithm}[H]
  \caption{Зашифрование сообщения криптосистемой RSA}\label{alg:encrypt}
  \begin{enumerate}
    \item Взять открытый ключ $(e, n)$;
    \item Взять открытый текст $m : m \in \Z_n, \gcd(m, n) = 1$;
    \item
      Зашифровать сообщение с использованием открытого ключа:
      $$c = E(m) = m^e \pmod{n}$$
  \end{enumerate}
\end{algorithm}

\begin{algorithm}[H]
  \caption{Расшифрование сообщения криптосистемой RSA}\label{alg:decrypt}
  \begin{enumerate}
    \item Принять зашифрованное сообщение $c$;
    \item Взять закрытый ключ $(d, n)$;
    \item
      Применить закрытый ключ для расшифрования сообщения:
      $$m = D(c) = c^d \pmod{n}$$
  \end{enumerate}
\end{algorithm}

\begin{definition}
  Порядок элемента в теории групп --- наименьшее положительное целое $m$, такое
  что $m$-кратное групповое умножение данного элемента $g \in G$ на себя даёт
  нейтральный элемент:
  $$\underbrace{g g \dots g}_m = g^m = 1$$
\end{definition}

Предположим, что мы знаем порядок открытой экспоненты $e$ в группе
$Z^*_{\varphi(n)}$ и он равен $k$. Тогда, по определению, справедливо сравнение
\begin{equation}
  e^k \equiv 1 \pmod{\varphi(n)}
  \label{eq:order1}
\end{equation}

Выражение \ref{eq:order1} также можно записать как
\begin{equation}
  e^{k - 1} \cdot e \equiv 1 \pmod{\varphi(n)}
  \label{eq:order2}
\end{equation}

Из выражений \ref{eq:order2} и \ref{eq:d-calc} можно заметить, что секретная
экспонента $d = e^{k - 1}$. Таким образом, зная порядок элемента $e$ в группе
$\Z^*_{\varphi(n)}$, можно вычислить секретную экспоненту $d$, и с её
помощью расшифровать сообщение $m^e \pmod{n})$ по алгоритму \ref{alg:decrypt}.

\begin{example}
  Пусть $p, q = 7, 13$. Получаем $n = 91, \varphi(n) = (p - 1) \cdot (q - 1)
  = 6 \cdot 12 = 72$. Выберем такое $e$, что $1 < e < \varphi(n),\, \gcd(e,
  \varphi(n)) = 1$. Пусть $e = 5$. Вычислим секретную экспоненту $d$ с помощью
  расширенного алгоритма Евклида.

  Для нахождения $d$ можно воспользоваться следующим свойством расширенного
  алгоритма Евклида: в случае, когда $\gcd(a, b) = 1$, то в выражении $ax + by
  = \gcd(a, b)$, $x$ является модульным обратным числа $a$ по модулю $b$, а $y$
  --- модульным обратным числа $b$ по модулю $a$.

  Таким образом, $d = x$ в выражении $ex + \varphi(n)y = \gcd(e, \varphi(n)) =
  1$. Вычислим это значение: $5x + 72y = \gcd(5, 72) = 1$.

  В первую очередь проведём вычисление НОД, несмотря на то, что он нам уже
  известен (число $e$ изначально подбиралось таким образом, что $\gcd(e,
  \varphi(n)) = 1$). Это нужно из-за того, что для вычисления $x$ и $y$
  необходимы промежуточные значения $a$ и $b$.
  \begin{align*}
    a_1 = 5&, b_1 = 72 \\
    a_2 = 72 \mod 5 = 2&, b_2 = 5 \\
    a_3 = 5 \mod 2 = 1&, b_3 = 2 \\
    a_4 = 2 \mod 1 = 0&, b_4 = 1
  \end{align*}

  На основе этих значений вычислим решения уравнения:
  \begin{align*}
    %1
    x_1 = 0&,\, y_1 = 1 \\
    %2
    x_2 = y_1 - \floor*{\frac{b}{a}} \cdot x_1 = 
          1 - \floor*{\frac{2}{1}} \cdot 0 = 1
    &,\, y_2 = x_1 = 0 \\
    %3
    x_3 = 0 - \floor*{\frac{5}{2}} \cdot 1 = -2&,\, y_3 = x_2 = 1 \\
    %4
    x_4 = 1 - \floor*{\frac{72}{5}} \cdot (-2) = 29&,\, y_4 = x_3 = -2 \\
  \end{align*}

  Получаем, что секретная экспонента $d = x_4 = 29$. Проверим это значение.
  Зашифруем сообщение $m = 23$ ($0 \leq m \leq n - 1,\, \gcd(m, n) = 1$):
  \begin{equation*}
    c = m^e \pmod{n} = 23^5 \pmod{91} = 4
  \end{equation*}

  Полученное значение попробуем расшифровать:
  \begin{equation*}
    c^d \pmod{n} = 4^29 \pmod{91} = 23
  \end{equation*}

  Так как получилось исходное сообщение можно сделать вывод, что экспонента $d$
  вычислена верно.

  Попробуем вычислить порядок $e$ в группе $\Z^*_{\varphi(n)}$. Для этого будем
  умножать $e$ на само себя до тех пор, пока не получится единица. Количество
  таких умножений и есть порядок элемента $e$.
  \begin{align*}
    e^1 \pmod{72} &= e \pmod{72} = 5 \pmod{72} = 5 \\
    e^2 \pmod{72} &= e^1 \cdot e \pmod{72} = 5 \cdot 5 \pmod {72} = 25 \pmod{72} = 25 \\
    e^3 \pmod{72} &= e^2 \cdot e \pmod{72} = 25 \cdot 5 \pmod {72} = 125 \pmod{72} = 53 \\
    e^4 \pmod{72} &= e^3 \cdot e \pmod{72} = 53 \cdot 5 \pmod {72} = 265 \pmod{72} = 49 \\
    e^5 \pmod{72} &= e^4 \cdot e \pmod{72} = 49 \cdot 5 \pmod {72} = 245 \pmod{72} = 29 \\
    e^6 \pmod{72} &= e^5 \cdot e \pmod{72} = 29 \cdot 5 \pmod {72} = 145 \pmod{72} = 1 \\
  \end{align*}

  Получаем, что порядок $e = 5$ в группе $\Z^*_{72}$ равен $k = 6$. При
  вычислении значения $k$ можно заметить, что $e^{k - 1} = e^5 = 29 = d$. Таким
  образом, зная порядок элемента $e$ можно легко вычислить секретную экспоненту
  $d$.
\end{example}

\end{document}