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 xvii

Acknowledgments for the Second Edition xxiii

Book Website xxv

About the Authors xxvii

I Mainly Cryptography 1

1 Historical Introduction and the Life and Work of 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 15

2 Classical Ciphers and Their Cryptanalysis 21

2.1 Introduction 22

2.2 The Caesar Cipher 22

2.3 The Scytale Cipher 24

2.4 The Vigen`ere Cipher 25

2.5 Frequency Analysis 26

2.6 Breaking the Vigen`ere Cipher, Babbage–Kasiski 27

2.7 The Enigma Machine and Its Mathematics 33

2.8 Modern Enciphering Systems 37

2.9 Problems 37

2.10 Solutions 39

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

3.1 The Basic Idea of Cryptography 49

3.2 Public Key Cryptography and RSA on a Calculator 53

3.3 The General RSA Algorithm 56

3.4 Public Key Versus Symmetric Key 60

3.5 Attacks, Security, Catch-22 of Cryptography 62

3.6 Summary of Encryption 65

3.7 The Diffie–Hellman Key Exchange 66

3.8 Intruder-in-the-Middle Attack on the Diffie–Hellman (or Elliptic Curve) Key-Exchange 69

3.9 TLS (Transport Layer Security) 70

3.10 PGP and GPG 72

3.11 Problems 73

3.12 Solutions 76

4 The Fundamentals of Modern Cryptography 83

4.1 Encryption Revisited 83

4.2 Block Ciphers, Shannon’s Confusion and Diffusion 86

4.3 Perfect Secrecy, Stream Ciphers, One-Time Pad 87

4.4 Hash Functions 91

4.5 Message Integrity Using Symmetric Cryptography 93

4.6 General Public Key Cryptosystems 94

4.7 Digital Signatures 97

4.8 Modifying Encrypted Data and Homomorphic Encryption 99

4.9 Quantum Encryption Using Polarized Photons 99

4.10 Quantum Encryption Using Entanglement 102

4.11 Quantum Key Distribution is Not a Silver Bullet 103

4.12 Postquantum Cryptography 104

4.13 Key Management and Kerberos 104

4.14 Problems 106

4.15 Solutions 107

5 Modes of Operation for AES and Symmetric Algorithms 109

5.1 Modes of Operation 109

5.2 The Advanced Encryption Standard Code 111

5.3 Overview of AES 114

6 Elliptic Curve Cryptography (ECC) 125

6.1 Abelian Integrals, Fields, Groups 126

6.2 Curves, Cryptography 128

6.3 The Hasse Theorem, and an Example 129

6.4 More Examples 131

6.5 The Group Law on Elliptic Curves 131

6.6 Key Exchange with Elliptic Curves 134

6.7 Elliptic Curves mod n 134

6.8 Encoding Plain Text 135

6.9 Security of ECC 135

6.10 More Geometry of Cubic Curves 135

6.11 Cubic Curves and Arcs 136

6.12 Homogeneous Coordinates 137

6.13 Fermat’s Last Theorem, Elliptic Curves, Gerhard Frey 137

6.14 A Modification of the Standard Version of Elliptic Curve Cryptography 138

6.15 Problems 139

6.16 Solutions 140

7 General and Mathematical Attacks in Cryptography 143

7.1 Cryptanalysis 143

7.2 Soft Attacks 144

7.3 Brute-Force Attacks 145

7.4 Man-in-the-Middle Attacks 146

7.5 Relay Attacks, Car Key Fobs 148

7.6 Known Plain Text Attacks 150

7.7 Known Cipher Text Attacks 151

7.8 Chosen Plain Text Attacks 151

7.9 Chosen Cipher Text Attacks, Digital Signatures 151

7.10 Replay Attacks 152

7.11 Birthday Attacks 152

7.12 Birthday Attack on Digital Signatures 154

7.13 Birthday Attack on the Discrete Log Problem 154

7.14 Attacks on RSA 155

7.15 Attacks on RSA using Low-Exponents 156

7.16 Timing Attack 156

7.17 Differential Cryptanalysis 157

7.18 Attacks Utilizing Preprocessing 157

7.19 Cold Boot Attacks on Encryption Keys 159

7.20 Implementation Errors and Unforeseen States 159

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

7.22 Keep Up with the Latest Attacks (If You Can) 164

8 Practical Issues in Modern Cryptography and Communications 165

8.1 Introduction 165

8.2 Hot Issues 167

8.3 Authentication 167

8.4 User Anonymity 174

8.5 E-commerce 175

8.6 E-government 176

8.7 Key Lengths 178

8.8 Digital Rights 179

8.9 Wireless Networks 179

8.10 Communication Protocols 180

II Mainly Information Theory 183

9 Information Theory and its Applications 185

9.1 Axioms, Physics, Computation 186

9.2 Entropy 186

9.3 Information Gained, Cryptography 188

9.4 Practical Applications of Information Theory 190

9.5 Information Theory and Physics 192

9.6 Axiomatics of Information Theory 193

9.7 Number Bases, Erd¨os and the Hand of God 194

9.8 Weighing Problems and Your MBA 196

9.9 Shannon Bits, the Big Picture 200

10 Random Variables and Entropy 201

10.1 Random Variables 201

10.2 Mathematics of Entropy 205

10.3 Calculating Entropy 206

10.4 Conditional Probability 207

10.5 Bernoulli Trials 211

10.6 Typical Sequences 213

10.7 Law of Large Numbers 214

10.8 Joint and Conditional Entropy 215

10.9 Applications of Entropy 221

10.10 Calculation of Mutual Information 221

10.11 Mutual Information and Channels 223

10.12 The Entropy of X + Y 224

10.13 Subadditivity of the Function −x log x 225

10.14 Entropy and Cryptography 225

10.15 Problems 226

10.16 Solutions 227

11 Source Coding, Redundancy 233

11.1 Introduction, Source Extensions 234

11.2 Encodings, Kraft, McMillan 235

11.3 Block Coding, the Oracle, Yes–No Questions 241

11.4 Optimal Codes 242

11.5 Huffman Coding 243

11.6 Optimality of Huffman Coding 248

11.7 Data Compression, Redundancy 249

11.8 Problems 251

11.9 Solutions 252

12 Channels, Capacity, the Fundamental Theorem 255

12.1 Abstract Channels 256

12.2 More Specific Channels 257

12.3 New Channels from Old, Cascades 258

12.4 Input Probability, Channel Capacity 261

12.5 Capacity for General Binary Channels, Entropy 265

12.6 Hamming Distance 266

12.7 Improving Reliability of a Binary Symmetric Channel 268

12.8 Error Correction, Error Reduction, Good Redundancy 268

12.9 The Fundamental Theorem of Information Theory 272

12.10 Proving the Fundamental Theorem 279

12.11 Summary, the Big Picture 281

12.12 Postscript: The Capacity of the Binary Symmetric Channel 282

12.13 Problems 283

12.14 Solutions 284

13 Signals, Sampling, Coding Gain, Shannon’s Information Capacity Theorem 287

13.1 Continuous Signals, Shannon’s Sampling Theorem 288

13.2 The Band-Limited Capacity Theorem 290

13.3 The Coding Gain 296

14 Ergodic and Markov Sources, Language Entropy 299

14.1 General and Stationary Sources 300

14.2 Ergodic Sources 302

14.3 Markov Chains and Markov Sources 304

14.4 Irreducible Markov Sources, Adjoint Source 308

14.5 Cascades and the Data Processing Theorem 310

14.6 The Redundancy of Languages 311

14.7 Problems 313

14.8 Solutions 315

15 Perfect Secrecy: The New Paradigm 319

15.1 Symmetric Key Cryptosystems 320

15.2 Perfect Secrecy and Equiprobable Keys 321

15.3 Perfect Secrecy and Latin Squares 322

15.4 The Abstract Approach to Perfect Secrecy 324

15.5 Cryptography, Information Theory, Shannon 325

15.6 Unique Message from Ciphertext, Unicity 325

15.7 Problems 327

15.8 Solutions 329

16 Shift Registers (LFSR) and Stream Ciphers 333

16.1 Vernam Cipher, Psuedo-Random Key 334

16.2 Construction of Feedback Shift Registers 335

16.3 Periodicity 337

16.4 Maximal Periods, Pseudo-Random Sequences 340

16.5 Determining the Output from 2m Bits 341

16.6 The Tap Polynomial and the Period 345

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

16.8 Problems 350

16.9 Solutions 352

17 Compression and Applications 355

17.1 Introduction, Applications 356

17.2 The Memory Hierarchy of a Computer 358

17.3 Memory Compression 358

17.4 Lempel–Ziv Coding 361

17.5 The WKdm Algorithms 362

17.6 Main Memory – to Compress or Not to Compress 370

17.7 Problems 373

17.8 Solutions 374

III Mainly Error-Correction 379

18 Error-Correction, Hadamard, and Bruen–Ott 381

18.1 General Ideas of Error Correction 381

18.2 Error Detection, Error Correction 382

18.3 A Formula for Correction and Detection 383

18.4 Hadamard Matrices 384

18.5 Mariner, Hadamard, and Reed–Muller 387

18.6 Reed–Muller Codes 388

18.7 Block Designs 389

18.8 The Rank of Incidence Matrices 390

18.9 The Main Coding Theory Problem, Bounds 391

18.10 Update on the Reed–Muller Codes: The Proof of an Old Conjecture 396

18.11 Problems 398

18.12 Solutions 399

19 Finite Fields, Modular Arithmetic, Linear Algebra, and Number Theory 401

19.1 Modular Arithmetic 402

19.2 A Little Linear Algebra 405

19.3 Applications to RSA 407

19.4 Primitive Roots for Primes and Diffie–Hellman 409

19.5 The Extended Euclidean Algorithm 412

19.6 Proof that the RSA Algorithm Works 413

19.7 Constructing Finite Fields 413

19.8 Pollard’s p − 1 Factoring Algorithm 418

19.9 Latin Squares 419

19.10 Computational Complexity, Turing Machines, Quantum Computing 421

19.11 Problems 425

19.12 Solutions 426

20 Introduction to Linear Codes 429

20.1 Repetition Codes and Parity Checks 429

20.2 Details of Linear Codes 431

20.3 Parity Checks, the Syndrome, and Weights 435

20.4 Hamming Codes, an Inequality 438

20.5 Perfect Codes, Errors, and the BSC 439

20.6 Generalizations of Binary Hamming Codes 440

20.7 The Football Pools Problem, Extended Hamming Codes 441

20.8 Golay Codes 442

20.9 McEliece Cryptosystem 443

20.10 Historical Remarks 444

20.11 Problems 445

20.12 Solutions 448

21 Cyclic Linear Codes, Shift Registers, and CRC 453

21.1 Cyclic Linear Codes 454

21.2 Generators for Cyclic Codes 457

21.3 The Dual Code 460

21.4 Linear Feedback Shift Registers and Codes 462

21.5 Finding the Period of a LFSR 465

21.6 Cyclic Redundancy Check (CRC) 466

21.7 Problems 467

21.8 Solutions 469

22 Reed-Solomon and MDS Codes, and the Main Linear Coding Theory Problem (LCTP) 473

22.1 Cyclic Linear Codes and Vandermonde 474

22.2 The Singleton Bound for Linear Codes 476

22.3 Reed–Solomon Codes 479

22.4 Reed-Solomon Codes and the Fourier Transform Approach 479

22.5 Correcting Burst Errors, Interleaving 481

22.6 Decoding Reed-Solomon Codes, Ramanujan, and Berlekamp–Massey 482

22.7 An Algorithm for Decoding and an Example 484

22.8 Long MDS Codes and a Partial Solution of a 60 Year-Old Problem 487

22.9 Problems 490

22.10 Solutions 491

23 MDS Codes, Secret Sharing, and Invariant Theory 493

23.1 Some Facts Concerning MDS Codes 493

23.2 The Case k = 2, Bruck Nets 494

23.3 Upper Bounds on MDS Codes, Bruck–Ryser 497

23.4 MDS Codes and Secret Sharing Schemes 499

23.5 MacWilliams Identities, Invariant Theory 500

23.6 Codes, Planes, and Blocking Sets 501

23.7 Long Binary Linear Codes of Minimum Weight at Least 4 504

23.8 An Inverse Problem and a Basic Question in Linear Algebra 506

24 Key Reconciliation, Linear Codes, and New Algorithms 507

24.1 Symmetric and Public Key Cryptography 508

24.2 General Background 509

24.3 The Secret Key and the Reconciliation Algorithm 511

24.4 Equality of Remnant Keys: The Halting Criterion 514

24.5 Linear Codes: The Checking Hash Function 516

24.6 Convergence and Length of Keys 518

24.7 Main Results 521

24.8 Some Details on the Random Permutation 530

24.9 The Case Where Eve Has Nonzero Initial Information 530

24.10 Hash Functions Using Block Designs 531

24.11 Concluding Remarks 532

25 New Identities for the Shannon Function with Applications 535

25.1 Extensions of a Binary Symmetric Channel 536

25.2 A Basic Entropy Equality 539

25.3 The New Identities 541

25.4 Applications to Cryptography and a Shannon-Type Limit 544

25.5 Problems 545

25.6 Solutions 545

26 Blockchain and Bitcoin 549

26.1 Ledgers, Blockchains 551

26.2 Hash Functions, Cryptographic Hashes 552

26.3 Digital Signatures 553

26.4 Bitcoin and Cryptocurrencies 553

26.5 The Append-Only Network, Identities, Timestamp, Definition of a Bitcoin 556

26.6 The Bitcoin Blockchain and Merkle Roots 556

26.7 Mining, Proof-of-Work, Consensus 557

26.8 Thwarting Double Spending 559

27 IoT, The Internet of Things 561

27.1 Introduction 562

27.2 Analog to Digital (A/D) Converters 562

27.3 Programmable Logic Controller 563

27.4 Embedded Operating Systems 564

27.5 Evolution, From SCADA to the Internet of Things 564

27.6 Everything is Fun and Games until Somebody Releases a Stuxnet 565

27.7 Securing the IoT, a Mammoth Task 567

27.8 Privacy and Security 567

28 In the Cloud 573

28.1 Introduction 575

28.2 Distributed Systems 576

28.3 Cloud Storage – Availability and Copyset Replication 577

28.4 Homomorphic Encryption 584

28.5 Cybersecurity 585

28.6 Problems 587

28.7 Solutions 588

29 Review Problems and Solutions 589

29.1 Problems 589

29.2 Solutions 594

Appendix A 603

A.1 ASCII 603

Appendix B 605

B.1 Shannon’s Entropy Table 605

Glossary 607

References 615

Index 643