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

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

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

Описание

Введение

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

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

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

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

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

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

$\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$ ^[3]

См. также

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

Примечания

↑ ¹ ² ³ Dan Boneh. Twenty Years of Attacks on the RSA Cryptosystem (неопр.). Дата обращения: 25 ноября 2016. Архивировано 26 марта 2016 года.
↑ Ушаков Константин. Взлом системы RSA (неопр.). Дата обращения: 25 ноября 2016. Архивировано 1 декабря 2016 года.
↑ Glenn Durfee. CRYPTANALYSIS OF RSA USING ALGEBRAIC AND LATTICE METHODS (неопр.) (июнь 2002). Дата обращения: 30 ноября 2016. Архивировано 4 марта 2016 года.

[:0-1] ¹ ² ³ Dan Boneh. Twenty Years of Attacks on the RSA Cryptosystem (неопр.). Дата обращения: 25 ноября 2016. Архивировано 26 марта 2016 года.

[2] Ушаков Константин. Взлом системы RSA (неопр.). Дата обращения: 25 ноября 2016. Архивировано 1 декабря 2016 года.

[3] Glenn Durfee. CRYPTANALYSIS OF RSA USING ALGEBRAIC AND LATTICE METHODS (неопр.) (июнь 2002). Дата обращения: 30 ноября 2016. Архивировано 4 марта 2016 года.

[1]

[2]

[3]