forked from vlsergey/infosec
-
Notifications
You must be signed in to change notification settings - Fork 0
/
pki_key_length.tex
91 lines (83 loc) · 6.48 KB
/
pki_key_length.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
\section{Длины ключей}
\selectlanguage{russian}
В таблице~\ref{tab:recommended-key-lengths} приведены битовые длины ключей для криптосистем.
%Традиционные рекомендации основаны на аппроксимации существующих алгоритмов для взлома на 10-30 лет вперед.
\begin{table}[!ht]
\centering
\caption{Минимальные длины ключей в битах по стандартам России и США\label{tab:recommended-key-lengths}}
\resizebox{\textwidth}{!}{ \begin{tabular}{|l|c|c|c|c|}
\hline
& \multirow{2}{*}{\parbox{1.5cm}{\medskip \centering Блочные шифры, $K$}} & \multicolumn{3}{|c|}{Схема ЭП} \\
\cline{3-5}
& & \parbox{1.5cm}{\centering RSA\index{криптосистема!RSA}, $n$} & \parbox{2.4cm}{\centering Эллипт. кривые, порядок точки} & \parbox{3.5cm}{\centering Эль-Гамаль\index{криптосистема!Эль-Гамаля} $\operatorname{mod} p$: модуль / порядок (под)группы} \\
\hline \hline
\multicolumn{5}{|c|}{Взломано} \\
\hline
Биты & 56 & 768 & 109 & 503 \\
Конкурс & \textsc{DesChal} & RSA-768 & ECC2K-108 & \\
Год & 1997 & 2009 & 2000 & \\
\hline \hline
\multicolumn{5}{|c|}{Стандарт России} \\
\hline
Биты & 256 & & 255 & \\
ГОСТ & 28147—89 & --- & 34.10-2001 & --- \\
Год & 1989 & & 2001 & \\
% \hline
% \multicolumn{2}{|l|}{\parbox{4cm}{Россия: нелицензируемая деятельность}} & \multicolumn{4}{c|}{40} \\
\hline \hline
\multicolumn{5}{|c|}{Стандарт США} \\
\hline
Биты & 128-256 & 1024-3072 & 151-480 & 1024-3072/160-256 \\
FIPS \No & 197 & draft 186-3 & draft 186-3 & draft 186-3 \\
Год & 2001 & 2006 & 2006 & 2006 \\
% \hline
% \multicolumn{2}{|l|}{\parbox{4cm}{США: экспортные ограничения до 2001 г.}} & 56 & 512 & 112 & 512/112 \\
% \hline \hline
% \multicolumn{2}{|l|}{Традиционные} & 80 & 1024 & 160 & 1024/160 \\
% \cline{3-6}
% \multicolumn{2}{|l|}{рекомендации} & 112 & 2048 & 224 & 2048/224 \\
% \hline
% \multicolumn{2}{|l|}{\parbox{4cm}{Рекомендация Lenstra, Verheul для 2010 г.}} & 78 & 1369 & 146-160 & 1369/138 \\
\hline
\end{tabular} }
\end{table}
%}\end{center}
\subsection*{Скорость вычисления ЭП}
Сравним производительность схем ЭП, чтобы продемонстрировать преимущества ЭП вида Эль-Гамаля\index{криптосистема!Эль-Гамаля} перед RSA\index{криптосистема!RSA} для больших ключей. В приложении показано, что в модульной арифметике по модулю числа $n$ с битовой длиной $k \simeq \log_2 n$ операции имеют битовую сложность:
\[ \begin{array}{lcl}
a^b \mod n & - & O(k^3), \\
ab \mod n, ~ a^{-1} \mod n & - & O(k^2), \\
a+b \mod n & - & O(k). \\
\end{array} \]
Так как все описанные схемы ЭП используют возведение в степень по модулю, то битовая сложность -- $O(k^3)$. Оценки количества целочисленных $t$-разрядных умножений при вычислении ЭП имеют вид:
\begin{enumerate}
\item RSA\index{электронная подпись!RSA}:
\[ (2 \log_2 n) \cdot \left( \frac{\log_2 n}{t} \right)^2; \]
\item DSA\index{электронная подпись!DSA} (\langen{Digital Signature Algorithm}, стандарт США~\cite{FIPS-PUB-186-4}), вычисляемая по принципу Эль-Гамаля\index{криптосистема!Эль-Гамаля} по модулю $p$ и с порядком циклической подгруппы $q$:
\[ (2 \log_2 q) \cdot \left( \frac{\log_2 p}{t} \right)^2; \]
\item ГОСТ Р 34.10-2001\index{электронная подпись!ГОСТ Р 34.10-2001} (стандарт России~\cite{GOST-2001}) и ECDSA\index{электронная подпись!ECDSA} (\langen{Elliptic Curve Digital Signature Algorithm}, стандарт США~\cite{FIPS-PUB-186-4}), вычисляемые по принципу Эль-Гамаля\index{криптосистема!Эль-Гамаля} в группе точек эллиптической кривой по модулю $p$:
\[ (2 \log_2 p) \cdot 4 \cdot \left( \frac{\log_2 p}{t} \right)^2. \]
\end{enumerate}
В таблице~\ref{tab:signature-rate} приведены оценки скорости вычисления ЭП (оценки числа умножений 64-битовых слов).
\begin{table}[!ht]
\centering
\caption{Оценочное число 64-битовых умножений для вычисления ЭП\label{tab:signature-rate}}
\begin{tabular}{|c|l|c|}
\hline
ЭП & Оценочное число 64-битовых умножений \\
\hline \hline
RSA\index{электронная подпись!RSA} 1024 & $(2 \cdot 1024) \cdot \left( \frac{1024}{64} \right)^2 \approx$ 500 000 \\
RSA\index{электронная подпись!RSA} 2048 & 4 000 000 \\
RSA\index{электронная подпись!RSA} 3072 & 14 000 000 \\
RSA\index{электронная подпись!RSA} 4096 & 34 000 000 \\
\hline \hline
DSA\index{электронная подпись!DSA} 1024/160 & $(2 \cdot 160) \cdot \left( \frac{1024}{64} \right)^2 \approx$ 82 000 \\
DSA\index{электронная подпись!DSA} 3072/256 & 1 200 000 \\
\hline \hline
ECDSA\index{электронная подпись!ECDSA} 160 & $(2 \cdot 160) \cdot 4 \cdot \left( \frac{160}{64} \right)^2 \approx$ 8 000 \\
ECDSA\index{электронная подпись!ECDSA} 512 & 260 000 \\
\hline \hline
ГОСТ Р 34.10-2001\index{электронная подпись!ГОСТ Р 34.10-2001} & $(2 \cdot 256) \cdot 4 \cdot \left( \frac{256}{64} \right)^2 \approx$ 33 000 \\
\hline
\end{tabular}
\end{table}