Метод медника

Метод Копперсмита , предложенный Доном Копперсмитом , представляет собой метод поиска небольших целых нулей одномерных или двумерных полиномов по модулю заданного целого числа . В этом методе используется алгоритм приведения решеточного базиса Ленстры-Ленстры-Ловаса (LLL) для поиска полинома, который имеет те же нули, что и целевой полином, но меньшие коэффициенты.

В криптографии метод Копперсмита в основном используется при атаках на RSA , когда части секретного ключа известны и образуют базу для атаки Копперсмита .

Подход

Подход Копперсмита представляет собой сведение решения модульных полиномиальных уравнений к решению полиномов над целыми числами.

Позволять $F(x)=x^{n}+a_{n-1}x^{n-1}+\ldots +a_{1}x+a_{0}$ и предположим, что $F(x_{0})\equiv 0{\pmod {M}}$ для некоторых целое число $|x_{0}|<M^{1/n}$. Для нахождения этого целочисленного решения можно использовать алгоритм Копперсмита. $x_{0}$.

Найти корни над Q легко, используя, например, Ньютона , но такой алгоритм не работает по модулю составного числа M. метод Идея метода Копперсмита состоит в том, чтобы найти другой полином f, связанный с F , который имеет тот же корень. $x_{0}$ по модулю M , но имеет лишь небольшие коэффициенты. Если коэффициенты и $x_{0}$ достаточно малы, чтобы $|f(x_{0})|<M$ над целыми числами, то мы имеем $f(x_{0})=0$, так что $x_{0}$ является корнем f над Q и его легко найти. В более общем смысле мы можем найти полином $f(x)$ с тем же корнем $x_{0}$ по модулю некоторой мощности $M^{a}$ М , удовлетворяющий $|f(x_{0})|<M^{a}$и решить для $x_{0}$ как указано выше.

Алгоритм Копперсмита использует алгоритм приведения решеточного базиса Ленстры-Ленстры-Ловаса (LLL) для построения многочлена f с малыми коэффициентами. Учитывая F , алгоритм строит полиномы $p_{1}(x),p_{2}(x),\dots ,p_{n}(x)$ что у всех один корень $x_{0}$ модуль $M^{a}$, где a — некоторое целое число, выбранное на основе степени F и размера $x_{0}$. Любая линейная комбинация этих полиномов также имеет $x_{0}$ как корень по модулю $M^{a}$.

Следующим шагом будет использование алгоритма LLL для построения линейной комбинации. $f(x)=\sum c_{i}p_{i}(x)$ принадлежащий $p_{i}(x)$ так что неравенство $|f(x_{0})|<M^{a}$ держит. Теперь стандартные методы факторизации могут вычислять нули $f(x)$ над целыми числами.

Реализации

Метод Копперсмита для одномерных полиномов реализован в

• Магма как функция SmallRoots;
• PARI/GP как функция zncoppersmith;
• SageMath как метод small_roots.

Ссылки

• Копперсмит, Д. (1996). «Нахождение малого корня одномерного модульного уравнения». Достижения в криптологии — EUROCRYPT '96 . Конспекты лекций по информатике. Том. 1070. С. 155–165. дои : 10.1007/3-540-68339-9_14 . ISBN  978-3-540-61186-8 .
• Копперсмит, Д. (1996). «Нахождение малого корня двумерного целочисленного уравнения; факторинг с известными старшими битами». Достижения в криптологии — EUROCRYPT '96 . Конспекты лекций по информатике. Том. 1070. стр. 178–189. дои : 10.1007/3-540-68339-9_16 . ISBN  978-3-540-61186-8 .
• Корон, Дж.С. (2004). «Ещё раз в поиске малых корней двумерных целочисленных полиномиальных уравнений» (PDF) . Достижения в криптологии – EUROCRYPT 2004 . Конспекты лекций по информатике. Том. 3027. стр. 492–505. дои : 10.1007/978-3-540-24676-3_29 . ISBN  978-3-540-21935-4 .
• Бауэр, А.; Жу, А. (2007). «К строгой вариации алгоритма Копперсмита с тремя переменными». Достижения в криптологии – EUROCRYPT 2007 . Конспекты лекций по информатике. Том. 4515. стр. 361–378. дои : 10.1007/978-3-540-72540-4_21 . ISBN  978-3-540-72539-8 .
• Корон, Дж.С. (2007). «Нахождение малых корней двумерных целочисленных полиномиальных уравнений: прямой подход» (PDF) . Достижения криптологии — КРИПТО 2007 . Конспекты лекций по информатике. Том. 4622. стр. 379–394. дои : 10.1007/978-3-540-74143-5_21 . ISBN  978-3-540-74142-8 .