Elliptic Curve Cryptography
Elliptic curve cryptography makes use of properties of an elliptic curve for encryption. The shape ellipse is known to all of us. However elliptic curves are less popular. In layman's terms elliptic curves can be thought of as arcs of an ellipse. However this definition is not quite correct and we must turn to mathematics for explanation. An elliptic curve is a plane smooth continuous curve which has no sharp points and can be represented by the simple algebraic equation y2 = x3 + ax + b, where x and y are variables and a and b are parametric coefficients and real numbers. An elliptic curve should not be confused with an ellipse. An ellipse is a closed figure whereas an elliptical curve doesn't necessarily have to be closed.
An elliptic curve can be defined over a number of fields which include real numbers field, rational number field, complex number field or finite fields. It will have a different definition and hence different uses in different fields. For the purpose of elliptical curve cryptography, we are concerned with elliptical curves over finite fields. The use of elliptic curves in cryptography is based on the principle that an elliptic curve can be divided into a large number of small elements. Each of these elements has a unique logarithmic value. Imagine the element as a key and its corresponding value as a lock which can be opened by only that particular key. Elliptic Curve Cryptography (ECC) uses the element as a key which will open only one lock out of the large number of locks. Clearly finding such a lock for a particular key is very difficult. Similarly, due to the large number of elements and their corresponding values, it is nearly impossible to find out an element's discrete logarithmic value from a publicly known base point (element). The mathematics used for solving an elliptical curve depends on the field chosen. Modular arithmetic is used for prime fields and polynomial arithmetic is for binary fields.
Elliptic curves defined on finite field need slight modification to be effectively employed in ECC. A finite field includes real numbers. Working on an elliptic curve over real numbers is not as quick and concise due to the round off error. Hence, usable finite field for ECC are cryptographic operations divided into two categories- Prime field and Binary field. Each of these has a large but finite number of points and is suitable for cryptographic purposes.
ECC is advantageous over other public-key systems like RSA algorithm. The security offered by a large RSA algorithm based system can be achieved by an elliptic curve with significantly less number of elements and lower bit size. Apart from beefing up security, ECC also has a faster execution. The reason for this is housed in the fact that computers which operate on bitwise operations with binary numbers can perform moduli of numbers near powers of two much faster than other numbers. ECC requires smaller key sixe and is more flexible. In real life, ECC usage transforms into faster and smaller chips in cell phones, pagers and other electronic devices. National Institute of Standards and Technology (NIST) recommends a total of fifteen elliptic curves, out of which five are prime curves and ten binary.
Apart from the advantages, ECC also has a few drawbacks. It involves tougher mathematics and applications can be hard to explain to clients. It is also known to be vulnerable to a modified form of an algorithm called Shor's algorithm. Shor's algorithm which can be run on quantum computers can break down the publically known integral base point into its prime numbers. Thus, security of e-commerce and other systems running on ECC may be compromised. The current protection of ECC methods from Shor's algorithm comes from the fact that sufficiently large quantum computers have not yet become easily available. Also, in areas where smaller key sizes are the prime concern, Hyperelleptic cryptosystems score over ECC systems.
ECC has been employed in key exchange, message transmission, authentication and key exchange. Its notable commercial implementations include Sun Java System Web Server 7.0 and upwards, Java Card, Elliptic Curve Point Multiply and Verify Core. ECC has also been used in several open source software solutions like TinyECC, NaCl, Curve25519, NSS and many others.
ECC is being seen as the future of cryptography. Although cryptographic systems based on elliptic curves have already been used as an addition to pre-existing systems but their use was limited by poor usability and high cost. Many government and private organizations like Royal Holloway College, RSA laboratories, and National Security Agency are involved in research on ECC systems. In a few years from now, we may witness a complete replacement of existing cryptography systems by ECC.
