Guide to Elliptic Curve Cryptography

Guide to Elliptic Curve Cryptography......Page 1
Contents......Page 6
List of Algorithms......Page 10
List of Tables......Page 14
List of Figures......Page 16
Acronyms......Page 18
Preface......Page 20
1 Introduction and Overview......Page 22
1.1 Cryptography basics......Page 23
1.2.1 RSAsystems......Page 27
1.2.2 Discrete logarithmsystems......Page 29
1.2.3 Elliptic curve systems......Page 32
1.3 Why elliptic curve cryptography?......Page 36
1.4 Roadmap......Page 40
1.5 Notes andfurther references......Page 42
2.1 Introduction to finite fields......Page 46
2.2 Primefieldarithmetic......Page 50
2.2.1 Addition and subtraction......Page 51
2.2.2 Integer multiplication......Page 52
2.2.3 Integer squaring......Page 55
2.2.4 Reduction......Page 56
2.2.5 Inversion......Page 60
2.2.6 NISTprimes......Page 65
2.3.1 Addition......Page 68
2.3.3 Polynomial multiplication......Page 69
2.3.4 Polynomial squaring......Page 73
2.3.5 Reduction......Page 74
2.3.6 Inversion anddivision......Page 78
2.4 Optimal extensionfieldarithmetic......Page 83
2.4.2 Multiplication and reduction......Page 84
2.4.3 Inversion......Page 88
2.5 Notes andfurther references......Page 90
3 Elliptic Curve Arithmetic......Page 96
3.1 Introduction to elliptic curves......Page 97
3.1.1 SimplifiedWeierstrass equations......Page 99
3.1.2 Group law......Page 100
3.1.3 Group order......Page 103
3.1.4 Group structure......Page 104
3.1.5 Isomorphismclasses......Page 105
3.2.1 Projective coordinates......Page 107
3.2.2 The elliptic curve y2 = x3 +ax +b......Page 110
3.2.3 The elliptic curve y2 +xy = x3 +ax2 +b......Page 114
3.3 Point multiplication......Page 116
3.3.1 Unknown point......Page 117
3.3.2 Fixed point......Page 124
3.3.3 Multiple point multiplication......Page 130
3.4.1 The Frobenius map and the ring Z[τ ]......Page 135
3.4.2 Point multiplication......Page 140
3.5 Curves with efficiently computable endomorphisms......Page 144
3.6 Point multiplication using halving......Page 150
3.6.1 Point halving......Page 151
3.6.2 Performing point halving efficiently......Page 153
3.6.3 Point multiplication......Page 158
3.7 Point multiplication costs......Page 162
3.8 Notes andfurther references......Page 168
4.1 The elliptic curve discrete logarithm problem......Page 174
4.1.1 Pohlig-Hellman attack......Page 176
4.1.2 Pollard\'s rho attack......Page 178
4.1.3 Index-calculus attacks......Page 186
4.1.4 Isomorphismattacks......Page 189
4.1.5 Relatedproblems......Page 192
4.2 Domainparameters......Page 193
4.2.1 Domainparametergeneration andvalidation......Page 194
4.2.2 Generating elliptic curves verifiably at random......Page 196
4.2.3 Determining the number of points on an elliptic curve......Page 200
4.3 Keypairs......Page 201
4.4 Signature schemes......Page 204
4.4.1 ECDSA......Page 205
4.4.2 EC-KCDSA......Page 207
4.5 Public-key encryption......Page 209
4.5.1 ECIES......Page 210
4.5.2 PSEC......Page 212
4.6 Keyestablishment......Page 213
4.6.1 Station-to-station......Page 214
4.6.2 ECMQV......Page 216
4.7 Notes andfurther references......Page 217
5 Implementation Issues......Page 226
5.1.1 Integer arithmetic......Page 227
5.1.2 Floating-point arithmetic......Page 230
5.1.3 SIMDandfieldarithmetic......Page 234
5.1.4 Platformmiscellany......Page 236
5.1.5 Timings......Page 240
5.2 Hardware implementation......Page 245
5.2.1 Designcriteria......Page 247
5.2.2 Field arithmeticprocessors......Page 250
5.3 Secure implementation......Page 259
5.3.1 Power analysis attacks......Page 260
5.3.3 Errormessageanalysis......Page 265
5.3.4 Fault analysis attacks......Page 269
5.4 Notes andfurther references......Page 271
A.1 Irreducible polynomials......Page 278
A.2.1 Random elliptic curves over Fp......Page 282
A.2.3 Koblitz elliptic curves over F2m......Page 284
B ECC Standards......Page 288
C.1 General-purpose tools......Page 292
C.2 Libraries......Page 294
Bibliography......Page 298
Index......Page 326