11-08-2012, 02:50 PM
Guide to Elliptic Curve Cryptography
GuideToECC.pdf (Size: 2.56 MB / Downloads: 40)
Introduction and Overview
Elliptic curves have a rich and beautiful history, having been studied by mathematicians
for over a hundred years. They have been used to solve a diverse range of problems. One
example is the congruent number problem that asks for a classification of the positive
integers occurring as the area of some right-angled triangle, the lengths of whose sides
are rational numbers. Another example is proving Fermat’s Last Theorem which states
that the equation xn +yn = zn has no nonzero integer solutions for x, y and z when the
integer n is greater than 2.
In 1985, Neal Koblitz and Victor Miller independently proposed using elliptic curves
to design public-key cryptographic systems. Since then an abundance of research has
been published on the security and efficient implementation of elliptic curve cryptography.
In the late 1990’s, elliptic curve systems started receiving commercial acceptance
when accredited standards organizations specified elliptic curve protocols, and private
companies included these protocols in their security products.
The purpose of this chapter is to explain the advantages of public-key cryptography
over traditional symmetric-key cryptography, and, in particular, to expound the virtues
of elliptic curve cryptography. The exposition is at an introductory level. We provide
more detailed treatments of the security and efficient implementation of elliptic curve
systems in subsequent chapters.
We begin in §1.1 with a statement of the fundamental goals of cryptography and
a description of the essential differences between symmetric-key cryptography and
public-key cryptography. In §1.2, we review the RSA, discrete logarithm, and elliptic
curve families of public-key systems. These systems are compared in §1.3 in which
we explain the potential benefits offered by elliptic curve cryptography. A roadmap for
the remainder of this book is provided in §1.4. Finally, §1.5 contains references to the
cryptographic literature.
Cryptography basics
Cryptography is about the design and analysis of mathematical techniques that enable
secure communications in the presence of malicious adversaries.
Adversarial model
In order to model realistic threats faced by A and B, we generally assume that the
adversary E has considerable capabilities. In addition to being able to read all data
transmitted over the channel, E can modify transmitted data and inject her own data.
Moreover, E has significant computational resources at her disposal. Finally, complete
descriptions of the communications protocols and any cryptographic mechanisms
deployed (except for secret keying information) are known to E. The challenge to cryptographers
is to design mechanisms to secure the communications in the face of such
powerful adversaries.
Symmetric-key cryptography
Cryptographic systems can be broadly divided into two kinds. In symmetric-key
schemes, depicted in Figure 1.2(a), the communicating entities first agree upon keying
material that is both secret and authentic. Subsequently, they may use a symmetric-key
encryption scheme such as the Data Encryption Standard (DES), RC4, or the Advanced
Encryption Standard (AES) to achieve confidentiality. They may also use a message authentication
code (MAC) algorithm such as HMAC to achieve data integrity and data
origin authentication.
Public-key cryptography
In a public-key cryptographic scheme, a key pair is selected so that the problem of
deriving the private key from the corresponding public key is equivalent to solving
a computational problem that is believed to be intractable. Number-theoretic problems
whose intractability form the basis for the security of commonly used public-key
schemes are:
1. The integer factorization problem, whose hardness is essential for the security of
RSA public-key encryption and signature schemes.
2. The discrete logarithm problem, whose hardness is essential for the security of
the ElGamal public-key encryption and signature schemes and their variants such
as the Digital Signature Algorithm (DSA).
3. The elliptic curve discrete logarithm problem, whose hardness is essential for the
security of all elliptic curve cryptographic schemes.