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

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

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

Описание

Введение

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

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

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

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

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

Предположим один отправитель отправляет одно и то же сообщение $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$

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

Пусть $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$

См. также

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