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 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$ – JacopoStanchi Jun 4 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 at 22:47
  • $\begingroup$ Is $e$ a Fermat prime like in most modern RSA implementations? $\endgroup$ – forest Jun 4 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$ – Samuel Neves Jun 5 at 1:52

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.