An Introduction to Mathematical Cryptography

Preface......Page 6
Contents......Page 8
Introduction......Page 14
 1.1 Simple Substitution Ciphers......Page 19
  1.1.1 Cryptanalysis of Simple Substitution Ciphers......Page 22
 1.2 Divisibility and Greatest Common Divisors......Page 28
 1.3 Modular Arithmetic......Page 37
  1.3.1 Modular Arithmetic and Shift Ciphers......Page 41
  1.3.2 The Fast Powering Algorithm......Page 42
 1.4 Prime Numbers, Unique Factorization, and Finite Fields......Page 44
 1.5 Powers and Primitive Roots in Finite Fields......Page 47
 1.6 Cryptography Before the Computer Age......Page 52
  1.7.1 Symmetric Ciphers......Page 55
  1.7.2 Encoding Schemes......Page 57
  1.7.3 Symmetric Encryption of Encoded Blocks......Page 58
  1.7.4 Examples of Symmetric Ciphers......Page 59
  1.7.5 Random Bit Sequences and Symmetric Ciphers......Page 62
  1.7.6 Asymmetric Ciphers Make a First Appearance......Page 64
 Exercises......Page 65
 2.1 The Birth of Public Key Cryptography......Page 78
 2.2 The Discrete Logarithm Problem......Page 81
 2.3 Diffie–Hellman Key Exchange......Page 84
 2.4 The Elgamal Public Key Cryptosystem......Page 87
 2.5 An Overview of the Theory of Groups......Page 91
 2.6 How Hard Is the Discrete Logarithm Problem?......Page 94
 2.7 A Collision Algorithm for the DLP......Page 98
 2.8 The Chinese Remainder Theorem......Page 100
  2.8.1 Solving Congruences with Composite Moduli......Page 103
 2.9 The Pohlig–Hellman Algorithm......Page 105
 2.10 Rings, Quotients, Polynomials, and Finite Fields......Page 111
  2.10.1 An Overview of the Theory of Rings......Page 112
  2.10.2 Divisibility and Quotient Rings......Page 113
  2.10.3 Polynomial Rings and the Euclidean Algorithm......Page 115
  2.10.4 Polynomial Ring Quotients and Finite Fields......Page 119
 Exercises......Page 124
 3.1 Euler's Formula and Roots Modulo pq......Page 133
 3.2 The RSA Public Key Cryptosystem......Page 139
 3.3 Implementation and Security Issues......Page 142
 3.4 Primality Testing......Page 144
  3.4.1 The Distribution of the Set of Primes......Page 149
  3.4.2 Primality Proofs Versus Probabilistic Tests......Page 152
 3.5 Pollard's p-1 Factorization Algorithm......Page 153
 3.6 Factorization via Difference of Squares......Page 157
  3.7.1 Smooth Numbers......Page 166
  3.7.2 The Quadratic Sieve......Page 171
  3.7.3 The Number Field Sieve......Page 178
 3.8 The Index Calculus and Discrete Logarithms......Page 182
 3.9 Quadratic Residues and Quadratic Reciprocity......Page 185
 3.10 Probabilistic Encryption......Page 193
 Exercises......Page 196
 4.1 What Is a Digital Signature?......Page 208
 4.2 RSA Digital Signatures......Page 211
 4.3 Elgamal Digital Signatures and DSA......Page 213
 Exercises......Page 218
5 Combinatorics, Probability, and Information Theory......Page 221
 5.1 Basic Principles of Counting......Page 222
  5.1.1 Permutations......Page 224
  5.1.2 Combinations......Page 225
  5.1.3 The Binomial Theorem......Page 227
 5.2 The Vigenère Cipher......Page 228
  5.2.1 Cryptanalysis of the Vigenère Cipher: Theory......Page 232
  5.2.2 Cryptanalysis of the Vigenère Cipher: Practice......Page 237
  5.3.1 Basic Concepts of Probability Theory......Page 242
  5.3.2 Bayes's Formula......Page 247
  5.3.3 Monte Carlo Algorithms......Page 250
  5.3.4 Random Variables......Page 252
  5.3.5 Expected Value......Page 258
  5.4.1 The Birthday Paradox......Page 260
  5.4.2 A Collision Theorem......Page 261
  5.4.3 A Discrete Logarithm Collision Algorithm......Page 264
 5.5 Pollard's ρ Method......Page 267
  5.5.1 Abstract Formulation of Pollard's ρ Method......Page 268
  5.5.2 Discrete Logarithms via Pollard's ρ Method......Page 273
  5.6.1 Perfect Secrecy......Page 277
  5.6.2 Entropy......Page 283
  5.6.3 Redundancy and the Entropyof Natural Language......Page 289
  5.6.4 The Algebra of Secrecy Systems......Page 291
 5.7 Complexity Theory and P Versus NP......Page 292
 Exercises......Page 296
 6.1 Elliptic Curves......Page 313
 6.2 Elliptic Curves over Finite Fields......Page 320
 6.3 The Elliptic Curve Discrete Logarithm Problem......Page 324
  6.3.1 The Double-and-Add Algorithm......Page 326
  6.3.2 How Hard Is the ECDLP?......Page 329
  6.4.1 Elliptic Diffie–Hellman Key Exchange......Page 330
  6.4.2 Elliptic Elgamal Public Key Cryptosystem......Page 333
 6.5 The Evolution of Public Key Cryptography......Page 335
 6.6 Lenstra's Elliptic Curve Factorization Algorithm......Page 338
 6.7 Elliptic Curves over F2 and over F2k......Page 343
 6.8 Bilinear Pairings on Elliptic Curves......Page 350
  6.8.1 Points of Finite Order on Elliptic Curves......Page 351
  6.8.2 Rational Functions and Divisors on Elliptic Curves......Page 352
  6.8.3 The Weil Pairing......Page 354
  6.8.4 An Efficient Algorithm to Compute the Weil Pairing......Page 357
  6.8.5 The Tate Pairing......Page 360
  6.9.1 Embedding Degree and the MOV Algorithm......Page 361
  6.9.2 Distortion Maps and a Modified Weil Pairing......Page 364
  6.9.3 A Distortion Map on y2=x3+x......Page 366
  6.10.1 Tripartite Diffie–Hellman Key Exchange......Page 370
  6.10.2 ID-Based Public Key Cryptosystems......Page 372
 Exercises......Page 375
 7.1 A Congruential Public Key Cryptosystem......Page 386
 7.2 Subset-Sum Problems and Knapsack Cryptosystems......Page 390
 7.3 A Brief Review of Vector Spaces......Page 397
 7.4 Lattices: Basic Definitions and Properties......Page 401
  7.5.1 The Shortest and the Closest Vector Problems......Page 408
  7.5.2 Hermite's Theorem and Minkowski's Theorem......Page 409
  7.5.3 The Gaussian Heuristic......Page 413
 7.6 Babai's Algorithm......Page 416
 7.7 Cryptosystems Based on Hard Lattice Problems......Page 420
 7.8 The GGH Public Key Cryptosystem......Page 422
 7.9 Convolution Polynomial Rings......Page 425
 7.10 The NTRU Public Key Cryptosystem......Page 429
  7.10.1 NTRUEncrypt......Page 430
  7.10.2 Mathematical Problems for NTRUEncrypt......Page 435
  7.11.1 The NTRU Lattice......Page 438
  7.11.2 Quantifying the Security of an NTRU Lattice......Page 440
  7.12.1 The GGH Digital Signature Scheme......Page 441
  7.12.2 Transcript Analysis......Page 443
  7.12.3 Rejection Sampling......Page 444
  7.12.4 Rejection Sampling Applied to an Abstract Signature Scheme......Page 446
  7.12.5 The NTRU Modular Lattice Signature Scheme......Page 447
  7.13.1 Gaussian Lattice Reduction in Dimension 2......Page 449
  7.13.2 The LLL Lattice Reduction Algorithm......Page 452
  7.13.3 Using LLL to Solve apprCVP......Page 461
  7.13.4 Generalizations of LLL......Page 462
 7.14 Applications of LLL to Cryptanalysis......Page 463
  7.14.2 Applying LLL to Knapsacks......Page 464
  7.14.3 Applying LLL to GGH......Page 465
  7.14.4 Applying LLL to NTRU......Page 466
 Exercises......Page 467
8 Additional Topics in Cryptography......Page 484
 8.1 Hash Functions......Page 485
 8.2 Random Numbers and Pseudorandom Number......Page 487
 8.3 Zero-Knowledge Proofs......Page 490
 8.4 Secret Sharing Schemes......Page 493
 8.5 Identification Schemes......Page 494
 8.6 Padding Schemes and the Random Oracle Model......Page 495
 8.7 Building Protocols from Cryptographic Primitives......Page 498
 8.8 Blind Digital Signatures, Digital Cash, and Bitcoin......Page 500
 8.9 Homomorphic Encryption......Page 503
 8.10 Hyperelliptic Curve Cryptography......Page 507
 8.11 Quantum Computing......Page 510
 8.12 Modern Symmetric Cryptosystems: DES and AES......Page 512
List of Notation......Page 515
References......Page 518
Index......Page 528