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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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}}}$,

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

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

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

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

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

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

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

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