Aiden A. Bruen - Cryptography, Information Theory, and Error-Correction

1 Cover

2 Series Page

3 Title Page

4 Copyright

5 Dedications

6 Preface to the Second EditionWELCOME, New Co‐author Intended Readership, Connections Between the Areas Problems with Solutions Style Possible Courses What's New Hardcover and eBook

7 Acknowledgments for the Second Edition

8 Book Website

9 About the Authors

10 Part I: Mainly Cryptography Chapter 1: Historical Introduction and the Life and Work of 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 The Data Encryption Standard Code, DES, 1977–2005 1.7 Post‐Shannon Developments Notes Chapter 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 Frequency Analysis 2.6 Breaking the Vigenère Cipher, Babbage–Kasiski 2.7 The Enigma Machine and Its Mathematics 2.8 Modern Enciphering Systems 2.9 Problems 2.10 Solutions Chapter 3: RSA, Key Searches, TLS, and Encrypting Email 3.1 The Basic Idea of Cryptography 3.2 Public Key Cryptography and RSA on a Calculator 3.3 The General RSA Algorithm 3.4 Public Key Versus Symmetric Key 3.5 Attacks, Security, Catch‐22 of Cryptography 3.6 Summary of Encryption 3.7 The Diffie–Hellman Key Exchange 3.8 Intruder‐in‐the‐Middle Attack on the Diffie–Hellman (or Elliptic Curve) Key‐Exchange 3.9 TLS (Transport Layer Security) 3.10 PGP and GPG 3.11 Problems 3.12 Solutions Notes Chapter 4: The Fundamentals of Modern Cryptography 4.1 Encryption Revisited 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 Digital Signatures 4.8 Modifying Encrypted Data and Homomorphic Encryption 4.9 Quantum Encryption Using Polarized Photons 4.10 Quantum Encryption Using Entanglement 4.11 Quantum Key Distribution is Not a Silver Bullet 4.12 Postquantum Cryptography 4.13 Key Management and Kerberos 4.14 Problems 4.15 Solutions Chapter 5: Modes of Operation for AES and Symmetric Algorithms 5.1 Modes of Operation 5.2 The Advanced Encryption Standard Code 5.3 Overview of AES Chapter 6: Elliptic Curve Cryptography (ECC) 6.1 Abelian Integrals, Fields, Groups 6.2 Curves, Cryptography 6.3 The Hasse Theorem, and an Example 6.4 More Examples 6.5 The Group Law on Elliptic Curves 6.6 Key Exchange with Elliptic Curves 6.7 Elliptic Curves mod n 6.8 Encoding Plain Text 6.9 Security of ECC 6.10 More Geometry of Cubic Curves 6.11 Cubic Curves and Arcs 6.12 Homogeneous Coordinates 6.13 Fermat's Last Theorem, Elliptic Curves, Gerhard Frey 6.14 A Modification of the Standard Version of Elliptic Curve Cryptography 6.15 Problems 6.16 Solutions Chapter 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 Relay Attacks, Car Key Fobs 7.6 Known Plain Text Attacks 7.7 Known Cipher Text Attacks 7.8 Chosen Plain Text Attacks 7.9 Chosen Cipher Text Attacks, Digital Signatures 7.10 Replay Attacks 7.11 Birthday Attacks 7.12 Birthday Attack on Digital Signatures 7.13 Birthday Attack on the Discrete Log Problem 7.14 Attacks on RSA 7.15 Attacks on RSA using Low‐Exponents 7.16 Timing Attack 7.17 Differential Cryptanalysis 7.18 Attacks Utilizing Preprocessing 7.19 Cold Boot Attacks on Encryption Keys 7.20 Implementation Errors and Unforeseen States 7.21 Tracking. Bluetooth, WiFi, and Your Smart Phone 7.22 Keep Up with the Latest Attacks (If You Can) Notes Chapter 8: Practical Issues in Modern Cryptography and Communications 8.1 Introduction 8.2 Hot Issues 8.3 Authentication 8.4 User Anonymity 8.5 E‐commerce 8.6 E‐government 8.7 Key Lengths 8.8 Digital Rights 8.9 Wireless Networks 8.10 Communication Protocols Notes

11 Part II: Mainly Information Theory Chapter 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 of Information Theory 9.7 Number Bases, Erdös and the Hand of God 9.8 Weighing Problems and Your MBA 9.9 Shannon Bits, the Big Picture Chapter 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 Chapter 11: Source Coding, Redundancy 11.1 Introduction, Source Extensions 11.2 Encodings, Kraft, McMillan 11.3 Block Coding, the Oracle, Yes–No Questions 11.4 Optimal Codes 11.5 Huffman Coding 11.6 Optimality of Huffman Coding 11.7 Data Compression, Redundancy 11.8 Problems 11.9 Solutions Chapter 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 Proving the Fundamental Theorem 12.11 Summary, the Big Picture 12.12 Postscript: The Capacity of the Binary Symmetric Channel 12.13 Problems 12.14 Solutions Chapter 13: Signals, Sampling, Coding Gain, Shannon's Information Capacity Theorem 13.1 Continuous Signals, Shannon's Sampling Theorem 13.2 The Band‐Limited Capacity Theorem 13.3 The Coding Gain Chapter 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 Cascades and the Data Processing Theorem 14.6 The Redundancy of Languages 14.7 Problems 14.8 Solutions Chapter 15: Perfect Secrecy: The New Paradigm 15.1 Symmetric Key Cryptosystems 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 Unique Message from Ciphertext, Unicity 15.7 Problems 15.8 Solutions Chapter 16: Shift Registers (LFSR) and Stream Ciphers 16.1 Vernam Cipher, Psuedo‐Random Key 16.2 Construction of Feedback Shift Registers 16.3 Periodicity 16.4 Maximal Periods, Pseudo‐Random Sequences 16.5 Determining the Output from 2 m Bits 16.6 The Tap Polynomial and the Period 16.7 Short Linear Feedback Shift Registers and the Berlekamp‐Massey Algorithm 16.8 Problems 16.9 Solutions Chapter 17: Compression and Applications 17.1 Introduction, Applications 17.2 The Memory Hierarchy of a Computer 17.3 Memory Compression 17.4 Lempel–Ziv Coding 17.5 The WKdm Algorithms 17.6 Main Memory – to Compress or Not to Compress 17.7 Problems 17.8 Solutions

12 Part III: Mainly Error‐Correction Chapter 18: Error‐Correction, Hadamard, and Bruen–Ott18.1 General Ideas of Error Correction 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 The Rank of Incidence Matrices 18.9 The Main Coding Theory Problem, Bounds 18.10 Update on the Reed–Muller Codes: The Proof of an Old Conjecture 18.11 Problems 18.12 Solutions Chapter 19: Finite Fields, Modular Arithmetic, 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 Pollard's