Guide to elliptic curve cryptography

Guide to Elliptic

Curve Cryptography

Darrel Hankerson

Alfred Menezes

Scott Vanstone

Springer

Guide to Elliptic Curve Cryptography

Springer

New York

Berlin

Heidelberg

Hong Kong

London

Milan

Paris

Tokyo

Darrel Hankerson

Alfred Menezes

Scott Vanstone

Guide to Elliptic

Curve Cryptography

With 38 Illustrations

Springer

Darrel Hankcrsnn

Department of Mathematics

Auburn University

Auhuni, Al. .36849-5107. USA

hankedr" 1

auburn, cdu

Scott Vanslone

Depart menl of Combinatorics and

Oplimi/.alion

University of Waterloo

Waterloo, Ontario. N2L 3Gl Canada

xavansUK"1

LI Waterloo.ea

Alfred Menezes

Departmet of Combinatories and

Optimization

University of Waterloo

Waterloo. Ontario, N2L 3G1 Canada

ajmeneze@

uwaterloo.ca

library of Congress Calaloging-in-Publication Data

Hankerson. Darrel R.

Guide to ellipti c curve cryptography / Darrel Hankerson, Alfred J. Menezes, Scott Vanstone.

p. cm.

Includes bibliographical references and index.

ISBN 0-387-95273-X (alk . paper)

1. Computer securiiy. 2. PuMic key cryptography. I. Vunsionc, Scott A,

11. Mene/.es. A. J. (Alfred J,) , 1965- III. Title,

QA76.9.A25H37 2003

005.8'(2-dc22 2003059137

ISBN 0-387-95273-X Printed un acid-free paper.

(c) 2004 Springer-Verlag New York, Inc.

All riglils reserved. This work may not Ix1

translated or copied in wimle or in pan without the written permission

ol'I he puhlishi-r I Springer-VL-rlag New York, Inc., 175 I-'ifth Avenue, New York, NY 10010,USA J, except for brief

excerpts in connection with reviews or scholarly analysis. Use in connection wit h any form of information storage

and reltrieval, electronic adaption , computer software, or by similar or dissimilar methodology now known 01

hereafter developed is forbidden.

The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not

identified as such, is not to be taken as an expression of opinion as to whedier or not they are subject to proprietary

rights.

Printed m the United States of America. (HAM )

987654321 SPIN 10832297

Springer-Vcrlag is a part of ' Springer science+Business Media

springeronline.com

Contents

List of Algorithms ix

List of Tables xiv

List of Figures xvi

Acronyms xvii

Preface xix

1 Introduction and Overview 1

1.1 Cryptography basics . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Public-key cryptography . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2.1 RSA systems . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2.2 Discrete logarithm systems . . . . . . . . . . . . . . . . . . . 8

1.2.3 Elliptic curve systems . . . . . . . . . . . . . . . . . . . . . 11

1.3 Why elliptic curve cryptography? . . . . . . . . . . . . . . . . . . . . 15

1.4 Roadmap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.5 Notes and further references . . . . . . . . . . . . . . . . . . . . . . 21

2 Finite Field Arithmetic 25

2.1 Introduction to finite fields . . . . . . . . . . . . . . . . . . . . . . . 25

2.2 Prime field arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.2.1 Addition and subtraction . . . . . . . . . . . . . . . . . . . . 30

2.2.2 Integer multiplication . . . . . . . . . . . . . . . . . . . . . . 31

2.2.3 Integer squaring . . . . . . . . . . . . . . . . . . . . . . . . 34

2.2.4 Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.2.5 Inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.2.6 NIST primes . . . . . . . . . . . . . . . . . . . . . . . . . . 44

vi Contents

2.3 Binary field arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 47

2.3.1 Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

2.3.2 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . 48

2.3.3 Polynomial multiplication . . . . . . . . . . . . . . . . . . . 48

2.3.4 Polynomial squaring . . . . . . . . . . . . . . . . . . . . . . 52

2.3.5 Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

2.3.6 Inversion and division . . . . . . . . . . . . . . . . . . . . . 57

2.4 Optimal extension field arithmetic . . . . . . . . . . . . . . . . . . . 62

2.4.1 Addition and subtraction . . . . . . . . . . . . . . . . . . . . 63

2.4.2 Multiplication and reduction . . . . . . . . . . . . . . . . . . 63

2.4.3 Inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

2.5 Notes and further references . . . . . . . . . . . . . . . . . . . . . . 69

3 Elliptic Curve Arithmetic 75

3.1 Introduction to elliptic curves . . . . . . . . . . . . . . . . . . . . . . 76

3.1.1 Simplified Weierstrass equations . . . . . . . . . . . . . . . . 78

3.1.2 Group law . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

3.1.3 Group order . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

3.1.4 Group structure . . . . . . . . . . . . . . . . . . . . . . . . . 83

3.1.5 Isomorphism classes . . . . . . . . . . . . . . . . . . . . . . 84

3.2 Point representation and the group law . . . . . . . . . . . . . . . . . 86

3.2.1 Projective coordinates . . . . . . . . . . . . . . . . . . . . . 86

3.2.2 The elliptic curve y2 = x3 +ax +b . . . . . . . . . . . . . . 89

3.2.3 The elliptic curve y2 + x y = x3 +ax2 +b . . . . . . . . . . . 93

3.3 Point multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

3.3.1 Unknown point . . . . . . . . . . . . . . . . . . . . . . . . . 96

3.3.2 Fixed point . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

3.3.3 Multiple point multiplication . . . . . . . . . . . . . . . . . . 109

3.4 Koblitz curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

3.4.1 The Frobenius map and the ring Z[τ ] . . . . . . . . . . . . . 114

3.4.2 Point multiplication . . . . . . . . . . . . . . . . . . . . . . . 119

3.5 Curves with efficiently computable endomorphisms . . . . . . . . . . 123

3.6 Point multiplication using halving . . . . . . . . . . . . . . . . . . . 129

3.6.1 Point halving . . . . . . . . . . . . . . . . . . . . . . . . . . 130

3.6.2 Performing point halving efficiently . . . . . . . . . . . . . . 132

3.6.3 Point multiplication . . . . . . . . . . . . . . . . . . . . . . . 137

3.7 Point multiplication costs . . . . . . . . . . . . . . . . . . . . . . . . 141

3.8 Notes and further references . . . . . . . . . . . . . . . . . . . . . . 147

Contents vii

4 Cryptographic Protocols 153

4.1 The elliptic curve discrete logarithm problem . . . . . . . . . . . . . 153

4.1.1 Pohlig-Hellman attack . . . . . . . . . . . . . . . . . . . . . 155

4.1.2 Pollard’s rho attack . . . . . . . . . . . . . . . . . . . . . . . 157

4.1.3 Index-calculus attacks . . . . . . . . . . . . . . . . . . . . . 165

4.1.4 Isomorphism attacks . . . . . . . . . . . . . . . . . . . . . . 168

4.1.5 Related problems . . . . . . . . . . . . . . . . . . . . . . . . 171

4.2 Domain parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

4.2.1 Domain parameter generation and validation . . . . . . . . . 173

4.2.2 Generating elliptic curves verifiably at random . . . . . . . . 175

4.2.3 Determining the number of points on an elliptic curve . . . . 179

4.3 Key pairs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180

4.4 Signature schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . 183

4.4.1 ECDSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184

4.4.2 EC-KCDSA . . . . . . . . . . . . . . . . . . . . . . . . . . 186

4.5 Public-key encryption . . . . . . . . . . . . . . . . . . . . . . . . . . 188

4.5.1 ECIES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189

4.5.2 PSEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191

4.6 Key establishment . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192

4.6.1 Station-to-station . . . . . . . . . . . . . . . . . . . . . . . . 193

4.6.2 ECMQV . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

4.7 Notes and further references . . . . . . . . . . . . . . . . . . . . . . 196

5 Implementation Issues 205

5.1 Software implementation . . . . . . . . . . . . . . . . . . . . . . . . 206

5.1.1 Integer arithmetic . . . . . . . . . . . . . . . . . . . . . . . . 206

5.1.2 Floating-point arithmetic . . . . . . . . . . . . . . . . . . . . 209

5.1.3 SIMD and field arithmetic . . . . . . . . . . . . . . . . . . . 213

5.1.4 Platform miscellany . . . . . . . . . . . . . . . . . . . . . . 215

5.1.5 Timings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219

5.2 Hardware implementation . . . . . . . . . . . . . . . . . . . . . . . 224

5.2.1 Design criteria . . . . . . . . . . . . . . . . . . . . . . . . . 226

5.2.2 Field arithmetic processors . . . . . . . . . . . . . . . . . . . 229

5.3 Secure implementation . . . . . . . . . . . . . . . . . . . . . . . . . 238

5.3.1 Power analysis attacks . . . . . . . . . . . . . . . . . . . . . 239

5.3.2 Electromagnetic analysis attacks . . . . . . . . . . . . . . . . 244

5.3.3 Error message analysis . . . . . . . . . . . . . . . . . . . . . 244

5.3.4 Fault analysis attacks . . . . . . . . . . . . . . . . . . . . . . 248

5.3.5 Timing attacks . . . . . . . . . . . . . . . . . . . . . . . . . 250

5.4 Notes and further references . . . . . . . . . . . . . . . . . . . . . . 250

viii Contents

A Sample Parameters 257

A.1 Irreducible polynomials . . . . . . . . . . . . . . . . . . . . . . . . . 257

A.2 Elliptic curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261

A.2.1 Random elliptic curves over Fp . . . . . . . . . . . . . . . . 261

A.2.2 Random elliptic curves over F2m . . . . . . . . . . . . . . . . 263

A.2.3 Koblitz elliptic curves over F2m . . . . . . . . . . . . . . . . 263

B ECC Standards 267

C Software Tools 271

C.1 General-purpose tools . . . . . . . . . . . . . . . . . . . . . . . . . . 271

C.2 Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273

Bibliography 277

Index 305

List of Algorithms

1.1 RSA key pair generation . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2 Basic RSA encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3 Basic RSA decryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.4 Basic RSA signature generation . . . . . . . . . . . . . . . . . . . . . . 8

1.5 Basic RSA signature verification . . . . . . . . . . . . . . . . . . . . . . 8

1.6 DL domain parameter generation . . . . . . . . . . . . . . . . . . . . . . 9

1.7 DL key pair generation . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.8 Basic ElGamal encryption . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.9 Basic ElGamal decryption . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.10 DSA signature generation . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.11 DSA signature verification . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.12 Elliptic curve key pair generation . . . . . . . . . . . . . . . . . . . . . . 14

1.13 Basic ElGamal elliptic curve encryption . . . . . . . . . . . . . . . . . . 14

1.14 Basic ElGamal elliptic curve decryption . . . . . . . . . . . . . . . . . . 14

2.5 Multiprecision addition . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.6 Multiprecision subtraction . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.7 Addition in Fp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.8 Subtraction in Fp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.9 Integer multiplication (operand scanning form) . . . . . . . . . . . . . . 31

2.10 Integer multiplication (product scanning form) . . . . . . . . . . . . . . . 32

2.13 Integer squaring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.14 Barrett reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.17 Montgomery exponentiation (basic) . . . . . . . . . . . . . . . . . . . . 38

2.19 Extended Euclidean algorithm for integers . . . . . . . . . . . . . . . . . 40

2.20 Inversion in Fp using the extended Euclidean algorithm . . . . . . . . . . 40

2.21 Binary gcd algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.22 Binary algorithm for inversion in Fp . . . . . . . . . . . . . . . . . . . . 41

2.23 Partial Montgomery inversion in Fp . . . . . . . . . . . . . . . . . . . . 42

x List of Algorithms

2.25 Montgomery inversion in Fp . . . . . . . . . . . . . . . . . . . . . . . . 43

2.26 Simultaneous inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

2.27 Fast reduction modulo p192 = 2192 −264 −1 . . . . . . . . . . . . . . . . 45

2.28 Fast reduction modulo p224 = 2224 −296 +1 . . . . . . . . . . . . . . . . 45

2.29 Fast reduction modulo p256 = 2256 −2224 +2192 +296 −1 . . . . . . . . 46

2.30 Fast reduction modulo p384 = 2384 −2128 −296 +232 −1 . . . . . . . . . 46

2.31 Fast reduction modulo p521 = 2521 −1 . . . . . . . . . . . . . . . . . . . 46

2.32 Addition in F2m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

2.33 Right-to-left shift-and-add field multiplication in F2m . . . . . . . . . . . 48

2.34 Right-to-left comb method for polynomial multiplication . . . . . . . . . 49

2.35 Left-to-right comb method for polynomial multiplication . . . . . . . . . 50

2.36 Left-to-right comb method with windows of width w . . . . . . . . . . . 50

2.39 Polynomial squaring . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

2.40 Modular reduction (one bit at a time) . . . . . . . . . . . . . . . . . . . . 53

2.41 Fast reduction modulo f (z) = z163 + z7 + z6 + z3 +1 . . . . . . . . . . . 55

2.42 Fast reduction modulo f (z) = z233 + z74 +1 . . . . . . . . . . . . . . . . 55

2.43 Fast reduction modulo f (z) = z283 + z12 + z7 + z5 +1 . . . . . . . . . . 56

2.44 Fast reduction modulo f (z) = z409 + z87 +1 . . . . . . . . . . . . . . . . 56

2.45 Fast reduction modulo f (z) = z571 + z10 + z5 + z2 +1 . . . . . . . . . . 56

2.47 Extended Euclidean algorithm for binary polynomials . . . . . . . . . . . 58

2.48 Inversion in F2m using the extended Euclidean algorithm . . . . . . . . . 58

2.49 Binary algorithm for inversion in F2m . . . . . . . . . . . . . . . . . . . 59

2.50 Almost Inverse Algorithm for inversion in F2m . . . . . . . . . . . . . . . 60

2.54 Reduction modulo M = Bn −c . . . . . . . . . . . . . . . . . . . . . . . 64

2.59 OEF inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

3.21 Point doubling (y2 = x3 −3x +b, Jacobian coordinates) . . . . . . . . . 91

3.22 Point addition (y2 = x3 −3x +b, affine-Jacobian coordinates) . . . . . . 91

3.23 Repeated point doubling (y2=x3−3x+b, Jacobian coordinates) . . . . . 93

3.24 Point doubling (y2+x y=x3+ax2+b, a∈{0,1}, LD coordinates) . . . . . 94

3.25 Point addition (y2+x y=x3+ax2+b, a∈{0,1}, LD-affine coordinates) . . 95

3.26 Right-to-left binary method for point multiplication . . . . . . . . . . . . 96

3.27 Left-to-right binary method for point multiplication . . . . . . . . . . . . 97

3.30 Computing the NAF of a positive integer . . . . . . . . . . . . . . . . . . 98

3.31 Binary NAF method for point multiplication . . . . . . . . . . . . . . . . 99

3.35 Computing the width-w NAF of a positive integer . . . . . . . . . . . . . 100

3.36 Window NAF method for point multiplication . . . . . . . . . . . . . . . 100

3.38 Sliding window method for point multiplication . . . . . . . . . . . . . . 101

3.40 Montgomery point multiplication (for elliptic curves over F2m ) . . . . . . 103

3.41 Fixed-base windowing method for point multiplication . . . . . . . . . . 104

3.42 Fixed-base NAF windowing method for point multiplication . . . . . . . 105

3.44 Fixed-base comb method for point multiplication . . . . . . . . . . . . . 106

List of Algorithms xi

3.45 Fixed-base comb method (with two tables) for point multiplication . . . . 106

3.48 Simultaneous multiple point multiplication . . . . . . . . . . . . . . . . . 109

3.50 Joint sparse form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

3.51 Interleaving with NAFs . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

3.61 Computing the TNAF of an element in Z[τ ] . . . . . . . . . . . . . . . . 117

3.62 Division in Z[τ ] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

3.63 Rounding off in Z[τ ] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

3.65 Partial reduction modulo δ = (τ m −1)/(τ −1) . . . . . . . . . . . . . . 119

3.66 TNAF method for point multiplication on Koblitz curves . . . . . . . . . 119

3.69 Computing a width-w TNAF of an element in Z[τ ] . . . . . . . . . . . . 123

3.70 Window TNAF point multiplication method for Koblitz curves . . . . . . 123

3.74 Balanced length-two representation of a multiplier . . . . . . . . . . . . . 127

3.77 Point multiplication with efficiently computable endomorphisms . . . . . 129

3.81 Point halving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

3.85 Solve x2 + x = c (basic version) . . . . . . . . . . . . . . . . . . . . . . 133

3.86 Solve x2 + x = c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

3.91 Halve-and-add w-NAF (right-to-left) point multiplication . . . . . . . . . 138

3.92 Halve-and-add w-NAF (left-to-right) point multiplication . . . . . . . . . 139

4.3 Pollard’s rho algorithm for the ECDLP (single processor) . . . . . . . . . 159

4.5 Parallelized Pollard’s rho algorithm for the ECDLP . . . . . . . . . . . . 161

4.14 Domain parameter generation . . . . . . . . . . . . . . . . . . . . . . . . 174

4.15 Explicit domain parameter validation . . . . . . . . . . . . . . . . . . . . 175

4.17 Generating a random elliptic curve over a prime field Fp . . . . . . . . . 176

4.18 Verifying that an elliptic curve over Fp was randomly generated . . . . . 176

4.19 Generating a random elliptic curve over a binary field F2m . . . . . . . . 177

4.21 Verifying that an elliptic curve over F2m was randomly generated . . . . . 177

4.22 Generating a random elliptic curve over an OEF Fpm . . . . . . . . . . . 178

4.23 Verifying that an elliptic curve over Fpm was randomly generated . . . . . 178

4.24 Key pair generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180

4.25 Public key validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

4.26 Embedded public key validation . . . . . . . . . . . . . . . . . . . . . . 181

4.29 ECDSA signature generation . . . . . . . . . . . . . . . . . . . . . . . . 184

4.30 ECDSA signature verification . . . . . . . . . . . . . . . . . . . . . . . 184

4.36 EC-KCDSA signature generation . . . . . . . . . . . . . . . . . . . . . . 187

4.37 EC-KCDSA signature verification . . . . . . . . . . . . . . . . . . . . . 187

4.42 ECIES encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189

4.43 ECIES decryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190

4.47 PSEC encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191

4.48 PSEC decryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191

4.50 Station-to-station key agreement . . . . . . . . . . . . . . . . . . . . . . 194

4.51 ECMQV key agreement . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

xii List of Algorithms

5.3 Most significant bit first (MSB) multiplier for F2m . . . . . . . . . . . . . 230

5.4 Least significant bit first (LSB) multiplier for F2m . . . . . . . . . . . . . 231

5.5 Digit-serial multiplier for F2m . . . . . . . . . . . . . . . . . . . . . . . 234

5.6 Inversion in F2m (m odd) . . . . . . . . . . . . . . . . . . . . . . . . . . 237

5.7 SPA-resistant left-to-right binary point multiplication . . . . . . . . . . . 242

5.8 RSA-OAEP encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . 246

5.9 RSA-OAEP decryption . . . . . . . . . . . . . . . . . . . . . . . . . . . 247

A.1 Testing a polynomial for irreducibility . . . . . . . . . . . . . . . . . . . 258

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 Operation counts for arithmetic on y2 = x3 −3x +b . . . . . . . . . . . 92

3.4 Operation counts for arithmetic on y2 + x y = x3 +ax2 +b . . . . . . . . 96

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

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

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

3.8 Koblitz 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.3 Timings for field arithmetic (binary vs prime vs OEF) . . . . . . . . . . . 220

5.4 Timings 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