Index

Symbols

O-notation (big-O), 16 o-notation (little-o), 16

Ln [α, c] (subexponential notation), 16 Fq (finite field of order q), 26

Fq (multiplicative group of Fq ), 29 F p (prime field), 26

F2m (binary field), 26

Q (the rational numbers), 25 R (the real numbers), 25

Z (the integers), 63

(bitwise exclusive-or), 47 & (bitwise AND), 47

i (right shift by i positions), 47i (left shift by i positions), 47 ∞ (point at infinity), 76

E(L) (L-rational points on E), 76

a b (concatenation of strings a, b), 104

#S (cardinality of a set S), 82

A

Abelian group, 11 Access control, 3 Additive group, 12

Admissible change of variables, 78 Advanced Encryption Standard, see AES Adversarial model, 3

AES, 3

Large, 18 Medium, 18 Small, 18

Affine coordinates, 79 Affine point, 87

AGM algorithm, 180, 201

Algorithm exponential-time, 16

fully-exponential-time, 16 polynomial-time, 16 running time, 16 subexponential-time, 16

Alignment, 218 Almost cyclic, 84

Almost inverse algorithm, 59, 223 Almost prime, 114, 173

American National Standards Institute, see ANSI

Anomalous binary curve, see Koblitz curve Anonymity, 3

ANSI, 267

X9.62, 175, 184, 257, 258, 267 X9.63, 189, 193, 195, 257, 258, 267

ASIC, 225

B

Barrett reduction, 36, 70, 220 Base point, 172

Big-O notation, 16 Binary field, 26

addition, 47, 229 arithmetic with MMX, 213 division, 57, 222 inversion, 57, 221, 236

Karatsuba-Ofman multiplication, 51 multiplication, 48, 221, 229 polynomial multiplication, 48 polynomial squaring, 52

reduction, 53 squaring, 235

306 Index

timings, 219–223 Binary inversion algorithm

for binary fields, 58, 223 for prime fields, 40

Birthday paradox, 157 Bit-serial multiplier, 230 Bleichenbacher’s attack, 255 Branch misprediction, 217

C

Carry bit, 30

Certicom ECDLP challenge, 22 Characteristic, 26 Characteristic-two finite field, 26 Chudnovsky coordinates, 90, 148 CM method, 179

co-NP, 154 Cofactor, 114, 172 Collision, 157 Comb method

for point multiplication, 105–109 for polynomial multiplication, 48–51

Confidentiality, 2 Coordinates

affine, 79 Chudnovsky, 90, 148 Jacobian, 88, 90, 93 LD, 93, 148 projective, 86–89

Cost-equivalent key sizes, 19 Cramer-Shoup public-key encryption, 204

Cryptographic Research and Evaluation Committee, see CRYPTREC

CRYPTREC, 191, 270 Cyclic group, 12

generator, 12 Cyclic subgroup, 12

D

Data encapsulation mechanism, 191 Data Encryption Standard, 3

Data integrity, 3

Data origin authentication, 3 DES, 3

Differential power analysis, see DPA Differential trace, 242

Diffie-Hellman problem, 10 Digit-serial multiplier, 230, 233 Digital Signature Algorithm (DSA), 10 Digital Signature Standard, 10 Discrete logarithm problem, 9 Discrete logarithm systems, 8–11

basic encryption scheme, 9 domain parameter generation, 9 key pair generation, 9 signature scheme, 10

Discriminant, 76 Distinguished point, 160

Division in binary fields, 60, 222 Domain parameters, 172–178, 257–263

generation, 174 validation, 175

DPA, 242, 254 DSA, 10

E

Early-abort strategy, 174, 180 EC-KCDSA, 186, 202

ECDLP, see elliptic curve discrete logarithm problem

ECDSA, 184, 202

ECIES, 189, 203

ECMQV, 195, 204 Efficient algorithm, 15

Electromagnetic analysis attacks, 244, 255 ElGamal encryption, 10, 14

Elliptic curve, 13

admissible change of variables, 78 affine coordinates, 79

affine point, 87

Chudnovsky coordinates, 90, 148 definition, 76

discriminant, 76 double of points, 79 endomorphism, 124 group law, 79–82 group structure, 83 Hessian form, 147, 254 isogenous, 199 isomorphic, 78

isomorphism classes, 84–86 Jacobi form, 147, 254

Jacobi model, 147

Jacobian coordinates, 88, 90, 93 LD coordinates, 93, 148 non-supersingular, 78, 83 order, 82

point, 13

point at infinity, 13, 76 projective point, 87 rational points, 76

selecting verifiably at random, 173 sum of points, 79

supersingular, 79, 83 trace, 82

underlying field, 77 Weierstrass equation, 77

Elliptic curve decision Diffie-Hellman problem, 172

Elliptic curve Diffie-Hellman problem, 171, 200

Elliptic curve discrete logarithm problem, 14, 153–172

GHS attack, 170, 199 index-calculus attack, 165 kangaroo algorithm, 197 Lambda method, 197

parallelized Pollard’s rho attack, 160 Pohlig-Hellman attack, 155 Pollard’s rho attack, 157, 197

prime-field-anomalous curves, 168, 198 Tate pairing attack, 169, 198

Weil descent attack, 170, 199 Weil pairing attack, 169, 198 xedni calculus, 198

Elliptic curve systems, 11–14 basic ElGamal encryption, 14 EC-KCDSA, 186

ECDSA, 184

ECIES, 189

ECMQV, 195

key pair generation, 14 PSEC, 191 station-to-station, 193

Embedding degree, 169 Endomorphism

definition of, 124

efficiently computable, 124–125, 150

Index 307

point multiplication, 129 Frobenius, 124

ring, 124

Entity authentication, 3

Error message analysis, 244–248 Explicit key authentication, 193 Exponent array, 105, 109 Exponential-time algorithm, 16 Extended Euclidean algorithm

for integers, 39

for polynomials, 57, 223 Extension field, 26, 28

F

Factor base, 165

Fault analysis, 248, 256

Federal Information Processing Standards, see FIPS

Field, 25

Finite field, 12, 25 binary, 26 characteristic, 26 extension, 26 isomorphic, 26 order, 26

prime, 26

primitive element, 63 subfield, 28

see also binary field, prime field, optimal extension field

FIPS, see NIST

Floating-point arithmetic, 209–212, 224 Floyd’s cycle-finding algorithm, 158 Forward secrecy, 193

FPGA, 225

Frobenius map, 67, 114, 124 Fully-exponential-time algorithm, 16

G

Gate, 225

Gate array, 225

Gaussian normal basis, 72, 263

Generator, 12

Generic group, 154

GH, 21

GHS attack, 170, 199

308 Index

GMR-secure, 183

GNU MP (gmp), 210, 215, 274 Greatest common divisor

of integers, 39

of polynomials, 57 Group, 11

generic, 154 Group law, 79–82

H

Half-trace function, 132 Hasse interval, 82 Hasse’s Theorem, 82 Hessian form, 147, 254 HMAC, 3

Hyperelliptic curve, 22, 150, 165, 170, 201 Hyperelliptic curve discrete logarithm prob-

lem, 170

I

IEEE, 269

1363-2000, 184, 195, 269 P1363a, 189, 269

IKE, 204

Implicit key authentication, 193 Implicit signature, 195 Index-calculus attack, 165

Institute of Electrical and Electronics Engineers, see IEEE

Integer

arithmetic with floating-point, 209, 224

Karatsuba-Ofman multiplication, 32 multiplication, 31, 206

reduction, 35 squaring, 34

Integer factorization problem, 6 Interleaving, 111

International Organization for Standardization, see ISO/IEC

Invalid-curve attack, 182, 201 Inversion

in binary fields, 57, 221, 236 in optimal extension fields, 67 in prime fields, 39

Irreducible polynomial, 257

ISO/IEC, 269 15946-1, 268

15946-2, 184, 186, 268

15946-3, 189, 195, 268

15946-4, 268

18033-2, 269 Isogenous elliptic curves, 199 Isomorphic

elliptic curves, 78, 84–86 fields, 26

J

Jacobi form, 147, 254

Jacobi model, 147

Jacobian coordinates, 88, 90, 93

Joint sparse form, 110, 149

K

Kangaroo algorithm, 197 Karatsuba-Ofman multiplication

for integers, 32, 223 for polynomials, 51 Kedlaya’s algorithm, 201

Key agreement protocol, 192 see also key establishment

Key confirmation, 193

Key derivation function, 182, 189, 191 Key distribution problem, 4

Key encapsulation mechanism, 191 Key establishment, 192–196

ECMQV, 195, 204 IKE, 204 OAKLEY, 204 security, 192 SKEME, 204

station-to-station, 193, 204 Key management problem, 4 Key pair, 180–182

generation, 14, 180 validation, 180, 201

Key transport protocol, 192

see also key establishment Key-compromise impersonation resilience,

193

Koblitz curve, 163, 263 almost-prime group order, 114

TNAF, 117

TNAF method, 119 window TNAF method, 123

L

Lambda method, 197 Latency, 208

LD coordinates, 93, 148 Lehmer’s gcd algorithm, 71

Lim-Lee exponentiation method, 108 Line at infinity, 87

Little-o notation, 16 LSB multiplier, 231 LUC, 21

M

Mobius¨ function, 258 MAC, 3 Malleability, 189 Modulus, 26

Monic polynomial, 257 Montgomery

inversion, 42, 71, 254 multiplication, 38

point multiplication, 102, 255 reduction, 38, 70

Mordell-Weil Theorem, 167 MSB multiplier, 230 Multiplexor, 226 Multiplicative group, 12

Index 309

reduction polynomial, 54, 220 Non-adjacent form (NAF), 98 Non-repudiation, 3 Non-supersingular, 78, 83

Normal basis, 72, 132, 253, 263 NP, 154

NP-hard, 154

Number Field Sieve, 17

O

OAKLEY, 204

OEF, see optimal extension field OpenSSL, 52, 256, 275

see also SSL

Optical fault induction attack, 256 Optimal extension field

addition, 63 inversion, 67 multiplication, 63 reduction, 63 subtraction, 63 timings, 219–220 Type, 62

Optimal normal basis, 72 Order

of a field element, 29 of a finite field, 26 of a group, 12

of a group element, 12 of an elliptic curve, 82

N

NAF, 98

National Institute of Standards and Technology, see NIST

NESSIE, 191, 270

New European Schemes for Signatures, Integrity and Encryption, see NESSIE

NIST, 269

FIPS 180-2, 269 FIPS 186, 10

FIPS 186-2, 184, 257, 261, 269 FIPS 197, 269

FIPS 198, 269

FIPS 46, 269 prime, 44, 220

P

Parallel processing, 226 Parallelized Pollard’s rho attack, 160 Pentanomial, 54, 130, 258 Pipelining, 226

Pohlig-Hellman attack, 155 Point, 13

double, 79 sum, 79

Point at infinity, 13, 76

Point counting algorithms, 179–180, 201 Point halving, 129–141, 151

halve-and-add, 137–141 Point multiplication, 95–113 binary NAF method, 99

310 Index

comparisons, 141–147 fixed-base comb method, 106

fixed-base NAF windowing method, 105

fixed-base windowing method, 104 halve-and-add, 137–141 interleaving, 111

left-to-right binary method, 97 Lim-Lee method, 108 right-to-left binary method, 96 sliding window method, 101 timings, 146–147

TNAF method, 119 window NAF method, 100 window TNAF method, 123

with efficiently computable endomorphisms, 129

Pollard’s rho attack, 17, 18, 157, 197 Polynomial

Karatsuba-Ofman multiplication, 51 multiplication, 48

reduction, 53 squaring, 52

Polynomial basis, 26 Polynomial security, 203 Polynomial-time algorithm, 16 Power analysis, 239–244

DPA, 242, 254

SPA, 240, 254 Power trace, 240 Prime field, 26

addition, 30

arithmetic with SIMD, 214, 224, 250 integer multiplication, 31

integer squaring, 34 inversion, 39

Karatsuba-Ofman multiplication, 32, 223

reduction, 35 subtraction, 30

timings, 219–220, 223–224 Prime-field-anomalous curve, 168, 198 Primitive element, 63

Program optimizations assembly coding, 217 duplicated code, 216

loop unrolling, 216

Projective coordinates, see coordinates Projective point, 87

PSEC, 191

Public key validation, 180, 201 Public-key cryptography, 4–5 Public-key encryption, 188–192 Cramer-Shoup, 204

ECIES, 189, 203 malleability, 189 polynomial security, 203 PSEC, 191

security, 188 semantic security, 203

Public-key infrastructure, 5

Q

Quadratic number field, 22, 165

Quantum computer, 196

Qubit, 196

R

Rational points, 76 RC4, 3

Reduction

Barrett, 36, 70, 220

Montgomery, 38, 70 polynomial, 27, 28

RSA, 6–8

basic encryption scheme, 6 basic signature scheme, 7 FDH, 248

key pair generation, 6 OAEP, 245, 256 PSS, 249

Running time, 16

S

Satoh’s algorithm, 180, 201

Scalar multiplication, see point multiplication

Schoof’s algorithm, 179, 201 SEA algorithm, 179, 201 SECG, 270

Security level, 18 Semantic security, 203

Session key, 192 SHA-1, 173 Shamir’s trick, 109

Side-channel attack, 238–250 electromagnetic analysis, 244 error message analysis, 244–248 fault analysis, 248–249

optical fault induction, 256 power analysis, 239–244 timing, 250

Signature scheme EC-KCDSA, 186, 202 ECDSA, 184, 202 security, 183

Signed digit representation, 98 SIMD, 213, 224, 250

Simple power analysis, see SPA Simultaneous inversion, 44 Single-instruction multiple-data, see SIMD SKEME, 204

SKIPJACK, 18

Small subgroup attack, 181, 201 SPA, 240, 254

SSL, 182, 228, 250, 256 see also OpenSSL SST algorithm, 180, 201

Standards, 267–270

ANSI, 267 CRYPTREC, 191, 270 FIPS, 269

IEEE, 269 ISO/IEC, 269 NESSIE, 191, 270 NIST, 269 SECG, 270

Standards for Efficient Cryptography Group (SECG), 270

Station-to-station protocol, 193, 204 STS, see station-to-station protocol Subexponential-time algorithm, 16 Subfield, 28

Superelliptic curve, 22 Supersingular, 79, 83 Symmetric-key cryptography, 3–4

Index 311

T

Tate pairing attack, 169, 198 Throughput, 208

Timing attack, 250, 256 TNAF, 117

Trace

function, 130

of an elliptic curve, 82 Trinomial, 53, 54, 130, 258 Triple-DES, 18

U

Underlying field, 77

Unknown key-share resilience, 193

V

VLSI, 225

W

Weierstrass equation, 77 Weil

descent attack, 170, 199 pairing attack, 169, 198

Width-w NAF, 99

TNAF, 120

X

Xedni calculus, 198

XTR, 21