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

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?

• I've edited your question to make it clear what you're asking. – kodlu Nov 9 '19 at 2:57
• What information do you have about $m$? If your knowledge is uniformly distributed among all possible values, then there is no way to distinguish one candidate value of $d$ from another. – Squeamish Ossifrage Nov 9 '19 at 3:04
• @SqueamishOssifrage I don't know anything about $m$. Is there a way to narrow down the choices for $d$ given that I can find $p$ and $q$? – Jess Nov 9 '19 at 3:32
• @Jess No. From the information you have, every one of the $\operatorname{lcm}(p-1,q-1)$ possible values for $(e,d)$ is equiprobable. If you narrowed $m$ down to a single possibility, you could compute $\log_c m$ (modulo $p$ and $q$ independently to accelerate it, and then combined to find it modulo $n$ with CRT). Similarly, if you knew a nonuniform probability distribution for $m$ that would induce a nonuniform probability distribution on $d = \log_c m$. But if as far as you know $m$ and $e$ are both uniformly distributed, then so is $d$. – Squeamish Ossifrage Nov 9 '19 at 3:34

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.