Оглавление
Aiden A. Bruen. Cryptography, Information Theory, and Error-Correction
Table of Contents
List of Tables
List of Illustrations
Guide
Pages
SERIES PAGE TITLE
Cryptography, Information Theory and Error-Correction. A Handbook for the 21st Century
Dedications
Preface to the Second Edition. WELCOME, New Co‐author
Intended Readership, Connections Between the Areas
Problems with Solutions
Style
Possible Courses
What's New
Hardcover and eBook
Acknowledgments for the Second Edition
Book Website
About the Authors
Chapter 1 Historical Introduction and the Life and Work of Claude E. Shannon
1.1 Historical Background
1.2 Brief Biography of Claude E. Shannon
1.3 Career
1.4 Personal – Professional
1.5 Scientific Legacy. Circuits
Cryptography
1.6 The Data Encryption Standard Code, DES, 1977–2005
1.7 Post‐Shannon Developments. Cybersecurity
Big data
Memory (RAM)
Central processing unit (CPU) and graphics processing unit (GPU)
Moore's law
Artificial intelligence (AI)
Smart phones
Streaming – video and audio
Social media
Cloud computing
Internet of Things (IoT)
Privacy concerns
Security and privacy
Cryptography
Postquantum cryptography
Blockchains
Notes
Chapter 2 Classical Ciphers and Their Cryptanalysis
2.1 Introduction
2.2 The Caesar Cipher
2.3 The Scytale Cipher
2.4 The Vigenère Cipher
2.5 Frequency Analysis
2.6 Breaking the Vigenère Cipher, Babbage–Kasiski
The Babbage–Kasiski method
The method of coincidences
Remark
Finding the keyword
Remark
2.7 The Enigma Machine and Its Mathematics
2.8 Modern Enciphering Systems
2.9 Problems
2.10 Solutions
Chapter 3 RSA, Key Searches, TLS, and Encrypting Email
3.1 The Basic Idea of Cryptography
3.2 Public Key Cryptography and RSA on a Calculator
Question
Remark 3.1
3.3 The General RSA Algorithm
The RSA Algorithm
Remark 3.2
Remark 3.3
Another example of the RSA algorithm
Remark 3.4
Remark 3.5
3.4 Public Key Versus Symmetric Key
3.5 Attacks, Security, Catch‐22 of Cryptography
Theorem 3.6
3.6 Summary of Encryption
3.7 The Diffie–Hellman Key Exchange
An example with a small prime
Diffie–Hellman problem
Discrete log problem
El Gamal Cryptosystem
The El Gamal digital signature scheme
3.8 Intruder‐in‐the‐Middle Attack on the Diffie–Hellman (or Elliptic Curve) Key‐Exchange
3.9 TLS (Transport Layer Security)
3.10 PGP and GPG
Encrypting/decrypting
Signing/authenticating
3.11 Problems
3.12 Solutions
Notes
Chapter 4 The Fundamentals of Modern Cryptography
4.1 Encryption Revisited
4.2 Block Ciphers, Shannon's Confusion and Diffusion
Confusion
Diffusion
4.3 Perfect Secrecy, Stream Ciphers, One‐Time Pad
4.4 Hash Functions
4.5 Message Integrity Using Symmetric Cryptography
4.6 General Public Key Cryptosystems
4.7 Digital Signatures
Digital signatures using symmetric encryption
4.8 Modifying Encrypted Data and Homomorphic Encryption
4.9 Quantum Encryption Using Polarized Photons
Polarized light and photons
4.10 Quantum Encryption Using Entanglement
4.11 Quantum Key Distribution is Not a Silver Bullet
Addendum to Section 4.11
4.12 Postquantum Cryptography
4.13 Key Management and Kerberos
4.14 Problems
4.15 Solutions
Chapter 5 Modes of Operation for AES and Symmetric Algorithms
5.1 Modes of Operation
5.2 The Advanced Encryption Standard Code
Fields
The field of 256 elements
5.3 Overview of AES. Using the S‐box for the code
Algebraic interpretation of the S‐box
Remark 5.5
Representing the input data
The ByteSub transformation
The ShiftRow transformation
The MixColumn transformation
Creating the W‐matrix which contains the keys for the code
RoundKey addition
Overview of the Rijndael encryption
Decryption of the AES Code
Overview of decryption of AES
Concluding comments
Remark
Chapter 6 Elliptic Curve Cryptography (ECC)
6.1 Abelian Integrals, Fields, Groups
Fields
Groups
6.2 Curves, Cryptography
6.3 The Hasse Theorem, and an Example
6.4 More Examples
6.5 The Group Law on Elliptic Curves
6.6 Key Exchange with Elliptic Curves
6.7 Elliptic Curves mod n
6.8 Encoding Plain Text
6.9 Security of ECC
6.10 More Geometry of Cubic Curves
6.11 Cubic Curves and Arcs
6.12 Homogeneous Coordinates
6.13 Fermat's Last Theorem, Elliptic Curves, Gerhard Frey
6.14 A Modification of the Standard Version of Elliptic Curve Cryptography
6.15 Problems
6.16 Solutions
Chapter 7 General and Mathematical Attacks in Cryptography
7.1 Cryptanalysis
7.2 Soft Attacks
7.3 Brute‐Force Attacks
7.4 Man‐in‐the‐Middle Attacks
7.5 Relay Attacks, Car Key Fobs
7.6 Known Plain Text Attacks
7.7 Known Cipher Text Attacks
7.8 Chosen Plain Text Attacks
7.9 Chosen Cipher Text Attacks, Digital Signatures
7.10 Replay Attacks
7.11 Birthday Attacks
7.12 Birthday Attack on Digital Signatures
7.13 Birthday Attack on the Discrete Log Problem
7.14 Attacks on RSA
7.15 Attacks on RSA using Low‐Exponents
7.16 Timing Attack
7.17 Differential Cryptanalysis
7.18 Attacks Utilizing Preprocessing
7.19 Cold Boot Attacks on Encryption Keys
7.20 Implementation Errors and Unforeseen States
7.21 Tracking. Bluetooth, WiFi, and Your Smart Phone
7.22 Keep Up with the Latest Attacks (If You Can)
Notes
Chapter 8 Practical Issues in Modern Cryptography and Communications
8.1 Introduction
8.2 Hot Issues
8.3 Authentication
Biometric authentication
Two‐factor authentication (2FA) and multifactor authentication (MFA)
8.4 User Anonymity
8.5 E‐commerce
8.6 E‐government
8.7 Key Lengths
8.8 Digital Rights
8.9 Wireless Networks
8.10 Communication Protocols
Notes
Chapter 9 Information Theory and its Applications
9.1 Axioms, Physics, Computation
9.2 Entropy
9.3 Information Gained, Cryptography
Definitions
Examples
9.4 Practical Applications of Information Theory. Data compression
Channel capacity
Cryptography
9.5 Information Theory and Physics
9.6 Axiomatics of Information Theory
9.7 Number Bases, Erdös and the Hand of God
Property
Erdös problem
9.8 Weighing Problems and Your MBA
Problem
General inequality
Additional weighing problems
9.9 Shannon Bits, the Big Picture
Chapter 10 Random Variables and Entropy
10.1 Random Variables
10.2 Mathematics of Entropy
Caution about notation
10.3 Calculating Entropy
Calculating tip
10.4 Conditional Probability
10.5 Bernoulli Trials
10.6 Typical Sequences
Theorem 10.11
Explanation of typical sequences
10.7 Law of Large Numbers
10.8 Joint and Conditional Entropy
Proof
Theorem 10.17
Proof
Proof
Comments
10.9 Applications of Entropy
10.10 Calculation of Mutual Information
10.11 Mutual Information and Channels
10.12 The Entropy of X + Y
Theorem 10.21
10.13 Subadditivity of the Function –x log x
10.14 Entropy and Cryptography
10.15 Problems
10.16 Solutions
Chapter 11 Source Coding, Redundancy
11.1 Introduction, Source Extensions
11.2 Encodings, Kraft, McMillan
Noiseless coding theorem
11.3 Block Coding, the Oracle, Yes–No Questions
11.4 Optimal Codes
11.5 Huffman Coding
Calculating the average length
11.6 Optimality of Huffman Coding. Proof of the optimality of Huffman coding
11.7 Data Compression, Redundancy
Arithmetic coding
11.8 Problems
11.9 Solutions
Chapter 12 Channels, Capacity, the Fundamental Theorem
12.1 Abstract Channels
12.2 More Specific Channels
12.3 New Channels from Old, Cascades
12.4 Input Probability, Channel Capacity
Channel capacity for binary symmetric channels
Remarks
12.5 Capacity for General Binary Channels, Entropy
Algebraic relation between input and output
12.6 Hamming Distance
12.7 Improving Reliability of a Binary Symmetric Channel
12.8 Error Correction, Error Reduction, Good Redundancy
Probability of error
12.9 The Fundamental Theorem of Information Theory
The fundamental theorem of information theory for binary symmetric channels
Approach 1
Fundamental principle. The capacity of a channel is the log of the maximum number of distinguishable inputs
Approach 2
Remark
Remark
Approach 3
Stirling's expansion
Approach 4
Remark
Approach 5
Converse
12.10 Proving the Fundamental Theorem
Proof of the fundamental theorem (for the binary symmetric channel)
12.11 Summary, the Big Picture
12.12 Postscript: The Capacity of the Binary Symmetric Channel
Remark
12.13 Problems
12.14 Solutions
Chapter 13 Signals, Sampling, Coding Gain, Shannon's Information Capacity Theorem
13.1 Continuous Signals, Shannon's Sampling Theorem
Theorem 13.1 (The sampling theorem)
13.2 The Band‐Limited Capacity Theorem
Information capacity theorem
Capacity Formula 2
Capacity Formula 3
13.3 The Coding Gain
Chapter 14 Ergodic and Markov Sources, Language Entropy
14.1 General and Stationary Sources
Proof
Proof
14.2 Ergodic Sources
Discussion
14.3 Markov Chains and Markov Sources
Question
Significance of
Caution
14.4 Irreducible Markov Sources, Adjoint Source
14.5 Cascades and the Data Processing Theorem
14.6 The Redundancy of Languages
14.7 Problems
14.8 Solutions
Chapter 15 Perfect Secrecy: The New Paradigm
15.1 Symmetric Key Cryptosystems
Example illustrating the one‐time pad
15.2 Perfect Secrecy and Equiprobable Keys
15.3 Perfect Secrecy and Latin Squares
Example
Remark
15.4 The Abstract Approach to Perfect Secrecy
15.5 Cryptography, Information Theory, Shannon
15.6 Unique Message from Ciphertext, Unicity
15.7 Problems
15.8 Solutions
Chapter 16 Shift Registers (LFSR) and Stream Ciphers
16.1 Vernam Cipher, Psuedo‐Random Key
16.2 Construction of Feedback Shift Registers
16.3 Periodicity
16.4 Maximal Periods, Pseudo‐Random Sequences
16.5 Determining the Output from 2m Bits
16.6 The Tap Polynomial and the Period
16.7 Short Linear Feedback Shift Registers and the Berlekamp‐Massey Algorithm
Remarks
16.8 Problems
16.9 Solutions
Chapter 17 Compression and Applications
17.1 Introduction, Applications
17.2 The Memory Hierarchy of a Computer
17.3 Memory Compression
Note:
Question:
17.4 Lempel–Ziv Coding
Procedure
17.5 The WKdm Algorithms
Notation 17.1
Definition 17.2
Definition 17.3
Algorithm 17.4 (WKdm compression)
Algorithm 17.7 (WKdm decompression)
17.6 Main Memory – to Compress or Not to Compress
Question 17.9
Question 17.10
Question 17.11
Definition 17.12
Algorithm 17.13
Definition 17.14
Algorithm 17.15
17.7 Problems
17.8 Solutions
Chapter 18 Error‐Correction, Hadamard, and Bruen–Ott. 18.1 General Ideas of Error Correction
18.2 Error Detection, Error Correction
18.3 A Formula for Correction and Detection
Proof
18.4 Hadamard Matrices
Example 18.3
Example 18.6
Example 18.7
Example 18.8
18.5 Mariner, Hadamard, and Reed–Muller
18.6 Reed–Muller Codes
Proof
18.7 Block Designs
Example 18.13
18.8 The Rank of Incidence Matrices
18.9 The Main Coding Theory Problem, Bounds
The main coding theory problem
Proof
Proof
Proof
Proof
Proof
Proof
Proof
18.10 Update on the Reed–Muller Codes: The Proof of an Old Conjecture
Definition 18.23
18.11 Problems
18.12 Solutions
Chapter 19 Finite Fields, Modular Arithmetic, Linear Algebra, and Number Theory. Goals, Discussion
19.1 Modular Arithmetic
19.2 A Little Linear Algebra
The Vandermonde technique
Subspaces
19.3 Applications to RSA
Euler's theorem
Fermat's little theorem
Justification of Equations 19.9, (19.10)
Question 1
19.4 Primitive Roots for Primes and Diffie–Hellman
Solving congruence equations
Chinese remainder theorem
Question 2
Primes and primality testing
Calculating inverses and the Euclidean algorithm
19.5 The Extended Euclidean Algorithm
19.6 Proof that the RSA Algorithm Works
19.7 Constructing Finite Fields
Polynomials
The general construction procedure
An example: constructing
A useful polynomial for coding
Another example: constructing
19.8 Pollard's p-1 Factoring Algorithm
An example
19.9 Latin Squares
Counterexample 19.3
Theorem 19.4
19.10 Computational Complexity, Turing Machines, Quantum Computing
Big O notation
Input
Turing machines
19.11 Problems
19.12 Solutions
Note
Chapter 20 Introduction to Linear Codes
20.1 Repetition Codes and Parity Checks
20.2 Details of Linear Codes
Properties of the encoding
How linear encoding works
Dimension formula
Double dual formula
Algebraic representation of
Remark
20.3 Parity Checks, the Syndrome, and Weights
Theorem 20.11
Syndrome decoding algorithm
20.4 Hamming Codes, an Inequality
20.5 Perfect Codes, Errors, and the BSC
20.6 Generalizations of Binary Hamming Codes
20.7 The Football Pools Problem, Extended Hamming Codes
Extended Hamming codes
20.8 Golay Codes
20.9 McEliece Cryptosystem
20.10 Historical Remarks. Soccer pools
20.11 Problems
20.12 Solutions
Chapter 21 Cyclic Linear Codes, Shift Registers, and CRC
21.1 Cyclic Linear Codes
Example 21.1
Example 21.2
Theorem 21.3
Proof
Example 21.4
Example 21.5
Fundamental Principle 21.6
Notation
Remark 21.7
Example 21.8
Example 21.9
21.2 Generators for Cyclic Codes
Question
Example 21.10
Theorem 21.11
Proof
Theorem 21.12
Proof
Proof of Part 4 of Theorem 21.11
Comment 21.13
21.3 The Dual Code
Example 21.14
Theorem 21.15
Proof
Explanation
21.4 Linear Feedback Shift Registers and Codes
Theorem 21.16
Proof
Proof of Theorem 21.16
Example 21.18
Theorem 21.19
Proof
21.5 Finding the Period of a LFSR
21.6 Cyclic Redundancy Check (CRC)
Example 21.20
Example 21.21
21.7 Problems
21.8 Solutions
Chapter 22 Reed‐Solomon and MDS Codes, and the Main Linear Coding Theory Problem (LCTP)
22.1 Cyclic Linear Codes and Vandermonde
22.2 The Singleton Bound for Linear Codes
Remark
Insight
22.3 Reed–Solomon Codes
22.4 Reed‐Solomon Codes and the Fourier Transform Approach
Remark
Remarks
Importance of Reed–Solomon codes
22.5 Correcting Burst Errors, Interleaving
22.6 Decoding Reed‐Solomon Codes, Ramanujan, and Berlekamp–Massey
22.7 An Algorithm for Decoding and an Example
Reed–Solomon Decoding Algorithm
A Worked Example
22.8 Long MDS Codes and a Partial Solution of a 60 Year‐Old Problem
Question
Conjecture
Conjecture
22.9 Problems
22.10 Solutions
Chapter 23 MDS Codes, Secret Sharing, and Invariant Theory
23.1 Some Facts Concerning MDS Codes
Explanation of Property P
23.2 The Case k = 2, Bruck Nets
Example 23.1
Example 23.2
23.3 Upper Bounds on MDS Codes, Bruck–Ryser
23.4 MDS Codes and Secret Sharing Schemes
23.5 MacWilliams Identities, Invariant Theory
23.6 Codes, Planes, and Blocking Sets
Example
Theorem 23.4
Theorem 23.5
Theorem 23.6
Proof
Question
Theorem 23.7
23.7 Long Binary Linear Codes of Minimum Weight at Least 4
23.8 An Inverse Problem and a Basic Question in Linear Algebra
Chapter 24 Key Reconciliation, Linear Codes, and New Algorithms
24.1 Symmetric and Public Key Cryptography
24.2 General Background
24.3 The Secret Key and the Reconciliation Algorithm
Blocks of size 2
Blocks of size 3
24.4 Equality of Remnant Keys: The Halting Criterion
24.5 Linear Codes: The Checking Hash Function
Security
24.6 Convergence and Length of Keys
24.7 Main Results
24.8 Some Details on the Random Permutation
24.9 The Case Where Eve Has Nonzero Initial Information
24.10 Hash Functions Using Block Designs
24.11 Concluding Remarks
Note
Chapter 25 New Identities for the Shannon Function with Applications
25.1 Extensions of a Binary Symmetric Channel
25.2 A Basic Entropy Equality
Extending Theorem 10.17
From Random Variables to Random Vectors
25.3 The New Identities
Blocks of Size 3
25.4 Applications to Cryptography and a Shannon‐Type Limit
25.5 Problems
25.6 Solutions
Addendum
Chapter 26 Blockchain and Bitcoin
26.1 Ledgers, Blockchains
26.2 Hash Functions, Cryptographic Hashes
26.3 Digital Signatures
26.4 Bitcoin and Cryptocurrencies
26.5 The Append‐Only Network, Identities, Timestamp, Definition of a Bitcoin
26.6 The Bitcoin Blockchain and Merkle Roots
26.7 Mining, Proof‐of‐Work, Consensus
Cryptojacking
26.8 Thwarting Double Spending
Chapter 27 IoT, The Internet of Things
27.1 Introduction
27.2 Analog to Digital (A/D) Converters
27.3 Programmable Logic Controller
27.4 Embedded Operating Systems
27.5 Evolution, From SCADA to the Internet of Things
27.6 Everything is Fun and Games until Somebody Releases a Stuxnet
27.7 Securing the IoT, a Mammoth Task
27.8 Privacy and Security
Privacy concerns
Security concerns
Short Range Networks
Notes
Chapter 28 In the Cloud
28.1 Introduction
28.2 Distributed Systems
28.3 Cloud Storage – Availability and Copyset Replication
Algorithm 28.4 (Simple random replication)
Definition 28.5
28.4 Homomorphic Encryption
Applications
28.5 Cybersecurity
28.6 Problems
28.7 Solutions
Chapter 29 Review Problems and Solutions. 29.1 Problems. Latin Squares
Linear Algebra and Codes
Logs, Entropy
Finite Fields
Modular Arithmetic
29.2 Solutions. Latin Squares
Linear Algebra and Codes
Logs, Entropy
Finite Fields
Modular Arithmetic
Appendix A. A.1 ASCII
Appendix B. B.1 Shannon's Entropy Table
Glossary
A
B
C
D
E
F
G
H
K
L
M
N
O
P
Q
R
S
T
V
W
X
References
Index
WILEY END USER LICENSE AGREEMENT
