Introduction to Cryptography with Coding Theory

Introduction to Cryptography with Coding Theory
Contents
Preface
Chapter 1 Overview of Cryptography and Its Applications
	1.1 Secure Communications
		1.1.1 Possible Attacks
		1.1.2 Symmetric and Public Key Algorithms
		1.1.3 Key Length
	1.2 Cryptographic Applications
Chapter 2 Classical Cryptosystems
	2.1 Shift Ciphers
	2.2 Affine Ciphers
	2.3 The Vigenère CipherThe Vigenère Cipher
		2.3.1 Finding the Key Length
		2.3.2 Finding the Key: First Method
		2.3.3 Finding the Key: Second Method
	2.4 Substitution Ciphers
	2.5 Sherlock Holmes
	2.6 The Playfair and ADFGX Ciphers
	2.7 Enigma
	2.8 Exercises
	2.9 Computer Problems
Chapter 3 Basic Number Theory
	3.1 Basic Notions
		3.1.1 Divisibility
		3.1.2 Prime Numbers
		3.1.3 Greatest Common Divisor
	3.2 The Extended Euclidean Algorithm
	3.3 Congruences
		3.3.1 Division
		3.3.2 Working with Fractions
	3.4 The Chinese Remainder Theorem
	3.5 Modular Exponentiation
	3.6 Fermat’s Theorem and Euler’s TheoremFermat’s Theorem and Euler’s Theorem
		3.6.1 Three-Pass Protocol
	3.7 Primitive Roots
	3.8 Inverting Matrices Mod n
	3.9 Square Roots Mod n
	3.10 Legendre and Jacobi Symbols
	3.11 Finite Fields
		3.11.1 Division
		3.11.2 GF(28)
		3.11.3 LFSR Sequences
	3.12 Continued Fractions
	3.13 Exercises
	3.14 Computer Problems
Chapter 4 The One-Time Pad
	4.1 Binary Numbers and ASCII
	4.2 One-Time Pads
	4.3 Multiple Use of a One-Time Pad
	4.4 Perfect Secrecy of the One-Time Pad
	4.5 Indistinguishability and Security
	4.6 Exercises
Chapter 5 Stream Ciphers
	5.1 Pseudorandom Bit Generation
	5.2 Linear Feedback Shift Register Sequences
	5.3 RC4
	5.4 Exercises
	5.5 Computer Problems
Chapter 6 Block Ciphers
	6.1 Block Ciphers
	6.2 Hill Ciphers
	6.3 Modes of Operation
		6.3.1 Electronic Codebook (ECB)
		6.3.2 Cipher Block Chaining (CBC)
		6.3.3 Cipher Feedback (CFB)
		6.3.4 Output Feedback (OFB)
		6.3.5 Counter (CTR)
	6.4 Multiple Encryption
	6.5 Meet-in-the-Middle Attacks
	6.6 Exercises
	6.7 Computer Problems
Chapter 7 The Data Encryption Standard
	7.1 Introduction
	7.2 A Simplified DES-Type Algorithm
	7.3 Differential Cryptanalysis
		7.3.1 Differential Cryptanalysis for Three Rounds
		7.3.2 Differential Cryptanalysis for Four Rounds
	7.4 DES
		7.4.1 DES Is Not a Group
	7.5 Breaking DES
	7.6 Password Security
	7.7 Exercises
	7.8 Computer Problems
Chapter 8 The Advanced Encryption Standard: Rijndael
	8.1 The Basic Algorithm
	8.2 The Layers
		8.2.1 The SubBytes Transformation
		8.2.2 The ShiftRows Transformation
		8.2.3 The MixColumns Transformation
		8.2.4 The RoundKey Addition
		8.2.5 The Key Schedule
		8.2.6 The Construction of the S-Box
	8.3 Decryption
	8.4 Design Considerations
	8.5 Exercises
Chapter 9 The RSA Algorithm
	9.1 The RSA Algorithm
	9.2 Attacks on RSA
		9.2.1 Low Exponent Attacks
		9.2.2 Short Plaintext
		9.2.3 Timing Attacks
	9.3 Primality Testing
	9.4 Factoring
		9.4.1 x2≡y2
		9.4.2 Using ar≡1
	9.5 The RSA Challenge
	9.6 An Application to Treaty Verification
	9.7 The Public Key Concept
	9.8 Exercises
	9.9 Computer Problems
Chapter 10 Discrete Logarithms
	10.1 Discrete Logarithms
	10.2 Computing Discrete Logs
		10.2.1 The Pohlig-Hellman Algorithm
		10.2.2 Baby Step, Giant Step
		10.2.3 The Index Calculus
		10.2.4 Computing Discrete Logs Mod 4
	10.3 Bit Commitment
	10.4 Diffie-Hellman Key Exchange
	10.5 The ElGamal Public Key Cryptosystem
		10.5.1 Security of ElGamal Ciphertexts
	10.6 Exercises
	10.7 Computer Problems
Chapter 11 Hash Functions
	11.1 Hash Functions
	11.2 Simple Hash Examples
	11.3 The Merkle-Damgård ConstructionThe Merkle-Damgård Construction
	11.4 SHA-2
		Padding and Preprocessing
		The Algorithm
	11.5 SHA-3/Keccak
	11.6 Exercises
Chapter 12 Hash Functions: Attacks and Applications
	12.1 Birthday Attacks
		12.1.1 A Birthday Attack on Discrete Logarithms
	12.2 Multicollisions
	12.3 The Random Oracle Model
	12.4 Using Hash Functions to Encrypt
	12.5 Message Authentication Codes
		12.5.1 HMAC
		12.5.2 CBC-MAC
	12.6 Password Protocols
		12.6.1 The Secure Remote Password protocol
		12.6.2 Lamport’s protocolLamport’s protocol
	12.7 Blockchains
	12.8 Exercises
	12.9 Computer Problems
Chapter 13 Digital Signatures
	13.1 RSA Signatures
	13.2 The ElGamal Signature Scheme
	13.3 Hashing and Signing
	13.4 Birthday Attacks on Signatures
	13.5 The Digital Signature Algorithm
	13.6 Exercises
	13.7 Computer Problems
Chapter 14 What Can Go Wrong
	14.1 An Enigma “Feature”An Enigma “Feature”
	14.2 Choosing Primes for RSA
	14.3 WEP
		14.3.1 CRC-32
	14.4 Exercises
Chapter 15 Security Protocols
	15.1 Intruders-in-the-Middle and Impostors
		15.1.1 Intruder-in-the-Middle Attacks
	15.2 Key Distribution
		15.2.1 Key Pre-distribution
		15.2.2 Authenticated Key Distribution
	15.3 Kerberos
	15.4 Public Key Infrastructures (PKI)
	15.5 X.509 Certificates
	15.6 Pretty Good Privacy
	15.7 SSL and TLS
	15.8 Secure Electronic Transaction
	15.9 Exercises
Chapter 16 Digital Cash
	16.1 Setting the Stage for Digital Economies
	16.2 A Digital Cash System
		16.2.1 Participants
		16.2.2 Initialization
		16.2.3 The Bank
		16.2.4 The Spender
		16.2.5 The Merchant
		16.2.6 Creating a Coin
		16.2.7 Spending the Coin
		16.2.8 The Merchant Deposits the Coin in the Bank
		16.2.9 Fraud Control
		16.2.10 Anonymity
	16.3 Bitcoin Overview
		16.3.1 Some More Details
	16.4 Cryptocurrencies
	16.5 Exercises
Chapter 17 Secret Sharing Schemes
	17.1 Secret Splitting
	17.2 Threshold Schemes
	17.3 Exercises
	17.4 Computer Problems
Chapter 18 Games
	18.1 Flipping Coins over the Telephone
	18.2 Poker over the Telephone
		18.2.1 How to Cheat
	18.3 Exercises
Chapter 19 Zero-Knowledge Techniques
	19.1 The Basic Setup
	19.2 The Feige-Fiat-Shamir Identification Scheme
	19.3 Exercises
Chapter 20 Information Theory
	20.1 Probability Review
	20.2 Entropy
	20.3 Huffman Codes
	20.4 Perfect Secrecy
	20.5 The Entropy of English
		20.5.1 Unicity Distance
	20.6 Exercises
Chapter 21 Elliptic Curves
	21.1 The Addition Law
	21.2 Elliptic Curves Mod p
		21.2.1 Number of Points Mod p
		21.2.2 Discrete Logarithms on Elliptic Curves
		21.2.3 Representing Plaintext
	21.3 Factoring with Elliptic Curves
		21.3.1 Singular Curves
	21.4 Elliptic Curves in Characteristic 2
	21.5 Elliptic Curve Cryptosystems
		21.5.1 An Elliptic Curve ElGamal Cryptosystem
		21.5.2 Elliptic Curve Diffie-Hellman Key Exchange
		21.5.3 ElGamal Digital Signatures
	21.6 Exercises
	21.7 Computer Problems
Chapter 22 Pairing-Based Cryptography
	22.1 Bilinear Pairings
	22.2 The MOV Attack
	22.3 Tripartite Diffie-Hellman
	22.4 Identity-Based Encryption
	22.5 Signatures
		22.5.1 BLS Signatures
		22.5.2 A Variation
		22.5.3 Identity-Based Signatures
	22.6 Keyword Search
	22.7 Exercises
Chapter 23 Lattice Methods
	23.1 Lattices
	23.2 Lattice Reduction
		23.2.1 Two-Dimensional Lattices
		23.2.2 The LLL algorithm
	23.3 An Attack on RSA
	23.4 NTRU
		23.4.1 An Attack on NTRU
	23.5 Another Lattice-Based Cryptosystem
	23.6 Post-Quantum Cryptography?
	23.7 Exercises
Chapter 24 Error Correcting Codes
	24.1 Introduction
	24.2 Error Correcting Codes
	24.3 Bounds on General Codes
		24.3.1 Upper Bounds
		24.3.2 Lower Bounds
	24.4 Linear Codes
		24.4.1 Dual Codes
	24.5 Hamming Codes
	24.6 Golay Codes
		Decoding G24
	24.7 Cyclic Codes
	24.8 BCH Codes
		24.8.1 Decoding BCH Codes
	24.9 Reed-Solomon Codes
	24.10 The McEliece Cryptosystem
	24.11 Other Topics
	24.12 Exercises
	24.13 Computer Problems
Chapter 25 Quantum Techniques in Cryptography
	25.1 A Quantum Experiment
	25.2 Quantum Key Distribution
	25.3 Shor’s AlgorithmShor’s Algorithm
		25.3.1 Factoring
		25.3.2 The Discrete Fourier Transform
		25.3.3 Shor’s AlgorithmShor’s Algorithm
		25.3.4 Final Words
	25.4 Exercises
Appendix A Mathematica® Examples
	A.1 Getting Started with Mathematica
	A.2 Some Commands
	A.3 Examples for Chapter 2
	A.4 Examples for Chapter 3
	A.5 Examples for Chapter 5
	A.6 Examples for Chapter 6
	A.7 Examples for Chapter 9
	A.8 Examples for Chapter 10
	A.9 Examples for Chapter 12
	A.10 Examples for Chapter 17
	A.11 Examples for Chapter 18
	A.12 Examples for Chapter 21
Appendix B Maple® Examples
	B.1 Getting Started with Maple
	B.2 Some Commands
	B.3 Examples for Chapter 2
	B.4 Examples for Chapter 3
	B.5 Examples for Chapter 5
	B.6 Examples for Chapter 6
	B.7 Examples for Chapter 9
	B.8 Examples for Chapter 10
	B.9 Examples for Chapter 12
	B.10 Examples for Chapter 17
	B.11 Examples for Chapter 18
	B.12 Examples for Chapter 21
Appendix C MATLAB® Examples
	C.1 Getting Started with MATLAB
	C.2 Examples for Chapter 2
	C.3 Examples for Chapter 3
	C.4 Examples for Chapter 5
	C.5 Examples for Chapter 6
	C.6 Examples for Chapter 9
	C.7 Examples for Chapter 10
	C.8 Examples for Chapter 12
	C.9 Examples for Chapter 17
	C.10 Examples for Chapter 18
	C.11 Examples for Chapter 21
Appendix D Sage Examples
	D.1 Computations for Chapter 2
	D.2 Computations for Chapter 3
	D.3 Computations for Chapter 5
	D.4 Computations for Chapter 6
	D.5 Computations for Chapter 9
	D.6 Computations for Chapter 10
	D.7 Computations for Chapter 12
	D.8 Computations for Chapter 17
	D.9 Computations for Chapter 18
	D.10 Computations for Chapter 21
Appendix E Answers and Hints for Selected Odd-Numbered Exercises
Appendix F Suggestions for Further Reading
Bibliography
Index