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

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

Описание

Введение

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

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

Чтобы уменьшить время шифрования или проверки подписи, желательно использовать маленькое ${\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).

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

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

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

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

См. также

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

Примечания