It is generally recognized that elliptic curve cryptography (ECC) can attain the same level of security as RSA with a shorter key length. This paper offers practical evidence of this claim. For both RSA and ECC, security depends on the intractability of a mathematical problem, namely the discrete logarithm problem for ECC (ECDLP) and the integer factorization problem (IFP) for RSA. To compare these two methods, the authors estimate the complexity of each one, in terms of the number of flops needed to solve an N-bit ECDLP or IFP problem in one year.

The fastest known algorithm for solving IFP is the general number field sieve (GNFS) method. For this method, the authors calculate complexities by estimating the values of the constants given in the formula for asymptotic complexity. Estimates are given for both limited and unlimited memory size. The fastest known method for solving ECDLP is the Pollard rho method. This is a probabilistic method in which a certain pseudo-random sequence is generated until a repetition (“collision”) is found. For this method, the authors estimate the number of iterations necessary for a collision to take place with 99 percent certainty.

Based on these estimates, the authors compare the strengths of IFP and ECDLP. A table is given listing the bit sizes of ECDLP and IFP that provide the same level of strength. For example, a 1024-bit IFP has approximately the same security as that of the 137-bit ECDLP over either prime or binary fields or for Koblitz curves.

This paper contains few new theoretic results, but contains many interesting estimates and comparisons of IFP and ECDLP, results due to the authors as well as to other sources, and should be of interest to both students and practitioners of public key cryptography. An extensive list of 53 references is given.