Cryptography, Information Theory, and Error-Correction: A Handbook for the 21st Century (Hardcover, 2)

· 제목 : Cryptography, Information Theory, and Error-Correction: A Handbook for the 21st Century (Hardcover, 2) 
· 분류 : 외국도서 > 컴퓨터 > 보안 > 암호
· ISBN : 9781119582427
· 쪽수 : 688쪽
· 출판일 : 2021-07-21

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