rsa.tex

\section{Криптосистема RSA}\index{криптосистема!RSA|(}
\selectlanguage{russian}

\subsection{Шифрование}\index{шифр!RSA|(}

В 1978 г. Рональд Рив\'{е}ст, Ади Шамир и Леонард Адлеман (\langen{Ronald Linn Rivest, Adi Shamir, Leonard Max Adleman}, \cite{RSA:1978}) предложили алгоритм, обладающий рядом интересных для криптографии свойств. На его основе была построена первая система шифрования с открытым ключом, получившая название по первым буквам фамилий авторов -- система RSA.

Рассмотрим принцип построения криптосистемы шифрования RSA с открытым ключом.

\begin{enumerate}
    \item \textbf{Создание пары из закрытого и открытого ключей}
        \begin{enumerate}
            \item Случайно выбрать большие простые\index{число!простое} различные числа $p$ и $q$, для которых $\log_2 p \simeq \log_2 q > 1024$ бит\footnote{Случайный выбор больших простых чисел не является простой задачей. См. раздел~\ref{section-pseudo-primes-generation} в приложении.}.
            \item Вычислить произведение $n = pq$.
            \item Вычислить функцию Эйлера\index{функция!Эйлера}\footnote{См. раздел~\ref{section-group-multiplicative} в приложении.} $\varphi(n) = (p-1)(q-1)$.
            \item Выбрать случайное целое число $e \in [3, \varphi(n)-1]$, взаимно простое с $\varphi(n)$: $~ \gcd(e, \varphi(n)) = 1$.
            \item Вычислить число $d$ такое, что $d \cdot e = 1 \mod \varphi(n)$.
            \item Закрытым ключом будем называть пару чисел $n$ и $d$, открытым ключом\footnote{Некоторые авторы считают некорректным включать число $n$ в состав закрытого ключа, так как оно уже входит в открытый. Авторы настоящего пособия включают число $n$ в состав закрытого ключа, что в результате позволяет в дальнейшем использовать для расшифрования и создания электронной подписи данные \emph{только} из закрытого ключа, не прибегая к <<помощи>> данных из открытого ключа.} -- пару чисел $n$ и $e$.
        \end{enumerate}

    \item \textbf{Шифрование с использованием открытого ключа}
        \begin{enumerate}
            \item Сообщение представляют целым числом $m \in [1, n-1]$.
            \item Шифртекст вычисляется как
                \[ c = m^e \mod n. \]
                Шифртекст -- также целое число из диапазона $[1, n-1]$.
        \end{enumerate}
    \item \textbf{Расшифрование с использованием закрытого ключа}

        Владелец закрытого ключа вычисляет
                \[ m = c^d \mod n. \]
\end{enumerate}

Покажем корректность схемы шифрования RSA. В результате расшифрования шифртекста $c$ (полученного путём шифрования открытого текста $m$) легальный пользователь имеет:
\[\begin{array}{ll}
    c^{d} & = m^{ed} \mod p = \\
          & = m^{ 1 + \alpha_1 \cdot \varphi(n)} \mod p = \\
          & = m^{ 1 + \alpha_1 \cdot ( p - 1 ) ( q - 1 )} \mod p = \\
          & = m^{ 1 + \alpha_2 \cdot ( p - 1 )} \mod p = \\
          & = m \cdot m^{\alpha_2 \cdot ( p - 1 )} \mod p. \\
\end{array}\]

Если $m$ и $p$ являются взаимно простыми, то из малой теоремы Ферма\index{теорема!Ферма малая} следует, что:
	\[m^{\left( p - 1 \right)} = 1 \mod p,\]
\[\begin{array}{ll}
	c^{d} & = m \cdot m^{\alpha_2 \cdot \left( p - 1 \right)} = \\
	      & = m \cdot \left( m^{\left(p - 1\right)} \right)^{\alpha_2} = \\
	      & = m \cdot 1^{\alpha_2} = \\
	      & = m \mod p.
\end{array}\]

Если же $m$ и $p$ не являются взаимно простыми, то есть $p$ является делителем $m$ (помним, что $p$ -- простое число), то $m = 0 \mod p$ и $c^{d} = 0 \mod p$.

В результате, для любых $m$ верно, что $c^{d} = m \mod p$. Аналогично доказывается, что $c^{d} = m \mod q$. Из китайской теоремы об остатках\index{теорема!китайская об остатках} (см. раздел~\ref{section-chinese-remainder-theorem} в приложении) следует:

\[\begin{cases}
	n = p \cdot q, \\
	c^{d} = m \mod p, \\
	c^{d} = m \mod q.
\end{cases} \Rightarrow\quad c^{d} = m \mod n.\]

\example Создание ключей, шифрование и расшифрование в криптосистеме RSA.

\begin{enumerate}
    \item Генерирование параметров.
        \begin{enumerate}
            \item Выберем числа $p=13, q=11, n = 143$.
            \item Вычислим $\varphi(n) = (p-1)(q-1) = 12 \cdot 10 = 120$.
            \item Выберем $e=23: ~ \gcd(e, \varphi(n))=1, ~ e \in [3, 119]$.
            \item Найдём $d = e^{-1} \bmod \varphi(n) = 23^{-1} \bmod 120 = 47$.
            \item Открытый и закрытый ключи:
                \[ \PK = (e:23, n:143), ~ \SK = (d:47, n:143). \]
        \end{enumerate}
    \item Шифрование.
        \begin{enumerate}
            \item Пусть сообщение $m = 22 \in [1, n-1]$.
            \item Вычислим шифртекст:
                \[ c = m^e \bmod n = 22^{23} \bmod 143 = 55 \bmod 143. \]
        \end{enumerate}
    \item Расшифрование.
        \begin{enumerate}
            \item Полученный шифртекст $c = 55$.
            \item Вычислим открытый текст:
                \[ m = c^d \bmod n = 55^{47} \bmod 143 = 22 \bmod 143. \]
        \end{enumerate}
\end{enumerate}
\exampleend

\index{шифр!RSA|)}

\subsection{Электронная подпись}\index{электронная подпись!RSA|(}

Предположим, что пользователь $A$ не шифрует свои сообщения, но хочет посылать их в виде открытых текстов с подписью. Для этого надо создать электронную подпись (ЭП). Это можно сделать, используя систему RSA. При этом должны быть выполнены следующие требования:
\begin{itemize}
    \item вычисление подписи от сообщения является вычислительно лёгкой задачей;
    \item фальсификация подписи при неизвестном закрытом ключе -- вычислительно трудная задача;
    \item подпись должна быть проверяемой открытым ключом.
\end{itemize}

Создание параметров ЭП RSA производится так же, как и для схемы шифрования RSA. Пусть $A$ имеет закрытый ключ $\SK = (n, 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$ получает открытый текст
        \[ s^{e} \mod n = \left( m^{d} \mod n \right)^{e} \mod n = m. \]
    \item $B$ cравнивает полученное значение с первой частью сообщения. При полном совпадении подпись принимается.
\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}


\example Создание и проверка электронной подписи в криптосистеме RSA.

\begin{enumerate}
    \item Генерирование параметров.
        \begin{enumerate}
            \item Выберем $p=13, q=17, n = 221$.
            \item Вычислим $\varphi(n) = (p-1)(q-1) = 12 \cdot 16 = 192$.
            \item Выберем $e=25: ~ \gcd(e = 25, \varphi(n) = 192) = 1, \\
                e \in [3, \varphi(n) - 1 = 191]$.
            \item Найдём $d = e^{-1} \mod \varphi(n) = 25^{-1} \mod 192 = 169$.
            \item Открытый и закрытый ключи:
                \[ \PK = (e:25, n:221), ~ \SK = (d:169, n:221). \]
        \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}

\index{электронная подпись!RSA|)}

\subsection{Семантическая безопасность шифров}

\emph{Семантически безопасной}\index{криптосистема!семантически-безопасная} называется криптосистема, для которой вычислительно невозможно извлечь любую информацию из шифртекстов, кроме длины шифртекста. Алгоритм RSA не является семантически безопасным. Одинаковые сообщения шифруются одинаково, и, следовательно, применима атака на различение сообщений.

Кроме того, сообщения длиной менее $\frac{k}{3}$ бит, зашифрованные на малой экспоненте $e=3$, \emph{дешифруются} нелегальным пользователем извлечением обычного кубического корня.

В приложениях RSA используется только в сочетании с рандомизацией\index{рандомизация шифрования}. В стандарте PKCS\#1 RSA Laboratories описана схема рандомизации перед шифрованием OAEP-RSA (\langen{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^{16}+1 = [10000000000000001]_2.
    \end{array}
\]

%Время шифрования или проверки подписи для малых экспонент становится $O(k^2)$ вместо $O(k^3)$, то есть в сотни раз быстрее для 1000-битовых чисел.


\subsubsection{Ускорение~шифрования по~китайской~теореме об~остатках}

Возводя $m$ в степень $e$ отдельно по $\Mod p$ и $\Mod q$ и применяя китайскую теорему об остатках\index{теорема!китайская об остатках} (\langen{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} \bmod p) + m_q p (p^{-1} \bmod 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} \bmod p), ~ pq) = q. \]
\exampleend


\subsubsection{Длина ключей}

В 2005 году было разложено 663-битовое число вида RSA. Время разложения в эквиваленте составило 75 лет вычислений одного ПК. Самые быстрые алгоритмы факторизации -- субэкспоненциальные\index{задача!факторизации}. Минимальная рекомендуемая длина модуля $n$ = 1024 бита, но лучше использовать 2048 или 4096 бит.

В июле 2012 года NIST опубликовала отчёт~\cite{NIST:SP800:57}, который включал в себя таблицу сравнения надёжности ключей с разной длиной для криптосистем, относящихся к разным классам. Таблица была составлена согласно как известным на тот момент атакам на классы криптосистем, так и на конкретные шифры (см.~\ref{table:aesrsakeycompare}).
	
\begin{table}[h]
\begin{tabular}{|c|c|c|c|}
\hline
\multicolumn{1}{|p{0.2\linewidth}|}{бит безопасности} & \multicolumn{1}{|p{0.2\linewidth}|}{пример симметричного шифра} & \multicolumn{1}{|p{0.2\linewidth}|}{$\log_2 n$ для RSA\tablefootnote{Сравнимая по предоставляемой безопасности битовая длина произведения $n$ простых чисел $p$ и $q$ для криптосистем, основанных на сложности задачи факторизации числа $n$ на простые множители $p$ и $q$, в том числе RSA.}} & \multicolumn{1}{|p{0.2\linewidth}|}{$\log_2 \| \group{G} \|$ для эллиптических кривых\tablefootnote{Сравнимая по предоставляемой безопасности битовая длина количества элементов $\|\group{G}\|$ в выбранной циклической подгруппе $\group{G}$ группы точек $\group{E}$ эллиптической кривой для криптосистем, основанных на сложности дискретного логарифма в группах точек эллиптических кривых над конечными полями (см.~\ref{section-elliptic-curve-cryptosystems}).}} \\
\hline
80	& 	2TDEA	&	1024	&	160--223	\\
112	& 	3TDEA	&	2048	&	224--255	\\
128	& 	AES-128	&	3072	&	256--383	\\
192	& 	AES-192	&	7680	&	384--511	\\
256	& 	AES-256	&	15360	&	512+	\\
\hline
\end{tabular}
\caption{Сравнимые длины ключей блочных симметричных шифров и ключевых параметров асимметричных шифров~\cite{NIST:SP800:57}}\label{table:aesrsakeycompare}
\end{table}

В приложении~\ref{section-modular-arithmetic} показано, что битовая сложность (количество битовых операций) вычисления произвольной степени $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$ раза.

\index{криптосистема!RSA|)}