Атака Копперсмита

Атака Копперсмита описывает класс криптографических атак на открытый ключ криптосистемы RSA, основанный на методе Копперсмита. Особенность применения этого метода для атак RSA включает случаи, когда открытая экспонента мала или когда частично известен секретный ключ.

Основы RSA

Открытый ключ криптосистемы RSA это пара натуральных чисел $\left\langle N,e\right\rangle$, где $N$ это произведение двух простых чисел $p$ и $q$, а число $e$ — открытая экспонента. Целое число $e$ ($1<e<\phi (N)$, где $\phi (N)=(p-1)(q-1)$ — функция Эйлера от числа $N$) взаимно простое со значением $\phi (N)$. Обычно в качество $e$ берут простые числа, содержащие небольшое количество единичных бит в двоичной записи, например, простые числа Ферма 17, 257 или 65537.

Секретный ключ определяется через закрытую экспоненту $d$. Число $d$ является мультипликативно обратным к числу $e$ по модулю $\phi (N)$, то есть число, удовлетворяет соотношению:

$d\cdot e\equiv 1{\bmod {\phi }}(N)$.

Пара $\left\langle N,e\right\rangle$ публикуется в качестве открытого ключа RSA (англ. RSA public key), а пара $\left\langle N,d\right\rangle$ играет роль закрытого ключа RSA (англ. RSA private key) и держится в секрете.

Теорема Копперсмита

Формулировка

Пусть $N\in \mathbb {Z}$ и $f(x)\in \mathbb {Z[x]} -$ нормированный многочлен степени $d$. Пусть $X=N^{{\tfrac {1}{d}}-\varepsilon }$, $\varepsilon \geqslant 0$. Тогда по паре $\left\langle N,f\right\rangle$ атакующий эффективно найдет все целые числа $\left\vert x_{0}\right\vert <\left\vert X\right\vert$, удовлетворяющие $f(x_{0})\equiv 0{\bmod {N}}$. Время выполнения определяется выполнением LLL-алгоритма на решетке размерности $O(\omega )$, где $\omega =\min \left\{{\tfrac {1}{\varepsilon }},\log _{2}{N}\right\}$.

Доказательство

$\Box$ Пусть $m>1$ натуральное число, которое мы определим позже. Определим

$g_{i,k}(x)=x^{i}(f(x)/M)^{k}$

Мы используем в качестве основы для нашей решетки $L$ полиномы $g_{i,k}(xX)$ для $i=0,...,d-1$ и $k=0,...,m-1$. Например, когда $d=3$ и $m=3$ мы получаем матрицу решетки, натянутую на строки:

${\begin{bmatrix}1\\&X\\&&X^{2}\\-&-&-&X^{3}M^{-1}\\&-&-&-&X^{4}M^{-1}\\&&-&-&-&X^{5}M^{-1}\\-&-&-&-&-&-&X^{6}M^{-2}\\&-&-&-&-&-&-&X^{7}M^{-2}\\&&-&-&-&-&-&-&X^{8}M^{-2}\end{bmatrix}}$,

где «—» обозначает ненулевые недиагональные элементы, значение которых не влияет на определитель. Размер этой решетки равен $\omega =md$, а её определитель считается так:

$\det(L)=X^{\omega (\omega -1)/2}M^{-\omega (m-1)/2}$

Потребуем, чтобы $\det(L)<2^{-\omega (\omega -1)/4}\omega ^{-\omega /2}$. Отсюда следует

$X<M^{(m-1)/(\omega -1)}2^{-1/2}\omega ^{-1/(\omega -1)}$

что можно упростить до

$X<\gamma _{\omega }\centerdot M^{{\tfrac {1}{d}}-\varepsilon }$,

где $\varepsilon ={\tfrac {d-1}{d(\omega -1)}}$ и ${\tfrac {1}{2{\sqrt {2}}}}\leqslant \gamma _{\omega }<{\tfrac {1}{\sqrt {2}}}$ для всех $\omega$. Если мы возьмем $m\rightarrow \infty$, то получим $\omega \rightarrow \infty$ а, следовательно, и $\varepsilon \rightarrow 0$. В частности, если мы хотим решить $X<M^{{\tfrac {1}{d}}-\varepsilon _{0}}$ для произвольного $\varepsilon _{0}$, достаточно взять $m=O(k/d)$, где $k=\min \left\{{\tfrac {1}{\varepsilon }},\log _{2}{N}\right\}$. $\blacksquare$

Атака Хастеда

Формулировка

Предположим один отправитель отправляет одно и то же сообщение $M$ в зашифрованном виде определённому количеству людей $P_{1};P_{2};...;P_{k}$, каждый из которых использует одну и ту же маленькую экспоненту кодирования ${\textstyle e}$, скажем $e=3$, и различные пары $\left\langle N_{i},e\right\rangle$, причем $M<N_{i},\forall i$. Отправитель зашифровывает сообщение, используя поочередно открытый ключ каждого пользователя, и отсылает его соответствующему адресату. Тогда, если противник прослушает канал передачи и соберет $k\geqslant 3$ переданных шифротекстов, то он сможет восстановить сообщение $M$.

Доказательство

$\Box$ Предположим противник перехватил $C_{1},C_{2}$ и $C_{3}$, где $C_{i}=M^{3}{\bmod {N}}_{i}$. Мы предполагаем, что $N_{1},N_{2},N_{3}$ взаимно просты, иначе наибольший общий делитель отличный от единицы означал нахождение делителя одного из $n$. Применяя китайскую теорему об остатках к $C_{1},C_{2}$ и $C_{3}$ получим $C\in \mathbb {Z} _{N_{1},N_{2},N_{3}}$, такое что $C_{i}\equiv C{\bmod {N}}_{i}$, которое имеет значение $C=M^{3}{\bmod {N}}_{1}N_{2}N_{3}$. Однако, зная что $M<N_{i},\forall i$, получаем $M^{3}<N_{1}N_{2}N_{3}$. Поэтому $C=M^{3}$, то есть противник может расшифровать сообщение $M$ взяв корень кубический от $C$.

Для восстановления сообщения $M$ с любым значением открытой экспоненты кодирования ${\textstyle e}$, необходимо противнику перехватить $k\geqslant e$ шифротекстов. $\blacksquare$

Атака Копперсмита

Формулировка

Предположим $\left\langle N,e\right\rangle$ открытый ключ RSA, где $N$ длины $n$-бит. Возьмем множество $m=\lfloor n/e^{2}\rfloor$. Пусть $M\in \mathbb {Z} _{N}$ сообщение длины не более $n-m$ бит. Определим $M_{1}=2^{m}M+r_{1}$ и $M_{2}=2^{m}M+r_{2}$, где $r_{1}$ и $r_{2}$ различные целые числа, причем $0\leqslant r_{1}$ и $r_{2}\leqslant 2^{m}$.Если противник получит $\left\langle N,e\right\rangle$ и шифры $C_{1},C_{2}$ от $M_{1},M_{2}$(но не получит $r_{1}$ или $r_{2}$), то он сможет эффективно восстановить сообщение $M$.

Доказательство

$\Box$ Определим $g_{1}(x,y)=x^{e}-C_{1}$ и $g_{1}(x,y)=(x+y)^{e}-C_{2}$. Мы знаем, что когда $y=r_{2}-r_{1}$, эти полиномы имеют $M_{1}$ в качестве общего корня. Другими словами $\Delta =r_{2}-r_{1}$ это корень «результирующей» $h(y)=\mathrm {res} _{x}(g_{1},g_{2})\in \mathbb {Z} _{N}[y]$. Степень $h$ чаще всего $e^{2}$. Более того, $|\Delta |<2^{m}<N^{1/e^{2}}$. Следовательно, $\Delta$ это малый корень $h$ по модулю $N$, и противник может эффективно найти его, используя теорему Копперсмита. Как только $\Delta$ известна, может быть использована атака Франклина-Рейтера, чтобы покрыть $M_{2}$, следовательно, и $M$. $\blacksquare$