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?

  • $\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$ – CodesInChaos Mar 28 '14 at 10:54

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.

| improve this answer | |

Your Answer

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

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