Mathematics of Public Key Cryptography

by Galbraith, Steven D.

• ISBN13: 9781107013926
• ISBN10: 1107013925
• Format: Hardcover
• Copyright: 2012-04-30
• Publisher: Cambridge Univ Pr

Summary

Public key cryptography is a major interdisciplinary subject with many real-world applications, such as digital signatures. A strong background in the mathematics underlying public key cryptography is essential for a deep understanding of the subject, and this book provides exactly that for students and researchers in mathematics, computer science and electrical engineering. Carefully written to communicate the major ideas and techniques of public key cryptography to a wide readership, this text is enlivened throughout with historical remarks and insightful perspectives on the development of the subject. Numerous examples, proofs and exercises make it suitable as a textbook for an advanced course, as well as for self-study. For more experienced researchers it serves as a convenient reference for many important topics: the Pollard algorithms, Maurer reduction, isogenies, algebraic tori, hyperelliptic curves and many more.

Author Biography

Steven D. Galbraith is a leading international authority on the mathematics of public key cryptography. He is an Associate Professor in the Department of Mathematics at the University of Auckland.

Table of Contents

Preface	p. xiii
Acknowledgements	p. xiv
Introduction	p. 1
Public key cryptography	p. 2
The textbook RSA cryptosystem	p. 2
Formal definition of public key cryptography	p. 4
Background	p. 11
Basic algorithmic number theory	p. 13
Algorithms and complexity	p. 13
Integer operations	p. 21
Euclid's algorithm	p. 24
Computing Legendre and Jacobi symbols	p. 27
Modular arithmetic	p. 29
Chinese remainder theorem	p. 31
Linear algebra	p. 32
Modular exponentiation	p. 33
Square roots modulo p	p. 36
Polynomial arithmetic	p. 38
Arithmetic in finite fields	p. 39
Factoring polynomials over finite fields	p. 40
Hensel lifting	p. 43
Algorithms in finite fields	p. 43
Computing orders of elements and primitive roots	p. 47
Fast evaluation of polynomials at multiple points	p. 51
Pseudorandom generation	p. 53
Summary	p. 53
Hash functions and MACs	p. 54
Security properties of hash functions	p. 54
Birthday attack	p. 55
Message authentication codes	p. 56
Constructions of hash functions	p. 56
Number-theoretic hash functions	p. 57
Full domain hash	p. 57
Random oracle model	p. 58
Algebraic Groups	p. 59
Preliminary remarks on algebraic groups	p. 61
Informal definition of an algebraic group	p. 61
Examples of algebraic groups	p. 62
Algebraic group quotients	p. 63
Algebraic groups over rings	p. 64
Varieties	p. 66
Affine algebraic sets	p. 66
Projective algebraic sets	p. 69
Irreducibility	p. 74
Function fields	p. 76
Rational maps and morphisms	p. 79
Dimension	p. 83
Weil restriction of scalars	p. 84
Tori, LUC and XTR	p. 86
Cyclotomic subgroups of finite fields	p. 86
Algebraic tori	p. 88
The group Gq,2	p. 89
The group Gq,6	p. 94
Further remarks	p. 99
Algebraic tori over rings	p. 99
Curves and divisor class groups	p. 101
Non-singular varieties	p. 101
Weierstrass equations	p. 105
Uniformisers on curves	p. 106
Valuation at a point on a curve	p. 108
Valuations and points on curves	p. 110
Divisors	p. 111
Principal divisors	p. 112
Divisor class group	p. 114
Elliptic curves	p. 116
Rational maps on curves and divisors	p. 121
Rational maps of curves and the degree	p. 121
Extensions of valuations	p. 123
Maps on divisor classes	p. 126
Riemann-Roch spaces	p. 129
Derivations and differentials	p. 130
Genus zero curves	p. 136
Riemann-Roch theorem and Hurwitz genus formula	p. 137
Elliptic curves	p. 138
Group law	p. 138
Morphisms between elliptic curves	p. 140
Isomorphisms of elliptic curves	p. 142
Automorphisms	p. 143
Twists	p. 144
Isogenics	p. 146
The invariant differential	p. 153
Multiplication by n and division polynomials	p. 155
Endomorphism structure	p. 156
Frobenius map	p. 158
Supersingular elliptic curves	p. 164
Alternative models for elliptic curves	p. 168
Statistical properties of elliptic curves over finite fields	p. 175
Elliptic curves over rings	p. 177
Hyperelliptic curves	p. 178
Non-singular models for hyperelliptic curves	p. 179
Isomorphisms, automorphisms and twists	p. 186
Effective affine divisors on hyperelliptic curves	p. 188
Addition in the divisor class group	p. 196
Jacobians, Abelian varieties and isogenics	p. 204
Elements of order n	p. 206
Hyperelliptic curves over finite fields	p. 206
Supersingular curves	p. 209
Exponentiation, Factoring and Discrete Logarithms	p. 213
Basic algorithms for algebraic groups	p. 215
Efficient exponentiation using signed exponents	p. 215
Multi-exponentiation	p. 219
Efficient exponentiation in specific algebraic groups	p. 221
Sampling from algebraic groups	p. 231
Determining group structure and computing generators for elliptic curves	p. 235
Testing subgroup membership	p. 236
Primality testing and integer factorisation using algebraic groups	p. 238
Primality testing	p. 238
Generating random primes	p. 240
The p - 1 factoring method	p. 242
Elliptic curve method	p. 244
Pollard-Strassen method	p. 245
Basic discrete logarithm algorithms	p. 246
Exhaustive search	p. 247
The Pohlig-Hellman method	p. 247
Baby-step-giant-step (BSGS) method	p. 250
Lower bound on complexity of generic algorithms for the DLP	p. 253
Generalised discrete logarithm problems	p. 256
Low Hamming weight DLP	p. 258
Low Hamming weight product exponents	p. 260
Factoring and discrete logarithms using pseudorandom walks	p. 262
Birthday paradox	p. 262
The Pollard rho method	p. 264
Distributed Pollard rho	p. 273
Speeding up the rho algorithm using equivalence classes	p. 276
The kangaroo method	p. 280
Distributed kangaroo algorithm	p. 287
The Gaudry-Schost algorithm	p. 292
Parallel collision search in other contexts	p. 296
Pollard rho factoring method	p. 297
Factoring and discrete logarithms in subexponential time	p. 301
Smooth integers	p. 301
Factoring using random squares	p. 303
Elliptic curve method revisited	p. 310
The number field sieve	p. 312
Index calculus in finite fields	p. 313
Discrete logarithms on hyperelliptic curves	p. 324
Weil descent	p. 328
Discrete logarithms on elliptic curves over extension fields	p. 329
Further results	p. 332
Lattices	p. 335
Lattices	p. 337
Basic notions on lattices	p. 338
The Hermite and Minkowski bounds	p. 343
Computational problems in lattices	p. 345
Lattice basis reduction	p. 347
Lattice basis reduction in two dimensions	p. 347
LLL-reduced lattice bases	p. 352
The Gram-Schmidt algorithm	p. 356
The LL algorithm	p. 358
Complexity of LLL	p. 362
Variants of the LLL algorithm	p. 365
Algorithms for the closest and shortest vector problems	p. 366
Babai's nearest plane method	p. 366
Babai's rounding technique	p. 371
The embedding technique	p. 373
Enumerating all short vectors	p. 375
Korkine-Zolotarev bases	p. 379
Coppersmith's method and related applications	p. 380
Coppersmith's method for modular univariate polynomials	p. 380
Multivariate modular polynomial equations	p. 387
Bivariate integer polynomials	p. 387
Some applications of Coppersmith's method	p. 390
Simultaneous Diophantine approximation	p. 397
Approximate integer greatest common divisors	p. 398
Learning with errors	p. 400
Further applications of lattice reduction	p. 402
Cryptography Related to Discrete Logarithms	p. 403
The Diffie-Hellman problem and cryptographic applications	p. 405
The discrete logarithm assumption	p. 405
Key exchange	p. 405
Textbook Elgamal encryption	p. 408
Security of textbook Elgamal encryption	p. 410
Security of Diffie-Hellman key exchange	p. 414
Efficiency considerations for discrete logarithm cryptography	p. 416
The Diffie-Hellman problem	p. 418
Variants of the Diffie-Hellman problem	p. 418
Lower bound on the complexity of CDH for generic algorithms	p. 422
Random self-reducibility and self-correction of CDH	p. 423
The den Boer and Maurer reductions	p. 426
Algorithms for static Diffie-Hellman	p. 435
Hard bits of discrete logarithms	p. 439
Bit security of Diffie-Hellman	p. 443
Digital signatures based on discrete logarithms	p. 452
Schnorr signatures	p. 452
Other public key signature schemes	p. 459
Lattice attacks on signatures	p. 466
Other signature functionalities	p. 467
Public key encryption based on discrete logarithms	p. 469
CCA secure Elgamal encryption	p. 469
Cramer-Shoup encryption	p. 474
Other encryption functionalities	p. 478
Crytography Related to Integer Factorisation	p. 483
The RSA and Rabin cryptosystems	p. 485
The textbook RSA cryptosystem	p. 485
The textbook Rabin cryptosystem	p. 491
Homomorphic encryption	p. 498
Algebraic attacks on textbook RSA and Rabin	p. 499
Attacks on RSA parameters	p. 504
Digital signatures based on RSA and Rabin	p. 507
Public key encryption based on RSA and Rabin	p. 511
Advanced Topics in Elliptic and Hyperelliptic Curves	p. 513
Isogenics of elliptic curves	p. 515
Isogenics and kernels	p. 515
Isogenies from j-invariants	p. 523
Isogeny graphs of elliptic curves over finite fields	p. 529
	p. 535
Constructing isogenies between elliptic curves	p. 540
Relating the discrete logarithm problem on isogenous curves	p. 543
Pairings on elliptic curves	p. 545
Weil reciprocity	p. 545
The Weil pairing	p. 546
The Tate-Lichtenbaum pairing	p. 548
Reduction of ECDLP to finite fields	p. 557
Computational problems	p. 559
Pairing-friendly elliptic curves	p. 561
Background mathematics	p. 564
Basic notation	p. 564
Groups	p. 564
Rings	p. 565
Modules	p. 565
Polynomials	p. 566
Field extensions	p. 567
Galois theory	p. 569
Finite fields	p. 570
Ideals	p. 571
Vector spaces and linear algebra	p. 572
Hermite normal form	p. 575
Orders in quadratic fields	p. 575
Binary strings	p. 576
Probability and combinatorics	p. 576
Reference	p. 579
Author index	p. 603
Subject index	p. 608
Table of Contents provided by Ingram. All Rights Reserved.