В 1978 г. Рональд Рив́ест, Ади Шамир и Леонард Адлеман (англ. Ronald Linn Rivest, Adi Shamir, Leonard Max Adleman, [89]) предложили алгоритм, обладающий рядом интересных для криптографии свойств. На его основе была построена первая система шифрования с открытым ключом, получившая название по первым буквам фамилий авторов – система RSA.
Рассмотрим принцип построения криптосистемы шифрования RSA с открытым ключом.
Создание пары из закрытого и открытого ключей
Случайно выбрать большие простые различные числа $p$ и $q$, для которых $\log_2 p \simeq \log_2 q > 1024$ битаСлучайный выбор больших простых чисел не является простой задачей. См. раздел16.6.2 в приложении..
Вычислить произведение $n = pq$.
Вычислить функцию ЭйлераСм. раздел16.3.3 в приложении.$\varphi(n) = (p-1)(q-1)$.
Выбрать случайное целое число $e \in [3, \varphi(n)-1]$, взаимно простое с $\varphi(n)$: $~ \gcd(e, \varphi(n)) = 1$.
Вычислить число $d$ такое, что $d \cdot e = 1 \mod \varphi(n)$.
Закрытым ключом будем называть пару чисел $n$ и $d$, открытым ключомНекоторые авторы считают некорректным включать число $n$ в состав закрытого ключа, так как оно уже входит в открытый. Авторы настоящего пособия включают число $n$ в состав закрытого ключа, что в результате позволяет в дальнейшем использовать для расшифрования и создания электронной подписи данные только из закрытого ключа, не прибегая к «помощи» данных из открытого ключа. – пару чисел $n$ и $e$.
Шифрование с использованием открытого ключа.
Сообщение представляют целым числом $m \in [1, n-1]$.
Шифртекст вычисляется как
$$ c = m^e \mod n. $$
Шифртекст – также целое число из диапазона $[1, n-1]$.
Расшифрование с использованием закрытого ключа.
Владелец закрытого ключа вычисляет
$$ m = c^d \mod n. $$
Покажем корректность схемы шифрования 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$ являются взаимно простыми, то из малой теоремы Ферма следует, что:
$$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$. Из китайской теоремы об остатках (см. раздел16.5.6 в приложении) следует:
$$\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.$$
Пример. Создание ключей, шифрование и расшифрование в криптосистеме RSA.
$$ c = m^e \bmod n = 22^{23} \bmod 143 = 55 \bmod 143. $$
Расшифрование.
Полученный шифртекст $c = 55$.
Вычислим открытый текст:
$$ m = c^d \bmod n = 55^{47} \bmod 143 = 22 \bmod 143. $$
9.1.2. Электронная подпись
Предположим, что пользователь $A$ не шифрует свои сообщения, но хочет посылать их в виде открытых текстов с подписью. Для этого надо создать электронную подпись (ЭП). Это можно сделать, используя систему RSA. При этом должны быть выполнены следующие требования:
вычисление подписи от сообщения является вычислительно лёгкой задачей;
фальсификация подписи при неизвестном закрытом ключе – вычислительно трудная задача;
подпись должна быть проверяемой открытым ключом.
Создание параметров ЭП RSA производится так же, как и для схемы шифрования RSA. Пусть $A$ имеет закрытый ключ ${\textrm{SK}}= (n, d)$, а получатель (проверяющий) $B$ – открытый ключ ${\textrm{PK}}= (e,n)$ пользователя $A$.
$A$ вычисляет подпись сообщения $m \in [1,n-1]$ как
$$ s = m^{d} \mod n $$
на своём закрытом ключе ${\textrm{SK}}$.
$A$ посылает $B$ сообщение в виде $(m, s)$, где $m$ – открытый текст, $s$ – подпись.
$B$ принимает сообщение $(m, s)$, возводит $s$ в степень $e$ по модулю $n$ ($e, n$ – часть открытого ключа). В результате вычислений $B$ получает открытый текст:
$$ s^{e} \mod n = \left( m^{d} \mod n \right)^{e} \mod n = m. $$
$B$ cравнивает полученное значение с первой частью сообщения. При полном совпадении подпись принимается.
Недостаток данной системы создания ЭП состоит в том, что подпись $m^{d} \mod n$ имеет большую длину, равную длине открытого сообщения $m$.
Для уменьшения длины подписи применяется другой вариант процедуры: вместо сообщения $m$ отправитель подписывает $h(m)$, где $h(x)$ – известная криптографическая хеш-функция. Модифицированная процедура состоит в следующем.
$A$ посылает $B$ сообщение в виде $(m, s)$, где $m$ – открытый текст,
$$ s = h(m)^d \mod n $$
– подпись.
$B$ принимает сообщение $(m, s)$, вычисляет хеш $h(m)$ и возводит подпись в степень:
$$ h_1 = s^e \mod n. $$
$B$ сравнивает значения $h(m)$ и $h_1$. При равенстве
$$ h(m) = h_1 $$
подпись считается подлинной, при неравенстве – фальсифицированной.
Пример. Создание и проверка электронной подписи в криптосистеме RSA.
Семантически безопасной называется криптосистема, для которой вычислительно невозможно извлечь любую информацию из шифртекстов, кроме длины шифртекста. Алгоритм RSA не является семантически безопасным. Одинаковые сообщения шифруются одинаково, и, следовательно, применима атака на различение сообщений.
Кроме того, сообщения длиной менее $\frac{k}{3}$ бит, зашифрованные на малой экспоненте $e=3$, дешифруются нелегальным пользователем извлечением обычного кубического корня.
В приложениях RSA используется только в сочетании с рандомизацией. В стандарте PKCS#1 RSA Laboratories описана схема рандомизации перед шифрованием OAEP-RSA (англ. Optimal Asymmetric Encryption Padding). Примерная схема:
Выбирается случайное $r$.
Для открытого текста $m$ вычисляется
$$ x = m \oplus H_1(r), ~ y = r \oplus H_2(x), $$
где $H_1$ и $H_2$ – криптографические хеш-функции.
Сообщение $M = x ~\|~ y$ далее шифруется RSA.
Восстановление $m$ из $M$ при расшифровании:
$$ r = y \oplus H_2(x), ~ m = x \oplus H_1(r). $$
В модификации OAEP+ $x$ вычисляется как
$$ x = \left( m \oplus H_1 \left( r \right) \right) \Vert \left. H_3 \left( m \Vert r \right) \right. .$$
В описанной выше схеме ЭП под $m$ понимается хеш открытого текста, вместо шифрования выполняется подписание, вместо расшифрования – проверка подписи.
9.1.4. Выбор параметров и оптимизация
Выбор экспоненты $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$ выбирается малымпростым числом и/или содержащим малое число единиц в битовой записи для ускорения шифрования или проверки подписи, например:
Возводя $m$ в степень $e$ отдельно по ${\operatorname{mod}}p$ и ${\operatorname{mod}}q$ и применяя китайскую теорему об остатках (англ. Chinese remainder theorem, CRT), можно быстрее выполнить шифрование.
Однако ускорение шифрования в криптосистеме RSA через CRT может породить уязвимости в отдельных реализациях, например в реализациях для смарт-карт.
Пример.
Пусть $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. $$
Длина ключей
В 2005 году было разложено 663-битовое число вида RSA. Время разложения в эквиваленте составило 75 лет вычислений одного ПК. Самые быстрые алгоритмы факторизации – субэкспоненциальные. Минимальная рекомендуемая длина модуля $n$ = 1024 бита, но лучше использовать 2048 или 4096 бит.
В июле 2012 года NIST опубликовала отчёт[88], который включал в себя таблицу сравнения надёжности ключей разных длин для криптосистем, относящихся к разным классам. Таблица была составлена согласно как известным на тот момент атакам на классы криптосистем, так и на конкретные шифры (см. таблицу[table:aesrsakeycompare]).
бит безопасности
пример симметричного шифра
$\log_2 n$ для RSAСравнимая по предоставляемой безопасности битовая длина произведения $n$ простых чисел $p$ и $q$ для криптосистем, основанных на сложности задачи разложения числа $n$ на простые множители $p$ и $q$, в том числе RSA.
$\log_2 \| {\mathbb{G}} \|$ для эллиптических кривыхСравнимая по предоставляемой безопасности битовая длина количества элементов $\|{\mathbb{G}}\|$ в выбранной циклической подгруппе ${\mathbb{G}}$ группы точек ${\mathbb{E}}$ эллиптической кривой для криптосистем, основанных на сложности дискретного логарифма в группах точек эллиптических кривых над конечными полями (см.9.3).
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+
Таблица 9.1 — Сравнимые длины ключей блочных симметричных шифров и ключевых параметров асимметричных шифров[88]
В приложении16.5 показано, что битовая сложность (количество битовых операций) вычисления произвольной степени $a^b \mod n$ является кубической $O(k^3)$, а возведения в квадрат $a^2 \mod n$ и умножения $a b \mod n$ – квадратичной $O(k^2)$, где $k$ – битовая длина чисел $a,b,n$.