Guide to Elliptic Curve Cryptography

Description

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 tools

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

 

Table of 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 RSAsystems . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 Discrete logarithmsystems . . . . . . . . . . . . . . . . . . . 8
1.2.3 Elliptic curve systems . . . . . . . . . . . . . . . . . . . . . 11
1.3 Why elliptic curve cryptography? . . . . . . . . . . . . . . . . . . . . 15
1.4 Roadmap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5 Notes andfurther references . . . . . . . . . . . . . . . . . . . . . . 21
2 Finite Field Arithmetic 25
2.1 Introduction to finite fields . . . . . . . . . . . . . . . . . . . . . . . 25
2.2 Primefieldarithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . 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 NISTprimes . . . . . . . . . . . . . . . . . . . . . . . . . . 44
vi Contents
2.3 Binaryfieldarithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 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 anddivision . . . . . . . . . . . . . . . . . . . . . 57
2.4 Optimal extensionfieldarithmetic . . . . . . . . . . . . . . . . . . . 62
2.4.1 Addition and subtraction . . . . . . . . . . . . . . . . . . . . 63
2.4.2 Multiplication and reduction . . . . . . . . . . . . . . . . . . 63
2.4.3 Inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
2.5 Notes andfurther references . . . . . . . . . . . . . . . . . . . . . . 69
3 Elliptic Curve Arithmetic 75
3.1 Introduction to elliptic curves . . . . . . . . . . . . . . . . . . . . . . 76
3.1.1 SimplifiedWeierstrass equations . . . . . . . . . . . . . . . . 78
3.1.2 Group law. . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
3.1.3 Group order . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.1.4 Group structure . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.1.5 Isomorphismclasses . . . . . . . . . . . . . . . . . . . . . . 84
3.2 Point representationandthe 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 +xy = 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 andfurther 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 Isomorphismattacks . . . . . . . . . . . . . . . . . . . . . . 168
4.1.5 Relatedproblems . . . . . . . . . . . . . . . . . . . . . . . . 171
4.2 Domainparameters . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
4.2.1 Domainparametergeneration andvalidation . . . . . . . . . 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 Keypairs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 Keyestablishment . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
4.6.1 Station-to-station . . . . . . . . . . . . . . . . . . . . . . . . 193
4.6.2 ECMQV . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
4.7 Notes andfurther 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 SIMDandfieldarithmetic . . . . . . . . . . . . . . . . . . . 213
5.1.4 Platformmiscellany . . . . . . . . . . . . . . . . . . . . . . 215
5.1.5 Timings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
5.2 Hardware implementation . . . . . . . . . . . . . . . . . . . . . . . 224
5.2.1 Designcriteria . . . . . . . . . . . . . . . . . . . . . . . . . 226
5.2.2 Field arithmeticprocessors . . . . . . . . . . . . . . . . . . . 229
5.3 Secure implementation . . . . . . . . . . . . . . . . . . . . . . . . . 238
5.3.1 Power analysis attacks . . . . . . . . . . . . . . . . . . . . . 239
5.3.2 Electromagnetic analysis attacks . . . . . . . . . . . . . . . . 244
5.3.3 Errormessageanalysis . . . . . . . . . . . . . . . . . . . . . 244
5.3.4 Fault analysis attacks . . . . . . . . . . . . . . . . . . . . . . 248
5.3.5 Timing attacks . . . . . . . . . . . . . . . . . . . . . . . . . 250
5.4 Notes andfurther 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