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

Теорема Копперсмита (метод Копперсмита) — теорема, позволяющая эффективно найти все нули нормированных многочленов по определённому модулю.

Теорема используется в основном для атак на криптосистему RSA. Этот метод является эффективным, если экспонента кодирования имеет достаточно малое значение, либо когда известна часть секретного ключа. Теорема также связана с LLL-алгоритмом.

ОписаниеПравить

ВведениеПравить

Теорема предлагает алгоритм эффективного нахождения корней нормированного многочлена $f$$f$  по модулю $N$$N$ , которые меньше чем $X=N^{1/d}$$X=N^{1/d}$ . Если $X$$X$  будет малым, то алгоритм будет работать быстрее. Преимущество теоремы это возможность находить малые корни многочлена по составному модулю $N$$N$ . Если же модуль — простое число, то нет смысла использовать теорему Копперсмита. Намного эффективнее будет использовать другие способы нахождения корней многочлена.

Маленькая экспонента кодированияПравить

Чтобы уменьшить время шифрования или проверки подписи, желательно использовать маленькое $e$${\textstyle e}$  (экспонента кодирования). Наименьшее возможное значение — $3$$3$ , однако рекомендуется использовать $e=2^{16}+1=65537$$e=2^{16}+1=65537$  (для защиты от некоторых атак). При использовании значения $2^{16}+1$$2^{{16}}+1$  на проверку подписи требуется 17 умножений ($\mathrm{\forall <!--\; \forall \; -->}e⩽<!--\; ⩽\; -->\mathrm{\varphi <!--\; \varphi \; -->}(N)$$\forall e\leqslant \phi (N)$ , где $\mathrm{\varphi <!--\; \varphi \; -->}(N)$$\phi (N)$  — порядок мультипликативной группы ${\mathbb{Z}}_N$$\mathbb {Z} _{N}$ , возможно около 1000). Атаки ориентированные на использование маленького $e$${\textstyle e}$  не всегда действенны.

Самые мощные атаки на маленькую экспоненту кодирования основываются на теореме Копперсмита, которая имеет много приложений, одно из которых атака Хастеда (Hasted).

Атака ХастедаПравить

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

ДоказательствоПравить

$\mathrm{◻<!--\; ◻\; -->}$$\Box$  Предположим противник перехватил $C_1,C_2$$C_{1},C_{2}$  и $C_3$$C_{3}$ , где $C_i=M^3{modN}_i$$C_{i}=M^{3}{\bmod {N}}_{i}$ . Мы предполагаем, что $N_1,N_2,N_3$$N_{1},N_{2},N_{3}$  взаимно просты, иначе наибольший общий делитель отличный от единицы означал нахождение делителя одного из $n$$n$ . Применяя китайскую теорему об остатках к $C_1,C_2$$C_{1},C_{2}$  и $C_3$$C_{3}$  получим $C\in <!--\; \in \; -->{\mathbb{Z}}_{N_1,N_2,N_3}$$C\in \mathbb {Z} _{N_{1},N_{2},N_{3}}$ , такое что $C_i\equiv <!--\; \equiv \; -->C{modN}_i$$C_{i}\equiv C{\bmod {N}}_{i}$ , которое имеет значение $C=M^3{modN}_1{N}_2{N}_3$$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$$C=M^{3}$ , то есть противник может расшифровать сообщение $M$$M$  взяв корень кубический от $C$$C$ .

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

ФормулировкаПравить

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

ДоказательствоПравить

$\mathrm{◻<!--\; ◻\; -->}$$\Box$  Пусть $m>1$$m>1$  натуральное число, которое мы определим позже. Определим

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

Мы используем в качестве основы для нашей решетки $L$$L$  полиномы $g_{i,k}(xX)$$g_{i,k}(xX)$  для $i=0,...,d-<!--\; -\; -->1$$i=0,...,d-1$  и $k=0,...,m-<!--\; -\; -->1$$k=0,...,m-1$ . Например, когда $d=3$$d=3$  и $m=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}}$ ,

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

$det(L)=X^{\mathrm{\omega <!--\; \omega \; -->}(\mathrm{\omega <!--\; \omega \; -->}-<!--\; -\; -->1)/2}{M}^{-<!--\; -\; -->\mathrm{\omega <!--\; \omega \; -->}(m-<!--\; -\; -->1)/2}$$\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 }$ ,

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

См. такжеПравить

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