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

\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}.

\end{document}