0

I'm a little confused as to how to go about this, I've read through the bottom answer to this question : RSA solving for $p$ and $q$ knowing $\phi(pq)$ and $n$ but in that question they find p and q after knowing phi(n) AND n. Any help would be appreciated, thanks.

Community
  • 1
NDTB
  • 243

2 Answers2

0

Given $p$:

  • $q=\frac{n}{p}$
  • $\phi(n)=(p-1)(q-1)$

Given $q$:

  • $p=\frac{n}{q}$
  • $\phi(n)=(p-1)(q-1)$

Given $\phi(n)$:

  • $p=\frac{(n-\phi(n)+1)+\sqrt{(n-\phi(n)+1)^2-4n}}{2}$
  • $q=\frac{n}{p}$
barak manos
  • 43,109
0

Let's first look at the two easy cases. If you know either $p$ or $q$, then finding the other two are very easy given that $pq =n$ and $n$ is publicly known.

Given that you know $\phi(n)$, then the answer provided in the link you gave is a really clever way of finding $p$ and $q$.

Auclair
  • 1,467
  • Thanks for the reminder, I don't think I had fully understood that n and e are publicly known. – NDTB May 24 '16 at 06:50