Cryptography Reference
In-Depth Information
7.6
ELLIPTIC CURVE CRYPTOGRAPHY
Most public key cryptosystems get their security from the assumed intractability
of inverting a one-way function (as discussed earlier). Against this background, it
is important to note that inverting a one-way function is not necessarily equally
difficult in all algebraic structures one may think of. If we look at inverting the
discrete exponentiation function in
Z p , then there are known algorithms that are sub-
exponential. This need not be the case in all possible groups (in which the function
is assumed to be one way). In fact, ECC has become popular (and important)
mainly because groups have been found in which subexponential algorithms to
invert the discrete exponentiation function (i.e., compute discrete logarithms) are
not known to exist. 7 This basically means that one has to use a general-purpose (and
exponential-time) algorithm to compute discrete logarithms and break the security
of the corresponding public key cryptosystem accordingly. Note, however, that it is
not known whether subexponential algorithms in these groups exist; we simply don't
know them.
The fact that subexponential algorithms are not known to exist has the positive
side effect (from the cryptographer's viewpoint) that the resulting elliptic curve cryp-
tosystems are equally secure with smaller key sizes than their conventional counter-
parts. This is important for implementations in which key sizes and performance are
important issues (e.g., smartcards). For example, to reach the security level of 1,024
(2,048) bits in a conventional public key cryptosystem (e.g., RSA), it is estimated
that 163 (224) bits are sufficient for an elliptic curve cryptosystem (e.g., [17]). This
is a nonnegligible factor that can speed up implementations considerably.
Most elliptic curve cryptosystems are based on the elliptic curve discrete
logarithm problem (ECDLP) in such a group. Similar to the DLP, the ECDLP can
be defined as suggested in Definition 7.13. Again, the ECDLP is assumed to be
computationally intractable.
Definition 7.13 (Elliptic Curve Discrete Logarithm Problem) Let E (
F q ) be an
elliptic curve over
F q , P be a point on E (
F q ) of order n , and Q be another point
on E (
F q ) . The ECDLP is to determine an integer x (with 0
x<n ), such that
Q = xP .
Based on the intractability assumption of the ECDLP, Neal Koblitz [18] and
Victor Miller [19] independently proposed using elliptic curves to implement public
key cryptosystems based on the DLP. This proposal dates back to the mid 1980s,
and since then many public key cryptosystems have been reformulated in an elliptic
7
An interesting online tutorial about elliptic curves in general, and ECC in particular, is available at
http://www.certicom.com/resources/ecc tutorial/ecc tutorial.html.
Search WWH ::




Custom Search