List of Tables

1.1	RSA, DL and EC key sizes for equivalent security levels . . . . . . . . .								19
2.1	OEF example parameters . . . . . . . . . . . . . . . . . . . . . . . . . .								62
2.2	Computational details for inversion in OEFs . . . . . . . . . . . . . . . .								68
2.3	Computational details for inversion in OEFs . . . . . . . . . . . . . . . .								68
3.1	Admissible orders of elliptic curves over F37 . . . . . . . . . . . . . . . .								83
3.2	Isomorphism classes of elliptic curves over F5 . . . . . . . . . . . . . . .								85
3.3	2	= x	3	x	+	b . . . . . . . . . . .			92
	Operation counts for arithmetic on y2			− 3 3			2	+ b . . . . . . . .
3.4	Operation counts for arithmetic on y	+ x y = x			+ ax				96

3.5Point addition cost in sliding versus window NAF methods . . . . . . . . 102

3.6 Operation counts for computing k P + l Q . . . . . . . . . . . . . . . . . 113

3.7Operation counts in comb and interleaving methods . . . . . . . . . . . . 113

3.8Koblitz curves with almost-prime group order . . . . . . . . . . . . . . . 115

3.9	Expressions for αu (for the Koblitz curve E0) . . . . . . . . . . . . . . .	121
3.10	Expressions for αu (for the Koblitz curve E1) . . . . . . . . . . . . . . .	122
3.11	Operation counts for point multiplication (random curve over F2163 ) . . .	140
3.12	Point multiplication costs for P-192 . . . . . . . . . . . . . . . . . . . .	143
3.13	Point multiplication costs for B-163 and K-163 . . . . . . . . . . . . . .	145
3.14	Point multiplication timings for P-192, B-163, and K-163 . . . . . . . . .	146
5.1	Partial history and features of the Intel IA-32 family of processors . . . .	207
5.2	Instruction latency/throughput for Pentium II/III vs Pentium 4 . . . . . .	208

5.3Timings for field arithmetic (binary vs prime vs OEF) . . . . . . . . . . . 220

5.4Timings for binary field arithmetic . . . . . . . . . . . . . . . . . . . . . 221

5.5	Timings for prime field arithmetic . . . . . . . . . . . . . . . . . . . . .	221
5.6	Multiplication and inversion times . . . . . . . . . . . . . . . . . . . . .	222
5.7	Multiplication times for the NIST prime p224 = 2224 − 296 + 1 . . . . . .	224
5.8	Priorities for hardware design criteria . . . . . . . . . . . . . . . . . . .	229
5.9	Operation counts for inversion via multiplication in binary fields . . . . .	238

xiv	List of Tables
A.1	Irreducible binary polynomials of degree m, 2 ≤ m ≤ 300. . . . . . . . .	259
A.2	Irreducible binary polynomials of degree m, 301 ≤ m ≤ 600. . . . . . . .	260
A.3	NIST-recommended random elliptic curves over prime fields. . . . . . . .	262
A.4	NIST-recommended random elliptic curves over binary fields. . . . . . .	264
A.5	NIST-recommended Koblitz curves over binary fields. . . . . . . . . . . .	265
B.1	ECC standards and draft standards . . . . . . . . . . . . . . . . . . . . .	268
B.2	URLs for standards bodies and working groups. . . . . . . . . . . . . . .	268

List of Figures

1.1	Basic communications model . . . . . . . . . . . . . . . . . . . . . . . .	2
1.2	Symmetric-key versus public-key cryptography . . . . . . . . . . . . . .	4
2.1	Representing a prime-field element as an array of words . . . . . . . . . .	29
2.2	Depth-2 splits for 224-bit integers (Karatsuba-Ofman multiplication) . . .	33
2.3	Depth-2 splits for 192-bit integers (Karatsuba-Ofman multiplication) . . .	34
2.4	Representing a binary-field element as an array of words . . . . . . . . .	47
2.5	Right-to-left comb method for polynomial multiplication . . . . . . . . .	49
2.6	Left-to-right comb method for polynomial multiplication . . . . . . . . .	49
2.7	Left-to-right comb method with windows of width w . . . . . . . . . . .	51
2.8	Squaring a binary polynomial . . . . . . . . . . . . . . . . . . . . . . . .	52
2.9	Reduction of a word modulo f (z) = z163 + z7 + z6 + z3 + 1 . . . . . . . .	54
3.1	ECDSA support modules . . . . . . . . . . . . . . . . . . . . . . . . . .	75
3.2	Elliptic curves over the real numbers . . . . . . . . . . . . . . . . . . . .	77
3.3	Geometric addition and doubling of elliptic curve points . . . . . . . . .	80

3.4Montgomery point multiplication . . . . . . . . . . . . . . . . . . . . . . 103

3.5 Fixed-base comb method for point multiplication . . . . . . . . . . . . . 107

3.6The exponent array in Lim-Lee combing methods . . . . . . . . . . . . . 108

3.7 Simultaneous point multiplication accumulation step . . . . . . . . . . . 109

3.8Interleaving with NAFs . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

4.1 Illustration of Pollard’s rho algorithm . . . . . . . . . . . . . . . . . . . 158

4.2Illustration of parallelized Pollard’s rho algorithm . . . . . . . . . . . . . 162

5.1Splitting of a 64-bit floating-point number . . . . . . . . . . . . . . . . . 211

5.2Hierarchy of operations in elliptic curve cryptographic schemes . . . . . . 226

5.3	Elliptic curve processor architecture . . . . . . . . . . . . . . . . . . . .	227
5.4	Most significant bit first (MSB) multiplier for F25 . . . . . . . . . . . . .	231
5.5	Least significant bit first (LSB) multiplier for F25 . . . . . . . . . . . . .	232

xvi List of Figures

5.6MSB multiplier with fixed reduction polynomial . . . . . . . . . . . . . . 232

5.7	MSB multiplier for fields F2m with 1 ≤ m ≤ 10 . . . . . . . . . . . . . .	233
5.8	MSB multiplier for fields F25 , F27 , and F210 . . . . . . . . . . . . . . . .	234

5.9Multiplicand in a 2-digit multiplier for F25 . . . . . . . . . . . . . . . . . 235

5.10	A 2-digit multiplier for F25 . . . . . . . . . . . . . . . . . . . . . . . . .	235
5.11	Squaring circuit for F27 with fixed reduction polynomial . . . . . . . . .	236
5.12	CMOS logic inverter . . . . . . . . . . . . . . . . . . . . . . . . . . . .	239

5.13Power trace for a sequence of addition and double operations . . . . . . . 240

5.14Power trace for SPA-resistant elliptic curve operations . . . . . . . . . . . 241

5.15OAEP encoding function . . . . . . . . . . . . . . . . . . . . . . . . . . 246

5.16OAEP decoding function . . . . . . . . . . . . . . . . . . . . . . . . . . 247