Making, Breaking Codes An Introduction To Cryptology

Preface . . . . . . . . . . . . . . . . . . . . xi Introduction . . . . . . . . . . . . . . . . . . xvi 1 More Probability . . . . . . . . . . . . . . . 1.1 Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Variance, Standard Deviation . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Chebyche 's Inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Law of Large Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Hash Functions . . . . . . . . . . . . . . . . 2.1 The Design Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Security Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 SHA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 MACs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Finite Fields . . . . . . . . . . . . . . . . . 3.1 Making Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Examples of Field Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Addition mod P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Multiplication mod P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Multiplicative Inverses mod P . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Error-correcting codes . . . . . . . . . . . . . 4.1 Noisy channels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Markov, Chebychev inequalities . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Law of Large Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Shannon's Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Linear ECCs . . . . . . . . . . . . . . . . . 5.1 Hamming [7,4] Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Some Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Linear Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Syndrome Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Hamming Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6 Gilbert-Varshamov Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.7 Singleton Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v.vi Contents 6 Constructing Linear ECCs . . . . . . . . . . . 6.1 Minimum Distance in Linear Codes . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Cyclic Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Vandermonde Determinants . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Variant Check Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5 Reed-Solomon, BCH codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.6 Hamming codes reconsidered . . . . . . . . . . . . . . . . . . . . . . . . . . 6.7 BCH codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.8 Laws of Exponents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.9 In nite Cyclic Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.10 Exponents of Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.11 Group Homomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.12 Roots and Powers in Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.13 Euclidean Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 More on Finite Fields . . . . . . . . . . . . . 7.1 Ideals in Commutative Rings . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Ring Homomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Quotient Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4 Maximal Ideals and Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.5 More on Field Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.6 Frobenius Automorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.7 Counting Irreducibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.8 Counting Primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361 Answers to Selected Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371Garrett, Paul is the author of 'Making, Breaking Codes An Introduction To Cryptology', published 2008 under ISBN 9780131861466 and ISBN 0131861468.