Finding public exponent e

I'm trying to create an algorithm to find the public exponent e given a plain (non-CRT) private key that doesn't include the public exponent, i.e. I've only got $n$ and $d$.

A question has already been asked how easy it would be to find the public key given a private key. The answer was that it was likely to be easier, but none of the answers specify a good algorithm for RSA.

What would be the most efficient algorithm for finding the public exponent for RSA given the private key?

• yes, I've got some ideas like checking the often used ones first and then check a simple encrypt/decrypt, but I would like the answers not to be influenced by my non-optimal ideas :) And yes, I am aware that this may be hard to do if the public exponent is very large, but this is not commonly the case. – Maarten Bodewes May 25 '15 at 15:37
• so does one know $n$, does one know $p,q$, does one know $\varphi(n)=(p-1)(q-1)$ or is it supposed to be "without modulus"? – SEJPM May 25 '15 at 15:47
• As calculating $e\equiv d^{-1} \pmod {\varphi(n)}$ would be too easy I guess a plain (non-CRT) private key consists solely of $(d,n)$. In this case all standard attacks against weak RSA private exponents would apply. – SEJPM May 25 '15 at 16:02
• @SOJPM Right, that's the problem. I've got $n$ and $d$. Note that $n$ and $d$ are supposed to have been correctly calculated. If I could calculate $p$ and $q$ then my problems would disappear, but $p$ and $q$ calculation from $n$ and $d$ seems to rely on $e$ being available. – Maarten Bodewes May 25 '15 at 16:04
• So you're in the exact same situation as if you would know $(e,n)$ and you would know that $d$ probably is rather small. There's no known algorithm to solve this problem fast in every circumstance, as this would mean you'd be able to break RSA. IMO the best route would be to try the most used $e$, like $3,17,2^{16}+1$, then brute-force the first $\approx 2^{32}$ ones and then try to apply Wieners's attack, if $log_2(e)<160$ – SEJPM May 25 '15 at 16:24

The fastest way to solve your problem instance is as outlined in the above comments.

First choose yourself a random message $m$ with $1<m<n-1$. Now compute $c\equiv m^d \pmod n$.

Try if any of the following equations holds, if an equation does hold you've found the public exponent $e$. $m \equiv c^3 \pmod n$
$m \equiv c^{17} \pmod n$
$m \equiv c^{65537} \pmod n$

If none of the above equations held you have two choices, based on the effort you're willing to spend and the probability that $e$ is rather small.

If you suspect $e<\frac{1}{3}N^{\frac{1}{4}}$, then you should use Wiener's attack on small decryption exponent RSA with the lost public exponent taking the role of the decryption exponent to find. Wikipedia explains the basics and Wiener's original attack.
As Maarten points out in the comments below this attack is very fast and consumes moderate amounts of memory.

If you think / know that $e<2^{40}$ and/or you're not willing to implement Wiener's attack you can use the following approach, as you can always come back to Wiener's attack in case you think that you've tried long enough.
The brute-force approach would work as follows ($i=3$, optimized using fgrieu's comment):

1. Set $c_m \gets (c * c) \bmod n$,
2. Check if $c \equiv m \pmod n$ or $c_m \equiv m \pmod n$, if the first holds, output 1, if the second holds, output 2.
3. Set $c_3 \gets (c * c_m) \bmod n$
4. Check if $c_{i}\equiv m \pmod n$ holds. If yes, output $i$
5. Set $c_{i+2}\gets (c_i*c_m) \bmod n$, goto step 3

If you can not apply Wiener's attack and you consider brute-force "way too inefficient" there are still two methods left:

1. Use your favorite factorization algorithm to factor $n$ and deduce $e$ from $(d,p,q)$
2. Use your favorite discrete logarithm algorithm to solve $c^e \equiv m \pmod n$ for $e$.
• Performing $m^d (\mod n)$ is much slower on my Java runtime than executing the entire Wiener attack :) – Maarten Bodewes May 25 '15 at 17:33
• In the brute-force algorithm, step 2, there's $m$ where $c$ is wanted. Also things can be sped up by a factor of two: set $c_1\gets c$; compute $c_2\gets c\cdot c\bmod n$; then repeatdly for odd $i$ increasing from $3$, compute $c_i=c_{i-2}\cdot c_2\bmod n$, until that's $m$, in which case output $i$ which is the desired $e$. – fgrieu May 25 '15 at 17:37
• Actually, if you think $2^{20} < e < 2^{40}$ is at all likely, then doing a Big Step/Little Step is feasible; for $n \approx 2^{20}$, you compute $m\cdot c^{-j}$ for odd $1 \le j < n$, and compute $c^{in}$ (for $0 \le i < n$), and scan the two lists for a common value; this checks all possible e's in the range $[1, n^2]$ in $O(n)$ time – poncho May 25 '15 at 18:13
• @poncho I might not be able to implement this using this description alone, but I'll look into it. I guess that for most keys $e$ is within $1..2^{16} + 1$. I may be able to use Big Step/Little Step for values larger than $2^{16} + 1$ as Wiener's attack seems to eat memory (which is OK for single fire tools, but not so nice if it is part of a library). Maybe this is more a separate answer than a comment? – Maarten Bodewes May 25 '15 at 18:35
• Java is very much based on 32 bit signed integers. But I was wrong, I just tested 2^64 - 59 and that one worked too. I mistook the number of iterations with the actual number. It was pretty fast (~1s on my aging laptop) for that number as well and used only about 40K of memory, so for all practical values of $e$ the Wiener attack should suffice. – Maarten Bodewes May 25 '15 at 20:51