forked from vlsergey/infosec
-
Notifications
You must be signed in to change notification settings - Fork 0
/
rsa.tex
250 lines (200 loc) · 21 KB
/
rsa.tex
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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
\section{Системы RSA}
\selectlanguage{russian}
\subsection[Шифрование]{Система шифрования RSA}
В 1978 г. Рональд Рив\'{е}ст, Ади Шамир и Леонард Адлеман (R. Rivest, A. Shamir, L. Adleman) предложили алгоритм, обладающий рядом интересных для криптографии свойств. На его основе была построена первая система шифрования с открытым ключом, получившая название по первым буквам фамилий авторов -- система RSA.
Рассмотрим принцип построения криптосистемы шифрования RSA с открытым ключом.
\begin{enumerate}
\item \textbf{Создание пары из секретного и открытого ключей.}
\begin{enumerate}
\item Случайно выбрать большие простые различные числа $p,q$, для которых $\log_2 p \simeq \log_2 q > 512$ бит.
\item Вычислить произведение $n = pq$.
\item Вычислить функцию Эйлера $\phi(n) = (p-1)(q-1)$.
\item Выбрать случайное целое число $e \in [2, \phi(n)-1]$ взаимно простое с $\phi(n)$: $~ \gcd(e, \phi(n)) = 1$. Свойство проверяют с помощью алгоритма Евклида.
\item Вычислить число $d$, такое, что $d e= 1 \mod \phi(n)$. Для вычисления используется расширенный алгоритм Евклида.
\item Секретный ключ -- $\SK$, открытый ключ -- $\PK$
\[ \SK = (d), ~ \PK = (n, e). \]
\end{enumerate}
Генерация модуля $n = pq$ RSA системы является трудной задачей. Действительно, количество нечетных целых длиной точно 500 бит равно $2^{(500-2)}$. Среди них имеется примерно
$(2^{500})/500 - (2^{499})/499 \approx (2^{500})/1000$ простых 500-разрядных чисел. Вероятность случайного выбора простого числа составляет примерно $1/250 $.
Поиск случайных больших простых чисел $p,q$ состоит в генерации случайного нечетного целого числа и проверке его по критериям (псевдо)простоты. Самый распространенный критерий -- вероятностный тест Миллера--Рабина\index{тест!Миллера-Рабина}. Все вероятностные тесты либо \emph{точно} определяют, что данное число составное, либо что оно \emph{возможно} простое. При $t$-кратной проверке тестом Миллера--Рабина со всеми положительными ответами <<возможно простое>> существует вероятность ошибки $P < \left( \frac{1}{4} \right)^t$, т.е. ненулевая вероятность того, что число окажется, на самом деле, составным. Существуют и многие другие детерминированные и вероятностные тесты на простоту числа.
Криптостойкость RSA системы определяется сложностью разложения на сомножители целого $n$-разрядного числа и отсутствием "лишних" делителей.
\item \textbf{Шифрование на открытом ключе $\PK$.}
\begin{enumerate}
\item Сообщение представляют целым числом $m \in [1, n-1]$.
\item Шифротекст вычисляется как
\[ c = m^e \mod n. \]
Шифротекст -- тоже целое число из диапазона $[1, n-1]$.
\end{enumerate}
\item \textbf{Расшифрование на секретном ключе $\SK$.}
\begin{enumerate}
\item Владелец секретного ключа вычисляет
\[ m = c^d \mod n. \]
\item Покажем верность расшифрования. Пусть
\[ ed = 1 + a \phi(n). \]
Если $m$ и $n$ взаимно простые, то по теореме Эйлера (по модулю $n$):
\[ c^d = m ^{ed} = m^1 m^{a\phi(n)} = m \cdot 1^a = m \mod n. \]
В общем случае $m$ и $n$ могут иметь общие делители, но расшифрование тоже оказывается верным. Пусть $m = 0 \mod p$. По китайской теореме об остатках:
\[
m = c^d \mod n ~\Leftrightarrow~
\left\{ \begin{array}{l}
m = c^d \mod p, \\
m = c^d \mod q. \\
\end{array} \right..
\]
Подставляя $c=m^e$, получаем тождество
\[ \left\{ \begin{array}{l}
m^{ed} = 0 = m \mod p, \\
m^{ed} = m \left( m^{q-1} \right)^{a(p-1)} = m \cdot 1^{a(p-1)} = m \mod q. \\
\end{array} \right. \]
Следовательно, $m^{ed} = m \mod pq$.
\end{enumerate}
\end{enumerate}
Что касается вычислительной сложности других операций, то применение алгоритма Евклида для проверки, являются ли число $e$ взаимно простым с числами $p-1, q-1$, а также вычисление обратного элемента $d$, считается легкой задачей (задачей с квадратичной сложностью, не более).
Возведение числа в заданную степень $d$ выполняется с помощью последовательного \emph{возведения в квадрат и перемножения}. Пусть
\[ d = d_0 + d_1 2^1 + d_2 2^2 + \ldots + d_{k-1} 2^{k-1} \]
двоичное представление с коэффициентами $d_{i} \in \{ 0, 1 \}$. Степень $c^d$ вычисляется рекуррентным образом:
\[ c^d =((... (((c^ {d_{k-1}})^2 (c^{d_{k-2}}))^2)\dots(c^{d_2}))^2 (c^{d_1}))^2 (c^{d_0}).\]
% \[ c^d = c^ {d_0} \cdot (c^2)^{d_1} \cdot (c^{2^2})^{d_2} \dots (c^{2^{k-1}})^{d_{k-1}}, \]
Всего выполняется $k-1$ операций возведения в квадрат и не более $k-1$ умножений, что считается легкой задачей.
\subsubsection{Пример схемы}
%\example
%Схема шифрования RSA.
\begin{enumerate}
\item Генерирование параметров.
\begin{enumerate}
\item Выберем числа $p=13, q=11, n = 143$.
\item Вычислим $\phi(n) = (p-1)(q-1) = 12 \cdot 10 = 120$.
\item Выберем $e=23: ~ \gcd(e, \phi(n))=1, ~ e \in [2, 119]$.
\item Найдем $d = e^{-1} \mod \phi(n) = 23^{-1} \mod 120 = 47$.
\item Открытый и секретные ключи:
\[ \PK = (e:23, n:143), ~ \SK = (d:47). \]
\end{enumerate}
\item Шифрование.
\begin{enumerate}
\item Пусть сообщение $m = 22 \in [1, n-1]$.
\item Вычислим шифротекст
\[ c = m^e = 22^{23} = 55 \mod 143. \]
\end{enumerate}
\item Расшифрование.
\begin{enumerate}
\item Полученный шифротекст $c = 55$.
\item Вычислим открытый текст
\[ m = c^d = 55^{47} = 22 \mod 143. \]
\end{enumerate}
\end{enumerate}
%Рассмотрим ее основные положения на примере криптосистемы с открытым ключом.
%Приведем общую схему алгоритма RSA.
%$C_i=M_{i}^{E_k}(mod N_j)$
%$N_j=P_{j}Q_{j}$
%$M_i=C_{i}^{D_k}(mod N_j)$
%$E_k\neq D_k$
%Вычислить $E_k$ из $D_k$ при длине блока сообщения $L_{блока} > L_{дополнения}$ можно только с экспоненциальной сложностью. $E_k D_K=1(mod \varphi(N_j))$
%Данное сравнение не дает единственного решения. Решение данного сравнения и можно свести к следующему уравнению:
%$ax+by=1$
%$E_k D_k=k \varphi(N_j)+1$
%$1\leq E_k D_k <\varphi(N_j)$
%$\varphi(N_j)(-k)+ E_k D_k=1$
%Стандарт ISO X.509 определяет требования по реализации алгоритма RSA, в частности, требования к общесистемным параметрам и ключам, методы распространения сертификатов ключей и ключевых параметров, а также порядок ввода их в действие и многое другое.
\subsection[Электронная цифровая подпись]{Электронная цифровая подпись \protect\\ RSA}
Предположим, что пользователь $A$ сообщения не шифрует, но хочет посылать свои сообщения в виде открытых текстов с подписью. Для этого надо создать электронную цифровую подпись (ЭЦП). Это можно сделать, используя систему RSA. При этом должны быть выполнены следующие требования:
\begin{itemize}
\item вычисление подписи от сообщения является вычислительно легкой задачей;
\item фальсификация подписи при неизвестном секретном ключе -- вычислительно трудная задача;
\item подпись должна быть проверяемой открытым ключом.
\end{itemize}
Создание параметров ЭЦП RSA производится так же, как и для схемы шифрования RSA. Пусть $A$ имеет секретный ключ $\SK = (d)$, а получатель (проверяющий) $B$ -- открытый ключ $\PK = (e,n)$ пользователя $A$.
\begin{enumerate}
\item $A$ вычисляет подпись сообщения $m \in [1,n-1]$ как
\[ s = m^{d} \mod n \]
на своем секретном ключе $\SK$.
\item $A$ посылает $B$ сообщение в виде $(m, s)$, где $m$ -- открытый текст, $s$ -- подпись.
\item $B$ принимает сообщение $(m, s)$, возводит $s$ в степень $e$ по модулю $n$ ($e, n$ -- часть открытого ключа). В результате вычислений $B$ получает открытый текст
\[ \left( m^{d} \mod n \right)^{e} \mod n = m. \]
\item Сравнивает полученное значение с первой частью сообщения. При полном совпадении подпись принимается.
\end{enumerate}
Недостаток этой системы создания ЭЦП состоит в том, что подпись $m^{d} \mod n$ имеет большую длину, равную длине открытого сообщения $m$.
Для уменьшения длины подписи применяется другой вариант процедуры: вместо сообщения $m$ отправитель подписывает $h(m)$, где $h(x)$ -- известная криптографическая хэш-функция. Модифицированная процедура состоит в следующем.
\begin{enumerate}
\item $A$ посылает $B$ сообщение в виде $(m, s)$, где $m$ -- открытый текст,
\[ s = h(m)^d \mod n \]
подпись.
\item $B$ принимает сообщение $(m, s)$, вычисляет хэш $h(m)$ и возводит подпись в степень
\[ h_1 = s^e \mod n. \]
\item $B$ сравнивает значения $h(m)$ и $h_1$. При равенстве
\[ h(m) = h_1 \]
подпись считается подлинной, при неравенстве -- фальсифицированной.
\end{enumerate}
\subsubsection{Пример схемы}
\begin{enumerate}
\item Генерирование параметров.
\begin{enumerate}
\item Выберем $p=13, q=17, n = 221$.
\item Вычислим $\phi(n) = (p-1)(q-1) = 12 \cdot 16 = 192$.
\item Выберем $e=25: ~ \gcd(e = 25, \phi(n) = 192) = 1, \\
e \in [2, \phi(n) - 1 = 191]$.
\item Найдем $d = e^{-1} \mod \phi(n) = 25^{-1} \mod 192 = 169$.
\item Открытый и секретные ключи:
\[ \PK = (e:25, n:221), ~ \SK = (d:169). \]
\end{enumerate}
\item Подписание.
\begin{enumerate}
\item Пусть хэш сообщения $h(m) = 12 \in [1, n-1]$.
\item Вычислим ЭЦП
\[ s = h^d = 12^{169} = 90 \mod 221. \]
\end{enumerate}
\item Проверка подписи.
\begin{enumerate}
\item Пусть хэш полученного сообщения $h(m) = 12$, полученная подпись $s = 90$.
\item Выполним проверку
\[ h_1 = s^e = 90^{25} = 12 \mod 221, ~~ h_1 = h, \]
подпись верна.
\end{enumerate}
\end{enumerate}
\subsection[Рандомизация шифрования и ЭЦП]{Рандомизация шифрования и \protect\\ подписания RSA}
\textbf{Семантически безопасной}\index{криптосистема!семантически-безопасная} называется криптосистема, для которой вычислительно невозможно извлечь любую информацию из шифротекстов, кроме длины шифротекста. Алгоритм RSA не является семантически безопасным. Одинаковые сообщения шифруются одинаково и, следовательно, применима атака на различение сообщений.
Кроме того, сообщения длиной менее $\frac{k}{3}$ бит, зашифрованные на малой экспоненте $e=3$, \emph{дешифруются} нелегальным пользователем извлечением обычного кубического корня.
В приложениях RSA используется только в сочетании с рандомизацией\index{рандомизация шифрования}. В стандарте PKCS\#1 RSA Laboratories описана схема рандомизации перед шифрованием OAEP-RSA (Optimal Asymmetric Encryption Padding). Примерная схема:
\begin{enumerate}
\item Выбирается случайное $r$.
\item Для открытого текста $m$ вычисляется
\[ x = m \oplus H_1(r), ~ y = r \oplus H_2(x), \]
где $H_1$ и $H_2$ -- криптографические хэш-функции.
\item Сообщение $M = x \| y$ далее шифруется RSA.
\end{enumerate}
Восстановление $m$ из $M$ при расшифровании:
\[ r = y \oplus H_2(x), ~ m = x \oplus H_1(r). \]
В модификации OAEP+ $x$ вычисляется как
\[ x = (m \oplus H_1(r)) \| H_3(m \| r). \]
В описанной выше схеме ЭЦП под $m$ понимается хэш открытого текста, вместо шифрования выполняется подписание, вместо расшифрования -- проверка подписи.
\subsection{Выбор параметров и оптимизация}
\subsubsection{Выбор экспоненты $e$}
В случайно выбранной экспоненте $e$ c битовой длиной $k = \lceil \log_2 e \rceil$ половина бит в среднем равна 0, половина -- 1. При возведении в степень $m^e \mod n$ по методу <<возводи в квадрат и перемножай>> получится $k-1$ возведений в квадрат и, в среднем,
$\frac{1}{2}(k-1)$ умножений.
Если выбрать $e$, содержащим малое число единиц в двоичной записи то число умножений уменьшится до числа единиц в $e$.
Часто экспонента $e$ выбирается \emph{малым} \emph{простым} числом и/или содержащим малое число единиц в битовой записи, для ускорения шифрования или проверки подписи, например:
\[
\begin{array}{l}
3 = [11]_2, \\
17 = 2^4+1 = [10001]_2, \\
257 = 2^8+1 = [100000001]_2, \\
65537 = 2^{17}+1 = [10000000000000001]_2.
\end{array}
\]
%Время шифрования или проверки подписи для малых экспонент становится $O(k^2)$ вместо $O(k^3)$, то есть в сотни раз быстрее для 1000-битовых чисел.
\subsubsection[Ускорение шифрования]{Ускорение шифрования по китайской \protect\\ теореме об остатках}
Возводя $m$ в степень $e$ отдельно по $\mod p$ и $\mod q$ и применяя китайскую теорему об остатках (Chinese remainder theorem, CRT), можно шифрование выполнить быстрее.
Однако ускорение шифрования в криптосистеме RSA через CRT может привести к уязвимостям в некоторых применениях, например, в смарт-картах.
\example
Пусть $c = m^e \mod n$ передается на расшифрование на смарт-карту, где вычисляется
\[ \begin{array}{c}
m_p = c^d \mod p, \\
m_q = c^d \mod q, \\
m = m_p q (q^{-1} \mod p) + m_q p (p^{-1} \mod q) \mod n. \\
\end{array} \]
Криптоаналитик внешним воздействием может вызвать сбой во время вычисления $m_p$ (или $m_q$), в результате получится $m_p'$ и $m'$ вместо $m$. Зная $m_p'$ и $m'$ криптоаналитик находит разложение числа $n$ на множители $p,q$:
\[ \gcd(m' - m, ~ n) = \gcd( (m_p' - m) q (q^{-1} \mod p), ~ pq) = q. \]
\exampleend
\subsubsection{Длина ключей}
В 2005 году было разложено 663-битовое число вида RSA. Время разложения в эквиваленте составило 75 лет вычислений одного ПК. Самые быстрые алгоритмы факторизации -- субэкспоненциальные\index{задача!факторизации}. Минимальная рекомендуемая длина модуля $n$ -- 1024 бит, но лучше использовать 2048 или 4096 бит.
В приложении показано, что битовая сложность (количество битовых операций) вычисления произвольной степени $a^b \mod n$ является кубической $O(k^3)$, а возведения в квадрат $a^2 \mod n$ и умножения $a b \mod n$ -- квадратичными $O(k^2)$, где $k$ -- битовая длина чисел $a,b,n$.
%Увеличение длины модуля $n$ в 2 раза увеличивает время возведения в степень в $2^3$ раз для большой экспоненты $e$, а для маленькой экспоненты -- в $2^2$ раза.