4
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes ♦
    Commented May 25, 2015 at 15:37
  • $\begingroup$ 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"? $\endgroup$
    – SEJPM
    Commented May 25, 2015 at 15:47
  • $\begingroup$ 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. $\endgroup$
    – SEJPM
    Commented May 25, 2015 at 16:02
  • $\begingroup$ @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. $\endgroup$
    – Maarten Bodewes ♦
    Commented May 25, 2015 at 16:04
  • 2
    $\begingroup$ 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$ $\endgroup$
    – SEJPM
    Commented May 25, 2015 at 16:24

1 Answer 1

Reset to default
3
$\begingroup$

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$.
Improve this answer
$\endgroup$
15
  • $\begingroup$ Performing $m^d (\mod n)$ is much slower on my Java runtime than executing the entire Wiener attack :) $\endgroup$
    – Maarten Bodewes ♦
    Commented May 25, 2015 at 17:33
  • 1
    $\begingroup$ 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$. $\endgroup$
    – fgrieu ♦
    Commented May 25, 2015 at 17:37
  • 1
    $\begingroup$ 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 $\endgroup$
    – poncho
    Commented May 25, 2015 at 18:13
  • $\begingroup$ @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? $\endgroup$
    – Maarten Bodewes ♦
    Commented May 25, 2015 at 18:35
  • 1
    $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes ♦
    Commented May 25, 2015 at 20:51

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.