RSA (криптосистема)

__NUMBEREDHEADINGS__



Основные утверждения

Самая известная и наиболее используемая криптосистема. В РФ используется практически везде, например, в банкоматах, терминалах оплаты, банковских системах.

Зашифрование

$~C=EE_{(n,e)}(M)=M^{e}(mod~n),M\in [0,n-1]$

Также система используется, как правило, для шифрования ключей. Трудоемкость возведения в степень $~T=O(\log _{n})$

Расшифрование

$~M=D_{(n,d)}(C)=C^{d}(mod~n)$

Трудоемкость = $~O(\log _{n})$, то есть полиномиальна, однако достаточно сложная.

Теорема Утверждение
Если $~e,d$ связаны соотношением: $~e,d:e\cdot d\equiv 1(mod~\varphi (n))$$\color{Maroon}(*)$, где $\varphi(n))$ - Функция Эйлера то $~\forall M,(M,n)=1$ выполняется соотношение: $~ D_{(n,d)} = (E_{(n,e)} (M))\equiv M(mod~n)$ (в этом случае преобразования корректны)
Доказательство
Если выполняется ${\color {Maroon}(*)}$: $~ e\cdot d = 1 + \varphi (n) \cdot t, t \in \mathbb{Z} \Rightarrow \left( M^e(mod~n)\right)^d(mod~n) = M^{ed}(mod~n) = M^{1+ P(n)t} = M \cdot (M^{\varphi(n)})^t (mod~n) = M(mod~n) \triangleleft$

Пример Замечание
Если выбрать произвольный ключ зашифрования е, то для нахождение d надо решить $~e\cdot x\equiv 1(mod~\varphi (n))$, то есть сравнение первой степени $~ ax = b(mod~n)$; оно имеет решение $~\Leftrightarrow$НОД$~(e,\varphi (n))|1\to (e,\varphi (n))=1$

RSA - блочная экспоненциальная симметричная система. Стойкость: основа - секретные ключи и открытый текст. В ГОСТ ключи зашифрования совпадают с ключами расшифрования, в RSA они связаны.

Криптосистемы типа RSA. Схема Полига - Хеллмана

Модуль $~m=p$ - большое простое число.

$~C=M^{e}(mod~p)$

$~M=C^{d}(mod~p)$

$~ e\cdot d \equiv 1(mod~(p-1) = \varphi(p))$

$e$ - открытый ключ зашифрования, $d$ - закрытый ключ зашифрования.

Эта схема была известна до появления RSA.

Предложили взять $~n=p\cdot q$ - модуль как произведение двух больших простых чисел.Законный пользователь знает $~p,q$ и расшифровывает все сообщения, которые к нему приходят. Найти $~n\to \varphi (n)$ никто не может быстрее, чем просто раскладывая на множители. Если бы факторизовали на $~p,q$:

$~n\to p,q\to \varphi (n)=\varphi (p)\varphi (q)=(p-1)(q-1)$

$~e\cdot x\equiv 1(mod~(p-1)(q-1))\to d\Rightarrow$ расшифрование всего. Если есть только $~n$ - сложная задача.

$~{\mathcal {Z}}$ (злоумышленник) знает $~C,e,n$, хочет извлечь корень $~{\sqrt[{e}]{C}}(mod~n)$ - пока не найдено способа быстрее. чем разложение на простые множители $~\Rightarrow$ основа криптосистемы открытого шифрования.

Пример Замечание
Однонаправленная функция с секретом: $~y=x^{e}(mod~p\cdot q)$. При знании дополнительной информации, т.е. p и q, можно найти прообраз за полиномиальное время.

Задача факторизации имеет субэкспоненциальную сложность.

$~(M,n)=1$ - будет ли это что-то менять? Вероятность найти не взаимно простые с модулем точки: $~P={\frac {n-\varphi (n)}{n}}={\frac {pq-(p-1)(q-1)}{pq}}={\frac {p+q-1}{pq}}<{\frac {1}{p}}+{\frac {1}{q}}$. Работает с очень большими простыми числами (порядка 1000 бит) $~\Rightarrow P$ очень маленькая.

Рассмотрим корректность $~C=M^{e}(mod~n),M=C^{d}(mod~n),ed\equiv 1(mod~n)$. Это схема открытого шифрования; теперь рассмотрим схему цифровой подписи.

Пример Замечание
Можно использовать такое соотношение: $~e\cdot d\equiv 1(mod~\lambda (n))$, $~\lambda (n)=exp(\mathbb {Z} _{n}^{*})$ - функция Кармайкла

Для этой функции справедливы теоремы Кармайкла: $~(a,n)=1,a\equiv 1(mod~n)$

$~ed=1+\lambda (n)t$

$~\lambda (pq)={\frac {\varphi (pq)}{HOD(p-1,q-1)}}$

Рассмотрим реализацию. Сначала разделим $~d=k(p-1)+r=j(q-1)+s$

В итоге уменьшился размер, уменьшилась степень возведения.

$~b=C^{d}=[(C^{q-1})^{j}C^{s}](mod~q)=(C(mod~q))^{d(mod(q-1))}$

Теперь надо решить такое сравнение:

$~u,0<u<p,u\cdot q\equiv 1(mod~p)$

Все это - следствия Китайской теоремы об остатках.

$~ M = \left\{ \begin{matrix} ((a-b(mod~p))u)(mod~p)^{q+b}, if ~a \geq b(mod~p)\\ ((a+p-b(mod~p))u)(mod~p)^{q+b}, if~ a < b(mod~p) \end{matrix}\right.$

$~ a = (\underbrace {C^{p-1}}_{\equiv 1})^kC^r (mod~p)= (C(mod~p))^{d(mod~p-1)}$ (так как $~r=d(mod~p-1)$)

Таким образом, сложность меньше, чем $~T=O(\log n)$

Атаки на схему RSA

Атака при малой энтропии открытого текста

$~C=m^{d}(mod~n)$

$~\{M_{1},\ldots ,M_{m}\}-$ небольшое множество ОТ(например, тексты платежей).

Противник имеет: $~C,e,n,\{M_{1},\ldots ,M_{m}\}$

Считаем $~M_{i}^{e}(mod~n)\equiv C~?~\Rightarrow$ находим М.

Значит, энтропию надо повышать. Для этого существуют различные способы, например, схема OAEP-RSA(optimal Asymmetric Encryption Padding).

Преобразование $~OAEP^{G,H}(M,r)=[M\oplus G(r)||r\oplus H(M\oplus G(r))],r-$случайный вектор.

Точно также с ЦП - перед подписью надо добавить случайный вектор. Параметры: $~(n,e,d,G,H,k_{0},k_{1})$. Генерация ЦП: $~SignPSS(H,d,r):r\in \{0,1\}^{k_{0}},W=H(H||r)$

$~r^{*}=G_{1}(W)\oplus r$

$~y=(0||W||r^{*}||G_{2}(W))$ - то, что будет подписывать.

$~u=y^{d}(mod~n)$

Генерация простых чисел

$~\left({\frac {p+q}{2}}\right)^{2}-n=\left({\frac {p-q}{2}}\right)^{2}$ - проверяем, выполняется ли. Если $~|p-q|<2^{56}$, то можно опробовать правую часть, прибавить к ней n и проверить, является ли квадратом. Поэтому требуется, чтобы $~|p-q|>2^{128}$

Факторизация

Раскладывает $~n\to p,q$. Самая естественная атака, позволяет полностью заменить законного получателя. Табличная (ЕС2000):

Decimals	Date	Algorythm	MIPS, years
RSA-110	1992	QS	75
RSA-129	1994	QS	5000
RSA-130	1996	NFS	1000
RSA-140	1999	NFS	2000
RSA-155	1999	NFS	5000

QS - Quadratic Sieve(Квадратичное решето)

NFS - Number Field Sieve

Формула, полученная из таких таблиц(год, в котором будет разложено число из D знаков(десятичных)):

$~y=13,24\cdot D^{1/3}+1928,6$

$~D=231~(768~bits)=2010$

$~D=309~(1024~bits)=2018$

Субэкспоненциальная оценка:

$~T=exp(1,9018+o(1))(\log n)^{1/3}(\log \log n)^{2/3},$ где n - число, которое факторизуется.

$~T_{RSA}\leq T_{fact}$

Теорема Утверждение
$~T_{\varphi (n)}=T_{n\to p,q}$
Доказательство
$~\Leftarrow$ очевидно (если умеем факторизовать, то и $~\varphi (n)$ сразу вычислим) $~\Rightarrow p^{2}-(n-\varphi (n)+1)p+n=0$ $~x^{2}-(n-\varphi (n)+1)x+n=0$ $~\varphi (n)=(p-1)(q-1)=(p-1)({\frac {n}{p}}-1)=n-{\frac {n}{p}}-p+1$ Итого, зная $~\varphi (n)$ находим $~p,n\triangleleft$.

Лемма «Утверждение»
$~T_{d}=T_{n\to p,q}$

Бесключевое чтение

Дано: $~n,e,C=M^{e}(mod~n)$

$~C^{e^{j}}(mod~n)\equiv C$

$~(\underbrace {C^{e^{j-1}}(mod~n)} _{M})^{e}(mod~n)\equiv C$

$~C^{e\Phi (e)}(mod~n)=C~?$

Хотели получить многочлен для нахождения открытого текста.

Атака по времени (Timing Attack)

Если знаем, сколько вычисляется функция, можно предположить, много там 1 или мало.

Дискретное логарифмирование (Discrete Logarithm Attack)

$~M=C^{d}(mod~n),d=\log _{c}M(mod~n)$

Атака Винера (Wiener Attack)

Лемма «Утверждение»
$~{\frac {1}{b}}$ - несократимая дробь: $~|\alpha -{\frac {b}{a}}|\leq {\frac {1}{2b^{2}}}$, то $~{\frac {a}{b}}-$ Одна из подходящих дробей для разложения $~\alpha$ в непрерывную дробь

Теорема Утверждение
Пусть $~n=pq,q<p<2q,d<{\frac {1}{3}}n^{\frac {1}{4}}\to RSA~is~insecure$
Доказательство
$~ed\equiv 1(mod~\varphi (n));\exists k:ed-k\varphi =1(def.)\Rightarrow |{\frac {e}{\varphi }}-{\frac {k}{d}}|={\frac {1}{d}}{\varphi }$ $~(p-1)(q-1)=\varphi \approx n=pq\to |n-\varphi |=|p+q-1|<3{\sqrt {n}}~(!)$ $~{\frac {e}{n}}\sim {\frac {k}{d}}$ $~|{\frac {e}{n}}-{\frac {k}{d}}|=|{\frac {ed-nk}{nd}}|=|{\frac {ed-k\varphi -nk+k\varphi }{nd}}|=|{\frac {1-k(n-\varphi )}{nd}}|\leq {\frac {3k}{d{\sqrt {n}}}}<{\frac {3d}{d{\sqrt {n}}}}\leq {\frac {1}{d{\sqrt[{4}]{n}}}}<{\frac {1}{2d^{2}}}$ Итого, $~|{\frac {e}{n}}-{\frac {k}{d}}|<{\frac {1}{2d^{2}}}$

Атака Боне и Дюрфи (Boneh, Durfee Attack)

$~d<n^{1-{\frac {1}{\sqrt {2}}}}=n^{0,192}\to RSA~is~insecure$

подняли границу по сравнением с Винером.

Малые значения открытой экспоненты

Если е мало, то также легко извлекается корень. На практике используют $~e=2^{16}+1~~(SSL)$

$~p,q\to (2^{16}+1)x\equiv 1(mod~\varphi (n))$

Атака Бляйхенбахера (Bleichebacher Attack)

$~M=(02||2||0||\underbrace {M} _{informative~~part})$

$~M^{e}(mod~n)C\to C\to M=(02||*||0||*)$

$~CS^{e}\equiv M^{e}S^{e}=(MS)^{e}(mod~n)$

Схема с общим модулем

Циркулярная связь:

$~\Phi _{1}(n,e_{1})\rightarrow$Ц$~ \leftarrow \Phi_2(n,e_2)$

Используется несколько раз, поскольку найти хорошие $~p,~q$ трудно.

НО: $~HOD(e_{1},e_{2})=1,re_{1}+se_{2}=1,$ можно найти $~r,~s$ с помощью расширенного алгоритма Евклида $~\Rightarrow M'=M^{re_{1}+se_{2}}=(C_{1})^{r}(C_{2})^{s}(mod~n)$

Метод DFA (Differential Fault Analysis)

Возник в 1997 году. Впервые был применен А. Шамиром (А. Shamir) против DES, затем применялся против ЦП RSA.

Дано: $M\,\!$ - открытый текст, $Q\,\!$ - цифровая подпись.

${\begin{cases}Q=Q_{p}\mod p\\Q=Q_{q}\mod q\end{cases}}\Rightarrow \,\!$ ищем $Q\,\!$ (по Китайской теореме об остатках).

Проверка цифровой подписи заключается в проверке выполнения равенства $\ Q^{e}\equiv M{\pmod {n}}\,\!$.

Пусть устройство делает ошибку, вычисляет не $Q_{p},\,\!$ а ${\tilde {Q_{p}}},\,\!$ и при этом $q\,\!$ одно и то же. Тогда:

${\tilde {Q^{e}}}\mod q\equiv M,\,\!$ так как $Q_{q}\,\!$ вычислено корректно. Следовательно: $q|({\tilde {Q^{e}}}-M).\,\!$

Однако: ${\tilde {Q^{e}}}\mod p\not \equiv M,\,\!$ а так как $n=p\cdot q\not {|}({\tilde {Q^{e}}}-M),\ {\tilde {Q^{e}}}\not \equiv M{\pmod {n}},\!$ то можно вычислить НОД$({\tilde {Q^{e}}}-M,\ n)=q,\ \ n=p\cdot q\,\!$

Таким образом, получен секретный параметр $\Rightarrow \,\!$ можно подписываться вместо законного пользователя.

Требования к выбору параметров схемы RSA

1. $l(p)=l(q)=l(n)/2-\,\!$ схемы с одинаковыми длинами называются сбалансированными;
2. $|p-q|\geqslant 2^{128};\,\!$
3. Все числа: $\tau _{p}|(p-1),\ \tau _{q}|(q-1),\ s_{p}|(p+1),\ s_{q}|(q+1)\,\!$ - должны иметь простые делители большой длины (~256 бит на сегодняшний день); если указанные величины не имеют простых делителей, то их можно относительно легко факторизовать.
4. Чтобы бесключевое чтение не привело к успеху, надо выбрать: $ord\ e=\,\!$НОК$[p-1,q-1]\rightarrow \infty ,\,\!$ где $e-\,\!$ мультипликативный порядок. Данное условие выполняется, если:$\ t_{p}|(\tau _{q}-1),\ t_{q}|(\tau _{q}-1),\,\!$ т.е. имеют простые делители, так, что:$l(t_{p}\cdot t_{q})\geqslant 128\,\!$ бит, а также ${\begin{cases}e^{(\tau _{p}-1)/t_{p}}\neq 1{\pmod {\tau _{p}}}\\e^{(\tau _{q}-1)/t_{q}}\neq 1{\pmod {\tau _{q}}}\end{cases}}\,\!$
5. Ограничение на $d>n^{0.292}\,\!$ (против атаки Винера и атаки Боне и Дюрфи).

Применение схемы RSA

Подпись вслепую (Blind Signature)

Схема RSA хороша своей многогранностью. Например, она применяется в схеме "Подпись вслепую".

$M\rightarrow H(M)=h,\ \ Sign_{sk}(h)=Q\,\!$

Определить по $h\,\!$ исходный текст нельзя, но если подписать $h\,\!$, то можно потом проверить, кому и когда подписывался $h\,\!$.

Подпись вслепую состоит из нескольких этапов:

1. Initializaion - подписывающий говорит каким видом подписи он будет подписывать документы;
2. Requesting - подготовка запроса и запрос подписи - запрашивающий заменяет документ $M:\ {\tilde {M}}=B(M,k)\ (blinding\ factor)\,\!$ не зная $k\,\!$ по $M'\,\!$ восстановить $M\,\!$ невозможно;
3. Signing - ${\tilde {M}}\,\!$ передается на подпись и подписывается;
4. Extracting - выделяем из полученной информации подпись.

${\tilde {S}}=Sign_{sk}({\tilde {M}})\,\!$

$S=U({\tilde {S}},k)\,\!$

Схема на базе RSA построена следующим образом:

1. $RSA:\ n=p\cdot q,\ e\,\!$
2. $A:\ k\in _{R}{\overline {1,n}},\ {\tilde {M}}=B(M,k)=M\cdot k^{e}{\pmod {n}}\,\!$
3. $B\cdot {\tilde {S}}={\tilde {M}}^{d}{\pmod {n}}\equiv (M\cdot k^{e})^{d}{\pmod {n}}\,\!$
4. $A:\ S={\frac {\tilde {M^{d}}}{k}}{\pmod {n}}\equiv frac{(M\cdot k^{e})^{d}}{k}\equiv M^{d}\cdot k^{ed-1}\equiv M^{d}\,\!$

$k^{ed}\equiv k{\pmod {n}}\,\!$

$k^{ed-1}\equiv 1\mod n\,\!$

Для того, чтобы это работало, необходимо $(k,n)=1\,\!$

Cистема тайного электронного голосования (e-Voting)

Требования к системе голосования:

1. Только имеющий права голоса может голосовать;
2. Голосовать можно не более одного раза;
3. Никто не может определить, кто конкретно за кого голосовал;
4. Никто не может подменить чей-либо выбор;
5. Проверка (ее сложно организовать);
6. Кто голосовал.

Протокол

1. Генерируется большое случайной число, добавляются туда "за", "против". Запечатываем его в конверт, хешируем документы, отправляем в избирательную комиссию.
2. Избирательная комиссия проверяет подписи, подписывает вслепую.
3. Получаем конверт, распечатываем его, смотрим все "за" и "против", подсчитываем голоса.
4. Публикуем список "За" - "Против".

Протокол электронных платежей

Но есть проблемы.

1. Проблема повторной траты (с одним чеком прийти к двум продавцам) - решается так: при оплате один раз анонимность плательщика сохраняется, при повторной оплате анонимность уже пропадает.
2. Можно поставить любую сумму, ведь банк подписывает вслепую. Решение: Cut-and-Choose-Technique