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)

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

2 Answers 2

Reset to default
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$)

Improve this answer
$\endgroup$
3
  • $\begingroup$ You probably mean 2048-bit and not "2-48-bit", right? $\endgroup$
    – malexmave
    Commented Mar 21, 2016 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 ♦
    Commented Mar 21, 2016 at 17:17
  • $\begingroup$ thanks guys, I guess then baby step giant step is best I can do. $\endgroup$
    – Blub
    Commented Mar 22, 2016 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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