Mathematics of public key cryptography

Select an Action

Place Hold(s)
Add to My Lists
Email
Print

Title:

Personal Author:

Galbraith, Steven D., author

Publication Information:

Cambridge ; New York : Cambridge University Press, 2012

Physical Description:

xiv, 615 pages ; 26 cm.

ISBN:

9781107013926

Abstract:

"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"--provided by publisher

Subject Term:

Coding theory

Cryptography -- Mathematics

Available:*

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... PSZ JB	30000010343205	QA268 G35 2012	Open Access Book	Book	Searching... Unknown

On Order

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 Notes

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.

Preface	p. xiii
Acknowledgements	p. xiv
1 Introduction	p. 1
1.1 Public key cryptography	p. 2
1.2 The textbook RSA cryptosystem	p. 2
1.3 Formal definition of public key cryptography	p. 4
Part I Background	p. 11
2 Basic algorithmic number theory	p. 13
2.1 Algorithms and complexity	p. 13
2.2 Integer operations	p. 21
2.3 Euclid's algorithm	p. 24
2.4 Computing Legendre and Jacobi symbols	p. 27
2.5 Modular arithmetic	p. 29
2.6 Chinese remainder theorem	p. 31
2.7 Linear algebra	p. 32
2.8 Modular exponentiation	p. 33
2.9 Square roots modulo p	p. 36
2.10 Polynomial arithmetic	p. 38
2.11 Arithmetic in finite fields	p. 39
2.12 Factoring polynomials over finite fields	p. 40
2.13 Hensel lifting	p. 43
2.14 Algorithms in finite fields	p. 43
2.15 Computing orders of elements and primitive roots	p. 47
2.16 Fast evaluation of polynomials at multiple points	p. 51
2.17 Pseudorandom generation	p. 53
2.18 Summary	p. 53
3 Hash functions and MACs	p. 54
3.1 Security properties of hash functions	p. 54
3.2 Birthday attack	p. 55
3.3 Message authentication codes	p. 56
3.4 Constructions of hash functions	p. 56
3.5 Number-theoretic hash functions	p. 57
3.6 Full domain hash	p. 57
3.7 Random oracle model	p. 58
Part II Algebraic Groups	p. 59
4 Preliminary remarks on algebraic groups	p. 61
4.1 Informal definition of an algebraic group	p. 61
4.2 Examples of algebraic groups	p. 62
4.3 Algebraic group quotients	p. 63
4.4 Algebraic groups over rings	p. 64
5 Varieties	p. 66
5.1 Affine algebraic sets	p. 66
5.2 Projective algebraic sets	p. 69
5.3 Irreducibility	p. 74
5.4 Function fields	p. 76
5.5 Rational maps and morphisms	p. 79
5.6 Dimension	p. 83
5.7 Weil restriction of scalars	p. 84
6 Tori, LUC and XTR	p. 86
6.1 Cyclotomic subgroups of finite fields	p. 86
6.2 Algebraic tori	p. 88
6.3 The group G q,2	p. 89
6.4 The group G q,6	p. 94
6.5 Further remarks	p. 99
6.6 Algebraic tori over rings	p. 99
l7 Curves and divisor class groups	p. 101
7.1 Non-singular varieties	p. 101
7.2 Weierstrass equations	p. 105
7.3 Uniformisers on curves	p. 106
7.4 Valuation at a point on a curve	p. 108
7.5 Valuations and points on curves	p. 110
7.6 Divisors	p. 111
7.7 Principal divisors	p. 112
7.8 Divisor class group	p. 114
7.9 Elliptic curves	p. 116
8 Rational maps on curves and divisors	p. 121
8.1 Rational maps of curves and the degree	p. 121
8.2 Extensions of valuations	p. 123
8.3 Maps on divisor classes	p. 126
8.4 Riemann-Roch spaces	p. 129
8.5 Derivations and differentials	p. 130
8.6 Genus zero curves	p. 136
8.7 Riemann-Roch theorem and Hurwitz genus formula	p. 137
9 Elliptic curves	p. 138
9.1 Group law	p. 138
9.2 Morphisms between elliptic curves	p. 140
9.3 Isomorphisms of elliptic curves	p. 142
9.4 Automorphisms	p. 143
9.5 Twists	p. 144
9.6 Isogenics	p. 146
9.7 The invariant differential	p. 153
9.8 Multiplication by n and division polynomials	p. 155
9.9 Endomorphism structure	p. 156
9.10 Frobenius map	p. 158
9.11 Supersingular elliptic curves	p. 164
9.12 Alternative models for elliptic curves	p. 168
9.13 Statistical properties of elliptic curves over finite fields	p. 175
9.14 Elliptic curves over rings	p. 177
10 Hyperelliptic curves	p. 178
10.1 Non-singular models for hyperelliptic curves	p. 179
10.2 Isomorphisms, automorphisms and twists	p. 186
10.3 Effective affine divisors on hyperelliptic curves	p. 188
10.4 Addition in the divisor class group	p. 196
10.5 Jacobians, Abelian varieties and isogenics	p. 204
10.6 Elements of order n	p. 206
10.7 Hyperelliptic curves over finite fields	p. 206
10.8 Supersingular curves	p. 209
Part III Exponentiation, Factoring and Discrete Logarithms	p. 213
11 Basic algorithms for algebraic groups	p. 215
11.1 Efficient exponentiation using signed exponents	p. 215
11.2 Multi-exponentiation	p. 219
11.3 Efficient exponentiation in specific algebraic groups	p. 221
11.4 Sampling from algebraic groups	p. 231
11.5 Determining group structure and computing generators for elliptic curves	p. 235
11.6 Testing subgroup membership	p. 236
12 Primality testing and integer factorisation using algebraic groups	p. 238
12.1 Primality testing	p. 238
12.2 Generating random primes	p. 240
12.3 The p - 1 factoring method	p. 242
12.4 Elliptic curve method	p. 244
12.5 Pollard-Strassen method	p. 245
13 Basic discrete logarithm algorithms	p. 246
13.1 Exhaustive search	p. 247
13.2 The Pohlig-Hellman method	p. 247
13.3 Baby-step-giant-step (BSGS) method	p. 250
13.4 Lower bound on complexity of generic algorithms for the DLP	p. 253
13.5 Generalised discrete logarithm problems	p. 256
13.6 Low Hamming weight DLP	p. 258
13.7 Low Hamming weight product exponents	p. 260
14 Factoring and discrete logarithms using pseudorandom walks	p. 262
14.1 Birthday paradox	p. 262
14.2 The Pollard rho method	p. 264
14.3 Distributed Pollard rho	p. 273
14.4 Speeding up the rho algorithm using equivalence classes	p. 276
14.5 The kangaroo method	p. 280
14.6 Distributed kangaroo algorithm	p. 287
14.7 The Gaudry-Schost algorithm	p. 292
14.8 Parallel collision search in other contexts	p. 296
14.9 Pollard rho factoring method	p. 297
15 Factoring and discrete logarithms in subexponential time	p. 301
15.1 Smooth integers	p. 301
15.2 Factoring using random squares	p. 303
15.3 Elliptic curve method revisited	p. 310
15.4 The number field sieve	p. 312
15.5 Index calculus in finite fields	p. 313
15.6 Discrete logarithms on hyperelliptic curves	p. 324
15.7 Weil descent	p. 328
15.8 Discrete logarithms on elliptic curves over extension fields	p. 329
15.9 Further results	p. 332
Part IV Lattices	p. 335
16 Lattices	p. 337
16.1 Basic notions on lattices	p. 338
16.2 The Hermite and Minkowski bounds	p. 343
16.3 Computational problems in lattices	p. 345
17 Lattice basis reduction	p. 347
17.1 Lattice basis reduction in two dimensions	p. 347
17.2 LLL-reduced lattice bases	p. 352
17.3 The Gram-Schmidt algorithm	p. 356
17.4 The LL algorithm	p. 358
17.5 Complexity of LLL	p. 362
17.6 Variants of the LLL algorithm	p. 365
18 Algorithms for the closest and shortest vector problems	p. 366
18.1 Babai's nearest plane method	p. 366
18.2 Babai's rounding technique	p. 371
18.3 The embedding technique	p. 373
18.4 Enumerating all short vectors	p. 375
18.5 Korkine-Zolotarev bases	p. 379
19 Coppersmith's method and related applications	p. 380
19.1 Coppersmith's method for modular univariate polynomials	p. 380
19.2 Multivariate modular polynomial equations	p. 387
19.3 Bivariate integer polynomials	p. 387
19.4 Some applications of Coppersmith's method	p. 390
19.5 Simultaneous Diophantine approximation	p. 397
19.6 Approximate integer greatest common divisors	p. 398
19.7 Learning with errors	p. 400
19.8 Further applications of lattice reduction	p. 402
Part V Cryptography Related to Discrete Logarithms	p. 403
20 The Diffie-Hellman problem and cryptographic applications	p. 405
20.1 The discrete logarithm assumption	p. 405
20.2 Key exchange	p. 405
20.3 Textbook Elgamal encryption	p. 408
20.4 Security of textbook Elgamal encryption	p. 410
20.5 Security of Diffie-Hellman key exchange	p. 414
20.6 Efficiency considerations for discrete logarithm cryptography	p. 416
21 The Diffie-Hellman problem	p. 418
21.1 Variants of the Diffie-Hellman problem	p. 418
21.2 Lower bound on the complexity of CDH for generic algorithms	p. 422
21.3 Random self-reducibility and self-correction of CDH	p. 423
21.4 The den Boer and Maurer reductions	p. 426
21.5 Algorithms for static Diffie-Hellman	p. 435
21.6 Hard bits of discrete logarithms	p. 439
21.7 Bit security of Diffie-Hellman	p. 443
22 Digital signatures based on discrete logarithms	p. 452
22.1 Schnorr signatures	p. 452
22.2 Other public key signature schemes	p. 459
22.3 Lattice attacks on signatures	p. 466
22.4 Other signature functionalities	p. 467
23 Public key encryption based on discrete logarithms	p. 469
23.1 CCA secure Elgamal encryption	p. 469
23.2 Cramer-Shoup encryption	p. 474
23.3 Other encryption functionalities	p. 478
Part VI Crytography Related to Integer Factorisation	p. 483
24 The RSA and Rabin cryptosystems	p. 485
24.1 The textbook RSA cryptosystem	p. 485
24.2 The textbook Rabin cryptosystem	p. 491
24.3 Homomorphic encryption	p. 498
24.4 Algebraic attacks on textbook RSA and Rabin	p. 499
24.5 Attacks on RSA parameters	p. 504
24.6 Digital signatures based on RSA and Rabin	p. 507
24.7 Public key encryption based on RSA and Rabin	p. 511
Part VII Advanced Topics in Elliptic and Hyperelliptic Curves	p. 513
25 Isogenics of elliptic curves	p. 515
25.1 Isogenics and kernels	p. 515
25.2 Isogenies from j-invariants	p. 523
25.3 Isogeny graphs of elliptic curves over finite fields	p. 529
25.4tThe structure of the ordinary isogeny graph p. 535
25.5 Constructing isogenies between elliptic curves	p. 540
25.6 Relating the discrete logarithm problem on isogenous curves	p. 543
26 Pairings on elliptic curves	p. 545
26.1 Weil reciprocity	p. 545
26.2 The Weil pairing	p. 546
26.3 The Tate-Lichtenbaum pairing	p. 548
26.4 Reduction of ECDLP to finite fields	p. 557
26.5 Computational problems	p. 559
26.6 Pairing-friendly elliptic curves	p. 561
Appendix A Background mathematics	p. 564
A.1 Basic notation	p. 564
A.2 Groups	p. 564
A.3 Rings	p. 565
A.4 Modules	p. 565
A.5 Polynomials	p. 566
A.6 Field extensions	p. 567
A.7 Galois theory	p. 569
A.8 Finite fields	p. 570
A.9 Ideals	p. 571
A.10 Vector spaces and linear algebra	p. 572
A.11 Hermite normal form	p. 575
A.12 Orders in quadratic fields	p. 575
A.13 Binary strings	p. 576
A.14 Probability and combinatorics	p. 576
Reference	p. 579
Author index	p. 603
Subject index	p. 608

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents