Making, Breaking Codes: Introduction to Cryptology

1 Simple Ciphers 1 -- 1.1 Shift Cipher 2 -- 1.2 Reduction/division Algorithm 5 -- 1.3 One-time Pad 10 -- 1.4 Affine Cipher 13 -- 2 Probability 18 -- 2.1 Counting 19 -- 2.2 Basic Ideas 21 -- 2.3 Statistics Of English 31 -- 2.4 Attack On The Affine Cipher 37 -- 3 Permutations 39 -- 3.1 Cryptograms: Substitutions 40 -- 3.2 Anagrams: Transpositions 43 -- 3.3 Permutations 47 -- 3.4 Shuffles 54 -- 3.5 Block Interleavers 56 -- 4 A Serious Cipher 58 -- 4.1 Vigenere Cipher 58 -- 4.2 Lcms And Gcds 62 -- 4.3 Kasiski Attack 64 -- 4.4 Expected Values 69 -- 4.5 Friedman Attack 73 -- 5 More Probability 88 -- 5.1 Generating Functions 89 -- 5.2 Variance, Standard Deviation 91 -- 5.3 Chebycheff's Inequality 93 -- 5.4 Law Of Large Numbers 94 -- 6 Modern Symmetric Ciphers 96 -- 6.1 Design Goals 96 -- 6.2 Data Encryption Standard 100 -- 6.3 Advanced Encryption Standard 106 -- 7 Integers 108 -- 7.1 Divisibility 108 -- 7.2 Unique Factorization 112 -- 7.3 Euclidean Algorithm 118 -- 7.4 Multiplicative Inverses 122 -- 7.5 Computing Inverses 124 -- 7.6 Equivalence Relations 127 -- 7.7 Integers Mod M 130 -- 7.8 Primitive Roots, Discrete Logs 136 -- 8 Hill Cipher 139 -- 8.1 Hill Cipher Operation 139 -- 8.2 Hill Cipher Attacks 141 -- 9 Complexity 147 -- 9.1 Big-oh/little-oh Notation 148 -- 9.2 Bit Operations 149 -- 9.3 Probabilistic Algorithms 153 -- 9.4 Complexity 153 -- 9.5 Subexponential Algorithms 155 -- 9.6 Kolmogorov Complexity 156 -- 9.7 Linear Complexity 157 -- 9.8 Worst-case Versus Expected 158 -- 10 Public-key Ciphers 159 -- 10.1 Trapdoors 161 -- 10.2 Rsa Cipher 162 -- 10.3 Diffie-hellman Key Exchange 171 -- 10.4 Elgamal Cipher 172 -- 10.5 Knapsack Ciphers 176 -- 10.6 Ntru Cipher 179 -- 10.7 Arithmetica Key Exchange 183 -- 10.8 Quantum Cryptography 187 -- 10.9 U.s. Export Regulations 189 -- 11 Prime Numbers 190 -- 11.1 Euclid's Theorem 190 -- 11.2 Prime Number Theorem 191 -- 11.3 Primes In Sequences 192 -- 11.4 Chebycheff's Theorem 193 -- 11.5 Sharpest Asymptotics 196 -- 11.6 Riemann Hypothesis 197 -- 12 Roots Mod P 199 -- 12.1 Fermat's Little Theorem 200 -- 12.2 Factoring Special Expressions 201 -- 12.3 Mersenne Numbers 203 -- 12.5 Exponentiation Algorithm 207 -- 12.6 Square Roots Mod P 210 -- 12.7 Higher Roots Mod P 211 -- 13 Roots Mod Composites 213 -- 13.1 Sun Ze's Theorem 214 -- 13.2 Special Systems 216 -- 13.3 Composite Moduli 219 -- 13.4 Hensel's Lemma 221 -- 13.5 Square-root Oracles 225 -- 13.6 Euler's Theorem 228 -- 13.7 Facts About Primitive Roots 229 -- 13.8 Euler's Criterion 231 -- 14 Weak Multiplicativity 234 -- 14.1 Weak Multiplicativity 234 -- 14.2 Arithmetic Convolutions 237 -- 14.3 Mobius Inversion 239 -- 15 Quadratic Reciprocity 242 -- 15.1 Square Roots 243 -- 15.2 Quadratic Symbols 244 -- 15.3 Multiplicative Property 245 -- 15.4 Quadratic Reciprocity 246 -- 15.5 Fast Computation 251 -- 16 Pseudoprimes 255 -- 16.1 Fermat Pseudoprimes 256 -- 16.2 Non-prime Pseudoprimes 258 -- 16.3 Euler Pseudoprimes 260 -- 16.4 Solovay-strassen Test 262 -- 16.5 Strong Pseudoprimes 263 -- 16.6 Miller-rabin Test 263 -- 17 Groups 265 -- 17.2 Subgroups 268 -- 17.3 Lagrange's Theorem 269 -- 17.4 Index Of A Subgroup 271 -- 17.5 Laws Of Exponents 272 -- 17.6 Cyclic Subgroups 274 -- 17.7 Euler's Theorem 276 -- 17.8 Exponents Of Groups 277 -- 18 Sketches Of Protocols 279 -- 18.1 Basic Public-key Protocol 280 -- 18.2 Diffie-hellman Key Exchange 281 -- 18.3 Secret Sharing 282 -- 18.4 Oblivious Transfer 284 -- 18.5 Zero-knowledge Proofs 287 -- 18.6 Authentication 288 -- 18.7 E-money, E-commerce 290 -- 19 Rings, Fields, Polynomials 292 -- 19.1 Rings, Fields 293 -- 19.2 Divisibility 298 -- 19.3 Polynomial Rings 300 -- 19.4 Euclidean Algorithm 302 -- 19.5 Euclidean Rings 307 -- 20 Cyclotomic Polynomials 312 -- 20.1 Characteristics 313 -- 20.2 Multiple Factors 315 -- 20.3 Cyclotomic Polynomials 318 -- 20.4 Primitive Roots 321 -- 20.5 Primitive Roots Mod P 322 -- 20.6 Prime Powers 323 -- 20.7 Counting Primitive Roots 326 -- 20.8 Non-existence 327 -- 20.9 Search Algorithm 329 -- 21 Random Number Generators 330 -- 21.1 Fake One-time Pads 331 -- 21.2 Period Of A Prng 332 -- 21.3 Congruential Generators 333 -- 21.4 Feedback Shift Generators 335 -- 21.5 Blum-blum-shub Generator 337 -- 21.6 Naor-reingold Generator 338 -- 21.7 Periods Of Lcgs 339 -- 21.8 Primitive Polynomials 343 -- 21.9 Periods Of Lfsrs 346 -- 21.10 Examples Of Primitives 349 -- 21.11 Testing For Primitivity 352 -- 22 More On Groups 355 -- 22.1 Group Homomorphisms 355 -- 22.2 Finite Cyclic Groups 359 -- 22.3 Infinite Cyclic Groups 363 -- 22.4 Roots And Powers In Groups 363 -- 22.5 Square Root Algorithm 367 -- 23 Pseudoprimality Proofs 371 -- 23.1 Lambda Function 371 -- 23.2 Carmichael Numbers 374 -- 23.3 Euler Witnesses 375 -- 23.4 Strong Witnesses 378 -- 24 Factorization Attacks 388 -- 24.1 Pollard's Rho Method 389 -- 24.2 Pollard's P -- 1 Method 392 -- 24.3 Pocklington-lehmer Criterion 396 -- 24.4 Strong Primes 402 -- 24.5 Primality Certificates 405 -- 25 Modern Factorization Attacks 411 -- 25.1 Gaussian Elimination 412 -- 25.2 Random Squares Factoring 414 -- 25.3 Dixon's Algorithm 415 -- 25.4 Non-sieving Quadratic Sieve 417 -- 25.5 Quadratic Sieve 421 -- 25.6 Other Improvements 421 -- 26 Finite Fields 423 -- 26.1 Making Finite Fields 424 -- 26.2 Examples Of Field Extensions 426 -- 26.3 Addition Mod P 427 -- 26.4 Multiplication Mod P 428 -- 26.5 Multiplicative Inverses Mod P 428 -- 27 Discrete Logs 431 -- 27.1 Baby-step Giant-step 432 -- 27.2 Pollard's Rho Method 434 -- 27.3 Index Calculus 441 -- 28 Elliptic Curves 444 -- 28.1 Abstract Discrete Logarithms 445 -- 28.2 Discrete Log Ciphers 445 -- 28.3 Elliptic Curves 448 -- 28.4 Points At Infinity 454 -- 28.5 Projective Elliptic Curves 456 -- 29 More On Finite Fields 457 -- 29.1 Ideals In Commutative Rings 458 -- 29.2 Ring Homomorphisms 462 -- 29.3 Quotient Rings 466 -- 29.4 Maximal Ideals And Fields 468 -- 29.5 More On Field Extensions 469 -- 29.6 Frobenius Automorphism 471 -- 29.7 Counting Irreducibles 479 -- 29.8 Counting Primitives 482 -- A.1 Sets And Functions 484 -- A.2 Searching, Sorting 489 -- A.3 Vectors 492 -- A.4 Matrices 497 -- A.5 Stirling's Formula 501 -- T.1 Factorizations Under 600 505 -- T.2 Primes Below 10,000 509 -- T.3 Primitive Roots Under 100 511. Paul Garrett. Includes Bibliographical References (p. 512-515) And Index.