Cryptography, Information Theory, and Error-Correction

Aiden A. Bruen, PhD, was most-recently adjunct research professor in the School of Mathematics and Statistics at Carleton University. He was professor of mathematics and honorary professor of applied mathematics at the University of Western Ontario from 1972-1999 and has instructed at various institutions since then. Dr. Bruen is the co-author of Cryptography, Information Theory, and Error-Correction: A Handbook for the 21st Century (Wiley, 2004).Mario A. Forcinito, PhD, is Director and Chief Engineer at AP Dynamics Inc. in Calgary. He is previously instructor at the Pipeline Engineering Center at the Schulich School of Engineering in Calgary. Dr. Forcinito is co-author of Cryptography, Information Theory, and Error-Correction: A Handbook for the 21st Century (Wiley, 2004).

• Preface to the Second Edition xviiAcknowledgments for the Second Edition xxiiiBook Website xxvAbout the Authors xxviiI Mainly Cryptography 11 Historical Introduction and the Life and Work of Claude E. Shannon 31.1 Historical Background 31.2 Brief Biography of Claude E. Shannon 91.3 Career 101.4 Personal – Professional 101.5 Scientific Legacy 111.6 The Data Encryption Standard Code, DES, 1977–2005 141.7 Post-Shannon Developments 152 Classical Ciphers and Their Cryptanalysis 212.1 Introduction 222.2 The Caesar Cipher 222.3 The Scytale Cipher 242.4 The Vigen`ere Cipher 252.5 Frequency Analysis 262.6 Breaking the Vigen`ere Cipher, Babbage–Kasiski 272.7 The Enigma Machine and Its Mathematics 332.8 Modern Enciphering Systems 372.9 Problems 372.10 Solutions 393 RSA, Key Searches, TLS, and Encrypting Email 473.1 The Basic Idea of Cryptography 493.2 Public Key Cryptography and RSA on a Calculator 533.3 The General RSA Algorithm 563.4 Public Key Versus Symmetric Key 603.5 Attacks, Security, Catch-22 of Cryptography 623.6 Summary of Encryption 653.7 The Diffie–Hellman Key Exchange 663.8 Intruder-in-the-Middle Attack on the Diffie–Hellman (or Elliptic Curve) Key-Exchange 693.9 TLS (Transport Layer Security) 703.10 PGP and GPG 723.11 Problems 733.12 Solutions 764 The Fundamentals of Modern Cryptography 834.1 Encryption Revisited 834.2 Block Ciphers, Shannon’s Confusion and Diffusion 864.3 Perfect Secrecy, Stream Ciphers, One-Time Pad 874.4 Hash Functions 914.5 Message Integrity Using Symmetric Cryptography 934.6 General Public Key Cryptosystems 944.7 Digital Signatures 974.8 Modifying Encrypted Data and Homomorphic Encryption 994.9 Quantum Encryption Using Polarized Photons 994.10 Quantum Encryption Using Entanglement 1024.11 Quantum Key Distribution is Not a Silver Bullet 1034.12 Postquantum Cryptography 1044.13 Key Management and Kerberos 1044.14 Problems 1064.15 Solutions 1075 Modes of Operation for AES and Symmetric Algorithms 1095.1 Modes of Operation 1095.2 The Advanced Encryption Standard Code 1115.3 Overview of AES 1146 Elliptic Curve Cryptography (ECC) 1256.1 Abelian Integrals, Fields, Groups 1266.2 Curves, Cryptography 1286.3 The Hasse Theorem, and an Example 1296.4 More Examples 1316.5 The Group Law on Elliptic Curves 1316.6 Key Exchange with Elliptic Curves 1346.7 Elliptic Curves mod n 1346.8 Encoding Plain Text 1356.9 Security of ECC 1356.10 More Geometry of Cubic Curves 1356.11 Cubic Curves and Arcs 1366.12 Homogeneous Coordinates 1376.13 Fermat’s Last Theorem, Elliptic Curves, Gerhard Frey 1376.14 A Modification of the Standard Version of Elliptic Curve Cryptography 1386.15 Problems 1396.16 Solutions 1407 General and Mathematical Attacks in Cryptography 1437.1 Cryptanalysis 1437.2 Soft Attacks 1447.3 Brute-Force Attacks 1457.4 Man-in-the-Middle Attacks 1467.5 Relay Attacks, Car Key Fobs 1487.6 Known Plain Text Attacks 1507.7 Known Cipher Text Attacks 1517.8 Chosen Plain Text Attacks 1517.9 Chosen Cipher Text Attacks, Digital Signatures 1517.10 Replay Attacks 1527.11 Birthday Attacks 1527.12 Birthday Attack on Digital Signatures 1547.13 Birthday Attack on the Discrete Log Problem 1547.14 Attacks on RSA 1557.15 Attacks on RSA using Low-Exponents 1567.16 Timing Attack 1567.17 Differential Cryptanalysis 1577.18 Attacks Utilizing Preprocessing 1577.19 Cold Boot Attacks on Encryption Keys 1597.20 Implementation Errors and Unforeseen States 1597.21 Tracking. Bluetooth, WiFi, and Your Smart Phone 1637.22 Keep Up with the Latest Attacks (If You Can) 1648 Practical Issues in Modern Cryptography and Communications 1658.1 Introduction 1658.2 Hot Issues 1678.3 Authentication 1678.4 User Anonymity 1748.5 E-commerce 1758.6 E-government 1768.7 Key Lengths 1788.8 Digital Rights 1798.9 Wireless Networks 1798.10 Communication Protocols 180II Mainly Information Theory 1839 Information Theory and its Applications 1859.1 Axioms, Physics, Computation 1869.2 Entropy 1869.3 Information Gained, Cryptography 1889.4 Practical Applications of Information Theory 1909.5 Information Theory and Physics 1929.6 Axiomatics of Information Theory 1939.7 Number Bases, Erd¨os and the Hand of God 1949.8 Weighing Problems and Your MBA 1969.9 Shannon Bits, the Big Picture 20010 Random Variables and Entropy 20110.1 Random Variables 20110.2 Mathematics of Entropy 20510.3 Calculating Entropy 20610.4 Conditional Probability 20710.5 Bernoulli Trials 21110.6 Typical Sequences 21310.7 Law of Large Numbers 21410.8 Joint and Conditional Entropy 21510.9 Applications of Entropy 22110.10 Calculation of Mutual Information 22110.11 Mutual Information and Channels 22310.12 The Entropy of X + Y 22410.13 Subadditivity of the Function −x log x 22510.14 Entropy and Cryptography 22510.15 Problems 22610.16 Solutions 22711 Source Coding, Redundancy 23311.1 Introduction, Source Extensions 23411.2 Encodings, Kraft, McMillan 23511.3 Block Coding, the Oracle, Yes–No Questions 24111.4 Optimal Codes 24211.5 Huffman Coding 24311.6 Optimality of Huffman Coding 24811.7 Data Compression, Redundancy 24911.8 Problems 25111.9 Solutions 25212 Channels, Capacity, the Fundamental Theorem 25512.1 Abstract Channels 25612.2 More Specific Channels 25712.3 New Channels from Old, Cascades 25812.4 Input Probability, Channel Capacity 26112.5 Capacity for General Binary Channels, Entropy 26512.6 Hamming Distance 26612.7 Improving Reliability of a Binary Symmetric Channel 26812.8 Error Correction, Error Reduction, Good Redundancy 26812.9 The Fundamental Theorem of Information Theory 27212.10 Proving the Fundamental Theorem 27912.11 Summary, the Big Picture 28112.12 Postscript: The Capacity of the Binary Symmetric Channel 28212.13 Problems 28312.14 Solutions 28413 Signals, Sampling, Coding Gain, Shannon’s Information Capacity Theorem 28713.1 Continuous Signals, Shannon’s Sampling Theorem 28813.2 The Band-Limited Capacity Theorem 29013.3 The Coding Gain 29614 Ergodic and Markov Sources, Language Entropy 29914.1 General and Stationary Sources 30014.2 Ergodic Sources 30214.3 Markov Chains and Markov Sources 30414.4 Irreducible Markov Sources, Adjoint Source 30814.5 Cascades and the Data Processing Theorem 31014.6 The Redundancy of Languages 31114.7 Problems 31314.8 Solutions 31515 Perfect Secrecy: The New Paradigm 31915.1 Symmetric Key Cryptosystems 32015.2 Perfect Secrecy and Equiprobable Keys 32115.3 Perfect Secrecy and Latin Squares 32215.4 The Abstract Approach to Perfect Secrecy 32415.5 Cryptography, Information Theory, Shannon 32515.6 Unique Message from Ciphertext, Unicity 32515.7 Problems 32715.8 Solutions 32916 Shift Registers (LFSR) and Stream Ciphers 33316.1 Vernam Cipher, Psuedo-Random Key 33416.2 Construction of Feedback Shift Registers 33516.3 Periodicity 33716.4 Maximal Periods, Pseudo-Random Sequences 34016.5 Determining the Output from 2m Bits 34116.6 The Tap Polynomial and the Period 34516.7 Short Linear Feedback Shift Registers and the Berlekamp-Massey Algorithm 34716.8 Problems 35016.9 Solutions 35217 Compression and Applications 35517.1 Introduction, Applications 35617.2 The Memory Hierarchy of a Computer 35817.3 Memory Compression 35817.4 Lempel–Ziv Coding 36117.5 The WKdm Algorithms 36217.6 Main Memory – to Compress or Not to Compress 37017.7 Problems 37317.8 Solutions 374III Mainly Error-Correction 37918 Error-Correction, Hadamard, and Bruen–Ott 38118.1 General Ideas of Error Correction 38118.2 Error Detection, Error Correction 38218.3 A Formula for Correction and Detection 38318.4 Hadamard Matrices 38418.5 Mariner, Hadamard, and Reed–Muller 38718.6 Reed–Muller Codes 38818.7 Block Designs 38918.8 The Rank of Incidence Matrices 39018.9 The Main Coding Theory Problem, Bounds 39118.10 Update on the Reed–Muller Codes: The Proof of an Old Conjecture 39618.11 Problems 39818.12 Solutions 39919 Finite Fields, Modular Arithmetic, Linear Algebra, and Number Theory 40119.1 Modular Arithmetic 40219.2 A Little Linear Algebra 40519.3 Applications to RSA 40719.4 Primitive Roots for Primes and Diffie–Hellman 40919.5 The Extended Euclidean Algorithm 41219.6 Proof that the RSA Algorithm Works 41319.7 Constructing Finite Fields 41319.8 Pollard’s p − 1 Factoring Algorithm 41819.9 Latin Squares 41919.10 Computational Complexity, Turing Machines, Quantum Computing 42119.11 Problems 42519.12 Solutions 42620 Introduction to Linear Codes 42920.1 Repetition Codes and Parity Checks 42920.2 Details of Linear Codes 43120.3 Parity Checks, the Syndrome, and Weights 43520.4 Hamming Codes, an Inequality 43820.5 Perfect Codes, Errors, and the BSC 43920.6 Generalizations of Binary Hamming Codes 44020.7 The Football Pools Problem, Extended Hamming Codes 44120.8 Golay Codes 44220.9 McEliece Cryptosystem 44320.10 Historical Remarks 44420.11 Problems 44520.12 Solutions 44821 Cyclic Linear Codes, Shift Registers, and CRC 45321.1 Cyclic Linear Codes 45421.2 Generators for Cyclic Codes 45721.3 The Dual Code 46021.4 Linear Feedback Shift Registers and Codes 46221.5 Finding the Period of a LFSR 46521.6 Cyclic Redundancy Check (CRC) 46621.7 Problems 46721.8 Solutions 46922 Reed-Solomon and MDS Codes, and the Main Linear Coding Theory Problem (LCTP) 47322.1 Cyclic Linear Codes and Vandermonde 47422.2 The Singleton Bound for Linear Codes 47622.3 Reed–Solomon Codes 47922.4 Reed-Solomon Codes and the Fourier Transform Approach 47922.5 Correcting Burst Errors, Interleaving 48122.6 Decoding Reed-Solomon Codes, Ramanujan, and Berlekamp–Massey 48222.7 An Algorithm for Decoding and an Example 48422.8 Long MDS Codes and a Partial Solution of a 60 Year-Old Problem 48722.9 Problems 49022.10 Solutions 49123 MDS Codes, Secret Sharing, and Invariant Theory 49323.1 Some Facts Concerning MDS Codes 49323.2 The Case k = 2, Bruck Nets 49423.3 Upper Bounds on MDS Codes, Bruck–Ryser 49723.4 MDS Codes and Secret Sharing Schemes 49923.5 MacWilliams Identities, Invariant Theory 50023.6 Codes, Planes, and Blocking Sets 50123.7 Long Binary Linear Codes of Minimum Weight at Least 4 50423.8 An Inverse Problem and a Basic Question in Linear Algebra 50624 Key Reconciliation, Linear Codes, and New Algorithms 50724.1 Symmetric and Public Key Cryptography 50824.2 General Background 50924.3 The Secret Key and the Reconciliation Algorithm 51124.4 Equality of Remnant Keys: The Halting Criterion 51424.5 Linear Codes: The Checking Hash Function 51624.6 Convergence and Length of Keys 51824.7 Main Results 52124.8 Some Details on the Random Permutation 53024.9 The Case Where Eve Has Nonzero Initial Information 53024.10 Hash Functions Using Block Designs 53124.11 Concluding Remarks 53225 New Identities for the Shannon Function with Applications 53525.1 Extensions of a Binary Symmetric Channel 53625.2 A Basic Entropy Equality 53925.3 The New Identities 54125.4 Applications to Cryptography and a Shannon-Type Limit 54425.5 Problems 54525.6 Solutions 54526 Blockchain and Bitcoin 54926.1 Ledgers, Blockchains 55126.2 Hash Functions, Cryptographic Hashes 55226.3 Digital Signatures 55326.4 Bitcoin and Cryptocurrencies 55326.5 The Append-Only Network, Identities, Timestamp, Definition of a Bitcoin 55626.6 The Bitcoin Blockchain and Merkle Roots 55626.7 Mining, Proof-of-Work, Consensus 55726.8 Thwarting Double Spending 55927 IoT, The Internet of Things 56127.1 Introduction 56227.2 Analog to Digital (A/D) Converters 56227.3 Programmable Logic Controller 56327.4 Embedded Operating Systems 56427.5 Evolution, From SCADA to the Internet of Things 56427.6 Everything is Fun and Games until Somebody Releases a Stuxnet 56527.7 Securing the IoT, a Mammoth Task 56727.8 Privacy and Security 56728 In the Cloud 57328.1 Introduction 57528.2 Distributed Systems 57628.3 Cloud Storage – Availability and Copyset Replication 57728.4 Homomorphic Encryption 58428.5 Cybersecurity 58528.6 Problems 58728.7 Solutions 58829 Review Problems and Solutions 58929.1 Problems 58929.2 Solutions 594Appendix A 603A.1 ASCII 603Appendix B 605B.1 Shannon’s Entropy Table 605Glossary 607References 615Index 643