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

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

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

Описание

Введение

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

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

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

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

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

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

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

$◻$ Предположим противник перехватил $C_1,C_2$ и $C_3$, где $C_i=M^3{modN}_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{modN}_i$, которое имеет значение $C=M^3{modN}_1{N}_2{N}_3$. Однако, зная что $M<N_i,\mathrm{\forall }i$, получаем $M^3<N_1{N}_2{N}_3$. Поэтому $C=M^3$, то есть противник может расшифровать сообщение $M$ взяв корень кубический от $C$.

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

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

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

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

$◻$ Пусть $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$ мы получаем матрицу решетки, натянутую на строки:

$\left[\begin{array}{c}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{array}\right]$,

где «—» обозначает ненулевые недиагональные элементы, значение которых не влияет на определитель. Размер этой решетки равен $\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 }\cdot M^{\frac{1}{d}-\epsilon }$,

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

См. также

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