1 files changed, 137 insertions, 0 deletions
diff --git a/reports/lab2/lab2.tex b/reports/lab2/lab2.tex
new file mode 100644
index 0000000..9a9c82d
--- /dev/null
+++ b/reports/lab2/lab2.tex
@@ -0,0 +1,137 @@
+\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}