Método del herrero

El método Coppersmith , propuesto por Don Coppersmith , es un método para encontrar raíces enteras pequeñas de polinomios univariados o bivariados , o sus raíces pequeñas módulo un entero dado . El método utiliza el algoritmo de reducción de base reticular de Lenstra-Lenstra-Lovász (LLL) para encontrar un polinomio que tenga las mismas raíces que el polinomio objetivo, pero con coeficientes menores.

En criptografía , el método Coppersmith se utiliza principalmente en ataques contra RSA cuando se conocen partes de la clave secreta y constituye la base del ataque de Coppersmith .

El método de Coppersmith consiste en reducir la resolución de ecuaciones polinómicas modulares a la resolución de polinomios sobre los números enteros.

Dejar${\displaystyle F(x)=x^{n}+a_{n-1}x^{n-1}+\ldots +a_{1}x+a_{0}}$y suponer que${\displaystyle F(x_{0})\equiv 0{\pmod {M}}}$para algún número entero${\displaystyle |x_{0}|<M^{1/n}}$El algoritmo de Coppersmith se puede utilizar para encontrar esta solución entera.${\displaystyle x_{0}}$.

Encontrar raíces sobre los racionales Q es fácil usando, por ejemplo, el método de Newton , pero dicho algoritmo no funciona módulo un número compuesto M. La idea detrás del método de Coppersmith es encontrar un polinomio diferente f relacionado con F que tenga la misma raíz.${\displaystyle x_{0}}$módulo M , pero solo tiene coeficientes pequeños. Si los coeficientes y${\displaystyle x_{0}}$son lo suficientemente pequeños como para${\displaystyle |f(x_{0})|<M}$sobre los enteros, entonces tenemos${\displaystyle f(x_{0})=0}$, de modo que${\displaystyle x_{0}}$es una raíz de f sobre Q y se puede encontrar fácilmente. De manera más general, podemos encontrar un polinomio${\displaystyle f(x)}$con la misma raíz${\displaystyle x_{0}}$módulo alguna potencia${\displaystyle M^{a}}$de M , que satisface${\displaystyle |f(x_{0})|<M^{a}}$y resolver para${\displaystyle x_{0}}$como se indicó anteriormente.

El algoritmo de Coppersmith utiliza el algoritmo de reducción de base reticular de Lenstra-Lenstra-Lovász (LLL) para construir el polinomio f con coeficientes pequeños. Dado F , el algoritmo construye polinomios${\displaystyle p_{1}(x),p_{2}(x),\dots ,p_{n}(x)}$que todos tienen la misma raíz${\displaystyle x_{0}}$módulo${\displaystyle M^{a}}$, donde a es algún número entero elegido en función del grado de F y el tamaño de${\displaystyle x_{0}}$Cualquier combinación lineal de estos polinomios también tiene${\displaystyle x_{0}}$como raíz módulo${\displaystyle M^{a}}$.

El siguiente paso es utilizar el algoritmo LLL para construir una combinación lineal.${\displaystyle f(x)=\sum c_{i}p_{i}(x)}$ del${\displaystyle p_{i}(x)}$de modo que la desigualdad${\displaystyle |f(x_{0})|<M^{a}}$se cumple. Ahora los métodos de factorización estándar pueden calcular los ceros de${\displaystyle f(x)}$sobre los números enteros.

El método de Coppersmith para polinomios univariados se implementa en

• El magma como función SmallRoots;
• PARI/GP como función zncoppersmith;
• SageMath como método small_roots.

• Coppersmith, D. (1996). «Encontrar una raíz pequeña de una ecuación modular univariada». Avances en criptología — EUROCRYPT '96 . Notas de clase en ciencias de la computación. Vol.  1070. pp. 155–165 . doi : 10.1007/3-540-68339-9_14 . ISBN  978-3-540-61186-8.
• Coppersmith, D. (1996). "Encontrar una raíz pequeña de una ecuación entera bivariada; factorización con bits altos conocidos". Avances en criptología — EUROCRYPT '96 . Notas de clase en ciencias de la computación. Vol.  1070. pp. 178–189 . doi : 10.1007/3-540-68339-9_16 . ISBN  978-3-540-61186-8.
• Coron, JS (2004). "Finding Small Roots of Bivariate Integer Polynomial Equations Revisited" (PDF) . Advances in Cryptology - EUROCRYPT 2004. Lecture Notes in Computer Science. Vol.  3027. pp. 492–505 . doi : 10.1007/978-3-540-24676-3_29 . ISBN  978-3-540-21935-4.
• Bauer, A.; Joux, A. (2007). «Hacia una variación rigurosa del algoritmo de Coppersmith con tres variables». Avances en criptología - EUROCRYPT 2007. Notas de clase en informática. Vol.  4515. pp. 361–378 . doi : 10.1007/978-3-540-72540-4_21 . ISBN  978-3-540-72539-8.
• Coron, JS (2007). "Encontrar raíces pequeñas de ecuaciones polinómicas enteras bivariadas: un enfoque directo" (PDF) . Avances en criptología - CRYPTO 2007. Notas de clase en ciencias de la computación. Vol.  4622. pp. 379–394 . doi : 10.1007/978-3-540-74143-5_21 . ISBN  978-3-540-74142-8.