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
