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?

  • 1
    $\begingroup$ I've edited your question to make it clear what you're asking. $\endgroup$
    – kodlu
    Nov 9 '19 at 2:57
  • $\begingroup$ 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. $\endgroup$ Nov 9 '19 at 3:04
  • $\begingroup$ @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$? $\endgroup$
    – Jess
    Nov 9 '19 at 3:32
  • 3
    $\begingroup$ @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$. $\endgroup$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.