Remarks on the Security of the Elliptic Curve Cryptosystem 3
Certicom
While the integer factorization problem has received some attention over the centuries from
well-known mathematicians like Fermat and Gauss, it is only in the past 20 years that significant
progress has been made towards its resolution. There are two main reasons for this phenomenon.
First, the invention of the RSA cryptosystem in 1978 stimulated many mathematicians to study
the problem. And second, high-speed computers became available for the implementation and
testing of sophisticated algorithms. Fermat and Gauss would have had little incentive for
inventing the number field sieve factoring algorithm (see Section 2.2) since this algorithm is
more cumbersome than trial division for the purpose of factoring integers by hand.
2.2 Known attacks
There are basically two types of factoring algorithms, special-purpose and general-purpose.
Special-purpose factoring algorithms attempt to exploit special features of the number n being
factored. In contrast, the running times of general-purpose factoring algorithms depend only on
the size of n.
One of the most powerful special-purpose factoring algorithms is the elliptic curve factoring
method (ECM) that was invented in 1985 by Hendrik Lenstra Jr. [16]. The running time of this
method depends on the size of the prime factors of n, and hence the algorithm tends to find small
factors first. The ECMNET project, started in January 1998 to find large factors by ECM, has
been successful in locating factors of 50 digits (166 bits) or more. The largest prime factor found
thus far by ECM is a 54-digit (180-bit) factor of a 127-digit (422-bit) number; the computation
was carried out by N. Lygeros and M. Mizony and reported on December 26, 1999.
Just prior to the development of the RSA cryptosystem, the best general-purpose factoring
algorithm was the continued fraction algorithm [19], which could factor numbers up to 40
decimal digits (133 bits). This algorithm was based on the idea of using a factor base of primes
and generating an associated set of linear equations whose solution ultimately led to a
factorization. This is the same idea underlying the best general-purpose algorithms used today:
the quadratic sieve (QS) and the number field sieve (NFS). Both these algorithms can be
easily parallelized to permit factoring on distributed networks of workstations. Large mainframe
computers or supercomputers are therefore not essential to factor large numbers.
The quadratic sieve was developed by Carl Pomerance in 1984 [25]. Initially, it was used to
factor numbers in the 70-decimal digit (233-bit) range. In 1994, it was used by a group of
researchers led by Arjen Lenstra [1] to factor the 129-decimal digit (429-bit) RSA challenge
number that was posed by Martin Gardner in 1977 [10]. The factorization was carried out in 8
months by about 1600 computers around the world. The total running time for the factorization
was estimated to be 5000 MIPS years.
The number field sieve as first developed in 1989 [15] works best on numbers of a special form.
The algorithm was used to factor the 155-decimal digit (513-bit) number 2
512
+ 1. It was
subsequently extended (see [3]) to a general-purpose factorization algorithm. While initially
thought to be slower in practice than the quadratic sieve for factoring integers having fewer than
150 decimal digits (500 bits), recent experiments have suggested that the NFS is indeed the
superior algorithm for factoring integers having at least 120 decimal digits (400 bits). In 1996, a
group led by Arjen Lenstra [4] used the NFS to factor a 130-decimal digit (432-bit) number. The
factorization was estimated to take less than 15% of the 5000 MIPS years that was required for
the factorization of the 129-decimal digit RSA challenge number. The authors concluded that