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.

There are elliptic curve variants of Diffie-Hellman, ElGamal, DSA and possibly other protocols/algorithms. I know that these elliptic curve variants have smaller key and ciphertext sizes which will make communications (or storage) more efficient.

Are there other advantages to the elliptic curve variants of these standard protocols/algorithms?

Specifically I am interested in speed and power consumption, but other potential advantages like resistance to side-channel attacks are also of interest.

share|improve this question
add comment

2 Answers

up vote 6 down vote accepted

Computations on elliptic curves are more efficient. Roughly speaking, when the base field has size $n$ (for DH/ElGamal/DSA, the size in bits of the modulus $p$; for elliptic curves, the size of the field for point coordinates) and a "security level" $t$ (e.g. $t = 80$ for "80-bit security" as can be expected when using a 160-bit subgroup and a 160-bit hash function), the computational cost of a private key operation (decryption, signature generation) is roughly $O(n^2t)$, both for the modular and the elliptic curve variants. The big-O notation hides a constant, which is about $10$: for the same $n$ and $t$, the elliptic curve variant will be 10 times slower than the older modular algorithm.

However, elliptic curves tolerate much lower $n$ for a given security level. Basically, for $t = 112$, we need $n = 2048$ for the modular algorithms, but $n = 224$ is sufficient for elliptic curves (these comparisons are always a bit subjective, see this site for details). Report the values in the formulas: even with the factor 10, the elliptic curve variant will be more than 8 times faster than the modular algorithm of comparable strength.

Another point is binary fields. When the implementation platform is a dedicated ASIC/FPGA, or even when the platform is a small CPU which does not offer a very optimized multiplication opcode (e.g. the ARM Cortex M0), then curves on binary fields give a huge implementation boost, especially Koblitz curves. It also has benefits for memory-constrained systems, see for instance this presentation. The "modular" algorithms cannot really benefit from binary field computations (it can be defined, but discrete logarithm on binary fields is easier than modulo a random prime, so a binary field variant of modular DH or ElGamal would require a $n$ twice larger, hence a four-fold slowdown).

share|improve this answer
add comment

Elliptic Curve Cryptography (ECC) is not known to be specifically more resistant to side channel attacks (of course the next question is more resistant than what).

  • This paper reviews power analysis side-channel attacks against ECC and countermeasures.

  • Given that ECC uses multiplication and many common implementations of the MUL instruction run in time dependent on input (x86 on intel fixed this on newer chips), there are probably some room for timing side channels on non-intel chips.

  • Or double ADD timing attacks:

"Since point doubling (P + P) requires slightly fewer processor arithmetic operations than arbitrary point addition (P + Q, P != Q) due to the ability to reduce the group law for P + P, the attacker can distinguish between these two cases, and the key can be reconstructed. This was one very concrete, simple example of how practical it is to attack an FPGA implementation with nothing more than an oscilloscope, although the countermeasures are easily implemented." - Pertinent Side Channel Attacks on Elliptic Curve Cryptographic Systems

share|improve this answer
add comment

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.