0
$\begingroup$

I have a 1024-bit number $n$ obtained by multiplying two 512-bit randomly generated prime numbers $p$ and $q$.

Then there's $\phi = (p-1)(q-1)$, which is another 1024-bit number.

I do not have $\phi$ but I do have the result obtained by multiplying $\phi$ with a random 1024-bit number.

I need to retrieve $p$ and $q$. I know how to get to $p$ and $q$ values starting from $\phi$ but I don't know how to extract $\phi$ from the product I have.

Is it even possible?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Do you need the original $\varphi$ or can you also make do with some multple of $\varphi$? (In the latter case you don't need to recover $\varphi$...) $\endgroup$ – SEJPM♦ Oct 29 '20 at 10:03
  • 1
    $\begingroup$ Very nearly a duplicate of Algorithm for factoring knowing RSA private key and Why is it important that phi(n) is kept a secret, in RSA?. Hint: One way is to factor $n$, then compute $\phi$. A concise description of Miller's algorithm to solve this is Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem, proof of fact 1. $\endgroup$ – fgrieu♦ Oct 29 '20 at 12:34
  • $\begingroup$ Also: depending on the smoothness of the random number and $\phi$, there may be other ways noticing that $n\approx\phi$. $\endgroup$ – fgrieu♦ Oct 29 '20 at 14:15
  • $\begingroup$ I need to retrieve $p$ and $q$ and in order to do that I need to somehow extract $\phi$ from the number I have. @fgrieu if I could factor $n$ then I would not need to compute $\phi$ as I would already have $p$ and $q$. Also, the Miller's algorithm seems to not be applicable to this problem as I do not have $d$ or $e$. It is not an RSA problem. $\endgroup$ – Combiner_85 Oct 31 '20 at 0:10
  • $\begingroup$ @SEJPM In fact I already have a multiple of $\phi$, can I extract $p$ and $q$ directly from it? $\endgroup$ – Combiner_85 Oct 31 '20 at 0:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.