0
$\begingroup$

Let's say we have just RSA public and private exponents $e$ and $d$ but not the corresponding modulus $n$. Is there a method to find $\phi(n)$?

This is for a CTF challenge. I am not concerned about retrieving $n$ at this stage.

My guess would be to start from $d = e^{-1} \mod \phi(n)$, which leads to $1 = e \times d \mod \phi(n)$.

Hence, $\phi(n)$ could be equal to $e \times d - 1$, but that could also not be the case, if $e \times d - 1$ is composite.

So is there a way to find the correct value for $\phi(n)$?

Thank you for your help.

$\endgroup$
11
  • $\begingroup$ Actually, we have $1 = e \cdot d \bmod \lambda(n)$, where $\lambda(n) = \phi(n) / \gcd(p-1, q-1)$; that complicates things somewhat... $\endgroup$
    – poncho
    Jun 4, 2021 at 21:48
  • $\begingroup$ $1 = e \times d \mod \phi(n)$ is incorrect? Damn, if we have to know $\textrm{gcd}(p-1,q-1)$, then I really don't know how my problem could be solved. Obviously, we do not have access to $p$ or $q$. $\endgroup$ Jun 4, 2021 at 21:59
  • $\begingroup$ The only reference I could find on this problem points to this paper cs.cmu.edu/~glmiller/Publications/Papers/Mi76.pdf. $\endgroup$
    – Myath
    Jun 4, 2021 at 22:47
  • $\begingroup$ Is $e$ a Fermat prime like in most modern RSA implementations? $\endgroup$
    – forest
    Jun 4, 2021 at 23:42
  • 1
    $\begingroup$ In fact, in your situation, you probably don't need any of that; $\gcd(e \cdot d_a-1, e \cdot d_b-1)$ will give you the common factor (plus some easy to remove extraneous factors) between $n_a$ and $n_b$. It should be easy to go from there. $\endgroup$ Jun 5, 2021 at 1:52

0

Your Answer

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

Browse other questions tagged or ask your own question.