Добавлен пример во второй лабе

2 files changed, 73 insertions, 0 deletions

diff --git a/reports/lab2/lab2.pdf b/reports/lab2/lab2.pdf
index 6fc4cbb..6ed67e7 100644
--- a/reports/lab2/lab2.pdf
+++ b/reports/lab2/lab2.pdf
diff --git a/reports/lab2/lab2.tex b/reports/lab2/lab2.tex
index 9a9c82d..4fd3542 100644
--- a/reports/lab2/lab2.tex
+++ b/reports/lab2/lab2.tex
@@ -18,6 +18,8 @@
 \floatname{algorithm}{Алгоритм}
 
 \newcommand{\Z}{\mathbb{Z}}
+\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
+\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
 
 \newtheorem{theorem}{Теорема}
 \newtheorem*{theorem*}{Теорема}
@@ -134,4 +136,75 @@ $Z^*_{\varphi(n)}$ и он равен $k$. Тогда, по определени
 $\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}