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.

Improve this question
$\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$
    – JacopoStanchi
    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$
    – Samuel Neves
    Jun 5, 2021 at 1:52

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.