 Guide to Elliptic Curve Cryptography Darrel Hankerson, Alfred Menezes, and Scott Vanstone

List of Algorithms
List of Tables
List of Figures

Preface

1 Introduction and Overview

1.1 Cryptography basics
1.2 Public-key cryptography
1.2.1 RSA systems
1.2.2 Discrete logarithm systems
1.2.3 Elliptic curve systems
1.3 Why elliptic curve cryptography?
1.5 Notes and further references
2 Finite Field Arithmetic
2.1 Introduction to finite fields
2.2 Prime field arithmetic
2.2.2 Integer multiplication
2.2.3 Integer squaring
2.2.4 Reduction
2.2.5 Inversion
2.2.6 NIST primes
2.3 Binary field arithmetic
2.3.2 Multiplication
2.3.3 Polynomial multiplication
2.3.4 Polynomial squaring
2.3.5 Reduction
2.3.6 Inversion and division
2.4 Optimal extension field arithmetic
2.4.2 Multiplication and reduction
2.5 Notes and further references
3 Elliptic Curve Arithmetic
3.1 Introduction to elliptic curves
3.1.1 Simplified Weierstrass equations
3.1.2 Group law
3.1.3 Group order
3.1.4 Group structure
3.1.5 Isomorphism classes
3.2 Point representation and the group law
3.2.1 Projective coordinates
3.2.2 The elliptic curve y2=x3 +ax +b
3.2.3 The elliptic curve y2+xy=x3 +ax2+b
3.3 Point multiplication
3.3.1 Unknown point
3.3.2 Fixed point
3.3.3 Multiple point multiplication
3.4 Koblitz curves
3.4.1 The Frobenius map and the ring Z[tau]
3.4.2 Point multiplication
3.5 Curves with efficiently-computable endomorphisms
3.6 Point multiplication using halving
3.6.1 Point halving
3.6.2 Performing point halving efficiently
3.6.3 Point multiplication
3.7 Point multiplication costs
3.8 Notes and further references
4 Cryptographic Protocols
4.1 The elliptic curve discrete logarithm problem
4.1.1 Pohlig-Hellman attack
4.1.2 Pollard's rho attack
4.1.3 Index-calculus attacks
4.1.4 Isomorphism attacks
4.1.5 Related problems
4.2 Domain parameters
4.2.1 Domain parameter generation and validation
4.2.2 Generating elliptic curves verifiably at random
4.2.3 Determining the number of points on an elliptic curve
4.3 Key pairs
4.4 Signature schemes
4.4.1 ECDSA
4.4.2 EC-KCDSA
4.5 Public-key encryption
4.5.1 ECIES
4.5.2 PSEC
4.6 Key establishment
4.6.1 Station-to-station
4.6.2 ECMQV
4.7 Notes and further references
5 Implementation Issues
5.1 Software implementation
5.1.1 Integer arithmetic
5.1.2 Floating-point arithmetic
5.1.3 SIMD and field arithmetic
5.1.4 Platform miscellany
5.1.5 Timings
5.2 Hardware implementation
5.2.1 Design criteria
5.2.2 Field arithmetic processors
5.3 Secure implementation
5.3.1 Power analysis attacks
5.3.2 Electromagnetic analysis attacks
5.3.3 Error message analysis
5.3.4 Fault analysis attacks
5.3.5 Timing attacks
5.4 Notes and further references
A Sample Parameters
A.1 Irreducible polynomials
A.2 Elliptic curves
A.2.1 Random elliptic curves over Fp
A.2.2 Random elliptic curves over F2m
A.2.3 Koblitz elliptic curves over F2m
B ECC Standards

C Software Tools

C.1 General-purpose tools
C.2 Libraries
Bibliography

Index

Guide to Elliptic Curve Cryptography / g2ecc@dms.auburn.edu / May 2004/ Illustration by Helen D'Souza