 |
 |
 |
|
 |
 |
 |
 |
|
 |
 |
 |
 |
 |
 |
 |
1 Introduction
Since the invention of public-key cryptography in 1976 by Whitfield Diffie and Martin Hellman, numerous public-key cryptographic systems have been proposed. All of these systems rely on the difficulty of a mathematical problem for their security.
Over the years, many of the proposed public-key cryptographic systems have been broken, and many others have been demonstrated to be impractical. Today, only three types of systems should be considered both secure and efficient. Examples of such systems, classified according to the mathematical problem on which they are based, are:
1. Integer factorization problem (IFP): RSA and Rabin-Williams.
2. Discrete logarithm problem (DLP): the U.S. government's Digital Signature Algorithm (DSA), the Diffie-Hellman and MQV key agreement schemes, the ElGamal encryption and signature schemes, and the Schnorr and Nyberg-Rueppel signature schemes.
3. Elliptic curve discrete logarithm problem (ECDLP): the elliptic curve analog of the DSA (ECDSA), and the elliptic curve analogs of the Diffie-Hellman and MQV key agreement schemes, the ElGamal encryption and signature schemes, and the Schnorr and Nyberg-Rueppel signature schemes.
None of these problems have been proven to be intractable (i.e., difficult to solve in an efficient manner). Rather, they are believed to be intractable because years of intensive study by leading mathematicians and computer scientists around the world has failed to yield efficient algorithms for solving them. As more effort is expended over time in studying and understanding these problems, our confidence in the security of the corresponding cryptographic systems will continue to grow.
1.2 Elliptic curve cryptosystems
Elliptic curve cryptosystems (ECC) were proposed independently in 1985 by Victor Miller [Miller] and Neal Koblitz [Koblitz]. At the time, both Miller and Koblitz regarded the concept of ECC as mathematically elegant, however they felt that its implementation would be impractical. Since 1985, ECC has received intense scrutiny from cryptographers, mathematicians, and computer scientists around the world. On the one hand, the fact that no significant weaknesses have been found has led to high confidence in the security of ECC. On the other hand, great strides have been made in improving the efficiency of the system, to the extent that today ECC is not just practical, but it is the most efficient public-key system known.
The primary reason for the attractiveness of ECC over systems such as RSA and DSA is that the best algorithm known for solving the underlying mathematical problem (namely, the ECDLP) takes fully exponential time. In contrast, subexponential-time algorithms are known for underlying mathematical problems on which RSA and DSA are based, namely the integer factorization (IFP) and the discrete logarithm (DLP) problems. This means that the algorithms for solving the ECDLP become infeasible much more rapidly as the problem size increases than those algorithms for the IFP and DLP. For this reason, ECC offers security equivalent to RSA and DSA while using far smaller key sizes.
The attractiveness of ECC will increase relative to other public-key cryptosystems as computing power improvements force a general increase in the key size. The benefits of this higher-strength-per-bit include:
- higher speeds,
- lower power consumption,
- bandwidth savings,
- storage efficiencies, and
- smaller certificates.
These advantages are particularly beneficial in applications where bandwidth, processing capacity, power availability, or storage are constrained. Such applications include:
- chip cards,
- electronic commerce systems,
- web servers,
- cellular telephones, and
- pagers.
The objectives of the Certicom ECC Challenge are the following:
1. To increase the cryptographic community's understanding of and appreciation of the difficulty for the ECDLP.
2. To confirm comparisons of the security levels of systems such as ECC, RSA and DSA that have been made based primarily on theoretical considerations.
3. To provide information on how users of elliptic curve public-key cryptosystems should select suitable key lengths for a desired level of security.
4. To determine whether there is any significant difference in the difficulty of the ECDLP for elliptic curves over F2m and the ECDLP for elliptic curves over Fp.
5. To determine whether there is any significant difference in the difficulty of the ECDLP for random elliptic curves over F2m and the ECDLP for Koblitz curves.
6. To encourage and stimulate research in computational and algorithmic number theory and, in particular, the study of the ECDLP.
Copyright © Certicom Corp., 1997-2000. All rights reserved.
Information subject to change. http://www.certicom.com