1
$\begingroup$

Could someone please tell me where I can find the source code of the Coppersmith method univariate written in C with the GMP library?

to be fair I will explain how I will use it for factoring

reference https://www.academia.edu/48848013/Lepore_Factorization_nr_88

Let's take the example N=1763 of Factorization nr 88 Part I

$P=27*b+1$ ; $p=65-8*b$

$Q=25*a+11$ ; $q=67-8*a$

$p^2=(65-8*b)^2=64*b^2-1040*b+4225$

We find the integer delta $D$ of $x*p+p^2$

$(27*x-1040)^2-4*64*(4225+x)=D^2$

$x=1/729*(28208-sqrt(729*D^2+795691264))$

$795691264=1763*451328$

A partial factorization of $451328$ that is $8$ is the biggest problem with my approach

we replace $D$

$28208-729*x-27*sqrt[(27*x-1040)^2-4*64*(4225+x)]=8*(67-8*a)$

$->$

$64*a^2+55344*a+11964681=729*W$

$55344+729*x=64*y$ $->$ $x=16$

$11964681+729*x=64*y$ $->$ $x=15$

$[64/64*a^2+(((55344+16*729)/64) mod (729))*a+(((11964681+15*729)/64) mod (729))] mod (729) = 0$

$(a^2+318*a+495) mod (729) = 0$

Applying the Coppersmith univariate method

$->$ $a=3$ $->$ $q=43$

$\endgroup$
3
  • $\begingroup$ @kelalaka not RSA attack $\endgroup$ Jan 26, 2022 at 14:28
  • 1
    $\begingroup$ Ah, I see. github.com/defund/coppersmith, no easy to convert to C/GNU/GMP. May be you can benefit from NTL on your progress. $\endgroup$
    – kelalaka
    Jan 26, 2022 at 14:54
  • $\begingroup$ @kelalaka thank you! I will try to learn over the years $\endgroup$ Jan 26, 2022 at 15:46

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.