An introduction to mathematical cryptography

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