An introduction to mathematical cryptography

✍ Scribed by Hoffstein J., Pipher J., Silverman J.

• Publisher: Springer
• Year: 2008
• Tongue: English
• Leaves: 533
• Series: Undergraduate Texts in Mathematics
• Category: Library

✦ Synopsis

An Introduction to Mathematical Cryptography provides an introduction to public key cryptography and underlying mathematics that is required for the subject. Each of the eight chapters expands on a specific area of mathematical cryptography and provides an extensive list of exercises. It is a suitable text for advanced students in pure and applied mathematics and computer science, or the book may be used as a self-study. This book also provides a self-contained treatment of mathematical cryptography for the reader with limited mathematical background.

✦ Table of Contents

0387779930......Page 1
Contents......Page 8
Preface......Page 6
Introduction......Page 11
1.1 Simple substitution ciphers......Page 16
1.2 Divisibility and greatest common divisors......Page 25
1.3 Modular arithmetic......Page 34
1.4 Prime numbers, unique factorization, and finite fields......Page 41
1.5 Powers and primitive roots in finite fields......Page 44
1.6 Cryptography before the computer age......Page 49
1.7 Symmetric and asymmetric ciphers......Page 51
Exercises......Page 62
2.1 The birth of public key cryptography......Page 74
2.2 The discrete logarithm problem......Page 77
2.3 Diffie–Hellman key exchange......Page 80
2.4 The ElGamal public key cryptosystem......Page 83
2.5 An overview of the theory of groups......Page 87
2.6 How hard is the discrete logarithm problem?......Page 90
2.7 A collision algorithm for the DLP......Page 94
2.8 The Chinese remainder theorem......Page 96
2.9 The Pohlig–Hellman algorithm......Page 101
2.10 Rings, quotients, polynomials, and finite fields......Page 107
Exercises......Page 120
3.1 Euler's formula and roots modulo pq......Page 128
3.2 The RSA public key cryptosystem......Page 134
3.3 Implementation and security issues......Page 137
3.4 Primality testing......Page 139
3.5 Pollard's p – 1 factorization algorithm......Page 148
3.6 Factorization via difference of squares......Page 152
3.7 Smooth numbers and sieves......Page 161
3.8 The index calculus and discrete logarithms......Page 177
3.9 Quadratic residues and quadratic reciprocity......Page 180
3.10 Probabilistic encryption......Page 187
Exercises......Page 191
4. Combinatorics, Probability, and Information Theory......Page 203
4.1 Basic principles of counting......Page 204
4.2 The Vigenère cipher......Page 210
4.3 Probability theory......Page 224
4.4 Collision algorithms and meet-in-the-middle attacks......Page 241
4.5 Pollard's p method......Page 248
4.6 Information theory......Page 257
4.7 Complexity Theory and P versus NP......Page 272
Exercises......Page 276
5.1 Elliptic curves......Page 292
5.2 Elliptic curves over finite fields......Page 299
5.3 The elliptic curve discrete logarithm problem......Page 303
5.4 Elliptic curve cryptography......Page 309
5.5 The evolution of public key cryptography......Page 314
5.6 Lenstra's elliptic curve factorization algorithm......Page 316
5.7 Elliptic curves over F[sub(2)] and over F[sub(2)][sup(k)]......Page 321
5.8 Bilinear pairings on elliptic curves......Page 328
5.9 The Weil pairing over fields of prime power order......Page 338
5.10 Applications of the Weil pairing......Page 347
Exercises......Page 352
6.1 A congruential public key cryptosystem......Page 362
6.2 Subset-sum problems and knapsack cryptosystems......Page 365
6.3 A brief review of vector spaces......Page 372
6.4 Lattices: Basic definitions and properties......Page 376
6.5 Short vectors in lattices......Page 383
6.6 Babai's algorithm......Page 392
6.7 Cryptosystems based on hard lattice problems......Page 396
6.8 The GGH public key cryptosystem......Page 397
6.9 Convolution polynomial rings......Page 400
6.10 The NTRU public key cryptosystem......Page 405
6.11 NTRU as a lattice cryptosystem......Page 413
6.12 Lattice reduction algorithms......Page 416
6.13 Applications of LLL to cryptanalysis......Page 431
Exercises......Page 435
7.1 What is a digital signature?......Page 449
7.2 RSA digital signatures......Page 452
7.3 ElGamal digital signatures and DSA......Page 454
7.4 GGH lattice-based digital signatures......Page 459
7.5 NTRU digital signatures......Page 462
Exercises......Page 470
8. Additional Topics in Cryptography......Page 476
8.1 Hash functions......Page 477
8.2 Random numbers and pseudorandom number generators......Page 479
8.3 Zero-knowledge proofs......Page 481
8.4 Secret sharing schemes......Page 484
8.5 Identification schemes......Page 485
8.6 Padding schemes and the random oracle model......Page 487
8.7 Building protocols from cryptographic primitives......Page 490
8.8 Hyperelliptic curve cryptography......Page 491
8.9 Quantum computing......Page 494
8.10 Modern symmetric cryptosystems: DES and AES......Page 496
List of Notation......Page 499
References......Page 502
A......Page 510
C......Page 511
D......Page 514
E......Page 515
F......Page 518
G......Page 519
H......Page 520
K......Page 521
N......Page 522
P......Page 525
R......Page 528
S......Page 529
V......Page 531
Z......Page 532