Potential Coppersmith's attack on RSA

Question

Sorry if I don't express myself well in English.

The solutions $h$ and $k$ of

$$[(h+1)^2]*[(2*h+2)^2/2-1]=X* M$$

and

$$[(k+1)^2]*[(2*k+2)^2/2-1]=Y*M$$

are such that each $M$ number divisible by $9$ has these characteristics:

$$(h+1)/3=(k+1)/6$$

and

$$k+h+2=M$$

and $M$ is a divisor of a sum of odd consecutive cubes from $1$ to $u=2*h+1$ and from $1$ to $v=2*k+1$

So we're going to look for numbers divisible by $9$ in this way:

let $N =a*b$ be a number to be factored then $N-(2 * s)^2-2*s*n=M$

where $n=b-a$ and $s$ goes from $1$ to $8$

Therefore, if $N != 9*c$ we will have $8$ formulas.

Solving:

$[(h+1)^2]*[(2*h+2)^2/2-1]=X*(N-(2*s)^2-2*s*n)$

,

$[(k+1)^2]*[(2*k+2)^2/2-1]=Y*(N-(2*s)^2-2*s*n)$

,

$(h+1)/3=(k+1)/6$

,

$k+h+2=(N-(2*s)^2-2*s*n)$

,$h$,$Y$,$X$,$k$

example $N=209$

for $s=1$

Solving:

$[(h+1)^2]*[(2*h+2)^2/2-1]=X*(209-4-2*n)$

,

$[(k+1)^2]*[(2*k+2)^2/2-1]=Y*(209-4-2*n)$

,

$(h+1)/3=(k+1)/6$

,

$k+h+2=(209-4-2*n)$

, $h$,$Y$,$X$,$k$

We will have:

$-16*n^3+4920*n^2-504282*n+17228405=X*81$

Now comes the part I don't understand, and I thought I'd use the Coppersmith method (if one can use it).

Since the maximum $n$ in a generic number to be factored in the integer part of $N/3-3$, so in our case the integer part of $209 / 3-3$ = $66$.

$[(66^3)/81] = 3549,...$ so we will take $P = 3557$

$-(3557*16)*n^3+(3557*4920)*n^2-(3557*504282)*n+(3557*17228405)=X*(3557*81)$

Now we know that there exists n0 such that |n0|<(3557*81)^(1/3) and that

$-(3557*16)*n0^3+(3557*4920)*n0^2-(3557*504282)*n0+(3557*17228405)=0 \pmod{81*3557}$

Now to use the Coppersmith method my questions are:

• should the coefficient of $n ^ 3$ be $1$?
• should the $GCD$ of all the coefficients of $n$ and $P * 81$ be $1$?
• If we know the factorization of $81*P$, can we benefit from it?
• What is the problem with using the Coppersmith method for $N$ with $1000$ digits?

EDIT $13$ September $2019$ :

$-16*n^3+4920*n^2-504282*n+17228405=X*81$

to make the coefficients less than $81$

we can do so

$-16*n^3+4860*n^2+60*n^2-504225*n-57*n+17228376+29=X*81$

$-16*n^3+(60*81)*n^2+60*n^2-(6225*81)*n-57*n+(212696*81)+29=X*81$

then

$-16*n^3+60*n^2-57*n+29=A*81$

Now is it easier to solve it?

Answer 1

I'll try to answer your questions. First I shall write Coppersmith's Theorem.

Theorem. Let $0<\varepsilon<1/d$ and $F(x)$ be a monic polynomial of degree $d$ with at least one root $x_0$ in ${\mathbb{Z}}_N$ and $|x_0|<X =\lceil 0.5N^{1/d-\varepsilon}\rceil.$ Then, we can find $x_0$ in time $poly(d,1/\varepsilon,\ln{N}).$

First, notice that in your polynomial you know the factorization of the modulus. But, in Coppersmith method, you can find a solution $\mod{N},$ even if you don't know the factorization of $N$ (e.g. if $N$ is an RSA modulus).

• should the coefficient of $𝑛^3$ be 1?

Yes, in the theorem of Coppersmith we deal with monic polynomials.

• should the 𝐺𝐶𝐷 of all the coefficients of $𝑛$ and $𝑃∗81$ be 1?

I did not understand what you mean. The gcd of the coefficients of the polynomial with $n?$

• If we know the factorization of 81∗𝑃, can we benefit from it?

$81*P$ is your modulus. So, no. You can apply Coppersmith without knowing the factorization of the modulus.

• What is the problem with using the Coppersmith method for 𝑁 with 1000 digits?

No problem, if the assumption of the Theorem are satisfied.