Cryptography Reference
In-Depth Information
curve setting. Examples include Diffie-Hellman, ElGamal, and DSA. Today, many
topics address ECC and elliptic curve cryptosystems in detail (e.g., [20-23]). You
may refer to any of these topics if you want to get more involved in elliptic curves
and ECC.
Since 1985, the ECDLP has received considerable attention from leading
mathematicians around the world. It is currently believed that the ECDLP is much
harder than integer factorization or DLP. More specifically, there is no algorithm
known that has a subexponential running time in the worst case. A few vulnera-
bilities and potential attacks should be considered with care and kept in mind when
elliptic curves are used. For example, it was shown that the ECDLP can be reduced to
the DLP in extension fields of
F
q
, where the index-calculus methods can be applied
[24]. However, this reduction algorithm is only efficient for a special class of elliptic
curves known as
supersingular curves
. Moreover, there is a simple test to ensure that
an elliptic curve is not supersingular and hence not vulnerable to this attack. Conse-
quently, it is possible to avoid them in the first place. Some other vulnerabilities and
potential attacks can be found in the literature.
A distinguishing feature of ECC is that each user may select a different elliptic
curve
E
(
F
q
)—even if all users use the same underlying finite field
F
q
.Froma
security viewpoint, this flexibility is advantageous (because the elliptic curve can be
changed periodically). From a practical viewpoint, however, this flexibility is also
disadvantageous (because it makes interoperability much more difficult and because
it has led to a situation in which the field of ECC is tied up in patents). Note that there
is (more or less) only one way to implement a conventional public key cryptosystem,
such as RSA, but usually many ways to implement an elliptic curve cryptosystem.
In fact, one can work with different finite fields, different elliptic curves over
these fields, and a wide variety of representations of the elements on these curves.
Each choice has advantages and disadvantages, and one can construct an efficient
curve for each application. Consequently, the relevant standardization bodies, such
as the Institute of Electrical and Electronics Engineers (IEEE),
8
ISO/IEC JTC1,
the American National Standards Institute (ANSI), and the National Institute of
Standards and Technology (NIST), are working hard to come up with ECC standards
and recommendations that are commonly accepted and widely deployed.
9
7.7
FINAL REMARKS
In this chapter, we elaborated on one-way functions and trapdoor functions. More
specifically, we defined the notion of a family of one-way functions or trapdoor
8
http://grouper.ieee.org/groups/1363
9
http://www.certicom.com/resources/standards/eccstandards.html
