1
$\begingroup$

I'm wondering if it's possible to find the public exponent ($e$) with an example and the (rather small) values of $p$ and $q$ given.

Currently the only option I found is bruteforcing this value, but this can be very slow for a large $e$.

And if there is no perfect technique, is there a way to limit the amount of options significantly?

Is it possible to find $e$ with $p$, $q$ and an example encrypted message + answer given?

|improve this question
$\endgroup$
  • 1
    $\begingroup$ There's an old answer that says discrete log in the composite modulus case is as difficult as it is in the prime case, so probably not. You can at least precompute all the powers of 2 modulii of your message and then just test combinations of them. $\endgroup$ – Rup May 23 at 15:10
  • 2
    $\begingroup$ Possible duplicate of Why does a non-prime DH modulus creates a "NOBUS" backdoor $\endgroup$ – Squeamish Ossifrage May 23 at 22:57
  • $\begingroup$ @SqueamishOssifrage As the question is explicitly about RSA you should at least indicate why you think this duplicates the other question, please. $\endgroup$ – Maarten Bodewes♦ May 26 at 15:51
  • 1
    $\begingroup$ The question is how to compute a discrete log (find $e$ given $x^e$) modulo a composite ($pq$). $\endgroup$ – Squeamish Ossifrage May 26 at 15:52

Your Answer

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

Browse other questions tagged or ask your own question.