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.

In RSA, encryption time is usually much less than decryption time due to having a small public exponent. Can this be achieved in Elliptic Curve Crypto (ECC)?

share|improve this question

3 Answers 3

up vote 0 down vote accepted

No. You need one point multiplication. All point multiplications need roughly the same time; in implementations, which are hardened against timing attacks exactly the same time.

share|improve this answer

Actually, there is one way which you can achieve a similar effect: if you have some idle time beforehand, you can perform some of the work even before you know the message you'll encrypt (or possibly even before you know the public key you'll be sending to -- you will need to know the curve). This doesn't decrease the total amount of work; however it can decrease the amount you work you need to when you get the message (because you did some of that work beforehand).

For example, let us assume you use ECIES; there, you pick a random number $r$, and compute the point $rG$ (where $G$ is the curve generator). You can do this before you know either the message or the public key you'll be sending to.

Then, when you get the message and the public key $P$, then you compute $rP$, generate the symmetric keys, and encrypt and MAC the message using the symmetric keys; then you package up the values $rG$ and the symmetric ciphertext -- this part is about half the amount of work you'd need to do without precomputation.

Now, this as stated doesn't really address the question (because it doesn't make the work less than the decryption part) -- however, if you also knew the public key $P$ first, you could move the computation of $rP$ into the precomputation step as well, and that would make the remaining part of the encryption (which is just playing around with symmetric ciphers) significantly less than decryption.

share|improve this answer

In ECC the public key is the scalar product of the randomly chosen private key and the base point of the curve, so there is no direct equivalent to the public exponent. Everything that affects speed is part of the curve definition: e.g. the primes are usually chosen to be close to powers of two for speed.

The encrypter can also cache multiples of a point. Typically scalar multiplication is implemented as doublings and additions. Having $2^iB$ cached allows the encrypter to avoid calculating the doublings when multiplying $B$. In ECISE this allows the encrypter to save work, but not the decrypter who needs to use a point he didn't know beforehand.

share|improve this answer
1  
Actually, if you are going to use precomputed tables to speed point multiplications, there are far more intelligent ways (smaller tables and better speedup) than just caching $2^iB$ –  poncho May 29 at 15:07
    
@poncho: Maybe you'd like to mention some in your answer, since they seem to be on topic? I haven't really ever dived into actually implementing an elliptic curve from the ground up. –  otus May 29 at 15:15

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.