Attacking the Elliptic Curve Discrete Logarithm Problem
This thesis by Matthew Musson was defended successfully in an oral examination
on March 28th, 2006.

-Attacking the Discrete Logarithm Problem
- Elliptic Curves and Other Essentials
-Attacking the Elliptic Curve Discrete Logarithm Problem
- Generating Cryptographically Strong Elliptic Curves


Introduced to cryptography in 1985, elliptic curves are quickly being adapted for
cryptographic purposes. Elliptic curve cryptography is quickly becoming a leader in
the industry, and is challenging other cryptosystems such as RSA and DSA to become
the industrial standard; this is due to an increase in speed during implementation, the
use of less memory, and smaller key sizes. Another advantage of such a cryptosystem
lies in the difficulty of solving the Elliptic Curve Discrete Log Problem (ECDLP). If
an elliptic curve is chosen with some care, the ECDLP is believed to be infeasible,
even with today's computational power. On the other hand, this obstacle has not
deterred those in their attempts to crack elliptic curve cryptosystems. A multitude
of attacks have been developed, tested, and analyzed when attacking the ECDLP.
For the most part the ECDLP has withstood all attempts; however, in some special
cases the problem is actually quite easy. It is simply these cases that must be avoided
when building such a cryptosystem.
Using elliptic curves presents a great advantage in a few areas. For instance,
compared to RSA cryptosystems, elliptic curve based systems require less memory;
for example, a key size of 4096 bits for RSA gives the same level of security as 313
bits in an elliptic curve system [5]. Also, using a PalmPilot, generating a 512-bit RSA
1
key takes around 3.4 minutes, while generating an equivalent 163-bit ECC-DSA key
takes 0.597 seconds [87, 159]. Immediately we begin to see the advantages of using
elliptic curves, especially on a small hand-held devices with little computing power.
It is clear that this now gives us the advantage of setting up schemes that require
smaller chip sizes, use less memory, require less resources to run, require less power
consumption, etc; and can be placed in small electronic devices, such as smart cards
and cell phones.
Many elliptic curve cryptosystems take advantage of what is known as the ECDLP.
Analogous to the Discrete Logarithm Problem (DLP) over a finite field F×p
, the
ECDLP is the following problem: given two points P and Q on an elliptic curve
E defined over a field Fq, where q is prime or a prime power, if P = [m]Q for some
m 2 Z, determine m. Schemes and protocols such as the Deffie-Hellman key exchange,
Massey-Omura encryption, El-Gamal public key encryption and El-Gamal
digital signatures and even the Elliptic Curve Digital Signature Algorithm(ECDSA),
all use the fact that attempting to solve the ECDLP is a difficult, if not intractable,
problem. In fact it is believed that the ECDLP is as difficult if not more so than
solving the DLP over Fp [5].
As mentioned although the ECDLP is thought to be an intractable problem, it
has not stopped people attempting to attack such a cryptosystem. Various attacks
have been devised, tested and analyzed by many leading mathematicians over the
years, in attempts to find weaknesses in elliptic curve cryptosystems. Some have
been partially successful, while others have not. The ECDLP has been shown to be
easily solved for the following situations:
2
1. If #E(Fp)= p + 1 (the supersingular case) then the ECDLP can be reduced to
the DLP on the multiplicative group of the finite field with pk elements. This is practical if k is not too large.
2. If #E(Fp) = p (the anomalous case) then the ECDLP can be reduced to simple
addition in Fp, essentially by lifting the curve modulo p2.
3. If #E(Fp) is divisible by only small primes, then one can use the Pohlig-Hellman method which solves the problem in time O(p p0), where p0 is the largest prime divisor of E(Fp). In each of these three cases the underlying curve can easily be modified so as to thwart each attack. For example if we had a curve for which our point P had large prime order, that is [m]P = O, for a large prime m, then the Pohlig-Hellman method becomes impractical.
The purpose of this thesis is to provide a detailed examination of the leading attacks against the ECDLP, and to use the knowledge of these attacks in an attempt to generate cryptographically strong elliptic curves.