2
$\begingroup$

An RSA key pair consists of the private key $(n,d)$ and a public key $(n,e)$ such that $de \equiv 1 \bmod{\lambda(n)} $.

Usually one chooses a small $e$ and computes $d$ by inverting it modulo $\lambda(n)$. This makes things computationally easy for the user of the public key, but makes it expensive to use the private key because $d$ is large (typically only a few bits shorter than $n$).

If one wants to shift computational cost from the private to the public side of the cryptosystem, would it be secure to select $d$ as, say, a random 128-bit number coprime to $\lambda(n)$ and then compute $e$ as its inverse instead of the usual way around?

$\endgroup$
1
  • $\begingroup$ If you can't use a different algorithm with faster signing/decryption, you could use multi-prime RSA and CRT. It's not a big speedup, but still nice if performance is really important. $\endgroup$ Mar 28, 2014 at 10:54

1 Answer 1

8
$\begingroup$

Selecting a small $d$ is known to be insecure.

Wiener has shown in 1990 that if $\log d \leq \frac14 \log N$, the private exponent $d$ can be reconstructed from the public key $(N,e)$.

If you're interested in making the private computational cost cheaper, then I would suggest that RSA is not the best solution; I would recommend you start looking at Elliptic Curve based solutions.

$\endgroup$
1
  • $\begingroup$ Wiener's attack is improved to $\log d\le0.292\log N$ by Dan Boneh and Glenn Durfee's Cryptanalysis of RSA with Private Key $d$ Less Than $N^{0.292}$. We don't know a safe bound, thus common wisdom is to choose $d$ from a small $e$, and not try to make $d$ particularly small. One non-proven but non-broken AFAIK way to speed-up RSA is to use the CRT with 128-bit $d_p$ and $d_q$, giving a speedup by a factor of about 8 for 2048-bit RSA (30 compared to use of $d$). $\endgroup$
    – fgrieu
    Apr 9 at 7:54

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.