Mathematics of Public Key Cryptography

Cover
......Page 1
MATHEMATICS OF PUBLIC KEY CRYPTOGRAPHY......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 7
Preface......Page 15
Acknowledgements......Page 16
1: Introduction......Page 17
1.2 The textbook RSA cryptosystem......Page 18
1.3 Formal definition of public key cryptography......Page 20
1.3.1 Security of encryption......Page 22
1.3.2 Security of signatures......Page 23
PART I: BACKGROUND......Page 27
2.1 Algorithms and complexity......Page 29
2.1.1 Randomised algorithms......Page 32
2.1.2 Success probability of a randomised algorithm......Page 33
2.1.3 Reductions......Page 35
2.1.4 Random self-reducibility......Page 36
2.2 Integer operations......Page 37
2.2.1 Faster integer multiplication......Page 38
2.3 Euclid's algorithm......Page 40
2.4 Computing Legendre and Jacobi symbols......Page 43
2.5 Modular arithmetic......Page 45
2.6 Chinese remainder theorem......Page 47
2.7 Linear algebra......Page 48
2.8 Modular exponentiation......Page 49
2.9 Square roots modulo p......Page 52
2.10 Polynomial arithmetic......Page 54
2.11 Arithmetic in finite fields......Page 55
2.12 Factoring polynomials over finite fields......Page 56
2.14.1 Constructing finite fields......Page 59
2.14.2 Solving quadratic equations in finite fields......Page 60
2.14.3 Isomorphisms between finite fields......Page 61
2.15.1 Sets of exponentials of products......Page 63
2.15.3 Computing primitive roots......Page 66
2.16 Fast evaluation of polynomials at multiple points......Page 67
2.18 Summary......Page 69
3.1 Security properties of hash functions......Page 70
3.2 Birthday attack......Page 71
3.4 Constructions of hash functions......Page 72
3.6 Full domain hash......Page 73
3.7 Random oracle model......Page 74
PART II: ALGEBRAIC GROUPS......Page 75
4.1 Informal definition of an algebraic group......Page 77
4.2 Examples of algebraic groups......Page 78
4.3 Algebraic group quotients......Page 79
4.4 Algebraic groups over rings......Page 80
5.1 Affine algebraic sets......Page 82
5.2 Projective algebraic sets......Page 85
5.3 Irreducibility......Page 90
5.4 Function fields......Page 92
5.5 Rational maps and morphisms......Page 95
5.6 Dimension......Page 99
5.7 Weil restriction of scalars......Page 100
6.1 Cyclotomic subgroups of finite fields......Page 102
6.2 Algebraic tori......Page 104
6.3 The group Gq,2......Page 105
6.3.1 The torus T2......Page 106
6.3.2 Lucas sequences......Page 108
6.4 The group Gq,6......Page 110
6.4.1 The torus T6......Page 111
6.4.2 XTR......Page 113
6.6 Algebraic tori over rings......Page 115
7.1 Non-singular varieties......Page 117
7.2 Weierstrass equations......Page 121
7.3 Uniformisers on curves......Page 122
7.4 Valuation at a point on a curve......Page 124
7.5 Valuations and points on curves......Page 126
7.6 Divisors......Page 127
7.7 Principal divisors......Page 128
7.8 Divisor class group......Page 130
7.9 Elliptic curves......Page 132
8.1 Rational maps of curves and the degree......Page 137
8.2 Extensions of valuations......Page 139
8.3 Maps on divisor classes......Page 142
8.4 Riemann-Roch spaces......Page 145
8.5 Derivations and differentials......Page 146
8.6 Genus zero curves......Page 152
8.7 Riemann–Roch theorem and Hurwitz genus formula......Page 153
9.1 Group law......Page 154
9.2 Morphisms between elliptic curves......Page 156
9.3 Isomorphisms of elliptic curves......Page 158
9.4 Automorphisms......Page 159
9.5 Twists......Page 160
9.6 Isogenies......Page 162
9.7 The invariant differential......Page 169
9.8 Multiplication by n and division polynomials......Page 171
9.9 Endomorphism structure......Page 172
9.10 Frobenius map......Page 174
9.10.1 Complex multiplication......Page 178
9.11 Supersingular elliptic curves......Page 180
9.12.1 Montgomery model......Page 184
9.12.2 Edwards model......Page 188
9.13 Statistical properties of elliptic curves over finite fields......Page 191
9.14 Elliptic curves over rings......Page 193
10: Hyperelliptic curves......Page 194
10.1 Non-singular models for hyperelliptic curves......Page 195
10.1.1 Projective models for hyperelliptic curves......Page 197
10.1.2 Uniformisers on hyperelliptic curves......Page 200
10.1.3 The genus of a hyperelliptic curve......Page 201
10.2 Isomorphisms, automorphisms and twists......Page 202
10.3 Effective affine divisors on hyperelliptic curves......Page 204
10.3.1 Mumford representation of semi-reduced divisors......Page 205
10.3.2 Addition and semi-reduction of divisors in Mumford representation......Page 207
10.3.3 Reduction of divisors in Mumford representation......Page 209
10.4 Addition in the divisor class group......Page 212
10.4.1 Addition of divisor classes on ramified models......Page 213
10.4.2 Addition of divisor classes on split models......Page 214
10.5 Jacobians, Abelian varieties and isogenies......Page 220
10.7 Hyperelliptic curves over finite fields......Page 222
10.8 Supersingular curves......Page 225
PART III: EXPONENTIATION, FACTORING AND
DISCRETE LOGARITHMS......Page 229
11.1 Efficient exponentiation using signed exponents......Page 231
11.1.1 Non-adjacent form......Page 232
11.2 Multi-exponentiation......Page 235
11.3.1 Alternative basic operations......Page 237
11.3.2 Frobenius expansions......Page 238
11.3.3 GLV method......Page 244
11.4 Sampling from algebraic groups......Page 247
11.4.2 Sampling from elliptic curves......Page 248
11.4.3 Hashing to algebraic groups......Page 250
11.5 Determining group structure and computing generators for elliptic curves......Page 251
11.6 Testing subgroup membership......Page 252
12.1.1 Fermat test......Page 254
12.1.2 The Miller–Rabin test......Page 255
12.2 Generating random primes......Page 256
12.2.1 Primality certificates......Page 257
12.3 The p − 1 factoring method......Page 258
12.4 Elliptic curve method......Page 260
12.5 Pollard–Strassen method......Page 261
13: Basic discrete logarithm algorithms......Page 262
13.2 The Pohlig–Hellman method......Page 263
13.3 Baby-step–giant-step (BSGS) method......Page 266
13.4.1 Shoup's model for generic algorithms......Page 269
13.4.2 Maurer's model for generic algorithms......Page 270
13.4.3 The lower bound......Page 271
13.5 Generalised discrete logarithm problems......Page 272
13.6 Low Hamming weight DLP......Page 274
13.7 Low Hamming weight product exponents......Page 276
14.1 Birthday paradox......Page 278
14.2 The Pollard rho method......Page 280
14.2.1 The pseudorandom walk......Page 281
14.2.2 Pollard rho using Floyd cycle finding......Page 282
14.2.3 Other cycle finding methods......Page 284
14.2.4 Distinguished points and Pollard rho......Page 285
14.2.5 Towards a rigorous analysis of Pollard rho......Page 288
14.3.1 The algorithm and its heuristic analysis......Page 289
14.4 Speeding up the rho algorithm using equivalence classes......Page 292
14.4.1 Examples of equivalence classes......Page 293
14.4.2 Dealing with cycles......Page 294
14.5 The kangaroo method......Page 296
14.5.1 The pseudorandom walk......Page 297
14.5.2 The kangaroo algorithm......Page 298
14.5.3 Heuristic analysis of the kangaroo method......Page 299
14.5.4 Comparison with the rho algorithm......Page 301
14.5.5 Using inversion......Page 302
14.6 Distributed kangaroo algorithm......Page 303
14.6.1 Van Oorschot and Wiener version......Page 304
14.6.2 Pollard version......Page 306
14.7 The Gaudry–Schost algorithm......Page 308
14.7.1 Two-dimensional discrete logarithm problem......Page 309
14.7.2 Discrete logarithm problem in an interval using equivalence classes......Page 311
14.8 Parallel collision search in other contexts......Page 312
14.9 Pollard rho factoring method......Page 313
15.1 Smooth integers......Page 317
15.2 Factoring using random squares......Page 319
15.2.1 Complexity of the random squares algorithm......Page 321
15.2.2 The quadratic sieve......Page 323
15.2.3 Summary......Page 325
15.3 Elliptic curve method revisited......Page 326
15.4 The number field sieve......Page 328
15.5 Index calculus in finite fields......Page 329
15.5.1 Rigorous subexponential discrete logarithms modulo p......Page 330
15.5.2 Heuristic algorithms for discrete logarithms modulo p......Page 332
15.5.3 Discrete logarithms in small characteristic......Page 333
15.5.4 Coppersmith's algorithm for the DLP in F2n*......Page 335
15.5.5 The Joux–Lercier algorithm......Page 339
15.6 Discrete logarithms on hyperelliptic curves......Page 340
15.6.2 The algorithm of Adleman, De Marrais and Huang......Page 342
15.6.3 Gaudry's algorithm......Page 343
15.7 Weil descent......Page 344
15.8.1 Semaev's summation polynomials......Page 345
15.8.2 Gaudry's variant of Semaev's method......Page 346
15.9.1 Diem's algorithm for plane curves of low degree......Page 348
15.9.3 Index calculus for general elliptic curves......Page 349
PART IV:
LATTICES......Page 351
16: Lattices......Page 353
16.1 Basic notions on lattices......Page 354
16.2 The Hermite and Minkowski bounds......Page 359
16.3 Computational problems in lattices......Page 361
17.1 Lattice basis reduction in two dimensions......Page 363
17.1.1 Connection between Lagrange–Gauss reduction and Euclid’s algorithm......Page 366
17.2 LLL-reduced lattice bases......Page 368
17.3 The Gram–Schmidt algorithm......Page 372
17.4 The LLL algorithm......Page 374
17.5 Complexity of LLL......Page 378
17.6 Variants of the LLL algorithm......Page 381
18.1 Babai's nearest plane method......Page 382
18.2 Babai's rounding technique......Page 387
18.3 The embedding technique......Page 389
18.4 Enumerating all short vectors......Page 391
18.4.1 Enumeration of closest vectors......Page 394
18.5 Korkine–Zolotarev bases......Page 395
19.1.1 First steps to Coppersmith's method......Page 396
19.1.2 The full Coppersmith method......Page 399
19.3 Bivariate integer polynomials......Page 403
19.4.1 Fixed padding schemes in RSA......Page 406
19.4.2 Factoring N = pq with partial knowledge of p......Page 407
19.4.3 Factoring prq......Page 409
19.4.4 Chinese remaindering with errors......Page 410
19.5 Simultaneous Diophantine approximation......Page 413
19.6 Approximate integer greatest common divisors......Page 414
19.7 Learning with errors......Page 416
19.8 Further applications of lattice reduction......Page 418
PART V: CRYPTOGRAPHY RELATED TO DISCRETE LOGARITHMS......Page 419
20.2.1 Diffie–Hellman key exchange......Page 421
20.2.2 Burmester–Desmedt key exchange......Page 423
20.3 Textbook Elgamal encryption......Page 424
20.4.1 OWE against passive attacks......Page 426
20.4.2 OWE security under CCA attacks......Page 427
20.4.3 Semantic security under passive attacks......Page 428
20.5 Security of Diffie–Hellman key exchange......Page 430
20.6 Efficiency considerations for discrete logarithm cryptography......Page 432
21.1 Variants of the Diffie–Hellman problem......Page 434
21.2 Lower bound on the complexity of CDH for generic algorithms......Page 438
21.3 Random self-reducibility and self-correction of CDH......Page 439
21.4.1 Implicit representations......Page 442
21.4.2 The den Boer reduction......Page 443
21.4.3 The Maurer reduction......Page 445
21.5 Algorithms for static Diffie–Hellman......Page 451
21.6 Hard bits of discrete logarithms......Page 455
21.7 Bit security of Diffie–Hellman......Page 459
21.7.1 The hidden number problem......Page 460
21.7.2 Hard bits for CDH modulo a prime......Page 463
21.7.3 Hard bits for CDH in other groups......Page 465
22.1.1 The Schnorr identification scheme......Page 468
22.1.2 Schnorr signatures......Page 472
22.1.3 Security of Schnorr signatures......Page 473
22.1.4 Efficiency considerations for Schnorr signatures......Page 474
22.2.1 Elgamal signatures in prime order subgroups......Page 475
22.2.2 DSA......Page 478
22.2.3 Signatures secure in the standard model......Page 479
22.3 Lattice attacks on signatures......Page 482
22.4 Other signature functionalities......Page 483
23.1 CCA secure Elgamal encryption......Page 485
23.1.1 The KEM/DEM paradigm......Page 487
23.1.2 Proof of security in the random oracle model......Page 488
23.2 Cramer–Shoup encryption......Page 490
23.3.1 Homomorphic encryption......Page 494
23.3.2 Identity-based encryption......Page 496
PART VI: 
CRYPTOGRAPHY RELATED TO
INTEGER FACTORISATION......Page 499
24.1 The textbook RSA cryptosystem......Page 501
24.1.1 Efficient implementation of RSA......Page 502
24.1.2 Variants of RSA......Page 503
24.1.3 Security of textbook RSA......Page 504
24.2 The textbook Rabin cryptosystem......Page 507
24.2.1 Redundancy schemes for unique decryption......Page 508
24.2.2 Variants of Rabin......Page 510
24.2.3 Security of textbook Rabin......Page 511
24.3 Homomorphic encryption......Page 514
24.4 Algebraic attacks on textbook RSA and Rabin......Page 515
24.4.2 Algebraic attacks......Page 516
24.4.4 Related message attacks......Page 517
24.4.5 Fixed pattern RSA signature forgery......Page 518
24.5.1 Wiener attack on small private exponent RSA......Page 520
24.5.2 Small CRT private exponents......Page 522
24.6.1 Full domain hash......Page 523
24.6.2 Secure Rabin–Williams signatures in the random oracle model......Page 525
24.7 Public key encryption based on RSA and Rabin......Page 527
PART VII: 
ADVANCED TOPICS IN ELLIPTIC AND
HYPERELLIPTIC CURVES......Page 529
25.1 Isogenies and kernels......Page 531
25.1.1 Vélu's formulae......Page 533
25.2 Isogenies from j-invariants......Page 539
25.2.1 Elkies' algorithm......Page 541
25.2.2 Stark's algorithm......Page 543
25.2.3 The small characteristic case......Page 544
25.3 Isogeny graphs of elliptic curves over finite fields......Page 545
25.3.1 Ordinary isogeny graph......Page 546
25.3.2 Expander graphs and Ramanujan graphs......Page 549
25.3.3 Supersingular isogeny graph......Page 550
25.4 The structure of the ordinary isogeny graph......Page 551
25.4.1 Isogeny volcanoes......Page 552
25.4.2 Kohel's algorithm (ordinary case)......Page 554
25.5 Constructing isogenies between elliptic curves......Page 556
25.5.1 The Galbraith algorithm......Page 557
25.5.2 The Galbraith–Hess–Smart algorithm......Page 558
25.6 Relating the discrete logarithm problem on isogenous curves......Page 559
26.1 Weil reciprocity......Page 561
26.2 The Weil pairing......Page 562
26.3 The Tate–Lichtenbaum pairing......Page 564
26.3.2 The reduced Tate–Lichtenbaum pairing......Page 566
26.3.3 Ate pairing......Page 569
26.3.4 Optimal pairings......Page 570
26.3.5 Pairing lattices......Page 571
26.4 Reduction of ECDLP to finite fields......Page 573
26.4.1 Anomalous curves......Page 574
26.5.1 Pairing inversion......Page 575
26.5.2 Solving DDH using Pairings......Page 576
26.6 Pairing-friendly elliptic curves......Page 577
26.6.1 Distortion maps......Page 578
A.2 Groups......Page 580
A.4 Modules......Page 581
A.5.1 Homogeneous polynomials......Page 582
A.6 Field extensions......Page 583
A.7 Galois theory......Page 585
A.8 Finite fields......Page 586
A.9 Ideals......Page 587
A.10 Vector spaces and linear algebra......Page 588
A.10.1 Inner products and norms......Page 589
A.10.3 Determinants......Page 590
A.12 Orders in quadratic fields......Page 591
A.14 Probability and combinatorics......Page 592
References......Page 595
Author index......Page 619
Subject index......Page 624