Elliptic Curve Cryptosystem

Original from http://www.sr3.t.u-tokyo.ac.jp/~kunihiro/crypto-detail/ellip.html
RSA scheme, ElGamal scheme and Diffie-Hellman key exchange scheme are based on operations over a prime field or a residue class ring. Difficulty in cryptanalysis depends on intractability of factorization or discrete-log problem. RSA scheme has fault that RSA with low exponent e, such as 3 or 5, is easily broken using Hasted Attack.

On the other hand, cryptosystems based on a finite abelian group defined by an elliptic curve over a finite field are proposed. RSA-type, ElGamal-type, Diffie-Hellman-type scheme are constructed using this group. Basically these schemes depend on difficulty in factorization or discrete-log problem. However, it is believed that cryptosystems based on elliptic curve are more secure because solving discrete-log problem over this group is more difficult than solving one over a residue class ring. And because one can not use Hasted Attack directly to this cryptosystems, one can not break RSA-type scheme with even low exponents. However this cryptosystem has a fault to take more time to encrypt and decrypt than previous systems.

One can construct cryptosystems based on not only an elliptic curve but also arbitrary algebraic curves. But it is believed that these systems are not practical for the complexity of group operations.


These cryptosystems require more time to encrypt or decrypt than previous systems.