Читать книгу Cryptography, Information Theory, and Error-Correction - Aiden A. Bruen - Страница 2
Table of Contents
Оглавление1 Cover
6 Preface to the Second Edition WELCOME, 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
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 2m 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–Ott 18.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 p-1 Factoring Algorithm 19.9 Latin Squares 19.10 Computational Complexity, Turing Machines, Quantum Computing 19.11 Problems 19.12 Solutions Note Chapter 20: Introduction to Linear Codes 20.1 Repetition Codes and Parity Checks 20.2 Details of Linear Codes 20.3 Parity Checks, the Syndrome, and Weights 20.4 Hamming Codes, an Inequality 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 Historical Remarks 20.11 Problems 20.12 Solutions Chapter 21: Cyclic Linear Codes, Shift Registers, and CRC 21.1 Cyclic Linear Codes 21.2 Generators for Cyclic Codes 21.3 The Dual Code 21.4 Linear Feedback Shift Registers and Codes 21.5 Finding the Period of a LFSR 21.6 Cyclic Redundancy Check (CRC) 21.7 Problems 21.8 Solutions Chapter 22: Reed‐Solomon and MDS Codes, and the Main Linear Coding Theory Problem (LCTP) 22.1 Cyclic Linear Codes and Vandermonde 22.2 The Singleton Bound for Linear Codes 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 Codes, Ramanujan, and Berlekamp–Massey 22.7 An Algorithm for Decoding and an Example 22.8 Long MDS Codes and a Partial Solution of a 60 Year‐Old Problem 22.9 Problems 22.10 Solutions Chapter 23: MDS Codes, Secret Sharing, and Invariant Theory 23.1 Some Facts Concerning MDS Codes 23.2 The Case k = 2, Bruck Nets 23.3 Upper Bounds on MDS Codes, Bruck–Ryser 23.4 MDS Codes and Secret Sharing Schemes 23.5 MacWilliams Identities, Invariant Theory 23.6 Codes, Planes, and Blocking Sets 23.7 Long Binary Linear Codes of Minimum Weight at Least 4 23.8 An Inverse Problem and a Basic Question in Linear Algebra Chapter 24: Key Reconciliation, Linear Codes, and New Algorithms 24.1 Symmetric and Public Key Cryptography 24.2 General Background 24.3 The Secret Key and the Reconciliation Algorithm 24.4 Equality of Remnant Keys: The Halting Criterion 24.5 Linear Codes: 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 Nonzero Initial Information 24.10 Hash Functions Using Block Designs 24.11 Concluding Remarks Note Chapter 25: New Identities for the Shannon Function with Applications 25.1 Extensions of a Binary Symmetric Channel 25.2 A Basic Entropy Equality 25.3 The New Identities 25.4 Applications to Cryptography and a Shannon‐Type Limit 25.5 Problems 25.6 Solutions Chapter 26: Blockchain and Bitcoin 26.1 Ledgers, Blockchains 26.2 Hash Functions, Cryptographic Hashes 26.3 Digital Signatures 26.4 Bitcoin and Cryptocurrencies 26.5 The Append‐Only Network, Identities, Timestamp, Definition of a Bitcoin 26.6 The Bitcoin Blockchain and Merkle Roots 26.7 Mining, Proof‐of‐Work, Consensus 26.8 Thwarting Double Spending Chapter 27: IoT, The Internet of Things 27.1 Introduction 27.2 Analog to Digital (A/D) Converters 27.3 Programmable Logic Controller 27.4 Embedded Operating Systems 27.5 Evolution, From SCADA to the Internet of Things 27.6 Everything is Fun and Games until Somebody Releases a Stuxnet 27.7 Securing the IoT, a Mammoth Task 27.8 Privacy and Security Notes Chapter 28: In the Cloud 28.1 Introduction 28.2 Distributed Systems 28.3 Cloud Storage – Availability and Copyset Replication 28.4 Homomorphic Encryption 28.5 Cybersecurity 28.6 Problems 28.7 Solutions Chapter 29: Review Problems and Solutions 29.1 Problems 29.2 Solutions
13 Appendix A A.1 ASCII
14 Appendix B B.1 Shannon's Entropy Table
15 Glossary
16 References
17 Index
