An introduction to mathematical cryptography

Jeffrey Hoffstein, Jill Pipher, J.H. Silverman9780387779935, 0387779930

This self-contained introduction to modern cryptography emphasizes the mathematics behind the theory of public key cryptosystems and digital signature schemes. The book focuses on these key topics while developing the mathematical tools needed for the construction and security analysis of diverse cryptosystems. Only basic linear algebra is required of the reader; techniques from algebra, number theory, and probability are introduced and developed as required.

The book covers a variety of topics that are considered central to mathematical cryptography. Key topics include:

* classical cryptographic constructions, such as Diffie-Hellmann key exchange, discrete logarithm-based cryptosystems, the RSA cryptosystem, and digital signatures;

* fundamental mathematical tools for cryptography, including primality testing, factorization algorithms, probability theory, information theory, and collision algorithms;

* an in-depth treatment of important recent cryptographic innovations, such as elliptic curves, elliptic curve and pairing-based cryptography, lattices, lattice-based cryptography, and the NTRU cryptosystem.

Additional topics, including hash functions, pseudorandom number generators, zero-knowledge proofs, digital cash and DES/AES, are briefly described in the final chapter. This book is an ideal introduction for mathematics and computer science students to the mathematical foundations of modern cryptography. The book includes an extensive bibliography and index; supplementary materials are available online.

---

Table of contents :
00000……Page 1
front-matter……Page 2
Preface……Page 6
Contents……Page 8
Introduction……Page 11
Simple substitution ciphers……Page 16
Divisibility and greatest common divisors……Page 25
Modular arithmetic……Page 34
Prime numbers, unique factorization, and finite fields……Page 41
Powers and primitive roots in finite fields……Page 44
Cryptography before the computer age……Page 49
Symmetric and asymmetric ciphers……Page 51
Exercises……Page 62
The birth of public key cryptography……Page 74
The discrete logarithm problem……Page 77
Diffie–Hellman key exchange……Page 80
The ElGamal public key cryptosystem……Page 83
An overview of the theory of groups……Page 87
How hard is the discrete logarithm problem?……Page 90
A collision algorithm for the DLP……Page 94
The Chinese remainder theorem……Page 96
The Pohlig–Hellman algorithm……Page 101
Rings, quotients, polynomials, and finite fields……Page 107
Exercises……Page 120
Euler’s formula and roots modulo pq……Page 128
The RSA public key cryptosystem……Page 134
Implementation and security issues……Page 137
Primality testing……Page 139
Pollard’s bold0mu mumu ppunitspppp-1 factorization algorithm……Page 148
Factorization via difference of squares……Page 152
Smooth numbers and sieves……Page 161
The index calculus and discrete logarithms……Page 177
Quadratic residues and quadratic reciprocity……Page 180
Probabilistic encryption……Page 187
Exercises……Page 191
Combinatorics, Probability, and Information Theory……Page 203
Basic principles of counting……Page 204
The Vigenère cipher……Page 210
Probability theory……Page 224
Collision algorithms and meet-in-the-middle attacks……Page 241
Pollard’s bold0mu mumu units method……Page 248
Information theory……Page 257
Complexity Theory and P versus NP……Page 272
Exercises……Page 276
Elliptic curves……Page 292
Elliptic curves over finite fields……Page 299
The elliptic curve discrete logarithm problem……Page 303
Elliptic curve cryptography……Page 309
The evolution of public key cryptography……Page 314
Lenstra’s elliptic curve factorization algorithm……Page 316
Elliptic curves over F2k and over F2k……Page 321
Bilinear pairings on elliptic curves……Page 328
The Weil pairing over fields of prime power order……Page 338
Applications of the Weil pairing……Page 347
Exercises……Page 352
A congruential public key cryptosystem……Page 362
Subset-sum problems and knapsack cryptosystems……Page 365
A brief review of vector spaces……Page 372
Lattices: Basic definitions and properties……Page 376
Short vectors in lattices……Page 383
Babai’s algorithm……Page 392
Cryptosystems based on hard lattice problems……Page 396
The GGH public key cryptosystem……Page 397
Convolution polynomial rings……Page 400
The NTRU public key cryptosystem……Page 405
NTRU as a lattice cryptosystem……Page 413
Lattice reduction algorithms……Page 416
Applications of LLL to cryptanalysis……Page 431
Exercises……Page 435
What is a digital signature?……Page 449
RSA digital signatures……Page 452
ElGamal digital signatures and DSA……Page 454
GGH lattice-based digital signatures……Page 459
NTRU digital signatures……Page 462
Exercises……Page 470
Additional Topics in Cryptography……Page 476
Hash functions……Page 477
Random numbers and pseudorandom number generators……Page 479
Zero-knowledge proofs……Page 481
Secret sharing schemes……Page 484
Identification schemes……Page 485
Padding schemes and the random oracle model……Page 487
Building protocols from cryptographic primitives……Page 490
Hyperelliptic curve cryptography……Page 491
Quantum computing……Page 494
Modern symmetric cryptosystems: DES and AES……Page 496
List of Notation……Page 499
Index……Page 502