1.4. Roadmap		19
			Security level (bits)
	80	112	128	192	256
	(SKIPJACK) (Triple-DES) (AES-Small) (AES-Medium) (AES-Large)
DL parameter q	160	224	256	384	512
EC parameter n
RSA modulus n	1024	2048	3072	8192	15360
DL modulus p

Table 1.1. RSA, DL and EC key sizes for equivalent security levels. Bitlengths are given for the DL parameter q and the EC parameter n, and the RSA modulus n and the DL modulus p, respectively.

the sieving stage, the size of the matrix, and the difficulty in parallelizing the matrix stage, while these factors are not present in the analysis of Pollard’s rho algorithm. It is possible to provide cost-equivalent key sizes that take into account the full cost of the algorithms—that is, both the running time as well as the cost to build or otherwise acquire the necessary hardware. However, such costs are difficult to estimate with a reasonable degree of precision. Moreover, recent work has shown that the full cost of the sieving and matrix stages can be significantly reduced by building customized hardware. It therefore seems prudent to take a conservative approach and only use time as the measure of efficiency for the NFS and Pollard’s rho algorithms.

The comparisons in Table 1.1 demonstrate that smaller parameters can be used in elliptic curve cryptography (ECC) than with RSA and DL systems at a given security level. The difference in parameter sizes is especially pronounced for higher security levels. The advantages that can be gained from smaller parameters include speed (faster computations) and smaller keys and certificates. In particular, private-key operations (such as signature generation and decryption) for ECC are many times more efficient than RSA and DL private-key operations. Public-key operations (such as signature verification and encryption) for ECC are many times more efficient than for DL systems. Public-key operations for RSA are expected to be somewhat faster than for ECC if a small encryption exponent e (such as e = 3 or e = 216 + 1) is selected for RSA. The advantages offered by ECC can be important in environments where processing power, storage, bandwidth, or power consumption is constrained.

1.4Roadmap

Before implementing an elliptic curve system, several selections have to be made concerning the finite field, elliptic curve, and cryptographic protocol:

1.a finite field, a representation for the field elements, and algorithms for performing field arithmetic;

201. Introduction and Overview

2.an elliptic curve, a representation for the elliptic curve points, and algorithms for performing elliptic curve arithmetic; and

3.a protocol, and algorithms for performing protocol arithmetic.

There are many factors that can influence the choices made. All of these must be considered simultaneously in order to arrive at the best solution for a particular application. Relevant factors include security considerations, application platform (software or hardware), constraints of the particular computing environment (e.g., processing speed, code size (ROM), memory size (RAM), gate count, power consumption), and constraints of the particular communications environment (e.g., bandwidth, response time).

Not surprisingly, it is difficult, if not impossible, to decide on a single “best” set of choices. For example, the optimal choices for a workstation application can be quite different from the optimal choices for a smart card application. The purpose of this book is to provide security practitioners with a comprehensive account of the various implementation and security considerations for elliptic curve cryptography, so that informed decisions of the most suitable options can be made for particular applications.

The remainder of the book is organized as follows. Chapter 2 gives a brief introduction to finite fields. It then presents algorithms that are well-suited for software implementation of the arithmetic operations in three kinds of finite fields—prime fields, binary fields and optimal extension fields.

Chapter 3 provides a brief introduction to elliptic curves, and presents different methods for representing points and for performing elliptic curve arithmetic. Also considered are techniques for accelerating the arithmetic on Koblitz curves and other elliptic curves admitting efficiently-computable endomorphisms.

Chapter 4 describes elliptic curve protocols for digital signatures, public-key encryption and key establishment, and considers the generation and validation of domain parameters and key pairs. The state-of-the-art in algorithms for solving the elliptic curve discrete logarithm problem are surveyed.

Chapter 5 considers selected engineering aspects of implementing elliptic curve cryptography in software and hardware. Also examined are side-channel attacks where an adversary exploits information leaked by cryptographic devices, including electromagnetic radiation, power consumption, and error messages.

The appendices present some information that may be useful to implementors. Appendix A presents specific examples of elliptic curve domain parameters that are suitable for cryptographic use. Appendix B summarizes the important standards that describe elliptic curve mechanisms. Appendix C lists selected software tools that are available for performing relevant number-theoretic calculations.

1.5. Notes and further references

21

1.5Notes and further references

§1.1

Popular books on modern cryptography include those of Schneier [409], Menezes, van Oorschot and Vanstone [319], Stinson [454], and Ferguson and Schneier [136]. These books describe the basic symmetric-key and public-key mechanisms outlined in §1.1 including symmetric-key encryption schemes, MAC algorithms, public-key encryption schemes, and digital signature schemes. Practical considerations with deploying public-key cryptography on a large scale are discussed in the books of Ford and Baum [145], Adams and Lloyd [2], and Housley and Polk [200].

§1.2

The notion of public-key cryptography was introduced by Diffie and Hellman [121] and independently by Merkle [321]. A lucid account of its early history and development is given by Diffie [120]; for a popular narrative, see Levy’s book [290]. Diffie and Hellman presented their key agreement algorithm using exponentiation in the multiplicative group of the integers modulo a prime, and described public-key encryption and digital signature schemes using generic trapdoor one-way functions. The first concrete realization of a public-key encryption scheme was the knapsack scheme of Merkle and Hellman [322]. This scheme, and its many variants that have been proposed, have been shown to be insecure.

The RSA public-key encryption and signature schemes are due to Rivest, Shamir and Adleman [391].

ElGamal [131] was the first to propose public-key encryption and signature schemes based on the hardness of the discrete logarithm problem. The Digital Signature Algorithm, specified in FIPS 186 [139], was invented by Kravitz [268]. Smith and Skinner [443], Gong and Harn [176], and Lenstra and Verheul [283] showed, respectively, how the elements of the subgroup of order p + 1 of F p2 , the subgroup of order p2 + p + 1 of F p3 , and the subgroup of order p2 − p + 1 of F p6 , can be compactly represented. In their systems, more commonly known as LUC, GH, and XTR, respectively, subgroup elements have representations that are smaller than the representations of field elements by factors of 2, 1.5 and 3, respectively.

Koblitz [250] and Miller [325] in 1985 independently proposed using the group of points on an elliptic curve defined over a finite field to devise discrete logarithm cryptographic schemes. Two books devoted to the study of elliptic curve cryptography are those of Menezes [313] and Blake, Seroussi and Smart [49] published in 1993 and 1999, respectively. The books by Enge [132] and Washington [474] focus on the mathematics relevant to elliptic curve cryptography.

Other applications of elliptic curves include the integer factorization algorithm of Lenstra [285] which is notable for its ability to quickly find any small prime factors of an integer, the primality proving algorithm of Goldwasser and Kilian [173], and the

22 1. Introduction and Overview

pseudorandom bit generators proposed by Kaliski [233]. Koyama, Maurer, Okamoto and Vanstone [267] showed how elliptic curves defined over the integers modulo a composite integer n could be used to design RSA-like cryptographic schemes where the order of the elliptic curve group is the trapdoor. The hardness of factoring n is necessary for these schemes to be secure, and hence n should be the same bitlength as the modulus used in RSA systems. The work of several people including Kurosawa, Okada and Tsujii [273], Pinch [374], Kaliski [236] and Bleichenbacher [52] has shown that these elliptic curve analogues offer no significant advantages over their RSA counterparts.

There have been many other proposals for using finite groups in discrete logarithm cryptographic schemes. These include the group of units of the integers modulo a composite integer by McCurley [310], the jacobian of a hyperelliptic curve over a finite field by Koblitz [251], the jacobian of a superelliptic curve over a finite field by Galbraith, Paulus and Smart [157], and the class group of an imaginary quadratic number field by Buchmann and Williams [80]. Buchmann and Williams [81] (see also Scheidler, Buchmann and Williams [405]) showed how a real quadratic number field which yields a structure that is ‘almost’ a group can be used to design discrete logarithm schemes. Analogous structures for real quadratic congruence function fields were studied by Scheidler, Stein and Williams [406], and M¨uller, Vanstone and Zuccherato [336].

§1.3

The number field sieve (NFS) for factoring integers was first proposed by Pollard [380], and is described in the book edited by Lenstra and Lenstra [280]. Cavallar et al. [87] report on their factorization using the NFS of a 512-bit RSA modulus.

Pollard’s rho algorithm is due to Pollard [379]. The number field sieve (NFS) for computing discrete logarithms in prime fields was proposed by Gordon [178] and improved by Schirokauer [408]. Joux and Lercier [228] discuss further improvements that were used in their computation in 2001 of discrete logarithms in a 397-bit (120-decimal digit) prime field. The fastest algorithm for computing discrete logarithms in binary fields is due to Coppersmith [102]. The algorithm was implemented by Thom´e [460] who succeeded in 2001 in computing logarithms in the 607-bit field F2607 .

The Certicom ECCp-109 challenge [88] was solved in 2002 by a team of contributors led by Chris Monico. The method used was the parallelized version of Pollard’s rho algorithm as proposed by van Oorschot and Wiener [463]. The ECCp-109 challenge asked for the solution of an ECDLP instance in an elliptic curve defined over a 109-bit prime field. The effort took 549 days and had contributions from over 10,000 workstations on the Internet.

The equivalent key sizes for ECC and DSA parameters in Table 1.1 are from FIPS 186- 2 [140] and NIST Special Publication 800-56 [342]. These comparisons are generally in agreement with those of Lenstra and Verheul [284] and Lenstra [279], who also consider cost-equivalent key sizes. Customized hardware designs for lowering the full

1.5. Notes and further references

23

cost of the matrix stage were proposed and analyzed by Bernstein [41], Wiener [481], and Lenstra, Shamir, Tomlinson and Tromer [282]. Customized hardware designs for lowering the full cost of sieving were proposed by Shamir [421] (see also Lenstra and Shamir [281]), Geiselmann and Steinwandt [169], and Shamir and Tromer [423]. Shamir and Tromer [423] estimate that the sieving stage for a 1024-bit RSA modulus can be completed in less than a year by a machine that would cost about US $10 million to build, and that the matrix stage is easier.

§1.4

Readers can stay abreast of the latest developments in elliptic curve cryptography and related areas by studying the proceedings of the annual cryptography conferences including ASIACRYPT, CRYPTO, EUROCRYPT, INDOCRYPT, the Workshop on Cryptographic Hardware and Embedded Systems (CHES), the International Workshop on Practice and Theory in Public Key Cryptography (PKC), and the biennial Algorithmic Number Theory Symposium (ANTS). The proceedings of all these conferences are published by Springer-Verlag in their Lecture Notes in Computer Science series, and are conveniently available online at http://link.springer.de/link/service/series/0558/. Another important repository for the latest research articles in cryptography is the Cryptology ePrint Archive website at http://eprint.iacr.org/.

This page intentionally left blank