When we study about RSA cracking, we could hear a lot about the Coppersmith Method
. Briefly, when we want to get some roots against the polynomial, we can compute it simply (not simple to me, simple to computer lol). But if the polynomial is on modulus field, it changes into a completely different problem. So the Coppersmith Method
is the innovation itself XD
Coppersmith Method
Let’s think about a simple polynomial
Overview
In the previous description, compared to the equation with modulus, the equation without modulus is relatively very easy to solve. Copersmith also devised the Copersmith method based on the method of eliminating modulus from equations in which modulus exists.
Above is the encryption process used in a typical RSA equation. As intended, the factorization of N is impossible in time issue, so N cannot be easily recovered.
But, what about this condition
let me think about the equation
Howgrave-Graham Theorem
This theorem converts
- The vector made of coefficients from function
called coefficient vector
. Can be expressed as- The norm of function
is the norm of coefficient vector. Can be expressed as
Now, we can talk about the conditions in this theorem.
- For some
, every var which matches also matches