Making, Breaking Codes
An Introduction to Cryptology
2nd Edition
Published on 28. October 2011
Book
Hardback
650 pages
978-0-13-186146-6 (ISBN)
More details
Edition
2nd edition
Language
English
Place of publication
United States
Publishing group
Pearson Education (US)
Target group
Professional and scholarly
Dimensions
Height: 229 mm
Width: 152 mm
ISBN-13
978-0-13-186146-6 (9780131861466)
Copyright in bibliographic data is held by Nielsen Book Services Limited or its licensors: all rights reserved.
Schweitzer Classification
Other editions
New editions
Book
10/2000
Pearson
€108.93
Article exhausted; check for reprint
Previous edition
Book
10/2000
Pearson
€108.93
Article exhausted; check for reprint
Content
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371