4
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So RSA is broken? $\endgroup$ – Alberico Lepore Sep 13 at 12:04
  • 1
    $\begingroup$ No. But you must choose two appropriately sized primes in RSA /at random/. If you use some method that allows an adversary to know enough stuff about your chosen primes, Coppersmith lets them expand that knowledge to discover the rest. It is easy to build something that generates random RSA keys, but it's tempting to build something that's a bit cheaper and faster but less random. Coppersmith makes that very dangerous. $\endgroup$ – tialaramex Sep 13 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.