Cryptography: Theory and Practice

Cover
Half Title
Title Page
Copyright Page
Dedication
Table of Contents
1: Introduction to Cryptography
	1.1 Cryptosystems and Basic Cryptographic Tools
		1.1.1 Secret-key Cryptosystems
		1.1.2 Public-key Cryptosystems
		1.1.3 Block and Stream Ciphers
		1.1.4 Hybrid Cryptography
	1.2 Message Integrity
		1.2.1 Message Authentication Codes
		1.2.2 Signature Schemes
		1.2.3 Nonrepudiation
		1.2.4 Certificates
		1.2.5 Hash Functions
	1.3 Cryptographic Protocols
	1.4 Security
	1.5 Notes and References
2: Classical Cryptography
	2.1 Introduction: Some Simple Cryptosystems
		2.1.1 The Shift Cipher
		2.1.2 The Substitution Cipher
		2.1.3 The Affine Cipher
		2.1.4 The Vigenère Cipher
		2.1.5 The Hill Cipher
		2.1.6 The Permutation Cipher
		2.1.7 Stream Ciphers
	2.2 Cryptanalysis
		2.2.1 Cryptanalysis of the Affine Cipher
		2.2.2 Cryptanalysis of the Substitution Cipher
		2.2.3 Cryptanalysis of the Vigenère Cipher
		2.2.4 Cryptanalysis of the Hill Cipher
		2.2.5 Cryptanalysis of the LFSR Stream Cipher
	2.3 Notes and References
	Exercises
3: Shannon’s Theory, Perfect Secrecy, and the One-Time Pad
	3.1 Introduction
	3.2 Elementary Probability Theory
	3.3 Perfect Secrecy
	3.4 Entropy
		3.4.1 Properties of Entropy
	3.5 Spurious Keys and Unicity Distance
	3.6 Notes and References
	Exercises
4: Block Ciphers and Stream Ciphers
	4.1 Introduction
	4.2 Substitution-Permutation Networks
	4.3 Linear Cryptanalysis
		4.3.1 The Piling-up Lemma
		4.3.2 Linear Approximations of S-boxes
		4.3.3 A Linear Attack on an SPN
	4.4 Differential Cryptanalysis
	4.5 The Data Encryption Standard
		4.5.1 Description of DES
		4.5.2 Analysis of DES
	4.6 The Advanced Encryption Standard
		4.6.1 Description of AES
		4.6.2 Analysis of AES
	4.7 Modes of Operation
		4.7.1 Padding Oracle Attack on CBC Mode
	4.8 Stream Ciphers
		4.8.1 Correlation Attack on a Combination Generator
		4.8.2 Algebraic Attack on a Filter Generator
		4.8.3 Trivium
	4.9 Notes and References
	Exercises
5: Hash Functions and Message Authentication
	5.1 Hash Functions and Data Integrity
	5.2 Security of Hash Functions
		5.2.1 The Random Oracle Model
		5.2.2 Algorithms in the Random Oracle Model
		5.2.3 Comparison of Security Criteria
	5.3 Iterated Hash Functions
		5.3.1 The Merkle-Damgård Construction
		5.3.2 Some Examples of Iterated Hash Functions
	5.4 The Sponge Construction
		5.4.1 SHA-3
	5.5 Message Authentication Codes
		5.5.1 Nested MACs and HMAC
		5.5.2 CBC-MAC
		5.5.3 Authenticated Encryption
	5.6 Unconditionally Secure MACs
		5.6.1 Strongly Universal Hash Families
		5.6.2 Optimality of Deception Probabilities
	5.7 Notes and References
	Exercises
6: The RSA Cryptosystem and Factoring Integers
	6.1 Introduction to Public-key Cryptography
	6.2 More Number Theory
		6.2.1 The Euclidean Algorithm
		6.2.2 The Chinese Remainder Theorem
		6.2.3 Other Useful Facts
	6.3 The RSA Cryptosystem
		6.3.1 Implementing RSA
	6.4 Primality Testing
		6.4.1 Legendre and Jacobi Symbols
		6.4.2 The Solovay-Strassen Algorithm
		6.4.3 The Miller-Rabin Algorithm
	6.5 Square Roots Modulo n
	6.6 Factoring Algorithms
		6.6.1 The Pollard p  ̶  1 Algorithm
		6.6.2 The Pollard Rho Algorithm
		6.6.3 Dixon’s Random Squares Algorithm
		6.6.4 Factoring Algorithms in Practice
	6.7 Other Attacks on RSA
		6.7.1 Computing Ø(n)
		6.7.2 The Decryption Exponent
		6.7.3 Wiener’s Low Decryption Exponent Attack
	6.8 The Rabin Cryptosystem
		6.8.1 Security of the Rabin Cryptosystem
	6.9 Semantic Security of RSA
		6.9.1 Partial Information Concerning Plaintext Bits
		6.9.2 Obtaining Semantic Security
	6.10 Notes and References
	Exercises
7: Public-Key Cryptography and Discrete Logarithms
	7.1 Introduction
		7.1.1 The ElGamal Cryptosystem
	7.2 Algorithms for the Discrete Logarithm Problem
		7.2.1 Shanks’ Algorithm
		7.2.2 The Pollard Rho Discrete Logarithm Algorithm
		7.2.3 The Pohlig-Hellman Algorithm
		7.2.4 The Index Calculus Method
	7.3 Lower Bounds on the Complexity of Generic Algorithms
	7.4 Finite Fields
		7.4.1 Joux’s Index Calculus
	7.5 Elliptic Curves
		7.5.1 Elliptic Curves over the Reals
		7.5.2 Elliptic Curves Modulo a Prime
		7.5.3 Elliptic Curves over Finite Fields
		7.5.4 Properties of Elliptic Curves
		7.5.5 Pairings on Elliptic Curves
		7.5.6 ElGamal Cryptosystems on Elliptic Curves
		7.5.7 Computing Point Multiples on Elliptic Curves
	7.6 Discrete Logarithm Algorithms in Practice
	7.7 Security of ElGamal Systems
		7.7.1 Bit Security of Discrete Logarithms
		7.7.2 Semantic Security of ElGamal Systems
		7.7.3 The Diffie-Hellman Problems
	7.8 Notes and References
	Exercises
8: Signature Schemes
	8.1 Introduction
		8.1.1 RSA Signature Scheme
	8.2 Security Requirements for Signature Schemes
		8.2.1 Signatures and Hash Functions
	8.3 The ElGamal Signature Scheme
		8.3.1 Security of the ElGamal Signature Scheme
	8.4 Variants of the ElGamal Signature Scheme
		8.4.1 The Schnorr Signature Scheme
		8.4.2 The Digital Signature Algorithm
		8.4.3 The Elliptic Curve DSA
	8.5 Full Domain Hash
	8.6 Certificates
	8.7 Signing and Encrypting
	8.8 Notes and References
	Exercises
9: Post-Quantum Cryptography
	9.1 Introduction
	9.2 Lattice-based Cryptography
		9.2.1 NTRU
		9.2.2 Lattices and the Security of NTRU
		9.2.3 Learning With Errors
	9.3 Code-based Cryptography and the McEliece Cryptosystem
	9.4 Multivariate Cryptography
		9.4.1 Hidden Field Equations
		9.4.2 The Oil and Vinegar Signature Scheme
	9.5 Hash-based Signature Schemes
		9.5.1 Lamport Signature Scheme
		9.5.2 Winternitz Signature Scheme
		9.5.3 Merkle Signature Scheme
	9.6 Notes and References
	Exercises
10: Identification Schemes and Entity Authentication
	10.1 Introduction
		10.1.1 Passwords
		10.1.2 Secure Identification Schemes
	10.2 Challenge-and-Response in the Secret-key Setting
		10.2.1 Attack Model and Adversarial Goals
		10.2.2 Mutual Authentication
	10.3 Challenge-and-Response in the Public-key Setting
		10.3.1 Public-key Identification Schemes
	10.4 The Schnorr Identification Scheme
		10.4.1 Security of the Schnorr Identification Scheme
	10.5 The Feige-Fiat-Shamir Identification Scheme
	10.6 Notes and References
	Exercises
11: Key Distribution
	11.1 Introduction
		11.1.1 Attack Models and Adversarial Goals
	11.2 Key Predistribution
		11.2.1 Diffie-Hellman Key Predistribution
		11.2.2 The Blom Scheme
		11.2.3 Key Predistribution in Sensor Networks
	11.3 Session Key Distribution Schemes
		11.3.1 The Needham-Schroeder Scheme
		11.3.2 The Denning-Sacco Attack on the NS Scheme
		11.3.3 Kerberos
		11.3.4 The Bellare-Rogaway Scheme
	11.4 Re-keying and the Logical Key Hierarchy
	11.5 Threshold Schemes
		11.5.1 The Shamir Scheme
		11.5.2 A Simplified (t, t)-threshold Scheme
		11.5.3 Visual Threshold Schemes
	11.6 Notes and References
	Exercises
12: Key Agreement Schemes
	12.1 Introduction
		12.1.1 Transport Layer Security (TLS)
	12.2 Diffie-Hellman Key Agreement
		12.2.1 The Station-to-station Key Agreement Scheme
		12.2.2 Security of STS
		12.2.3 Known Session Key Attacks
	12.3 Key Derivation Functions
	12.4 MTI Key Agreement Schemes
		12.4.1 Known Session Key Attacks on MTI/A0
	12.5 Deniable Key Agreement Schemes
	12.6 Key Updating
	12.7 Conference Key Agreement Schemes
	12.8 Notes and References
	Exercises
13: Miscellaneous Topics
	13.1 Identity-based Cryptography
		13.1.1 The Cocks Identity-based Cryptosystem
		13.1.2 The Boneh-Franklin Identity-based Cryptosystem
	13.2 The Paillier Cryptosystem
	13.3 Copyright Protection
		13.3.1 Fingerprinting
		13.3.2 Identifiable Parent Property
		13.3.3 2-IPP Codes
		13.3.4 Tracing Illegally Redistributed Keys
	13.4 Bitcoin and Blockchain Technology
	13.5 Notes and References
	Exercises
A: Number Theory and Algebraic Concepts for Cryptography
	A.1 Modular Arithmetic
	A.2 Groups
		A.2.1 Orders of Group Elements
		A.2.2 Cyclic Groups and Primitive Elements
		A.2.3 Subgroups and Cosets
		A.2.4 Group Isomorphisms and Homomorphisms
		A.2.5 Quadratic Residues
		A.2.6 Euclidean Algorithm
		A.2.7 Direct Products
	A.3 Rings
		A.3.1 The Chinese Remainder Theorem
		A.3.2 Ideals and Quotient Rings
	A.4 Fields
B: Pseudorandom Bit Generation for Cryptography
	B.1 Bit Generators
	B.2 Security of Pseudorandom Bit Generators
	B.3 Notes and References
Bibliography
Index