- About MAA
- Membership
- MAA Publications
- Periodicals
- Blogs
- MAA Book Series
- MAA Press (an imprint of the AMS)
- MAA Notes
- MAA Reviews
- Mathematical Communication
- Information for Libraries
- Author Resources
- Advertise with MAA
- Meetings
- Competitions
- Programs
- Communities
- MAA Sections
- SIGMAA
- MAA Connect
- Students
- MAA Awards
- Awards Booklets
- Writing Awards
- Teaching Awards
- Service Awards
- Research Awards
- Lecture Awards
- Putnam Competition Individual and Team Winners
- D. E. Shaw Group AMC 8 Awards & Certificates
- Maryam Mirzakhani AMC 10 A Awards & Certificates
- Two Sigma AMC 10 B Awards & Certificates
- Jane Street AMC 12 A Awards & Certificates
- Akamai AMC 12 B Awards & Certificates
- High School Teachers
- News
You are here
Cryptography, Information Theory, and Error-Correction: A Handbook for the 21st Century
Publisher:
John Wiley
Publication Date:
2004
Number of Pages:
468
Format:
Hardcover
Price:
99.95
ISBN:
0-471-65317-9
Category:
Monograph
[Reviewed by , on ]
William Satzer
06/23/2005
The authors call it a handbook, but that calls to mind a heavy reference volume like the Handbook of Chemistry and Physics, something that you would never actually read. But Cryptography, Information Theory and Error-Correction, although encyclopedic, is lively and engaging, written with palpable enthusiasm.
There are three major parts of the book, called “Mainly Cryptographyâ€, “Mainly Information Theoryâ€, and “Mainly Error-Correctionâ€. While these were once considered largely separate disciplines, new research and continuing developments in technology have served to emphasize their deep interconnections. It should be no surprise - Claude Shannon’s pioneering work crossed back and forth through all three areas.
The book is too rich in topics for the reviewer even to mention them all. Let’s just map out elements of the approach and point out some particularly interesting nuggets. The section of cryptography takes us from classical ciphers like the Caesar and Vigenère ciphers to modern approaches including RSA, DES and quantum encryption systems. A whole chapter is devoted to elliptic curve cryptography. Another chapter describes cryptographic attacks: methods of breaking modern ciphers and compromising cryptographic systems. Beyond issues about conveying information secretly, the authors also address related questions of authentication, identification and the distribution of cryptographic keys. (The key distribution problem is succinctly described by a Catch 22: “To communicate in secret, one must first communicate in secret.â€)
The section on information theory takes a more or less standard approach, but offers a couple of unusual applications. One of them is how to achieve perfect privacy using a scheme with Latin squares. A chapter on biology focuses on the genetic code and looks at DNA as an information channel with a computable channel capacity.
The chapters on error-correction establish the general ideas of error-correction codes and develop some of the tools from finite fields, linear algebra and number theory. After that, the authors discuss linear codes (including Golay and Hamming codes), linear cyclic codes, and Reed-Solomon codes. Maximum Distance Separable (MDS) codes are described and then applied to the sharing of secrets – partitioning a secret among separate parties while maintaining security and enabling reconstruction of the secret from less than all the pieces.
This book’s strengths are breadth rather than depth, and the clearly communicated sense of interconnections among the parts. There are about three hundred examples and problems with solutions. Prerequisites are limited: basic calculus, the rudiments of linear algebra, some probability, and a little familiarity with groups and fields. There are a few sections (Shannon’s sampling theorem and elliptic curve cryptography, for example) that require some more sophistication. This is a very readable text, one that encourages a reader to dip in and sample the treats.
Bill Satzer (wjsatzer@mmm.com) is a senior intellectual property scientist at 3M Company, having previously been a lab manager at 3M for composites and electromagnetic materials. His training is in dynamical systems and particularly celestial mechanics; his current interests are broadly in applied mathematics and the teaching of mathematics.
Preface.
I. CRYPTOGRAPHY.
1. History and Claude E. Shannon.
1.1 Historical Background.
1.2 Brief Biography of Claude E. Shannon.
1.3 Career.
1.4 Personal - Professional.
1.5 Scientific Legacy.
1.6 Modern Developments.
2. Classical Ciphers and Their Cryptanalysis.
2.1 Introduction.
2.2 The Caesar Cipher.
2.3 The Scytale Cipher.
2.4 The VigenÅ re Cipher.
2.5 Affine Ciphers.
2.6 The Enigma Machine and its Mathematics.
2.7 Frequency Analysis.
2.8 Breaking the VigenÅ re Cipher.
2.9 Modern Enciphering Systems.
2.10 Problems.
2.11 Solutions.
3. RSA and Key Searches.
3.1 Background.
3.2 The Basic Idea.
3.3 Public-key Cryptography and RSA on a Calculator.
3.4 The General RSA Algorithm.
3.5 Public Key Versus Symmetric Key.
3.6 Attacks, Security of DES.
3.7 Summary.
3.8 Problems.
3.9 Solutions.
4. The Fundamentals of Modern Cryptography.
4.1 Encryption Re-visited.
4.2 Block Ciphers, Shannon's Confusion and Diffusion.
4.3 Perfect Secrecy, Stream Ciphers, One-Time Pad.
4.4 Hash Functions.
4.5 Message Integrity Using Symmetric Cryptography.
4.6 General Public-Key Cryptosystems.
4.7 Electronic Signatures.
4.8 The Diffie-Hellman Key Exchange.
4.9 Quantum Encryption.
4.10 Key Management and Kerberos.
4.11 DES.
4.12 Problems.
4.13 Solutions.
5. DES, AES and Operating Modes.
5.1 The Data Encryption Standard Code.
5.2 Triple DES.
5.3 DES and Unix.
5.4 The Advanced Encryption Standard Code.
5.5 Problems.
5.6 Solutions.
6. Elliptic Curve Cryptography (ECC).
6.1 Abelian Integrals, Fields, Groups.
6.2 Curves, Cryptography.
6.3 Non-singularity.
6.4 The Hasse Theorem, and an Example.
6.5 More Examples.
6.6 The Group Law on Elliptic Curves.
6.7 Key Exchange Using Elliptic Curves.
6.8 Elliptic Curves Mod n.
6.9 Encoding Plain Text.
6.10 Security of ECC.
6.11 More Geometry of Cubic Curves.
6.12 Cubic Curves and Arcs.
6.13 Homogeneous Coordinates.
6.14 Fermat's Last Theorem, Elliptic Curves. Gerhard Frey.
6.15 Problems.
6.16 Solutions.
7. General and Mathematical Attacks in Cryptography.
7.1 Cryptanalysis.
7.2 Soft Attacks.
7.3 Brute Force Attacks.
7.4 Man-In-The-Middle Attacks.
7.5 Known Plain-Text Attacks.
7.6 Known Cipher-Text Attacks.
7.7 Chosen Plain-Text Attacks.
7.8 Chosen Cipher-Text Attacks.
7.9 Replay Attacks.
7.10 Birthday Attacks.
7.11 Birthday Attack on Digital Signatures.
7.12 Birthday Attack on the Discrete Log-Problem.
7.13 Attacks on RSA.
7.14 Attacks on RSA Using Low-Exponents.
7.15 Timing-Attack.
7.16 Differential Cryptanalysis.
7.17 Implementation Errors and Unforeseen States.
8. Topical Issues in Cryptography and Communications.
8.1 Introduction.
8.2 Hot Issues.
8.3 Authentication.
8.4 e-commerce.
8.5 e-government.
8.6 Key Lengths.
8.7 Digital Rights.
8.8 Wireless Networks.
8.9 Communication Protocols.
II. INFORMATION THEORY.
9. Information Theory and Its Applications.
9.1 Axioms, Physics, Computation.
9.2 Entropy.
9.3 Information Gained, Cryptography.
9.4 Practical Applications of Information Theory.
9.5 Information Theory and Physics.
9.6 Axiomatics.
9.7 Number Bases, Erdos and the Hand of God.
9.8 Weighing Problems and Your MBA.
9.9 Shannon Bits, the Big Picture.
10. Random Variables and Entropy.
10.1 Random Variables.
10.2 Mathematics of Entropy.
10.3 Calculating Entropy.
10.4 Conditional Probability.
10.5 Bernoulli Trials.
10.6 Typical Sequences.
10.7 Law of Large Numbers.
10.8 Joint and Conditional Entropy.
10.9 Applications of Entropy.
10.10 Calculation of Mutual Information.
10.11 Mutual Information and Channels.
10.12 The Entropy of X + Y.
10.13 Subadditivity of the Function x log x.
10.14 Entropy and Cryptography.
10.15 Problems.
10.16 Solutions.
11. Source Coding, Data Compression, Redundancy.
11.1 Introduction, Source Extensions.
11.2 Encodings, Kraft, McMillan.
11.3 Block Coding, The Oracle, 20 Questions.
11.4 Optimal Codes.
11.5 Huffman Coding.
11.6 Optimality of Huffman Encoding.
11.7 Data Compression, Lempel-Ziv Coding, Redundancy.
11.8 Problems.
11.9 Solutions.
12. Channels, Capacity, the Fundamental Theorem.
12.1 Abstract Channels.
12.2 More Specific Channels.
12.3 New Channels from Old, Cascades.
12.4 Input Probability, Channel Capacity.
12.5 Capacity for General Binary Channels, Entropy.
12.6 Hamming Distance.
12.7 Improving Reliability of a Binary Symmetric Channel.
12.8 Error Correction, Error Reduction, Good Redundancy.
12.9 The Fundamental Theorem of Information Theory.
12.10 Summary, the Big Picture.
12.11 Problems.
12.12 Solutions.
13. Signals, Sampling, S/N Ratio, Coding Gain.
13.1 Continuous Signals, Shannon's Sampling Theorem.
13.2 The Band-limited Capacity Theorem.
13.3 The Coding Gain.
14. Ergodic and Markov Sources, Language Entropy.
14.1 General and Stationary Sources.
14.2 Ergodic Sources.
14.3 Markov Chains and Markov Sources.
14.4 Irreducible Markov Sources, Adjoint Source.
14.5 Markov Chains, Cascades, the Data Processing Theorem.
14.6 The Redundancy of Languages.
14.7 Problems.
14.8 Solutions.
15. Perfect Secrecy: The New Paradigm.
15.1 Introduction.
15.2 Perfect Secrecy and Equiprobable Keys.
15.3 Perfect Secrecy and Latin Squares.
15.4 The Abstract Approach to Perfect Secrecy.
15.5 Cryptography, Information Theory, Shannon.
15.6 Problems.
15.7 Solutions.
16. Linear Feedback Shift Registers (LFSR).
16.1 Introduction.
16.2 Construction of Feedback Shift Registers.
16.3 Periodicity.
16.4 Maximal Periods and Pseudo Random Sequences.
16.5 Determining the Output From 2m Bits.
16.6 The Tap Polynomial and the Period.
16.7 Berlekamp-Massey Algorithm.
16.8 Problems.
16.9 Solutions.
17. The Genetic Code.
17.1 Introduction.
17.2 History of Genetics.
17.3 Structure and Purpose of DNA.
17.4 The Double Helix, Replication.
17.5 Protein Synthesis.
17.6 Viruses.
17.7 Criminology.
17.8 Entropy and Compression in Genetics.
17.9 Channel Capacity of the Genetic Code.
III. ERROR-CORRECTION.
18. Error-Correction, Hadamard, and Bruen-Ott.
18.1 Introduction.
18.2 Error Detection, Error Correction.
18.3 A Formula for Correction and Detection.
18.4 Hadamard Matrices.
18.5 Mariner, Hadamard and Reed-Muller.
18.6 Reed-Muller Codes.
18.7 Block Designs.
18.8 A Problem of Lander, the Bruen-Ott Theorem.
18.9 The Main Coding Theory Problem, Bounds.
19. Finite Fields, Linear Algebra, and Number Theory.
19.1 Modular Arithmetic.
19.2 A Little Linear Algebra.
19.3 Applications to RSA.
19.4 Primitive Roots for Primes and Diffie-Hellman.
19.5 The Extended Euclidean Algorithm.
19.6 Proof that the RSA Algorithm Works.
19.7 Constructing Finite Fields.
19.8 Problems.
19.9 Solutions.
20. Introduction to Linear Codes.
20.1 Introduction.
20.2 Details of Linear Codes.
20.3 Parity Checks, the Syndrome, Weights.
20.4 Hamming Codes.
20.5 Perfect Codes, Errors and the BSC.
20.6 Generalizations of Binary Hamming Codes.
20.7 The Football Pools Problem, Extended Hamming Codes.
20.8 Golay Codes.
20.9 McEliece Cryptosystem.
20.10 CRC32.
20.11 Problems.
20.12 Solutions.
21. Linear Cyclic Codes and Shift Registers.
21.1 Cyclic Linear Codes.
21.2 Generators for Cyclic Codes.
21.3 The Dual Code and The Two Methods.
21.4 Linear Feedback Shift Registers and Codes.
21.5 Finding the Period of a LFSR.
21.6 Problems.
21.7 Solutions.
22. Reed Solomon and MDS Codes, Bruen-Thas-Blockhuis.
22.1 Cyclic Linear Codes and the Vandermonde Matrix.
22.2 The Singleton Bound.
22.3 Reed-Solomon Codes.
22.4 Reed-Solomon Codes and the Fourier Transform Approach.
22.5 Correcting Burst Errors, Interleaving.
22.6 Decoding Reed-Solomon, Ramanujan, Berlekamp-Massey.
22.7 An Algorithm and an Example.
22.8 MDS Codes and a Solution of the Fifty Year-old Problem.
22.9 Problems.
22.10 Solutions.
23. MDS Codes, Secret Sharing, Invariant Theory.
23.1 General MDS codes.
23.2 The Case k=2, Bruck Nets.
23.3 Upper Bounds, Bruck-Ryser.
23.4 MDS Codes and Secret Sharing Schemes.
23.5 MacWilliams Identities, Invariant Theory.
23.6 Codes, Planes, Blocking Sets.
23.7 Binary Linear Codes of Minimum Distance 4.
24. Key Reconciliation, Linear Codes, New Algorithms.
24.1 Introduction.
24.2 General Background.
24.3 The Secret Key and The Reconciliation Algorithm.
24.4 Equality of Remnant Keys: The Halting Criterion.
24.5 Convergence of Keys: The Checking Hash Function.
24.6 Convergence and Length of Keys.
24.7 Main Results.
24.8 Some Details on the Random Permutation.
24.9 The Case where Eve has Non-zero Initial Information.
24.10 Hash, Functions using Block Designs.
24.11 Concluding Remarks.
ASCII.
Shannon's Entropy Table.
Glossary.
Bibliography.
Index.
- Log in to post comments
