0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Everyone is supposed to know $n$. $\endgroup$
    – Auclair
    May 24 '16 at 6:38
0
$\begingroup$

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}$
$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks for the reminder, I don't think I had fully understood that n and e are publicly known. $\endgroup$
    – NDTB
    May 24 '16 at 6:50

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.