3
$\begingroup$

Is there a way to recover the public exponent e (assume in this case it is in fact not public) used in an encryption if I know the following:

  • Factorization of N : p and q
  • one plaintext m and its encryption c = m^e mod N

Obviously I can just bruteforce if e is small, but is there a more elegant way? (or just assume e is too large to simply bruteforce)

$\endgroup$
  • $\begingroup$ What is the point of recovering a public exponent ? O.o $\endgroup$ – Biv Mar 21 '16 at 16:30
  • $\begingroup$ That is not the question. Just assume it is not public ;) edit: I edited the question to clarify. $\endgroup$ – Blub Mar 21 '16 at 16:32
8
$\begingroup$

If $e$ is a random number, then knowledge of the factorization allows us to reduce the recovery operation to:

$$(c \bmod p) = (m \bmod p)^{e \bmod p-1} \pmod p$$ $$(c \bmod q) = (m \bmod q)^{e \bmod q-1} \pmod q$$

Solving both these discrete log problems will give us enough information on $e$ to efficiently recover it.

Now, while solving these two subproblems is easier than factoring $N$, or recovering $e$ without knowing the factorization, it is still nontrivial. If we assume that the RSA modulus was a 2048-bit key, then each of these subproblems is a 1024 bit discrete log problem; that's larger than any published result.

On the other hand, if we are allowed to assume that $e$ is small (but perhaps a bit larger than we can brute-force), there are more efficient methods than simply trying each possible $e$ value. For example, using the Baby Step Giant Step algorithm, you can efficiently check all possible values $e < 2^{61}$ with $2^{31}$ modular multiplications, and a few tens of Gigabytes of disk space. You don't even need to know the factorization of $n$ (however, it would make it a bit more efficient, as that would allow you to compute everything modulo $p$)

$\endgroup$
  • $\begingroup$ You probably mean 2048-bit and not "2-48-bit", right? $\endgroup$ – malexmave Mar 21 '16 at 16:52
  • 1
    $\begingroup$ Most e values are simply set to 0x10001, some are smaller than that and all the others I've met are the same size as the modulus, in which case you're out of luck. So I wonder if there is a practical use case other than to simply try all numbers of F4 (the fourth and highest Fermat prime found so far) and lower. $\endgroup$ – Maarten Bodewes Mar 21 '16 at 17:17
  • $\begingroup$ thanks guys, I guess then baby step giant step is best I can do. $\endgroup$ – Blub Mar 22 '16 at 8:59
0
$\begingroup$

If you really mean the public exponent, most likely, the exponent $e$ is small; in fact, it's usually one of $\{ 3, 17, 65537 \}$. Just calculate $m^e \mod N$ and check whether it equals $c$.

If you're trying to do this with the private exponent $d$, there's certainly no way you could guess $d$ in a reasonable time. You could do a discrete logarithm, as in poncho's answer, but this is probably infeasible as well.

However, it's probably still the case that $e$ is one of $\{ 3, 17, 65537 \}$. If $c$ is in fact $m^d \mod N$, flip the operation around and check to see whether $c^e \mod N = m$. This corresponds to the digital signature case.

Either way, if you can determine $e$, you can determine $d' = e^{-1} \mod \textrm{lcm}(p-1, q-1)$. The actual $d$ being used may be greater than that; any choice of $d = d' + k \textrm{ lcm}(p-1, q-1)$ for integer $k$ will function identically to $d'$ with RSA, so you can't determine exactly which is used.

$\endgroup$

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.