RSA - Calculating $d$ given $\varphi (N)$ and $N$

Question

From this discussion, I know that if I know $\varphi (N)$ and $N$ (where $N=pq$, $p$ and $q$ prime), then I can very easily get $p$ and $q$.

Suppose I have the encrypted message $c$. I want to get the exponent $d$ such that $c^d \pmod N$ is the original message $m,$ without knowing $e.$

I know that it is theoretically possible to go through all the exponents from $1$ to $\varphi (N)$, and then see if the resulting message makes sense. But since I know $p$ and $q$ and $N$, I think there should be a better way than brute force.

I don't know if trying to factor $\varphi (N)$ is that much easier than trying to factor $N$? That means that even though not all numbers between $1$ and $\varphi (N)$ will have inverses (since they will not all be relatively prime to $\varphi (N)$) I won't know based on the information I have.

Is there a better approach to breaking the encryption?

Answer 1

Problem summary: in textbook RSA, it is given $N$, $\phi(N)$, and a ciphertext $c$. It is wanted the plaintext message $m$ and a private exponent $d$.

If $e$ or $m$ was random, that would be infeasible. But usually, $e$ is small thus guessable, and $m$ is highly redundant/recognizable. Thus we can try to compute $$\begin{align} d_e&=e^{-1}\bmod\phi(N)\\ m_e&=c^{d_e}\bmod N \end{align}$$ for various small values of $e$ coprime with $\phi(N)$, and see which $m_e$ makes sense. Computing an $m_e$ has moderate cost, comparable to a normal decryption.

I'd first try $e=F_i=2^{(2^i)}+1$ for $i\in[0,4]$ (the Fermat primes, with $F_4=65537$ and $F_0=3$ very common). Then we can try (other) small odd integer $e>1$, including the popular $43$. I've also seen $e=2^{F_i}+1$ ($i\le3$), apparently due to a coding error.

If we find that a candidate $e$ is not coprime with $\phi(n)$, we can increase it by $2$ until it does, because some key generators do just that.