Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  CodesInChaos Mar 28 at 10:54

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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