Cryptography, Information Theory, and Error-Correction A Handbook for the 21st Century

A rich examination of the technologies supporting secure digital information transfers from respected leaders in the field

As technology continues to evolve Cryptography, Information Theory, and Error-Correction: A Handbook for the 21^ST Century is an indispensable resource for anyone interested in the secure exchange of financial information. Identity theft, cybercrime, and other security issues have taken center stage as information becomes easier to access. Three disciplines offer solutions to these digital challenges: cryptography, information theory, and error-correction, all of which are addressed in this book.

This book is geared toward a broad audience. It is an excellent reference for both graduate and undergraduate students of mathematics, computer science, cybersecurity, and engineering. It is also an authoritative overview for professionals working at financial institutions, law firms, and governments who need up-to-date information to make critical decisions. The book’s discussions will be of interest to those involved in blockchains as well as those working in companies developing and applying security for new products, like self-driving cars. With its reader-friendly style and interdisciplinary emphasis this book serves as both an ideal teaching text and a tool for self-learning for IT professionals, statisticians, mathematicians, computer scientists, electrical engineers, and entrepreneurs.

Six new chapters cover current topics like Internet of Things security, new identities in information theory, blockchains, cryptocurrency, compression, cloud computing and storage.  Increased security and applicable research in elliptic curve cryptography are also featured. The book also:

• Shares vital, new research in the field of information theory
• Provides quantum cryptography updates
• Includes over 350 worked examples and problems for greater understanding of ideas.

Cryptography, Information Theory, and Error-Correction guides readers in their understanding of reliable tools that can be used to store or transmit digital information safely.

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 xviii

I Cryptography 1

1 History and Claude E. Shannon 3

1.1 Historical Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Brief Biography of Claude E. Shannon . . . . . . . . . . . . . . . . . . . . . . 9

1.3 Career . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.4 Personal—Professional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.5 Scientific Legacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.6 The Data Encryption Standard Code, DES, 1977 - 2005 . . . . . . . . . . . . 14

1.7 Post-Shannon Developments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2 Classical Ciphers and their Cryptanalysis 19

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.2 The Caesar Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.3 The Scytale Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.4 The Vigenère Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.5 Frequency Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.6 Breaking the Vigenère Cipher, Babbage-Kasiski . . . . . . . . . . . . . . . . 25

2.7 The Enigma Machine and Its Mathematics . . . . . . . . . . . . . . . . . . . 30

2.8 Modern Enciphering Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.10 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3 RSA, Key Searches, TLS, and Encrypting Email 43

3.1 The Basic Idea of Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.2 Public Key Cryptography and RSA on a Calculator . . . . . . . . . . . . . . 48

3.3 The General RSA Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3.4 Public Key Versus Symmetric Key . . . . . . . . . . . . . . . . . . . . . . . . 55

3.5 Attacks, Security, Catch-22 of Cryptography . . . . . . . . . . . . . . . . . . . 58

3.6 Summary of Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

3.7 The Diffie-Hellman Key Exchange . . . . . . . . . . . . . . . . . . . . . . . . 61

3.8 Intruder-in-the-Middle — Diffie-Hellman Key-Exchange . . . . . . . . . . . . 65

3.9 TLS (Transport Layer Security) . . . . . . . . . . . . . . . . . . . . . . . . . . 65

3.10 PGP and GPG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

3.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

3.12 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

4 The Fundamentals of Modern Cryptography 79

4.1 Encryption Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

4.2 Block Ciphers, Shannon’s Confusion and Diffusion . . . . . . . . . . . . . . . 82

4.3 Perfect Secrecy, Stream Ciphers, One-Time Pad . . . . . . . . . . . . . . . . . 83

4.4 Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

4.5 Message Integrity Using Symmetric Cryptography . . . . . . . . . . . . . . . 89

4.6 General Public Key Cryptosystems . . . . . . . . . . . . . . . . . . . . . . . . 91

4.7 Digital Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

4.8 Modifying Encrypted Data and Homomorphic Encryption . . . . . . . . . . . 95

4.9 Quantum Encryption using Polarized Photons . . . . . . . . . . . . . . . . . . 95

4.10 Quantum Encryption using Entanglement . . . . . . . . . . . . . . . . . . . . 98

4.11 Quantum Key Distribution is Not a Silver Bullet . . . . . . . . . . . . . . . . 99

4.12 Post-Quantum Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

4.13 Key Management and Kerberos . . . . . . . . . . . . . . . . . . . . . . . . . . 100

4.14 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

4.15 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

5 Modes of Operation for AES and Symmetric Algorithms 105

5.1 Modes of Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

5.2 The Advanced Encryption Standard Code . . . . . . . . . . . . . . . . . . . . 107

6 Elliptic Curve Cryptography (ECC) 119

6.1 Abelian Integrals, Fields, Groups . . . . . . . . . . . . . . . . . . . . . . . . . 120

6.2 Curves, Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

6.3 Nonsingularity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

6.4 The Hasse Theorem, and an Example . . . . . . . . . . . . . . . . . . . . . . 123

6.5 More Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

6.6 The Group Law on Elliptic Curves . . . . . . . . . . . . . . . . . . . . . . . . 125

6.7 Key Exchange with Elliptic Curves . . . . . . . . . . . . . . . . . . . . . . . . 128

6.8 Elliptic Curves mod n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

6.9 Encoding Plain Text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

6.10 Security of ECC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

6.11 More Geometry of Cubic Curves . . . . . . . . . . . . . . . . . . . . . . . . . 129

6.12 Cubic Curves and Arcs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

6.13 Homogeneous Coordinates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

6.14 Fermat’s Last Theorem, Elliptic Curves, Gerhard Frey . . . . . . . . . . . . . 131

6.15 A Modification of the Standard Version of Elliptic Curve Cryptography . . . 132

6.16 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

6.17 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

7 Attacks in Cryptography 139

7.1 Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

7.2 Soft Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140

7.3 Brute-Force Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

7.4 Man-in-the-Middle Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

7.5 Relay Attacks, Car Key Fobs . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

7.6 Known Plain Text Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

7.7 Known Cipher Text Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

7.8 Chosen Plain Text Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

7.9 Chosen Cipher Text Attacks, Digital Signatures . . . . . . . . . . . . . . . . . 147

7.10 Replay Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

7.11 Birthday Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

7.12 Birthday Attack on Digital Signatures . . . . . . . . . . . . . . . . . . . . . . 150

7.13 Birthday Attack on the Discrete Log Problem . . . . . . . . . . . . . . . . . . 150

7.14 Attacks on RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

7.15 Attacks on RSA using Low-Exponents . . . . . . . . . . . . . . . . . . . . . . 151

7.16 Timing Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

7.17 Differential Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

7.18 Attacks utilizing Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . 153

7.19 Cold Boot Attacks on Encryption Keys . . . . . . . . . . . . . . . . . . . . . 154

7.20 Implementation Errors and Unforeseen States . . . . . . . . . . . . . . . . . . 155

7.21 Tracking. Bluetooth, WiFi, and Your Smart Phone . . . . . . . . . . . . . . . 159

7.22 Keep Up with the Latest Attacks, (If You Can) . . . . . . . . . . . . . . . . . 160

8 Practical Issues in Modern Cryptography and Communications 161

8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

8.2 Hot Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

8.3 Authentication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

8.4 User Anonymity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

8.5 E-commerce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171

8.6 E-government . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

8.7 Key Lengths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174

8.8 Digital Rights . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174

8.9 Wireless Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

8.10 Communication Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176

II Information Theory 179

9 Information Theory and its Applications 181

9.1 Axioms, Physics, Computation . . . . . . . . . . . . . . . . . . . . . . . . . . 181

9.2 Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

9.3 Information Gained, Cryptography . . . . . . . . . . . . . . . . . . . . . . . . 184

9.4 Practical Applications of Information Theory . . . . . . . . . . . . . . . . . . 186

9.5 Information Theory and Physics . . . . . . . . . . . . . . . . . . . . . . . . . 188

9.6 Axiomatics of Information Theory . . . . . . . . . . . . . . . . . . . . . . . . 189

9.7 Number Bases, Erdös and the Hand of God . . . . . . . . . . . . . . . . . . . 190

9.8 Weighing Problems and Your MBA . . . . . . . . . . . . . . . . . . . . . . . . 192

9.9 Shannon Bits, the Big Picture . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

10 Random Variables and Entropy 197

10.1 Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197

10.2 Mathematics of Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201

10.3 Calculating Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202

10.4 Conditional Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203

10.5 Bernoulli Trials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207

10.6 Typical Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209

10.7 Law of Large Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

10.8 Joint and Conditional Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . 211

10.9 Applications of Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217

10.10Calculation of Mutual Information . . . . . . . . . . . . . . . . . . . . . . . . 217

10.11Mutual Information and Channels . . . . . . . . . . . . . . . . . . . . . . . . 219

10.12The Entropy of X + Y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220

10.13Subadditivity of the Function −x log x . . . . . . . . . . . . . . . . . . . . . . 221

10.14Entropy and Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221

10.15Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222

10.16Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223

11 Source Coding, Redundancy 229

11.1 Introduction, Source Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . 230

11.2 Encodings, Kraft, McMillan . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231

11.3 Block Coding, the Oracle, Yes-No Questions . . . . . . . . . . . . . . . . . . . 237

11.4 Optimal Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238

11.5 Huffman Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239

11.6 Optimality of Huffman Coding . . . . . . . . . . . . . . . . . . . . . . . . . . 245

11.7 Data Compression, Redundancy . . . . . . . . . . . . . . . . . . . . . . . . . 246

11.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248

11.9 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249

12 Channels, Capacity, the Fundamental Theorem 251

12.1 Abstract Channels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252

12.2 More Specific Channels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253

12.3 New Channels from Old, Cascades . . . . . . . . . . . . . . . . . . . . . . . . 254

12.4 Input Probability, Channel Capacity . . . . . . . . . . . . . . . . . . . . . . . 257

12.5 Capacity for General Binary Channels, Entropy . . . . . . . . . . . . . . . . . 261

12.6 Hamming Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262

12.7 Improving Reliability of a Binary Symmetric Channel . . . . . . . . . . . . . 264

12.8 Error Correction, Error Reduction, Good Redundancy . . . . . . . . . . . . . 264

12.9 The Fundamental Theorem of Information Theory . . . . . . . . . . . . . . . 268

12.10Proving the Fundamental Theorem . . . . . . . . . . . . . . . . . . . . . . . . 275

12.11Summary, the Big Picture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277

12.12Postscript: The Capacity of the Binary Symmetric Channel . . . . . . . . . . 278

12.13Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279

12.14Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280

13 Shannon’s Information Capacity Theorem 283

13.1 Continuous Signals, Shannon’s Sampling Theorem . . . . . . . . . . . . . . . 284

13.2 The Band-Limited Capacity Theorem . . . . . . . . . . . . . . . . . . . . . . 286

13.3 The Coding Gain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292

14 Ergodic and Markov Sources, Language Entropy 295

14.1 General and Stationary Sources . . . . . . . . . . . . . . . . . . . . . . . . . . 296

14.2 Ergodic Sources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298

14.3 Markov Chains and Markov Sources . . . . . . . . . . . . . . . . . . . . . . . 300

14.4 Irreducible Markov Sources, Adjoint Source . . . . . . . . . . . . . . . . . . . 303

14.5 Cascades and the Data Processing Theorem . . . . . . . . . . . . . . . . . . . 305

14.6 The Redundancy of Languages . . . . . . . . . . . . . . . . . . . . . . . . . . 307

14.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309

14.8 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311

15 Perfect Secrecy: the New Paradigm 313

15.1 Symmetric Key Cryptosystems . . . . . . . . . . . . . . . . . . . . . . . . . . 313

15.2 Perfect Secrecy and Equiprobable Keys . . . . . . . . . . . . . . . . . . . . . 315

15.3 Perfect Secrecy and Latin Squares . . . . . . . . . . . . . . . . . . . . . . . . 316

15.4 The Abstract Approach to Perfect Secrecy . . . . . . . . . . . . . . . . . . . . 318

15.5 Cryptography, Information Theory, Shannon . . . . . . . . . . . . . . . . . . 319

15.6 Unique Message from Ciphertext, Unicity . . . . . . . . . . . . . . . . . . . . 319

15.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321

15.8 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322

16 Shift Registers (LFSR) and Stream Ciphers 327

16.1 Vernam Cipher, Psuedo-Random Key . . . . . . . . . . . . . . . . . . . . . . 328

16.2 Construction of Feedback Shift Registers . . . . . . . . . . . . . . . . . . . . 329

16.3 Periodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332

16.4 Maximal Periods, Pseudo-Random Sequences . . . . . . . . . . . . . . . . . . 334

16.5 Determining the Output from 2m Bits . . . . . . . . . . . . . . . . . . . . . 336

16.6 The Tap Polynomial and the Period . . . . . . . . . . . . . . . . . . . . . . . 340

16.7 Short Linear Feedback Shift Registers and the Berlekamp-Massey Algorithm . 341

16.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345

16.9 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346

17 Compression and Applications 349

17.1 Introduction, Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350

17.2 The Memory Hierarchy of a computer . . . . . . . . . . . . . . . . . . . . . . 351

17.3 Memory Compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352

17.4 Lempel-Ziv Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355

17.5 The WKdm algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357

17.6 Main Memory - to Compress or Not to Compress. . . . . . . . . . . . . . . . 364

17.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366

17.8 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368

III Error-Correction 371

18 Error-Correction, Hadamard, and Bruen-Ott 373

18.1 General Ideas of Error Correction . . . . . . . . . . . . . . . . . . . . . . . . . 373

18.2 Error Detection, Error Correction . . . . . . . . . . . . . . . . . . . . . . . . . 374

18.3 A Formula for Correction and Detection . . . . . . . . . . . . . . . . . . . . . 375

18.4 Hadamard Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376

18.5 Mariner, Hadamard and Reed-Muller . . . . . . . . . . . . . . . . . . . . . . . 379

18.6 Reed-Muller Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380

18.7 Block Designs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381

18.8 The Rank of Incidence Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 382

18.9 The Main Coding Theory Problem, Bounds . . . . . . . . . . . . . . . . . . . 383

18.10Update on the Reed-Muller Codes . . . . . . . . . . . . . . . . . . . . . . . . 388

18.11Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390

18.12Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390

19 Finite Fields, Modular Arithmetic, Linear Algebra, Number Theory 393

19.1 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393

19.2 A Little Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397

19.3 Applications to RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399

19.4 Primitive Roots for Primes and Diffie-Hellman . . . . . . . . . . . . . . . . . 400

19.5 The Extended Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 403

19.6 Proof that the RSA Algorithm Works . . . . . . . . . . . . . . . . . . . . . . 404

19.7 Constructing Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404

19.8 Pollard’s p − 1 Factoring Algorithm . . . . . . . . . . . . . . . . . . . . . . . 409

19.9 Latin Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410

19.10Complexity, Turing Machines, Quantum Computing . . . . . . . . . . . . . . 412

19.11Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415

19.12Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416

20 Introduction to Linear Codes 419

20.1 Repetition Codes and Parity Checks . . . . . . . . . . . . . . . . . . . . . . . 419

20.2 Details of Linear Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421

20.3 Parity Checks, the Syndrome, Weights . . . . . . . . . . . . . . . . . . . . . . 425

20.4 Hamming Codes, an Inequality . . . . . . . . . . . . . . . . . . . . . . . . . . 427

20.5 Perfect Codes, Errors and the BSC . . . . . . . . . . . . . . . . . . . . . . . . 429

20.6 Generalizations of Binary Hamming Codes . . . . . . . . . . . . . . . . . . . . 429

20.7 The Football Pools Problem, Extended Hamming Codes . . . . . . . . . . . . 430

20.8 Golay Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431

20.9 McEliece Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433

20.10Historical Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434

20.11Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435

20.12Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437

21 Cyclic Linear Codes, Shift Registers and CRC 443

21.1 Cyclic Linear Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443

21.2 Generators for Cyclic Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446

21.3 The Dual Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450

21.4 Linear Feedback Shift Registers and Codes . . . . . . . . . . . . . . . . . . . 452

21.5 Finding the Period of a LFSR . . . . . . . . . . . . . . . . . . . . . . . . . . . 455

21.6 Cyclic Redundancy Check (CRC) . . . . . . . . . . . . . . . . . . . . . . . . . 455

21.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457

21.8 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459

22 Reed-Solomon, MDS Codes, the Main LCTP Problem 463

22.1 Cyclic Linear Codes and Vandermonde . . . . . . . . . . . . . . . . . . . . . . 464

22.2 The Singleton Bound for Linear Codes . . . . . . . . . . . . . . . . . . . . . . 466

22.3 Reed-Solomon Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468

22.4 Reed-Solomon Codes and the Fourier Transform Approach . . . . . . . . . . . 469

22.5 Correcting Burst Errors, Interleaving . . . . . . . . . . . . . . . . . . . . . . . 471

22.6 Decoding Reed-Solomon Codes . . . . . . . . . . . . . . . . . . . . . . . . . . 472

22.7 An Algorithm for Decoding and an Example . . . . . . . . . . . . . . . . . . . 474

22.8 MDS Codes, a Partial Solution of a Sixty Year-Old Problem . . . . . . . . . . 477

22.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480

22.10Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480

23 MDS Codes, Secret Sharing, Invariant Theory 483

23.1 Some Facts Concerning MDS Codes . . . . . . . . . . . . . . . . . . . . . . . 483

23.2 The Case k = 2, Bruck Nets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484

23.3 Upper bounds on MDS Codes, Bruck-Ryser . . . . . . . . . . . . . . . . . . . 486

23.4 MDS Codes and Secret Sharing Schemes . . . . . . . . . . . . . . . . . . . . . 489

23.5 MacWilliams Identities, Invariant Theory . . . . . . . . . . . . . . . . . . . . 490

23.6 Codes, Planes, Blocking Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 490

23.7 Long Binary Linear Codes of Minimum Weight at Least 4 . . . . . . . . . . . 494

23.8 An Inverse Problem and a Basic Question in Linear Algebra . . . . . . . . . . 495

24 Key Reconciliation, Linear Codes, New Algorithms 497

24.1 Symmetric and Public Key Cryptography . . . . . . . . . . . . . . . . . . . . 498

24.2 General Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498

24.3 The Secret Key and the Reconciliation Algorithm . . . . . . . . . . . . . . . . 500

24.4 Equality of Remnant Keys: the Halting Criterion . . . . . . . . . . . . . . . . 504

24.5 Linear Codes: the Checking Hash Function . . . . . . . . . . . . . . . . . . . 506

24.6 Convergence and Length of Keys . . . . . . . . . . . . . . . . . . . . . . . . . 508

24.7 Main Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 510

24.8 Some Details on the Random Permutation . . . . . . . . . . . . . . . . . . . . 516

24.9 The Case where Eve has Non-Zero Initial Information . . . . . . . . . . . . . 516

24.10Hash Functions using Block Designs . . . . . . . . . . . . . . . . . . . . . . . 517

24.11Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518

25 New Identities for the Shannon Function and an Application 521

25.1 Extensions of a Binary Symmetric Channel . . . . . . . . . . . . . . . . . . . 522

25.2 A Basic Entropy Equality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524

25.3 The New Identities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526

25.4 Applications to Cryptography and a Shannon-type Limit . . . . . . . . . . . 529

25.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531

25.6 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531

26 Blockchain and Bitcoin 535

26.1 Ledgers, Blockchains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537

26.2 Hash Functions, Cryptographic Hashes . . . . . . . . . . . . . . . . . . . . . . 538

26.3 Digital Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539

26.4 Bitcoin and Cryptocurrencies . . . . . . . . . . . . . . . . . . . . . . . . . . . 539

26.5 The Append-Only Network, Identities, Timestamp, Bitcoin . . . . . . . . . . 542

26.6 The Bitcoin Blockchain and Merkle Roots . . . . . . . . . . . . . . . . . . . . 542

26.7 Mining, Proof-of-Work, Consensus . . . . . . . . . . . . . . . . . . . . . . . . 543

26.8 Thwarting Double Spending . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545

27 IoT, the Internet of Things 547

27.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548

27.2 Analog to Digital (A/D) Converters . . . . . . . . . . . . . . . . . . . . . . . 548

27.3 Programmable Logic Controller . . . . . . . . . . . . . . . . . . . . . . . . . . 549

27.4 Embedded Operating Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 549

27.5 Evolution, From SCADA to the Internet of Things . . . . . . . . . . . . . . . 550

27.6 Everything is Fun and Games until Somebody Releases a Stuxnet . . . . . . . 551

27.7 Securing the IoT, a Mammoth Task . . . . . . . . . . . . . . . . . . . . . . . 553

27.8 Privacy and Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553

28 In the Cloud 559

28.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 560

28.2 Distributed Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562

28.3 Cloud Storage — Availability and Copyset Replication . . . . . . . . . . . . 563

28.4 Homomorphic Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 569

28.5 Cybersecurity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571

28.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573

28.7 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573

29 Additional Problems and Solutions 575

29.1 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575

29.2 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 579

Appendices 589

A ASCII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 590

B Shannon’s Entropy Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 591

Glossary 593

Bibliography 628

Index 644

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.