Guide to Elliptic Curve Cryptography (eBook)

Contents 6
List of Algorithms 10
List of Tables 14
List of Figures 16
Acronyms 18
Preface 20
CHAPTER 1 Introduction and Overview 22
1.1 Cryptography basics 23
1.2 Public-key cryptography 27
1.2.1 RSA systems 27
1.2.2 Discrete logarithm systems 29
1.2.3 Elliptic curve systems 32
1.3 Why elliptic curve cryptography? 36
1.4 Roadmap 40
1.5 Notes and further references 42
CHAPTER 2 Finite Field Arithmetic 46
2.1 Introduction to .nite .elds 46
2.2 Prime field arithmetic 50
2.2.1 Addition and subtraction 51
2.2.2 Integer multiplication 52
2.2.3 Integer squaring 55
2.2.4 Reduction 56
2.2.5 Inversion 60
2.2.6 NIST primes 65
2.3 Binary field arithmetic 68
2.3.1 Addition 68
2.3.2 Multiplication 69
2.3.3 Polynomial multiplication 69
2.3.4 Polynomial squaring 73
2.3.5 Reduction 74
2.4 Optimal extension .eld arithmetic 83
2.4.1 Addition and subtraction 84
2.4.2 Multiplication and reduction 84
2.4.3 Inversion 88
2.5 Notes and further references 90
CHAPTER 3 Elliptic Curve Arithmetic 96
3.1 Introduction to elliptic curves 97
3.1.1 Simpli.edWeierstrass equations 99
3.1.2 Group law 100
3.1.3 Group order 103
3.1.4 Group structure 104
3.1.5 Isomorphism classes 105
3.2 Point representation and the group law 107
3.2.1 Projective coordinates 107
3.2.2 The elliptic curve y2 = x3+ax +b 110
3.2.3 The elliptic curve y2+xy = x3+ax2+b 114
3.3 Point multiplication 116
3.3.1 Unknown point 117
3.3.2 Fixed point 124
3.3.3 Multiple point multiplication 130
3.4 Koblitz curves 135
3.4.1 The Frobenius map and the ringZ[? ] 135
3.4.2 Point multiplication 140
3.5 Curves with ef.ciently computable endomorphisms 144
3.6 Point multiplication using halving 150
3.6.1 Point halving 151
3.6.2 Performing point halving ef.ciently 153
3.6.3 Point multiplication 158
3.7 Point multiplication costs 162
3.8 Notes and further references 168
CHAPTER 4 Cryptographic Protocols 174
4.1 The elliptic curve discrete logarithm problem 174
4.1.1 Pohlig-Hellman attack 176
4.1.2 Pollard’s rho attack 178
4.1.3 Index-calculus attacks 186
4.1.4 Isomorphism attacks 189
4.1.5 Related problems 192
4.2 Domain parameters 193
4.2.1 Domain parameter generation and validation 194
4.2.2 Generating elliptic curves veri.ably at random 196
4.2.3 Determining the number of points on an elliptic curve 200
4.3 Key pairs 201
4.4 Signature schemes 204
4.4.1 ECDSA 205
4.4.2 EC-KCDSA 207
4.5 Public-key encryption 209
4.5.1 ECIES 210
4.5.2 PSEC 212
4.6 Key establishment 213
4.6.1 Station-to-station 214
4.6.2 ECMQV 216
4.7 Notes and further references 217
CHAPTER 5 Implementation Issues 226
5.1 Software implementation 227
5.1.1 Integer arithmetic 227
5.1.2 Floating-point arithmetic 230
5.1.3 SIMD and .eld arithmetic 234
5.1.4 Platform miscellany 236
5.1.5 Timings 240
5.2 Hardware implementation 245
5.2.1 Design criteria 247
5.2.2 Field arithmetic processors 250
5.3 Secure implementation 259
5.3.1 Power analysis attacks 260
5.3.2 Electromagnetic analysis attacks 265
5.3.3 Error message analysis 265
5.3.4 Fault analysis attacks 269
5.3.5 Timing attacks 271
5.4 Notes and further references 271
APPENDIX A Sample Parameters 278
A.1 Irreducible polynomials 278
A.2 Elliptic curves 282
A.2.1 Random elliptic curves overFp 282
A.2.2 Random elliptic curves overF2m 284
A.2.3 Koblitz elliptic curves overF2m 284
APPENDIX B ECC Standards 288
APPENDIX C Software Tools 292
C.1 General-purpose tools 292
C.2 Libraries 294
Bibliography 298
Index 326
Mehr eBooks bei www.ciando.com 0

Roadmap (p. 19-20)

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;

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 infiuence 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.