Introduction to Modern Cryptography

Cover
Half Title
Series Page
Title Page
Copyright Page
Dedication
Table of Contents
Preface
I: Introduction and Classical Cryptography
1: Introduction
1.1 Cryptography and Modern Cryptography
1.2 The Setting of Private-Key Encryption
1.3 Historical Ciphers and Their Cryptanalysis
1.4 Principles of Modern Cryptography
1.4.1 Principle 1 { Formal Denitions
1.4.2 Principle 2 { Precise Assumptions
1.4.3 Principle 3 { Proofs of Security
1.4.4 Provable Security and Real-World Security
References and Additional Reading
Exercises
2: Perfectly Secret Encryption
2.1 Defnitions
2.2 The One-Time Pad
2.3 Limitations of Perfect Secrecy
2.4 *Shannon's Theorem
References and Additional Reading
Exercises
II: Private-Key (Symmetric) Cryptography
3: Private-Key Encryption
3.1 Computational Security
3.1.1 The Concrete Approach
3.1.2 The Asymptotic Approach
3.2 Defining Computationally Secure Encryption
3.2.1 The Basic Definition of Security (EAV-Security)
3.2.2 *Semantic Security
3.3 Constructing an EAV-Secure Encryption Scheme
3.3.1 Pseudorandom Generators
3.3.2 Proofs by Reduction
3.3.3 EAV-Security from a Pseudorandom Generator
3.4 Stronger Security Notions
3.4.1 Security for Multiple Encryptions
3.4.2 Chosen-Plaintext Attacks and CPA-Security
3.4.3 CPA-Security for Multiple Encryptions
3.5 Constructing a CPA-Secure Encryption Scheme
3.5.1 Pseudorandom Functions and Permutations
3.5.2 CPA-Security from a Pseudorandom Function
3.6 Modes of Operation and Encryption in Practice
3.6.1 Stream Ciphers
3.6.2 Stream-Cipher Modes of Operation
3.6.3 Block Ciphers and Block-Cipher Modes of Operation
3.6.4 *Nonce-Based Encryption
References and Additional Reading
Exercises
4: Message Authentication Codes
4.1 Message Integrity
4.1.1 Secrecy vs. Integrity
4.1.2 Encryption vs. Message Authentication
4.2 Message Authentication Codes (MACs) - Definitions
4.3 Constructing Secure Message Authentication Codes
4.3.1 A Fixed-Length MAC
4.3.2 Domain Extension for MACs
4.4 CBC-MAC
4.4.1 The Basic Construction
4.4.2 *Proof of Security
4.5 GMAC and Poly1305
4.5.1 MACs from Difference-Universal Functions
4.5.2 Instantiations
4.6 *Information-Theoretic MACs
4.6.1 One-Time MACs from Strongly Universal Functions
4.6.2 One-Time MACs from Difference-Universal Functions
4.6.3 Limitations on Information-Theoretic MACs
References and Additional Reading
Exercises
5: CCA-Security and Authenticated Encryption
5.1 Chosen-Ciphertext Attacks and CCA-Security
5.1.1 Padding-Oracle Attacks
5.1.2 Defining CCA-Security
5.2 Authenticated Encryption
5.2.1 Defining Authenticated Encryption
5.2.2 CCA Security vs. Authenticated Encryption
5.3 Authenticated Encryption Schemes
5.3.1 Generic Constructions
5.3.2 Standardized Schemes
5.4 Secure Communication Sessions
References and Additional Reading
Exercises
6: Hash Functions and Applications
6.1 Definitions
6.1.1 Collision Resistance
6.1.2 Weaker Notions of Security
6.2 Domain Extension: The Merkle-Damgård Transform
6.3 Message Authentication Using Hash Functions
6.3.1 Hash-and-MAC
6.3.2 HMAC
6.4 Generic Attacks on Hash Functions
6.4.1 Birthday Attacks for Finding Collisions
6.4.2 Small-Space Birthday Attacks
6.4.3 *Time/Space Tradeoffs for Inverting Hash Functions
6.5 The Random-Oracle Model
6.5.1 The Random-Oracle Model in Detail
6.5.2 Is the Random-Oracle Methodology Sound?
6.6 Additional Applications of Hash Functions
6.6.1 Fingerprinting and Deduplication
6.6.2 Merkle Trees
6.6.3 Password Hashing
6.6.4 Key Derivation
6.6.5 Commitment Schemes
References and Additional Reading
Exercises
7: Practical Constructions of Symmetric-Key Primitives
7.1 Stream Ciphers
7.1.1 Linear-Feedback Shift Registers
7.1.2 Adding Nonlinearity
7.1.3 Trivium
7.1.4 RC4
7.1.5 ChaCha20
7.2 Block Ciphers
7.2.1 Substitution-Permutation Networks
7.2.2 Feistel Networks
7.2.3 DES - The Data Encryption Standard
7.2.4 3DES: Increasing the Key Length of a Block Cipher
7.2.5 AES - The Advanced Encryption Standard
7.2.6 *Differential and Linear Cryptanalysis
7.3 Compression Functions and Hash Functions
7.3.1 Compression Functions from Block Ciphers
7.3.2 MD5, SHA-1, and SHA-2
7.3.3 The Sponge Construction and SHA-3 (Keccak)
References and Additional Reading
Exercises
8: *Theoretical Constructions of Symmetric-Key Primitives
8.1 One-Way Functions
8.1.1 Definitions
8.1.2 Candidate One-Way Functions
8.1.3 Hard-Core Predicates
8.2 From One-Way Functions to Pseudorandomness
8.3 Hard-Core Predicates from One-Way Functions
8.3.1 A Simple Case
8.3.2 A More Involved Case
8.3.3 The Full Proof
8.4 Constructing Pseudorandom Generators
8.4.1 Pseudorandom Generators with Minimal Expansion
8.4.2 Increasing the Expansion Factor
8.5 Constructing Pseudorandom Functions
8.6 Constructing (Strong) Pseudorandom Permutations
8.7 Assumptions for Private-Key Cryptography
8.8 Computational Indistinguishability
References and Additional Reading
Exercises
III: Public-Key (Asymmetric) Cryptography
9: Number Theory and Cryptographic Hardness Assumptions
9.1 Preliminaries and Basic Group Theory
9.1.1 Primes and Divisibility
9.1.2 Modular Arithmetic
9.1.3 Groups
9.1.4 The Group ℤ*N
9.1.5 *Isomorphisms and the Chinese Remainder Theorem
9.2 Primes, Factoring, and RSA
9.2.1 Generating Random Primes
9.2.2 *Primality Testing
9.2.3 The Factoring Assumption
9.2.4 The RSA Assumption
9.2.5 *Relating the Factoring and RSA Assumptions
9.3 Cryptographic Assumptions in Cyclic Groups
9.3.1 Cyclic Groups and Generators
9.3.2 The Discrete-Logarithm/Diffie-Hellman Assumptions
9.3.3 Working in (Subgroups of) ℤ*p
9.3.4 Elliptic Curves
9.4 *Cryptographic Applications
9.4.1 One-Way Functions and Permutations
9.4.2 Collision-Resistant Hash Functions
References and Additional Reading
Exercises
10: *Algorithms for Factoring and Computing Discrete Logarithms
10.1 Algorithms for Factoring
10.1.1 Pollard's p - 1 Algorithm
10.1.2 Pollard's Rho Algorithm
10.1.3 The Quadratic Sieve Algorithm
10.2 Generic Algorithms for Computing Discrete Logarithms
10.2.1 The Pohlig-Hellman Algorithm
10.2.2 The Baby-Step/Giant-Step Algorithm
10.2.3 Discrete Logarithms from Collisions
10.3 Index Calculus: Computing Discrete Logarithms in ℤ*p
10.4 Recommended Key Lengths
References and Additional Reading
Exercises
11: Key Management and the Public-Key Revolution
11.1 Key Distribution and Key Management
11.2 A Partial Solution: Key-Distribution Centers
11.3 Key Exchange and the Diffie-Hellman Protocol
11.4 The Public-Key Revolution
References and Additional Reading
Exercises
12: Public-Key Encryption
12.1 Public-Key Encryption - An Overview
12.2 Definitions
12.2.1 Security against Chosen-Plaintext Attacks
12.2.2 Multiple Encryptions
12.2.3 Security against Chosen-Ciphertext Attacks
12.3 Hybrid Encryption and the KEM/DEM Paradigm
12.3.1 CPA-Security
12.3.2 CCA-Security
12.4 CDH/DDH-Based Encryption
12.4.1 El Gamal Encryption
12.4.2 DDH-Based Key Encapsulation
12.4.3 *A CDH-Based KEM in the Random-Oracle Model
12.4.4 *Chosen-Ciphertext Security and DHIES/ECIES
12.5 RSA-Based Encryption
12.5.1 Plain RSA Encryption
12.5.2 Padded RSA and PKCS #1 v1.5
12.5.3 *CPA-Secure Encryption without Random Oracles
12.5.4 OAEP and PKCS #1 v2
12.5.5 *A CCA-Secure KEM in the Random-Oracle Model
12.5.6 RSA Implementation Issues and Pitfalls
References and Additional Reading
Exercises
13: Digital Signature Schemes
13.1 Digital Signatures - An Overview
13.2 Definitions
13.3 The Hash-and-Sign Paradigm
13.4 RSA-Based Signatures
13.4.1 Plain RSA Signatures
13.4.2 RSA-FDH and PKCS #1 Standards
13.5 Signatures from the Discrete-Logarithm Problem
13.5.1 Identification Schemes and Signatures
13.5.2 The Schnorr Identification/Signature Schemes
13.5.3 DSA and ECDSA
13.6 Certificates and Public-Key Infrastructures
13.7 Putting It All Together - TLS
13.8 *Signcryption
References and Additional Reading
Exercises
14: *Post-Quantum Cryptography
14.1 Post-Quantum Symmetric-Key Cryptography
14.1.1 Grover's Algorithm and Symmetric-Key Lengths
14.1.2 Collision-Finding Algorithms and Hash Functions
14.2 Shor's Algorithm and its Impact on Cryptography
14.3 Post-Quantum Public-Key Encryption
14.4 Post-Quantum Signatures
14.4.1 Lamport's Signature Scheme
14.4.2 Chain-Based Signatures
14.4.3 Tree-Based Signatures
References and Additional Reading
Exercises
15 *Advanced Topics in Public-Key Encryption
15.1 Public-Key Encryption from Trapdoor Permutations
15.1.1 Trapdoor Permutations
15.1.2 Public-Key Encryption from Trapdoor Permutations
15.2 The Paillier Encryption Scheme
15.2.1 The Structure of ℤ*N2
15.2.2 The Paillier Encryption Scheme
15.2.3 Homomorphic Encryption
15.3 Secret Sharing and Threshold Encryption
15.3.1 Secret Sharing
15.3.2 Verifiable Secret Sharing
15.3.3 Threshold Encryption and Electronic Voting
15.4 The Goldwasser-Micali Encryption Scheme
15.4.1 Quadratic Residues Modulo a Prime
15.4.2 Quadratic Residues Modulo a Composite
15.4.3 The Quadratic Residuosity Assumption
15.4.4 The Goldwasser-Micali Encryption Scheme
15.5 The Rabin Encryption Scheme
15.5.1 Computing Modular Square Roots
15.5.2 A Trapdoor Permutation Based on Factoring
15.5.3 The Rabin Encryption Scheme
References and Additional Reading
Exercises
Index of Common Notation
Appendix A: Mathematical Background
A.1 Identities and Inequalities
A.2 Asymptotic Notation
A.3 Basic Probability
A.4 The "Birthday" Problem
A.5 *Finite Fields
Appendix B: Basic Algorithmic Number Theory
B.1 Integer Arithmetic
B.1.1 Basic Operations
B.1.2 The Euclidean and Extended Euclidean Algorithms
B.2 Modular Arithmetic
B.2.1 Basic Operations
B.2.2 Computing Modular Inverses
B.2.3 Modular Exponentiation
B.2.4 *Montgomery Multiplication
B.2.5 Choosing a Uniform Group Element
B.3 *Finding a Generator of a Cyclic Group
B.3.1 Group-Theoretic Background
B.3.2 Efficient Algorithms
References and Additional Reading
Exercises
References
Index