Hankerson / Menezes / Vanstone Guide to Elliptic Curve Cryptography

1. Auflage 2006
ISBN: 978-0-387-21846-5
Verlag: Springer US
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 332 Seiten

Reihe: Springer Professional Computing

After two decades of research and development, elliptic curve cryptography now has widespread exposure and acceptance. Industry, banking, and government standards are in place to facilitate extensive deployment of this efficient public-key mechanism. Anchored by a comprehensive treatment of the practical aspects of elliptic curve cryptography (ECC), this guide explains the basic mathematics, describes state-of-the-art implementation methods, and presents standardized protocols for public-key encryption, digital signatures, and key establishment. In addition, the book addresses some issues that arise in software and hardware implementation, as well as side-channel attacks and countermeasures.

Readers receive the theoretical fundamentals as an underpinning for a wealth of practical and accessible knowledge about efficient application. Features & Benefits:* Breadth of coverage and unified, integrated approach to elliptic curve cryptosystems* Describes important industry and government protocols, such as the FIPS 186-2 standard from the U. S. National Institute for Standards and Technology* Provides full exposition on techniques for efficiently implementing finite-field and elliptic curve arithmetic* Distills complex mathematics and algorithms for easy understanding* Includes useful literature references, a list of algorithms, and appendices on sample parameters, ECC standards, and software toolsThis comprehensive, highly focused reference is a useful and indispensable resource for practitioners, professionals, or researchers in computer science, computer engineering, network design, and network data security.

Autoren/Hrsg.

Hankerson, Darrel

Menezes, Alfred J.

Vanstone, Scott

Inhaltsverzeichnis

1;Contents;6
2;List of Algorithms;10
3;List of Tables;14
4;List of Figures;16
5;Acronyms;18
6;Preface;20
7;CHAPTER 1 Introduction and Overview;22
7.1;1.1 Cryptography basics;23
7.2;1.2 Public-key cryptography;27
7.3;1.2.1 RSA systems;27
7.4;1.2.2 Discrete logarithm systems;29
7.5;1.2.3 Elliptic curve systems;32
7.6;1.3 Why elliptic curve cryptography?;36
7.7;1.4 Roadmap;40
7.8;1.5 Notes and further references;42
8;CHAPTER 2 Finite Field Arithmetic;46
8.1;2.1 Introduction to .nite .elds;46
8.2;2.2 Prime field arithmetic;50
8.2.1;2.2.1 Addition and subtraction;51
8.2.2;2.2.2 Integer multiplication;52
8.2.3;2.2.3 Integer squaring;55
8.2.4;2.2.4 Reduction;56
8.2.5;2.2.5 Inversion;60
8.2.6;2.2.6 NIST primes;65
8.3;2.3 Binary field arithmetic;68
8.3.1;2.3.1 Addition;68
8.3.2;2.3.2 Multiplication;69
8.3.3;2.3.3 Polynomial multiplication;69
8.3.4;2.3.4 Polynomial squaring;73
8.3.5;2.3.5 Reduction;74
8.4;2.4 Optimal extension .eld arithmetic;83
8.4.1;2.4.1 Addition and subtraction;84
8.4.2;2.4.2 Multiplication and reduction;84
8.4.3;2.4.3 Inversion;88
8.5;2.5 Notes and further references;90
9;CHAPTER 3 Elliptic Curve Arithmetic;96
9.1;3.1 Introduction to elliptic curves;97
9.1.1;3.1.1 Simpli.edWeierstrass equations;99
9.1.2;3.1.2 Group law;100
9.1.3;3.1.3 Group order;103
9.1.4;3.1.4 Group structure;104
9.1.5;3.1.5 Isomorphism classes;105
9.2;3.2 Point representation and the group law;107
9.2.1;3.2.1 Projective coordinates;107
9.2.2;3.2.2 The elliptic curve y2 = x3+ax +b;110
9.2.3;3.2.3 The elliptic curve y2+xy = x3+ax2+b;114
9.3;3.3 Point multiplication;116
9.3.1;3.3.1 Unknown point;117
9.3.2;3.3.2 Fixed point;124
9.4;3.3.3 Multiple point multiplication;130
9.5;3.4 Koblitz curves;135
9.5.1;3.4.1 The Frobenius map and the ringZ[? ];135
9.5.2;3.4.2 Point multiplication;140
9.6;3.5 Curves with ef.ciently computable endomorphisms;144
9.7;3.6 Point multiplication using halving;150
9.7.1;3.6.1 Point halving;151
9.7.2;3.6.2 Performing point halving ef.ciently;153
9.7.3;3.6.3 Point multiplication;158
9.8;3.7 Point multiplication costs;162
9.9;3.8 Notes and further references;168
10;CHAPTER 4 Cryptographic Protocols;174
10.1;4.1 The elliptic curve discrete logarithm problem;174
10.1.1;4.1.1 Pohlig-Hellman attack;176
10.1.2;4.1.2 Pollard’s rho attack;178
10.1.3;4.1.3 Index-calculus attacks;186
10.1.4;4.1.4 Isomorphism attacks;189
10.1.5;4.1.5 Related problems;192
10.2;4.2 Domain parameters;193
10.2.1;4.2.1 Domain parameter generation and validation;194
10.2.2;4.2.2 Generating elliptic curves veri.ably at random;196
10.2.3;4.2.3 Determining the number of points on an elliptic curve;200
10.3;4.3 Key pairs;201
10.4;4.4 Signature schemes;204
10.4.1;4.4.1 ECDSA;205
10.4.2;4.4.2 EC-KCDSA;207
10.5;4.5 Public-key encryption;209
10.5.1;4.5.1 ECIES;210
10.5.2;4.5.2 PSEC;212
10.6;4.6 Key establishment;213
10.6.1;4.6.1 Station-to-station;214
10.6.2;4.6.2 ECMQV;216
10.7;4.7 Notes and further references;217
11;CHAPTER 5 Implementation Issues;226
11.1;5.1 Software implementation;227
11.1.1;5.1.1 Integer arithmetic;227
11.1.2;5.1.2 Floating-point arithmetic;230
11.1.3;5.1.3 SIMD and .eld arithmetic;234
11.1.4;5.1.4 Platform miscellany;236
11.1.5;5.1.5 Timings;240
11.2;5.2 Hardware implementation;245
11.2.1;5.2.1 Design criteria;247
11.2.2;5.2.2 Field arithmetic processors;250
11.3;5.3 Secure implementation;259
11.3.1;5.3.1 Power analysis attacks;260
11.3.2;5.3.2 Electromagnetic analysis attacks;265
11.3.3;5.3.3 Error message analysis;265
11.3.4;5.3.4 Fault analysis attacks;269
11.4;5.3.5 Timing attacks;271
11.5;5.4 Notes and further references;271
12;APPENDIX A Sample Parameters;278
12.1;A.1 Irreducible polynomials;278
12.2;A.2 Elliptic curves;282
12.2.1;A.2.1 Random elliptic curves overFp;282
12.2.2;A.2.2 Random elliptic curves overF2m;284
12.2.3;A.2.3 Koblitz elliptic curves overF2m;284
13;APPENDIX B ECC Standards;288
14;APPENDIX C Software Tools;292
14.1;C.1 General-purpose tools;292
14.2;C.2 Libraries;294
15;Bibliography;298
16;Index;326
17;Mehr eBooks bei www.ciando.com;0

Leseproben

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.