forked from vlsergey/infosec
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmodular_ariphmetics.tex
139 lines (118 loc) · 9.13 KB
/
modular_ariphmetics.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
\section{Модульная арифметика}\label{section-modular-arithmetic}
\selectlanguage{russian}
\subsection{Сложность модульных операций}
Криптосистемы с открытым ключом, как правило, построены в модульной арифметике с длиной модуля от сотни до нескольких тысяч разрядов. Сложность алгоритмов оценивают как количество битовых операций в зависимости от длины. В таблице~\ref{tab:mod-binary-complexity} приведены оценки (с точностью до порядка) сложности модульных операций\index{битовая сложность} для простых (или <<школьных>>) алгоритмов вычислений. На самом деле, для реализации арифметики длинных чисел (сотни или тысячи двоичных разрядов) следует применять существенно более эффективные (более <<хитрые>>) алгоритмы вычислений, использующие, например, специальный вид быстрого преобразования Фурье и другие приёмы.
\begin{table}[!ht]
\centering
\caption{Битовая сложность операций по модулю $n$ длиной $k= \log n$ бит\label{tab:mod-binary-complexity}}
\begin{tabular}{| p{0.75\textwidth} | c |}
\hline
Операция, алгоритм & Сложность \\
\hline
1. $a \pm b \mod n$ & $O(k)$ \\
2. $a \cdot b \mod n$ & $O(k^2)$ \\
3. $\gcd(a, b)$, алгоритм Евклида & $O(k^2)$ \\
4. $(a,b) \rightarrow (x,y,d) : ax + by = d = \gcd(a,b)$, расширенный алгоритм Евклида & $O(k^2)$ \\
5. $a^{-1} \mod n$, расширенный алгоритм Евклида & $O(k^2)$ \\
6. Китайская теорема об остатках & $O(k^2)$ \\
7. $a^b \mod n$ & $O(k^3)$ \\
\hline
\end{tabular}
\end{table}
\subsection{Возведение в степень по модулю}
Рассмотрим два алгоритма возведения числа $a$ в степень $b$ по модулю $n$ (см.~\cite[9.3.1. Простые двоичные схемы]{Crandall:Pomerance:2011}). Оба этих алгоритма основываются на разложении показателя $b$ в двоичное представление:
\begin{equation}
\begin{array}{l}
b = \sum\limits_{i=1}^{k} b_i 2^i, \\
b_i \in \{0, 1\}.
\end{array}
\label{eq:power-mod-b}
\end{equation}
\subsubsection{Схема <<слева направо>>}
Алгоритм~\ref{alg:power-mod-left-to-right} сводится к вычислению следующей формулы:
\[ c = \left( \left( \left( \left( \left( 1 \cdot a^{b_k} \right)^2 \cdot a^{b_{k-1}} \right)^2 \cdot a^{b_{k-2}} \right)^2 \dots \right)^2 \cdot a^{b_2} \right)^2 \cdot a^{b_1} \mod n.\]
\begin{algorithm}[ht]
\caption{Простая двоичная схема возведения в степень типа <<слева направо>>\label{alg:power-mod-left-to-right}}
\begin{algorithmic}
\STATE $c := a$;
\FOR{ $i := k-1$ \TO $1$}
\STATE $c := c^2 \mod n$;
\IF { $\left( b_i == 1 \right)$ }
\STATE $c := c \cdot a \mod n$;
\ENDIF
\ENDFOR
\RETURN $c$;
\end{algorithmic}
\end{algorithm}
Алгоритм требует $k-1$ возведений в квадрат и $t-1$ умножений, где $t$ -- количество единиц в двоичном представлении показателя степени. Так как возведение в квадрат можно сделать примерно в два раза быстрее, чем умножение на произвольное число, то, например, в криптосистеме RSA\index{криптосистема!RSA} показатель степени стараются выбрать таким образом, чтобы в его двоичной записи было мало бит, отличных от нуля: $3_{10} = 11_{2}$ или $65537_{10} = 10000000000000001_{2}$.
\example Посчитаем с помощью простой двоичной схемы возведения в степень типа <<слева направо>> значение $175^{235} \mod 257$. Представим число $235$ в двоичном виде:
\[ 235_{10} = 11101011_{2}.\]
Полное выражение для вычисления имеет вид:
\[ c = (((((((1 \cdot a^1)^2 \cdot a^1)^2 \cdot a^1)^2 \cdot a^0)^2 \cdot a^1)^2 \cdot a^0)^2 \cdot a^1)^2 \cdot a^1 \mod 257.\]
\begin{enumerate}
\item $c := 175$;
\item $c := 175^2 \mod 257 = 42, $\\
$c := 42 \times 175 \mod 257 = 154;$
\item $c := 154^2 \mod 257 = 72, $\\
$c := 72 \times 175 \mod 257 = 7;$
\item $c := 7^2 \mod 257 = 49; $
\item $c := 49^2 \mod 257 = 88, $\\
$c := 88 \times 175 \mod 257 = 237;$
\item $c := 237^2 \mod 257 = 143; $
\item $c := 143^2 \mod 257 = 146, $\\
$c := 146 \times 175 \mod 257 = 107;$
\item $c := 107^2 \mod 257 = 141, $\\
$c := 141 \times 175 \mod 257 = 3;$
\item Ответ: 3. Потребовалось 7 возведений в квадрат и 5 умножений.
\end{enumerate}
\exampleend
Алгоритм можно обобщить на использование произвольного основания разложения степени. Например, использование основания, представляющего собой степень двойки, будет являться методом улучшения описанной выше схемы под названием <<просматривание>> (\langen{windowing}, см.~\cite[9.3.2. Улучшение схем возведение в степень]{Crandall:Pomerance:2011}). Если в качестве основания выбрать $s = 4$, то формула из примера выше для вычисления $175^{235} \mod 257$ принимает вид:
\[\begin{array}{l}
235_{10} = 3223_{4}; \\
c = \left(\left(\left( 1 \cdot 175^3 \right)^4 \cdot 175^2 \right)^4 \cdot 175^2 \right)^4 \cdot 175^3 \mod 257.
\end{array}\]
Для вычисления уже потребуется $3 \times 2 = 6$ возведений в квадрат и $3$ умножения. Но сначала потребуется вычислить значения $175^2 \mod 257$ и $175^3 \mod 257$. Для больших показателей степени $n$ выгода в количестве умножений будет очевидна.
\subsubsection{Схема <<справа налево>>}
Другим вариантом является схема типа <<справа налево>> (см. алгоритм~\ref{alg:power-mod-right-to-left}). Она также основывается на разложении показателя степени по степеням двойки~\ref{eq:power-mod-b}. Её можно представить следующей формулой:
\[\begin{array}{ll}
c & = a^b = \\
& = a^{\sum b_i 2^{i-1}} = \\
& = a^{b_1} \times a^{(b_2 2)} \times a^{(b_3 2^2)} \times a^{(b_4 2^3)} \times \dots \times a^{(b_k 2^{k-1})} = \\
& = a^{b_1} \times \left(a^2\right)^{b_2} \times \left(a^4\right)^{b_3} \times \left(a^8\right)^{b_4} \times \dots \times \left(a^{2^{k-1}}\right)^{b_k} = \\
& = \prod\limits_{i=1}^{k} \left(a^{2^{i-1}}\right)^{b_i}.
\end{array}\]
\begin{algorithm}[ht]
\caption{Простая двоичная схема возведения в степень типа <<справа налево>>\label{alg:power-mod-right-to-left}}
\begin{algorithmic}
\STATE $c := 1$;
\STATE $t := a$;
\FOR{ $i := 1$ \TO $k$ }
\IF { $\left( b_i == 1 \right)$ }
\STATE $c := c \cdot t \mod n$;
\ENDIF
\STATE $t := t^2 \mod n$;
\ENDFOR
\RETURN $c$.
\end{algorithmic}
\end{algorithm}
\example Посчитаем с помощью простой двоичной схемы возведения в степень типа <<справа налево>> значение $175^{235} \mod 257$. Представим число $235$ в двоичном виде:
\[ 235_{10} = 11101011_{2}.\]
\begin{enumerate}
\item $ c := 1 \times 175 \mod 257 = 175$, \\
$ t:= 175^2 \mod 257 = 42$;
\item $ c := 175 \times 42 \mod 257 = 154$, \\
$ t:= 42^2 \mod 257 = 222$;
\item $ t:= 222^2 \mod 257 = 197$;
\item $ c := 154 \times 197 \mod 257 = 12$, \\
$ t:= 197^2 \mod 257 = 2$;
\item $ t:= 2^2 \mod 257 = 4$;
\item $ c := 12 \times 4 \mod 257 = 48$, \\
$ t:= 4^2 \mod 257 = 16$;
\item $ c := 48 \times 16 \mod 257 = 254$, \\
$ t:= 16^2 \mod 257 = 256$;
\item $ c := 254 \times 256 \mod 257 = 3$.
\item Ответ: 3. Потребовалось 7 возведений в квадрат и 5 умножений.
\end{enumerate}
\exampleend
\input{euclidean_algorithm}
\input{chinese_remainder_theorem}