Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)

share|improve this question
    
What is the point of recovering a public exponent ? O.o – Biv Mar 21 at 16:30
    
That is not the question. Just assume it is not public ;) edit: I edited the question to clarify. – Blub Mar 21 at 16:32
up vote 9 down vote accepted

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$)

share|improve this answer
    
You probably mean 2048-bit and not "2-48-bit", right? – malexmave Mar 21 at 16:52
1  
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. – Maarten Bodewes Mar 21 at 17:17
    
thanks guys, I guess then baby step giant step is best I can do. – Blub Mar 22 at 8:59

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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