Cryptography, information theory, and error-correction : a handbook for the 21st century

Author(s)

Bibliographic Information

Cryptography, information theory, and error-correction : a handbook for the 21st century

Aiden A. Bruen, Mario A. Forcinito, James M. McQuillan

Wiley, 2021

2nd ed.

  • :hbk.

Available at  / 1 libraries

Search this Book/Journal

Note

Includes bibliographical references and index

Description and Table of Contents

Description

CRYPTOGRAPHY, INFORMATION THEORY, AND ERROR-CORRECTION 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 21ST 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.

Table of Contents

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, Erdos 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

by "Nielsen BookData"

Details

Page Top