Coppersmith Method – RSA

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 $x^2 + x + 1 = 0$. We can calculate the roots about this polynomial, it is simple enough to calculate (for me too lol). But when we think about the same polynomial with a modulus field appended, like $x^2 + x + 1 \equiv 0 \pmod{123456789}$. Can u?

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.
$$C \equiv M^e \pmod{n}$$
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 $ M < n^{\frac{1}{e}}$ added? The modulus field will be unused, so we can just calculate on integer field. This is the basic idea of coppersmith method.

let me think about the equation $f(x) \equiv 0 \pmod{a}$. If there is some $x_0$ which matches $|f(x_0)| < a$, we can remove the modulus as the previous example. Too trivial, but it is hard to get some $x_0$ which satisfies this condition. So coppersmith will change this into a condition based on $x$ not $f(x)$.

Howgrave-Graham Theorem

This theorem converts $f(x) \equiv 0 \pmod{a}$ to $f(x) = 0$. Let me define some things below.

1. The vector made of coefficients from function $f$ called coefficient vector. Can be expressed as $[a_0, a_1, \cdots, a_n]$
   
2. The norm of function $f$ is the norm of coefficient vector. Can be expressed as $||f||^2 = \sum{{a_i}^2}$

Now, we can talk about the conditions in this theorem.

1. For some $X$, every var which matches $|x_0| < X$ also matches $f(x_0) \equiv 0 \pmod{a}$