rsa.tex

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

\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 Вычислить функцию Эйлера $\varphi(n) = (p-1)(q-1)$.
            \item Выбрать случайное целое число $e \in [2, \varphi(n)-1]$ взаимно простое с $\varphi(n)$: $~ \gcd(e, \varphi(n)) = 1$. Свойство проверяют с помощью алгоритма Евклида.
            \item Вычислить число $d$, такое, что  $d e= 1 \mod \varphi(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 \varphi(n). \]
                Если $m$ и $n$ взаимно простые, то по теореме Эйлера (по модулю $n$):
                \[ c^d = m ^{ed} = m^1 m^{a\varphi(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 Вычислим $\varphi(n) = (p-1)(q-1) = 12 \cdot 10 = 120$.
            \item Выберем $e=23: ~ \gcd(e, \varphi(n))=1, ~ e \in [2, 119]$.
            \item Найдем $d = e^{-1} \mod \varphi(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[Электронная подпись]{Электронная подпись 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 Вычислим $\varphi(n) = (p-1)(q-1) = 12 \cdot 16 = 192$.
            \item Выберем $e=25: ~ \gcd(e = 25, \varphi(n) = 192) = 1, \\
                e \in [2, \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). \]
        \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^{16}+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$ раза.