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 Jan 8 at 19:41
  • 2
    $\begingroup$ Or just brute force searching around $\sqrt{N}$ $\endgroup$ – poncho Jan 8 at 19:43
  • $\begingroup$ docs.microsoft.com/en-us/dotnet/api/… $\endgroup$ – kelalaka Jan 8 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 Jan 8 at 20:42
  • $\begingroup$ I presume symbols means decimal digits? $\endgroup$ – kodlu Jan 8 at 23:55
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, privacy policy and cookie policy

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