0
$\begingroup$

I've got an RSA encryption I need to crack, but to do it I need to find the p and q values of an N I am given - it's quite large, around 308 symbols.

I know that N is the product of primes p & q, but I don't know what kind of searching algorithm I'd implement to find the exact p & q that fit |p-q|<10000. Since it needs to be an efficient method, I'm looking for a way that excludes finding ALL possible combinations of p*q = n.

How would I go about doing it? How would I even start with inputting the 308 symbol number anywhere? It's too large to fit any kind of variable in c# for example...

$\endgroup$
5
  • 1
    $\begingroup$ Fermat factorization? $\endgroup$
    – kelalaka
    Commented Jan 8, 2021 at 19:41
  • 2
    $\begingroup$ Or just brute force searching around $\sqrt{N}$ $\endgroup$
    – poncho
    Commented Jan 8, 2021 at 19:43
  • $\begingroup$ docs.microsoft.com/en-us/dotnet/api/… $\endgroup$
    – kelalaka
    Commented Jan 8, 2021 at 20:00
  • 1
    $\begingroup$ For RSA numbers of cryptographic size, simplified Fermat will do: compute $a=\left\lceil\sqrt N\right\rceil$, $p=a+\sqrt{a^2-N}$ which will always be an integer, and $q=a-\sqrt{a^2-N}$. $\endgroup$
    – fgrieu
    Commented Jan 8, 2021 at 20:42
  • $\begingroup$ I presume symbols means decimal digits? $\endgroup$
    – kodlu
    Commented Jan 8, 2021 at 23:55

1 Answer 1

1
$\begingroup$

As @fgrieu said, it will work when ${|p-q|< N^{1/4}}$ , where ${\sqrt N}$ and ${A}$ both are very nearer. then we can take ${A = \sqrt N}$ to start with.

  • Let ${A=(p+q)/2}$ , i.e., A is mid point of p and q, which could be nearer to ${\sqrt N}$

  • There exist an integer ${x}$ so that, ${A-x=p}$ and ${A+x=q}$

  • ${N=pq}$ ${=}$ ${(A-x)(A+x)=A^2-x^2}$

  • ${x= \sqrt{A^2-N}}$

  • Since we know A and N we can find x and subsequently p and q.

$\endgroup$

Your Answer

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

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