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...

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

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

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