A Survey of Elliptic Curve Cryptosystems, Part I: Introductory
San C. Vo · 2003
The theory of elliptic curves is a classical topic in many branches of algebra and number theory, but recently it is receiving more attention in cryptography. An elliptic curve is a two-dimensional (planar) curve defined by an equation involving a cubic power of coordinate x and a square power of coordinate y. One class of these curves is elliptic curves over finite fields, also called Galois fields. These elliptic curves are finite groups with special structures, which can play naturally, and even more flexibly, the roles of the modulus groups in the discrete logarithm problems. Elliptic curves have been used actively in designing many mathematical, computational and cryptographic algorithms, such as integer factoring, primality proving, public key cryptosystems and pseudo-random number generators, etc. Essentially, elliptic curve cryptosystems promise a better future for cryptography: more security against powerful attacks in the era of computing capability. Many research papers in Elliptic Curve Cryptography (ECC) have been published by researchers all over the world. However, the idea of using elliptic curves in cryptography is still considered a difficult concept and is neither widely accepted nor understood by typical technical people. The problem may stem from the fact that there is a large gap between the theoretical mathematics of elliptic curves and the applications of elliptic curves in cryptography. A large amount of ECC literature was collected and organized in the development of this survey on ECC. Part I (Introductory) of this survey gives a modest overview of how elliptic curves have been applied to public key cryptography. The objective is to introduce a bridge between the mathematical facts of elliptic curves and its application for cryptography. The document attempts to provide clear, intuitive and elementary explanations to guide a typical technical reader into the world of elliptic curve cryptography. However, basic knowledge of cryptography and abstract algebra, including group theory and number theory, would be helpful for readers in several technical areas. Part II of this survey, that will be developed, intends to focus more on practical implementations. The materials cover elliptic curves and their basic mathematical rules, the Elliptic Curve Discrete Logarithm Problem (ECDLP) and many typical attacks on ECDLP-based cryptosystems. Also included are descriptions of elliptic curve public key cryptosystems or schemes (encryption/decryption, digital signature, key agreement and key transport schemes). The document concludes with discussions of elliptic curve implementations, the security and advantages of ECC. It is hoped that this survey could provide readers good initial background on the path into the new and exciting area of elliptic curve cryptography, that is attracting more attention from cryptographers, computer scientists and researchers all over the world.