# Given $e$ and $d$, find $\phi(n)$

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)$$?

• Actually, we have $1 = e \cdot d \bmod \lambda(n)$, where $\lambda(n) = \phi(n) / \gcd(p-1, q-1)$; that complicates things somewhat... – poncho Jun 4 at 21:48
• $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$. – JacopoStanchi Jun 4 at 21:59
• Is $e$ a Fermat prime like in most modern RSA implementations? – forest Jun 4 at 23:42
• 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. – Samuel Neves Jun 5 at 1:52