Русская Википедия:Теорема Копперсмита
Теорема Копперсмита (метод Копперсмита) — теорема, позволяющая эффективно найти все нули нормированных многочленов по определённому модулю.[1]
Теорема используется в основном для атак на криптосистему RSA. Этот метод является эффективным, если экспонента кодирования имеет достаточно малое значение, либо когда известна часть секретного ключа. Теорема также связана с LLL-алгоритмом.
Описание
Введение
Теорема предлагает алгоритм эффективного нахождения корней нормированного многочлена <math>f</math> по модулю <math>N</math>, которые меньше чем <math>X=N^{1/d}</math>. Если <math>X</math> будет малым, то алгоритм будет работать быстрее. Преимущество теоремы это возможность находить малые корни многочлена по составному модулю <math>N</math>. Если же модуль — простое число, то нет смысла использовать теорему Копперсмита. Намного эффективнее будет использовать другие способы нахождения корней многочлена.[1]
Маленькая экспонента кодирования
Чтобы уменьшить время шифрования или проверки подписи, желательно использовать маленькое <math display="inline">e</math> (экспонента кодирования). Наименьшее возможное значение — <math>3</math>, однако рекомендуется использовать <math>e = 2^{16}+1=65537</math> (для защиты от некоторых атак). При использовании значения <math>2^{16}+1</math> на проверку подписи требуется 17 умножений (<math>\forall e\leqslant\phi(N)</math>, где <math>\phi(N)</math> — порядок мультипликативной группы <math>\mathbb{Z}_N</math>, возможно около 1000). Атаки ориентированные на использование маленького <math display="inline">e</math> не всегда действенны.
Самые мощные атаки на маленькую экспоненту кодирования основываются на теореме Копперсмита, которая имеет много приложений, одно из которых атака Хастеда (Hasted).[2]
Атака Хастеда
Предположим один отправитель отправляет одно и то же сообщение <math>M</math> в зашифрованном виде определённому количеству людей <math>P_1;P_2;...;P_k</math>, каждый из которых использует одну и ту же маленькую экспоненту кодирования <math display="inline">e</math>, скажем <math>e=3</math>, и различные пары <math>\left \langle N_i,e \right \rangle</math>, причем <math>M<N_i, \forall i</math>. Отправитель зашифровывает сообщение, используя поочередно открытый ключ каждого пользователя, и отсылает его соответствующему адресату. Тогда, если противник прослушает канал передачи и соберет <math>k\geqslant3</math> переданных шифротекстов, то он сможет восстановить сообщение <math>M</math>.
Доказательство
<math>\Box</math> Предположим противник перехватил <math>C_1,C_2</math> и <math>C_3</math>, где <math>C_i = M^3\bmod N_i</math>. Мы предполагаем, что <math>N_1,N_2,N_3</math> взаимно просты, иначе наибольший общий делитель отличный от единицы означал нахождение делителя одного из <math>n</math>. Применяя китайскую теорему об остатках к <math>C_1,C_2</math> и <math>C_3</math> получим <math>C\in \mathbb{Z}_{N_1,N_2,N_3}</math>, такое что <math>C_i\equiv C\bmod N_i</math>, которое имеет значение <math>C = M^3\bmod N_1 N_2 N_3</math>. Однако, зная что <math>M<N_i,\forall i</math>, получаем <math>M^3<N_1 N_2 N_3</math>. Поэтому <math>C= M^3</math>, то есть противник может расшифровать сообщение <math>M</math> взяв корень кубический от <math>C</math>.
Для восстановления сообщения <math>M</math> с любым значением открытой экспоненты кодирования <math display="inline">e</math>, необходимо противнику перехватить <math>k\geqslant e</math> шифротекстов. <math>\blacksquare</math>
Формулировка
Пусть <math>N\in\mathbb{Z}</math> и <math>f(x)\in\mathbb{Z[x]} -</math> нормированный многочлен степени <math>d</math>. Пусть <math>X=N^{\tfrac{1}{d} - \varepsilon}</math>, <math>\varepsilon \geqslant 0</math>. Тогда по паре <math>\left \langle N,f \right \rangle</math> атакующий эффективно найдет все целые числа <math>\left \vert x_{0} \right \vert<\left \vert X \right \vert</math>, удовлетворяющие <math>f(x_{0})\equiv 0 \bmod N</math>. Время выполнения определяется выполнением LLL-алгоритма на решетке размерности <math>O(\omega)</math>, где <math>\omega = \min\left \{ \tfrac{1}{\varepsilon},\log_{2}{N}\right \}</math>.[1]
Доказательство
<math>\Box</math> Пусть <math>m>1</math> натуральное число, которое мы определим позже. Определим
<math>g_{i,k}(x)=x^i(f(x)/M)^k</math>
Мы используем в качестве основы для нашей решетки <math>L</math> полиномы <math>g_{i,k}(xX)</math> для <math>i=0,...,d-1</math> и <math>k=0,...,m-1</math>. Например, когда <math>d=3</math> и <math>m=3</math> мы получаем матрицу решетки, натянутую на строки:
<math>\begin{bmatrix} 1 \\ & X \\ & & X^2 \\ - & - & - & X^3M^{-1} \\ & - & - & - & X^4M^{-1} \\ & & - & - & - & X^5M^{-1} \\ - & - & - & - & - & - & X^6M^{-2} \\ & - & - & - & - & - & - & X^7M^{-2} \\ & & - & - & - & - & - & - & X^8M^{-2} \end{bmatrix}</math>,
где «—» обозначает ненулевые недиагональные элементы, значение которых не влияет на определитель. Размер этой решетки равен <math>\omega=md</math>, а её определитель считается так:
<math>\det(L) = X^{\omega(\omega-1)/2}M^{-\omega(m-1)/2}</math>
Потребуем, чтобы <math>\det(L) < 2^{-\omega(\omega-1)/4}\omega^{-\omega/2}</math>. Отсюда следует
<math>X<M^{(m-1)/(\omega-1)}2^{-1/2}\omega^{-1/(\omega-1)}</math>
что можно упростить до
<math>X < \gamma_\omega\centerdot M^{\tfrac{1}{d}-\varepsilon}</math>,
где <math>\varepsilon=\tfrac{d-1}{d(\omega-1)}</math> и <math>\tfrac{1}{2\sqrt 2}\leqslant\gamma_\omega<\tfrac{1}{\sqrt 2}</math> для всех <math>\omega</math>. Если мы возьмем <math>m\rightarrow \infty</math>, то получим <math>\omega \rightarrow \infty</math> а, следовательно, и <math>\varepsilon \rightarrow 0</math>. В частности, если мы хотим решить <math>X < M^{\tfrac{1}{d}-\varepsilon_0}</math> для произвольного <math>\varepsilon_0</math>, достаточно взять <math>m=O(k/d)</math>, где <math>k = \min\left \{ \tfrac{1}{\varepsilon},\log_{2}{N}\right \}</math>. <math>\blacksquare</math>[3]
См. также
Примечания
