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. RSA systems ......................................... 6
1.2.2. Discrete logarithm systems .......................... 8
1.2.3. Elliptic curve systems ............................. 11
1.3. Why elliptic curve cryptography? .......................... 15
1.4. Roadmap ................................................... 19
1.5. Notes and further references .............................. 21
2. Finite Field Arithmetic ..................................... 25
2.1. Introduction to finite fields ............................. 25
2.2. Prime field arithmetic .................................... 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. NIST primes ........................................ 44
2.3. Binary field arithmetic ................................... 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 and division ............................. 57
2.4. Optimal extension field arithmetic ........................ 62
2.4.1. Addition and subtraction ........................... 63
2.4.2. Multiplication and reduction ....................... 63
2.4.3. Inversion .......................................... 67
2.5. Notes and further references .............................. 69
3. Elliptic Curve Arithmetic ................................... 75
3.1. Introduction to elliptic curves ........................... 76
3.1.1. Simplified Weierstrass equations ................... 78
3.1.2. Group law .......................................... 79
3.1.3. Group order ........................................ 82
3.1.4. Group structure .................................... 83
3.1.5. Isomorphism classes ................................ 84
3.2. Point representation and the 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 у2 + ху = х3 + ах2 + 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[r] ............... 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 and further references ............................. 147
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. Isomorphism attacks ............................... 168
4.1.5. Related problems .................................. 171
4.2. Domain parameters ........................................ 172
4.2.1. Domain parameter generation and validation ........ 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. Key pairs ................................................ 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. Key establishment ........................................ 192
4.6.1. Station-to-station ................................ 193
4.6.2. ECMQV ............................................. 195
4.7. Notes and further 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. SIMD and field arithmetic ......................... 213
5.1.4. Platform miscellany ............................... 215
5.1.5. Timings ........................................... 219
5.2. Hardware implementation .................................. 224
5.2.1. Design criteria ................................... 226
5.2.2. Field arithmetic processors ....................... 229
5.3. Secure implementation .................................... 238
5.3.1. Power analysis attacks ............................ 239
5.3.2. Electromagnetic analysis attacks .................. 244
5.3.3. Error message analysis ............................ 244
5.3.4. Fault analysis attacks ............................ 248
5.3.5. Timing attacks .................................... 250
5.4. Notes and further references ............................. 250
A. Sample Parameters .......................................... 257
A.l. 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
В. ЕСС Standards .............................................. 267
С. Software Tools ............................................. 271
C.l. General-purpose tools ................................. 271
C.2. Libraries ............................................. 273
Bibliography .................................................. 277
Index ......................................................... 305
List of Algorithms
1.1. RSA key pair generation .................................... 7
1.2. Basic RSA encryption ....................................... 7
1.3. Basic RSA decryption ....................................... 7
1.4. Basic RSA signature generation ............................. 8
1.5. Basic RSA signature verification ........................... 8
1.6. DL domain parameter generation ............................. 9
1.7. DL key pair generation ..................................... 9
1.8. Basic ElGamal encryption .................................. 10
1.9. Basic ElGamal decryption .................................. 10
1.10.DSA signature generation .................................. 11
1.11.DSA signature verification ................................ 11
1.12.Elliptic curve key pair generation ........................ 14
1.13.Basic ElGamal elliptic curve encryption ................... 14
1.14.Basic ElGamal elliptic curve decryption ................... 14
2.5. Multiprecision addition ................................... 30
2.6. Multiprecision subtraction ................................ 30
2.7. Addition in Fp ............................................ 31
2.8. Subtraction in Fp ......................................... 31
2.9. Integer multiplication (operand scanning form) ............ 31
2.10.Integer multiplication (product scanning form) ............ 32
2.13.Integer squaring .......................................... 35
2.14.Barrett reduction ......................................... 36
2.17.Montgomery exponentiation (basic) ......................... 38
2.19.Extended Euclidean algorithm for integers ................. 40
2.20.Inversion in Ґp using the extended Euclidean algorithm .... 40
2.21.Binary gcd algorithm ...................................... 41
2.22.Binary algorithm for inversion in Fp ...................... 41
2.23.Partial Montgomery inversion in Fp ........................ 42
List of Algorithms
2.25.Montgomery inversion in Fp ................................ 43
2.26.Simultaneous inversion .................................... 44
2.27.Fast reduction modulo p192 = 2192 - 264 - 1 ................ 45
2.28.Fast reduction modulo p224 = 2224 - 296 + l ................ 45
2.29.Fast reduction modulo p256 = 2256 - 2224 + 2192 + 296 - l ... 46
2.30.Fast reduction modulo р384 = 2384 - 2128 - 2% + 232 - 1 ..... 46
2.31.Fast reduction modulo p521 = 2521 - 1 ...................... 46
2.32.Addition in F2m ............................................ 47
2.33.Right-to-left shift-and-add field multiplication in F2m .... 48
2.34.Right-to-left comb method for polynomial multiplication .... 49
2.35.Left-to-right comb method for polynomial multiplication .... 50
2.36.Left-to-right comb method with windows of width ω .......... 50
2.39.Polynomial squaring ........................................ 53
2.40.Modular reduction (one bit at a time) ...................... 53
2.41.Fast reduction modulo f(z) = zl63 + z7 + z6 + z3 + l ........ 55
2.42.Fast reduction modulo f(z) = z233 + z74 + 1 ................. 55
2.43.Fast reduction modulo f(z) = z283 + z12 + z7 + z5 + l ....... 56
2.44.Fast reduction modulo f(z) = z409 + z87 + 1 ................. 56
2.45.Fast reduction modulo f(z) = z571 + z10 + z5 + z2 + 1 ....... 56
2.47.Extended Euclidean algorithm for binary polynomials ........ 58
2.48.Inversion in F2m using the extended Euclidean algorithm .... 58
2.49.Binary algorithm for inversion in F2m ...................... 59
2.50.Almost Inverse Algorithm for inversion in F2m .............. 60
2.54 Reduction modulo M = Bn - c ................................ 64
2.59 OEF inversion .............................................. 69
3.21.Point doubling (y2 = x3 — 3х + b, Jacobian coordinates) .... 91
3.22.Point addition (y2 = x3 — 3х + b, affine-Jacobian
coordinates) .............................................. 91
3.23.Repeated point doubling (y2 = x3 - 3x + b,
Jacobian coordinates) ..................................... 93
3.24.Point doubling (y2 + xy = x3 + ax2 + b,
а∈{0,1}, LD coordinates) .................................. 94
3.25.Point addition (у2 + ху = х3 + ах2 + b,
а∈{0,1}, LD-affine coordinates) ........................... 95
3.26.Right-to-left binary method for point multiplication ...... 96
3.27.Left-to-right binary method for point multiplication ...... 97
3.30.Computing the NAF of a positive integer ................... 98
3.31.Binary NAF method for point multiplication ................ 99
3.35.Computing the width-w NAF of a positive integer .......... 100
3.36.Window NAF method for point multiplication ............... 100
3.38 Sliding window method for point multiplication ........... 101
3.40.Montgomery point multiplication (for elliptic
curves over F2m) ......................................... 103
3.41.Fixed-base windowing method for point multiplication ..... 104
3.42.Fixed-base NAF windowing method for point
multiplication ........................................... 105
3.44.Fixed-base comb method for point multiplication .......... 106
3.45.Fixed-base comb method (with two tables) for point
multiplication ........................................... 106
3.48 Simultaneous multiple point multiplication ............... 109
3.50.Joint sparse form ........................................ 1ll
3.51.Interleaving with NAFs ................................... 112
3.61.Computing the TNAF of an element in Z[r] ................. 117
3.62.Division in Z[r] ......................................... 118
3.63.Rounding off in Z[t] ..................................... 118
3.65.Partial reduction modulo δ = (rm - l)/(r - 1) ............ 119
3.66.TNAF method for point multiplication on Koblitz curves ... 119
3.69.Computing a width-tu TNAF of an element in Z[r] .......... 123
3.70.Window TNAF point multiplication method for Koblitz
curves ................................................... 123
3.74.Balanced length-two representation of a multiplier ....... 127
3.77.Point multiplication with efficiently computable
endomorphisms ............................................ 129
3.81.Point halving ............................................ 131
3.85.Solve x2 + x = с (basic version) ......................... 133
3.86.Solve x2 + x = c ......................................... 134
3.91.Halve-and-add w-NAF (right-to-left) point
multiplication ........................................... 138
3.92.Halve-and-add w-NAF (left-to-right) point
multiplication ........................................... 139
4.3. Pollard's rho algorithm for the ECDLP (single
processor) ............................................... 159
4.5. Parallelized Pollard's rho algorithm for the ECDLP ....... 161
4.14.Domain parameter generation .............................. 174
4.15.Explicit domain parameter validation ..................... 175
4.17.Generating a random elliptic curve over a prime
field Fp ................................................. 176
4.18.Verifying that an elliptic curve over Fp was randomly
generated ................................................ 176
4.19.Generating a random elliptic curve over a binary
field F2m ................................................ 177
4.21.Verifying that an elliptic curve over F2m > was
randomly generated ....................................... 177
4.22.Generating a random elliptic curve over an OEF F2m ....... 178
4.23.Verifying that an elliptic curve over Fpm was randomly
generated ................................................ 178
4.24.Key pair generation ...................................... 180
4.25.Public key validation .................................... 181
4.26.Embedded public key validation ........................... 181
4.29.ECDSA signature generation ............................... 184
4.30.ECDSA signature verification ............................. 184
4.36.EC-KCDSA signature generation ............................ 187
4.37.EC-KCDSA signature verification .......................... 187
4.42.ECIES encryption ......................................... 189
4.43.ECIES decryption ......................................... 190
4.47.PSEC encryption .......................................... 191
4.48.PSEC decryption .......................................... 191
4.50.Station-to-station key agreement ......................... 194
4.51.ECMQV key agreement ...................................... 195
5.3. Most significant bit first (MSB) multiplier for F2m ...... 230
5.4. Least significant bit first (LSB) multiplier for F2m ..... 231
5.5. Digit-serial multiplier for F2m .......................... 234
5.6. Inversion in F2m (m odd) ................................. 237
5.7. SPA-resistant left-to-right binary point
multiplication ........................................... 242
5.8. RSA-OAEP encryption ...................................... 246
5.9. RSA-OAEP decryption ...................................... 247
A.l. Testing a polynomial for irreducibility .................. 258
List of Tables
1.1. RSA, DL and EC key sizes for equivalent security
levels .................................................... 19
2.1. OEF example parameters .................................... 62
2.2. Computational details for inversion in OEFs ............... 68
2.3. Computational details for inversion in OEFs ............... 68
3.1. Admissible orders of elliptic curves over F37 ............. 83
3.2. Isomorphism classes of elliptic curves over F5 ............ 85
3.3. Operation counts for arithmetic on у2 = х3 — Зх + b ....... 92
3.4. Operation counts for arithmetic on
y2 + xy = x3 + ax2 + b .................................... 96
3.5. Point addition cost in sliding versus window NAF
methods .................................................. 102
3.6. Operation counts for computing kP + lQ ................... 113
3.7. Operation counts in comb and interleaving methods ........ 113
3.8. Koblitz curves with almost-prime group order ............. 115
3.9. Expressions for αu (for the Koblitz curve Ј0) ............ 121
3.10.Expressions for αu (for the Koblitz curve E1) ............ 122
3.11.Operation counts for point multiplication (random
curve over F2163 ......................................... 140
3.12.Point multiplication costs for P-192 ..................... 143
3.13.Point multiplication costs for B-163 and K-163 ........... 145
3.14.Point multiplication timings for P-192, B-163, and
K-163 .................................................... 146
5.1. Partial history and features of the Intel IA-32
family of processors ..................................... 207
5.2. Instruction latency/throughput for Pentium II/III vs
Pentium 4 ................................................ 208
5.3. Timings for field arithmetic (binary vs prime vs OEF) .... 220
5.4. Timings for binary field arithmetic ...................... 221
5.5. Timings for prime field arithmetic ....................... 221
5.6. Multiplication and inversion times ....................... 222
5.7. Multiplication times for the MST prime
p224 = 2224 - 296 + l ..................................... 224
5.8. Priorities for hardware design criteria .................. 229
5.9. Operation counts for inversion via multiplication in
binary fields ............................................ 238
A.l. Irreducible binary polynomials of degree m,
2 ≤ m ≤ 300 .............................................. 259
A.2 Irreducible binary polynomials of degree m,
301 ≤ m ≤ 600 ............................................ 260
A.3. NIST-recommended random elliptic curves over prime
fields ................................................... 262
A.4. NIST-recommended random elliptic curves over binary
fields ................................................... 264
A.5. NIST-recommended Koblitz curves over binary fields ....... 265
B.l. ECC standards and draft standards ........................ 268
B.2. URLs for standards bodies and working groups ............. 268
List of Figures
1.1. Basic communications model ................................. 2
1.2. Symmetric-key versus public-key cryptography ............... 4
2.1. Representing a prime-field element as an array of words ... 29
2.2. Depth-2 splits for 224-bit integers (Karatsuba-Ofman
multiplication) ........................................... 33
2.3. Depth-2 splits for 192-bit integers (Karatsuba-Ofman
multiplication) ........................................... 34
2.4. Representing a binary-field element as an array of
words ..................................................... 47
2.5. Right-to-left comb method for polynomial multiplication ... 49
2.6. Left-to-right comb method for polynomial multiplication ... 49
2.7. Left-to-right comb method with windows of width ω ......... 51
2.8. Squaring a binary polynomial .............................. 52
2.9. Reduction of a wordmodulo
f(z) = z163 + z7 + z6 + z3 + l ............................. 54
3.1. ECDSA support modules ..................................... 75
3.2. Elliptic curves over the real numbers ..................... 77
3.3. Geometric addition and doubling of elliptic curve
points .................................................... 80
3.4. Montgomery point multiplication .......................... 103
3.5. Fixed-base comb method for point multiplication .......... 107
3.6. The exponent array in Lim-Lee combing methods ............ 108
3.7. Simultaneous point multiplication accumulation step ...... 109
3.8. Interleaving with NAFs ................................... 112
4.1. Illustration of Pollard's rho algorithm .................. 158
4.2. Illustration of parallelized Pollard's rho algorithm ..... 162
5.1. Splitting of a 64-bit floating-point number .............. 211
5.2. Hierarchy of operations in elliptic curve
cryptographic schemes .................................... 226
5.3. Elliptic curve processor architecture .................... 227
5.4. Most significant bit first (MSB) multiplier for F25 ...... 231
5.5. Least significant bit first (LSB) multiplier for F25 ..... 232
5.6. MSB multiplier with fixed reduction polynomial ........... 232
5.7. MSB multiplier for fields F2m with 1 ≤ m ≤ 10 ............ 233
5.8. MSB multiplier for fields F25,F27,and F210 ................ 234
5.9. Multiplicand in a 2-digit multiplier for F25 ............. 235
5.10.A 2-digit multiplier for F25 ............................. 235
5.11.Squaring circuit for F27 with fixed
reduction polynomial ..................................... 236
5.12.CMOS logic inverter ...................................... 239
5.13.Power trace for a sequence of addition and double
operations ............................................... 240
5.14.Power trace for SPA-resistant elliptic curve
operations ............................................... 241
5.15.OAEP encoding function ................................... 246
5.16.OAEP decoding function ................................... 247
|
