1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
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}
|
