Mathematics of Public Key Cryptography (Version 1.1)

ToC
......Page 1
Acknowledgements......Page 11
1 Introduction......Page 12
1.2 The Textbook RSA Cryptosystem......Page 13
1.3 Formal Definition of Public Key Cryptography......Page 15
1.3.1 Security of Encryption......Page 16
1.3.2 Security of Signatures......Page 18
I Background......Page 21
2.1 Algorithms and Complexity......Page 23
2.1.1 Randomised Algorithms......Page 25
2.1.2 Success Probability of a Randomised Algorithm......Page 26
2.1.3 Reductions......Page 28
2.1.4 Random Self-Reducibility......Page 29
2.2 Integer Operations......Page 30
2.2.1 Faster Integer Multiplication......Page 31
2.3 Euclid's Algorithm......Page 33
2.4 Computing Legendre and Jacobi Symbols......Page 36
2.5 Modular Arithmetic......Page 38
2.6 Chinese Remainder Theorem......Page 39
2.7 Linear Algebra......Page 40
2.8 Modular Exponentiation......Page 41
2.9 Square Roots Modulo p......Page 43
2.10 Polynomial Arithmetic......Page 46
2.11 Arithmetic in Finite Fields......Page 47
2.12 Factoring Polynomials over Finite Fields......Page 49
2.14.1 Constructing Finite Fields......Page 51
2.14.2 Solving Quadratic Equations in Finite Fields......Page 52
2.14.3 Isomorphisms Between Finite Fields......Page 53
2.15 Computing Orders of Elements and Primitive Roots......Page 54
2.15.1 Sets of Exponentials of Products......Page 55
2.15.3 Computing Primitive Roots......Page 57
2.16 Fast Evaluation of Polynomials at Multiple Points......Page 58
2.18 Summary......Page 59
3.1 Security Properties of Hash Functions......Page 61
3.2 Birthday Attack......Page 62
3.5 Number-Theoretic Hash Functions......Page 63
3.7 Random Oracle Model......Page 64
II Algebraic Groups......Page 67
4.1 Informal Definition of an Algebraic Group......Page 69
4.3 Algebraic Group Quotients......Page 71
4.4 Algebraic Groups over Rings......Page 72
5.1 Affine algebraic sets......Page 73
5.2 Projective Algebraic Sets......Page 77
5.3 Irreducibility......Page 82
5.4 Function Fields......Page 84
5.5 Rational Maps and Morphisms......Page 86
5.6 Dimension......Page 90
5.7 Weil Restriction of Scalars......Page 91
6.1 Cyclotomic Subgroups of Finite Fields......Page 95
6.2 Algebraic Tori......Page 97
6.3 The Group G_{q,2}......Page 98
6.3.1 The Torus T2......Page 99
6.3.2 Lucas Sequences......Page 100
6.4 The Group Gq,6......Page 102
6.4.1 The Torus T6......Page 103
6.4.2 XTR......Page 105
6.6 Algebraic Tori over Rings......Page 106
7.1 Non-Singular Varieties......Page 109
7.2 Weierstrass Equations......Page 113
7.3 Uniformizers on Curves......Page 115
7.4 Valuation at a Point on a Curve......Page 117
7.5 Valuations and Points on Curves......Page 119
7.6 Divisors......Page 120
7.7 Principal Divisors......Page 121
7.8 Divisor Class Group......Page 124
7.9 Elliptic Curves......Page 126
8.1 Rational Maps of Curves and the Degree......Page 131
8.2 Extensions of Valuations......Page 134
8.3 Maps on Divisor Classes......Page 136
8.4 Riemann-Roch Spaces......Page 140
8.5 Derivations and Differentials......Page 141
8.6 Genus Zero Curves......Page 147
8.7 Riemann-Roch Theorem and Hurwitz Genus Formula......Page 148
9.1 Group law......Page 151
9.2 Morphisms Between Elliptic Curves......Page 153
9.3 Isomorphisms of Elliptic Curves......Page 154
9.4 Automorphisms......Page 156
9.5 Twists......Page 157
9.6 Isogenies......Page 158
9.7 The Invariant Differential......Page 164
9.8 Multiplication by n and Division Polynomials......Page 166
9.9 Endomorphism Structure......Page 168
9.10 Frobenius map......Page 169
9.10.1 Complex Multiplication......Page 172
9.11 Supersingular Elliptic Curves......Page 174
9.12.1 Montgomery Model......Page 177
9.12.2 Edwards Model......Page 181
9.13 Statistics of Elliptic Curves over Finite Fields......Page 184
9.14 Elliptic Curves over Rings......Page 185
10 Hyperelliptic Curves......Page 187
10.1 Non-Singular Models for Hyperelliptic Curves......Page 188
10.1.1 Projective Models for Hyperelliptic Curves......Page 190
10.1.2 Uniformizers on Hyperelliptic Curves......Page 193
10.2 Isomorphisms, Automorphisms and Twists......Page 195
10.3 Effective Affine Divisors on Hyperelliptic Curves......Page 198
10.3.1 Mumford Representation of Semi-Reduced Divisors......Page 199
10.3.2 Addition and Semi-Reduction of Divisors in Mumford Representation......Page 200
10.3.3 Reduction of Divisors in Mumford Representation......Page 203
10.4.1 Addition of Divisor Classes on Ramified Models......Page 205
10.4.2 Addition of Divisor Classes on Split Models......Page 207
10.5 Jacobians, Abelian Varieties and Isogenies......Page 212
10.6 Elements of Order n......Page 214
10.7 Hyperelliptic Curves Over Finite Fields......Page 215
10.9 Supersingular Curves......Page 219
III Exponentiation, Factoring and Discrete Logarithms......Page 221
11 Basic Algorithms for Algebraic Groups......Page 223
11.1.1 Non-Adjacent Form......Page 224
11.1.2 Width-w Non-Adjacent Form......Page 227
11.2 Multi-exponentiation......Page 228
11.3.1 Alternative Basic Operations......Page 230
11.3.2 Frobenius Expansions......Page 231
11.3.3 GLV Method......Page 237
11.4 Sampling from Algebraic Groups......Page 238
11.4.1 Sampling from Tori......Page 239
11.4.2 Sampling from Elliptic Curves......Page 240
11.5 Determining Elliptic Curve Group Structure......Page 243
11.7 Elliptic Curve Point Compression......Page 245
12.1 Primality Testing......Page 247
12.1.2 The Miller-Rabin Test......Page 248
12.2 Generating Random Primes......Page 249
12.2.1 Primality Certificates......Page 250
12.3 The p - 1 Factoring Method......Page 251
12.4 Elliptic Curve Method......Page 252
12.5 Pollard-Strassen Method......Page 253
13 Basic Discrete Logarithm Algorithms......Page 255
13.2 The Pohlig-Hellman Method......Page 256
13.3 Baby-Step-Giant-Step (BSGS) Method......Page 259
13.4 Lower Bounds on the DLP......Page 261
13.4.2 Maurer's Model for Generic Algorithms......Page 262
13.4.3 The Lower Bound......Page 263
13.5 Generalised Discrete Logarithm Problems......Page 264
13.6 Low Hamming Weight DLP......Page 265
13.7 Low Hamming Weight Product Exponents......Page 267
13.8 Wagner's Generalised Birthday Algorithm......Page 268
14.1 Birthday Paradox......Page 271
14.2 The Pollard Rho Method......Page 273
14.2.1 The Pseudorandom Walk......Page 274
14.2.2 Pollard Rho Using Floyd Cycle Finding......Page 275
14.2.3 Other Cycle Finding Methods......Page 278
14.2.4 Distinguished Points and Pollard Rho......Page 279
14.2.5 Towards a Rigorous Analysis of Pollard Rho......Page 281
14.3.1 The Algorithm and its Heuristic Analysis......Page 283
14.4 Using Equivalence Classes......Page 286
14.4.1 Examples of Equivalence Classes......Page 287
14.4.2 Dealing with Cycles......Page 288
14.4.3 Practical Experience with the Distributed Rho Algorithm......Page 289
14.5 The Kangaroo Method......Page 290
14.5.2 The Kangaroo Algorithm......Page 291
14.5.3 Heuristic Analysis of the Kangaroo Method......Page 292
14.5.5 Using Inversion......Page 294
14.5.6 Towards a Rigorous Analysis of the Kangaroo Method......Page 295
14.6.1 Van Oorschot and Wiener Version......Page 297
14.6.2 Pollard Version......Page 300
14.7 The Gaudry-Schost Algorithm......Page 301
14.7.1 Two-Dimensional Discrete Logarithm Problem......Page 302
14.8 Parallel Collision Search in Other Contexts......Page 304
14.8.1 The Low Hamming Weight DLP......Page 305
14.9 Pollard Rho Factoring Method......Page 306
14.10 Pollard Kangaroo Factoring......Page 308
15.1 Smooth Integers......Page 309
15.2 Factoring using Random Squares......Page 311
15.2.1 Complexity of the Random Squares Algorithm......Page 313
15.2.2 The Quadratic Sieve......Page 315
15.3 Elliptic Curve Method Revisited......Page 316
15.4 The Number Field Sieve......Page 318
15.5.1 Rigorous Subexponential Discrete Logarithms Modulo p......Page 320
15.5.2 Heuristic Algorithms for Discrete Logarithms Modulo p......Page 322
15.5.3 Discrete Logarithms in Small Characteristic......Page 323
15.5.4 Coppersmith's Algorithm for the DLP in F*_{2^n}......Page 324
15.5.5 The Joux-Lercier Algorithm......Page 327
15.5.7 Discrete Logarithms for all Finite Fields......Page 328
15.6 Discrete Logarithms on Hyperelliptic Curves......Page 329
15.6.1 Index Calculus on Hyperelliptic Curves......Page 330
15.6.3 Gaudry's Algorithm......Page 331
15.7 Weil Descent......Page 332
15.8.1 Semaev's Summation Polynomials......Page 333
15.8.2 Gaudry's Variant of Semaev's Method......Page 334
15.8.3 Diem's Algorithm for the ECDLP......Page 335
15.9.3 Index Calculus for General Elliptic Curves......Page 336
IV Lattices......Page 339
16 Lattices......Page 341
16.1 Basic Notions on Lattices......Page 343
16.2 The Hermite and Minkowski Bounds......Page 346
16.3 Computational Problems in Lattices......Page 348
17 Lattice Basis Reduction......Page 351
17.1 Lattice Basis Reduction in Two Dimensions......Page 352
17.1.1 Connection Between Lagrange-Gauss Reduction and Euclid's Algorithm......Page 354
17.2 LLL-Reduced Lattice Bases......Page 355
17.3 The Gram-Schmidt Algorithm......Page 359
17.4 The LLL Algorithm......Page 361
17.5 Complexity of LLL......Page 364
17.6 Variants of the LLL Algorithm......Page 367
18.1 Babai's Nearest Plane Method......Page 369
18.2 Babai's Rounding Technique......Page 374
18.3 The Embedding Technique......Page 376
18.4 Enumerating all Short Vectors......Page 377
18.5 Korkine-Zolotarev Bases......Page 380
19 Coppersmith's Method and Related Applications......Page 383
19.1.1 First Steps to Coppersmith's Method......Page 384
19.1.2 The Full Coppersmith Method......Page 386
19.3 Bivariate Integer Polynomials......Page 389
19.4.1 Fixed Padding Schemes in RSA......Page 392
19.4.2 Factoring N = pq with Partial Knowledge of p......Page 393
19.4.4 Chinese Remaindering with Errors......Page 395
19.5 Simultaneous Diophantine Approximation......Page 398
19.6 Approximate Integer Greatest Common Divisors......Page 399
19.7 Learning with Errors......Page 400
19.8 Further Applications of Lattice Reduction......Page 402
19.9 Goldreich-Goldwasser-Halevi Cryptosystem......Page 403
19.10 Cryptanalysis of GGH Encryption......Page 406
19.11 GGH Signatures......Page 408
19.13 Knapsack Cryptosystems......Page 409
19.13.1 Public Key Encryption Using Knapsacks......Page 411
19.13.2 Cryptanalysis of Knapsack Cryptosystems......Page 413
V Cryptography Related to Discrete Logarithms......Page 419
20.1 The Discrete Logarithm Assumption......Page 421
20.2.1 Diffie-Hellman Key Exchange......Page 422
20.2.3 Key Derivation Functions......Page 423
20.3 Textbook Elgamal Encryption......Page 424
20.4 Security of Textbook Elgamal Encryption......Page 425
20.4.2 OWE Security Under CCA Attacks......Page 426
20.4.3 Semantic Security Under Passive Attacks......Page 427
20.5 Security of Diffie-Hellman Key Exchange......Page 429
20.6 Efficiency of Discrete Logarithm Cryptography......Page 431
21.1 Variants of the Diffie-Hellman Problem......Page 433
21.2 Lower Bound on the Complexity of CDH for Generic Algorithms......Page 436
21.3 Random Self-Reducibility and Self-Correction of CDH......Page 437
21.4.1 Implicit Representations......Page 440
21.4.2 The den Boer Reduction......Page 441
21.4.3 The Maurer Reduction......Page 443
21.5 Algorithms for Static Diffie-Hellman......Page 448
21.6 Hard Bits of Discrete Logarithms......Page 451
21.6.1 Hard Bits for DLP in Algebraic Group Quotients......Page 454
21.7 Bit Security of Diffie-Hellman......Page 455
21.7.1 The Hidden Number Problem......Page 456
21.7.2 Hard Bits for CDH Modulo a Prime......Page 458
21.7.3 Hard Bits for CDH in Other Groups......Page 460
21.8 Further Topics......Page 461
22.1.1 The Schnorr Identification Scheme......Page 463
22.1.2 Schnorr Signatures......Page 467
22.1.3 Security of Schnorr Signatures......Page 468
22.2 Other Public Key Signature Schemes......Page 469
22.2.1 Elgamal Signatures in Prime Order Subgroups......Page 470
22.2.2 DSA......Page 472
22.2.3 Signatures Secure in the Standard Model......Page 473
22.3 Lattice Attacks on Signatures......Page 475
22.4 Other Signature Functionalities......Page 476
23.1 CCA Secure Elgamal Encryption......Page 479
23.1.1 The KEM/DEM Paradigm......Page 481
23.1.2 Proof of Security in the Random Oracle Model......Page 482
23.2 Cramer-Shoup Encryption......Page 484
23.3.1 Homomorphic Encryption......Page 487
23.3.2 Identity-Based Encryption......Page 488
VI Cryptography Related to Integer Factorisation......Page 491
24.1 The Textbook RSA Cryptosystem......Page 493
24.1.2 Variants of RSA......Page 495
24.1.3 Security of Textbook RSA......Page 497
24.2 The Textbook Rabin Cryptosystem......Page 499
24.2.1 Redundancy Schemes for Unique Decryption......Page 500
24.2.2 Variants of Rabin......Page 502
24.2.3 Security of Textbook Rabin......Page 503
24.2.4 Other Computational Problems Related to Factoring......Page 505
24.3 Homomorphic Encryption......Page 506
24.4.1 The Hastad Attack......Page 508
24.4.3 Desmedt-Odlyzko Attack......Page 509
24.4.5 Fixed Pattern RSA Signature Forgery......Page 510
24.4.6 Two Attacks by Bleichenbacher......Page 512
24.5.1 Wiener Attack on Small Private Exponent RSA......Page 513
24.5.2 Small CRT Private Exponents......Page 515
24.5.3 Large Common Factor of p - 1 and q - 1......Page 516
24.6.1 Full Domain Hash......Page 517
24.6.2 Secure Rabin-Williams Signatures in the Random Oracle Model......Page 518
24.6.3 Other Signature and Identification Schemes......Page 520
24.7.1 Padding Schemes for RSA and Rabin......Page 522
24.7.2 OAEP......Page 523
24.7.3 Rabin-SAEP......Page 524
24.7.4 Further Topics......Page 527
VII Advanced Topics in Elliptic and Hyperelliptic Curves......Page 529
25.1 Isogenies and Kernels......Page 531
25.1.1 V???elu's Formulae......Page 533
25.2 Isogenies from j-invariants......Page 538
25.2.1 Elkies' Algorithm......Page 540
25.2.3 The Small Characteristic Case......Page 542
25.3 Isogeny Graphs of Elliptic Curves over Finite Fields......Page 543
25.3.1 Ordinary Isogeny Graph......Page 544
25.3.2 Expander Graphs and Ramanujan Graphs......Page 547
25.3.3 Supersingular Isogeny Graph......Page 548
25.4.1 Isogeny Volcanoes......Page 549
25.4.2 Kohel's Algorithm (Ordinary Case)......Page 552
25.5 Constructing Isogenies Between Elliptic Curves......Page 553
25.5.1 The Galbraith Algorithm......Page 554
25.5.2 The Galbraith-Hess-Smart Algorithm......Page 555
25.6 Relating Discrete Logs......Page 556
26.1 Weil Reciprocity......Page 559
26.2 The Weil Pairing......Page 560
26.3 The Tate-Lichtenbaum Pairing......Page 562
26.3.1 Miller's Algorithm......Page 563
26.3.2 The Reduced Tate-Lichtenbaum Pairing......Page 564
26.3.3 Ate Pairing......Page 566
26.3.4 Optimal Pairings......Page 567
26.3.5 Pairing Lattices......Page 568
26.4 Reduction of ECDLP to Finite Fields......Page 569
26.4.1 Anomalous Curves......Page 570
26.5.1 Pairing Inversion......Page 571
26.6 Pairing-Friendly Elliptic Curves......Page 572
26.6.2 Using Twists to Improve Pairing-Based Cryptography......Page 574
Appendices......Page 575
A.4 Modules......Page 576
A.5 Polynomials......Page 577
A.5.2 Resultants......Page 578
A.6 Field Extensions......Page 579
A.7.1 Galois Cohomology......Page 580
A.8 Finite Fields......Page 581
A.9 Ideals......Page 582
A.10 Vector Spaces and Linear Algebra......Page 583
A.10.1 Inner Products and Norms......Page 584
A.10.3 Determinants......Page 585
A.13 Binary Strings......Page 586
A.14 Probability and Combinatorics......Page 587
B Hints and Solutions to Exercises......Page 591
Author Index......Page 665
Subject Index......Page 672