Introduction to modern cryptography /
Katz, Jonathan,
Introduction to modern cryptography / Jonathan Katz, University of Maryland, College Park, MD, USA, Yehuda Lindell, Bar-llan University, Ramat Gan, Israel. - Second edition. - xx, 583 pages : illustrations ; 25 cm.
Includes bibliographical references and index.
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 Definitions
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 Definitions
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
3.2.2 *Semantic Security
3.3 Constructing Secure Encryption Schemes
3.3.1 Pseudorandom Generators and Stream Ciphers
3.3.2 Proofs by Reduction
3.3.3 A Secure Fixed-Length Encryption ocneme
3.4 Stronger Security Notion.s
3.4.1 Sc^curity for Multiple Encryptions .
3.4.2 Chosen-Plaintext Attacks and CPA-Security .
3.5 Constructing CPA-Secure Encryption Schemes
3.5.1 Pseudorandom Functions and Block Ciphers
3.5.2 CPA-Secure Encryption from Pseudorandom Functions
3.6 Modes of Operation
3.6.1 Stream-Cipher Modes of Operation
3.6.2 Block-Cipher Mod(\s of Operation
3.7 Chosen-Ciphertext Attacks
3.7.1 Defining CCA-Security
3.7.2 Padding-Oracle Attacks
References and Additional Reading
Exercises
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 - 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 Authenticated Encryption
4.5.1 Definitions
4.5.2 Generic Constructions .
4.5.3 Secure Communication Sessions
4.5.4 CCA-Secure Encryption
4.6 *Information-Theoretic MACs
4.6.1 Constructing Information-Theoretic MACs
4.6.2 Limitations on Information-Theoretic MACs
References and Additional Reading
Exercises
Hash Functions and Applications
5.1 Definitions
5.1.1 Collision Resistance
5.1.2 Weaker Notions of Security
5.2 Domain Extension: The Merkle-Damgard Transform
5.3 Message Authentication Using Hash Functions
5.3.1 Hash-and-MAC
5.3.2 HMAC
5.4 Generic Attacks on Hash Functions
5.4.1 Birthday Attacks for Finding Collisions .
5.4.2 Small-Space Birthday Attacks .
5.4.3 *Time/Space Tradeoffs for Inverting Functions .
5.5 The Random-Oracle Model
5.5.1 The Random-Oracle Model in Detail
5.5.2 Is the Random-Oracle Methodology Sound?
5.6 Additional Applications of Hash Functions
5.6.1 Fingerprinting and Deduplication
5.6.2 Merkle Trees
5.6.3 Password Hashing
5.6.4 Key Derivation
5.6.5 Commitment Schemes
References and Additional Reading
Exercises
6 Practical Constructions of Symmetric-Key Primitives
6.1 Stream Ciphers
6.1.1 Linear-Feedback Shift Registers
6.1.2 Adding Nonlinearity
6.1.3 Trivium
6.1.4 RC4 . .
6.2 Block Ciphers
6.2.1 Substitution-Permutation Networks
6.2.2 Feistel Networks
6.2.3 DES - The Data Encryption Standard
6.2.4 3DES: Increasing the Key Length of a Block Cipher
6.2.5 AES - The Advanced Encryption Standard
6.2.6 *Differential and Linear Cryptanalysis
6.3 Hash Functions
6.3.1 Hash Functions from Block Ciphers .
6.3.2 MD5 .
6.3.3 SHA-0, SHA-1, and SHA-2
6.3.4 SHA-3 (Keccak)
References and Additional Reading
Exercises
7 *Theoretical Constructions of Symmetric-Key Primitives
7.1 One-Way Functions
7.1.1 Definitions .
7.1.2 Candidate One-Way Functions
7.1.3 Hard-Core Predicates
7 2 From One-Way Functions to Pseudorandomness
7 3 Hard-Core Predicates from One-Way Functions
7.3.1 A Simple Case
7.3.2 A More Involved Case
7.3.3 The FxiW Proof
7.4 Constructing Pseudorandom Generators . .
7.4.1 Pseudorandom Generators with Minimal Expansion
7.4.2 Increasing the Expansion Factor
7.5 Constructing Pseudorandom Functions
7.6 Constructing (Strong) Pseudorandom Permutations
7.7 Assumptions for Private-Key Cryptography
7.8 Computational Indistingtiishability
References and Additional Reading
Exercises
III Public-Key (Asymmetric) Cryptography
8 Number Theory and Cryptographic Hardness Assumptions
8.1 Preliminaries and Basic Group Theory
8.1.1 Primes and Divisibility
8.1.2 Modular Arithmetic .
8.1.3 Groups
8.1.4 The Group
8.1.5 *Isomorphisms and the Chinese Remainder Theorem .
8.2 Primes, Factoring, and RSA . . . .
8.2.1 Generating Random Primes .
8.2.2 *Primality Testing .
8.2.3 The Factoring Assumption .
8.2.4 The RSA Assumption . . . .
8.2.5 *Relating the RSA and Factoring Assumptions
8.3 Cryptographic Assumptions in Cyclic Groups
8.3.1 Cyclic Groups and Generators . . . .
8.3.2 The Discrete-Logarithm/Diffie-Hellman Assumptions
8.3.3 Working in (Subgroups of) Z*
8.3.4 Elliptic Curves . . . .
8.4 * Cryptographic Applications
8.4.1 One-Way Functions and Permutations .
8.4.2 Constructing Collision-Resistant Hash Functions
References and Additional Reading
Exercises
9 *Algorithms for Factoring and Computing Discrete Loga
rithms
9.1 Algorithms for Factoring
9.1.1 Pollard's p — 1 Algorithm
9.1.2 Pollard's Rho Algorithm .
9.1.3 The Quadratic Sieve Algorithm .
9.2 Algorithms for Computing Discrete Logarithms
9.2.1 The Pohlig-Hellman Algorithm . . . .
9.2.2 The Baby-Step/Giant-Step Algorithm
9.2.3 Discrete Logarithms from Collisions .
9.2.4 The Index Calculus Algorithm . . . .
9.3 Recommended Key Lengths
References and Additional Reading
Exercises
10 Key Management and the Public-Key Revolution
10.1 Key Distribution and Key Management
10.2 A Partial Solution: Key-Distribution Centers .
10.3 Key Exchange and the Diffie-Hellman Protocol
10.4 The Public-Key Revolution . .
References and Additional Reading
Exercises
11 Public-Key Encryption
11.1 Public-Key Encryption - An Overview
11.2 Definitions
11.2.1 Security against Chosen-Plaintext Attacks . .
11.2.2 Multiple Encryptions .
11.2.3 Security against Chosen-Ciphertext Attacks .
11.3 Hybrid Encryption and the KEM/DEM Paradigm .
11.3.1 CPA-Security
11.3.2 CCA-Security
11.4 CDH/DDH-Based Encryption
11.4.1 El Camal Encryption .
11.4.2 DDK-Based Key Encapsulation .
11.4.3 *A CDH-Based KEM in the Random-Oracle Model
11.4.4 Chosen-Ciphertext Security and DHIES/ECIES . . .
11.5 RSA Encryption
11.5.1 Plain RSA
11.5.2 Padded RSA and PKCS #1 vl.5
11.5.3 *CPA-Secure Encryption without Random Oracles .
11.5.4 OAEP and RSA PKCS #1 v2.0
11.5.5 *A CCA-Secure KEM in the Random-Oracle Model
11.5.6 RSA Implementation Issues and Pitfalls
References and Additional Reading . .
Exercises
12 Digital Signature Schemes
12.1 Digital Signatures - An Overview
12.2 Definitions
12.3 The Hash-and-Sign Paradigm . . .
12.4 RSA Signatures
12.4.1 Plain RSA
12.4.2 RSA-FDH and PRCS #1 v2.1
12.5 Signatures from the Discrete-Logarithm Problem
12.5.1 The Schnorr Signature Scheme
12.5.2 DSA and ECDSA
12.6 *Signatures from Hash Functions
12.6.1 Lamport's Signature Scheme
12.6.2 Chain-Based Signatures
12.6.3 Tree-Based Signatures .
12.7 *Certificates and Public-Key Infrastructures
12.8 Putting It All Together - SSL/TLS
12.9 *Signcryption
References and Additional Reading
Exercises .
13 *Advanced Topics in Public-Key Encryption
13.1 Public-Key Encryption from Trapdoor Permutations
13.1.1 Trapdoor Permutations
13.1.2 Public-Key Encryption from Trapdoor Permutations
13.2 The Paillier Encryption Scheme
13.2.1 The Structure of • •
13.2.2 The Paillier Encryption Scheme .
13.2.3 Homomorphic Encryption
13.3 Secret Sharing and Threshold Encryption
13.3.1 Secret Sharing
13.3.2 Verifiable Secret Sharing .
13.3.3 Threshold Encryption and Electronic Voting
13.4 The Goldwasser-Micali Encryption Scheme
13.4.1 Quadratic Residues Modulo a Prime
13.4.2 Quadratic Residues Modulo a Composite
13.4.3 The Quadratic Residuosity Assumption
13.4.4 The Goldwasser-Micali Encryption Scheme .
13.5 The Rabin Encryption Scheme
13.5.1 Computing Modular Square Roots
13.5.2 A Trapdoor Permutation Based on Factoring
13.5.3 The Rabin Encryption Scheme
References and Additional Reading
Exercises
9781466570269 (hardback)
Computer security.
Cryptography.
COMPUTERS / Operating Systems / General.
COMPUTERS / Security / Cryptography.
MATHEMATICS / Combinatorics.
005.82 / KAT/M
Introduction to modern cryptography / Jonathan Katz, University of Maryland, College Park, MD, USA, Yehuda Lindell, Bar-llan University, Ramat Gan, Israel. - Second edition. - xx, 583 pages : illustrations ; 25 cm.
Includes bibliographical references and index.
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 Definitions
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 Definitions
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
3.2.2 *Semantic Security
3.3 Constructing Secure Encryption Schemes
3.3.1 Pseudorandom Generators and Stream Ciphers
3.3.2 Proofs by Reduction
3.3.3 A Secure Fixed-Length Encryption ocneme
3.4 Stronger Security Notion.s
3.4.1 Sc^curity for Multiple Encryptions .
3.4.2 Chosen-Plaintext Attacks and CPA-Security .
3.5 Constructing CPA-Secure Encryption Schemes
3.5.1 Pseudorandom Functions and Block Ciphers
3.5.2 CPA-Secure Encryption from Pseudorandom Functions
3.6 Modes of Operation
3.6.1 Stream-Cipher Modes of Operation
3.6.2 Block-Cipher Mod(\s of Operation
3.7 Chosen-Ciphertext Attacks
3.7.1 Defining CCA-Security
3.7.2 Padding-Oracle Attacks
References and Additional Reading
Exercises
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 - 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 Authenticated Encryption
4.5.1 Definitions
4.5.2 Generic Constructions .
4.5.3 Secure Communication Sessions
4.5.4 CCA-Secure Encryption
4.6 *Information-Theoretic MACs
4.6.1 Constructing Information-Theoretic MACs
4.6.2 Limitations on Information-Theoretic MACs
References and Additional Reading
Exercises
Hash Functions and Applications
5.1 Definitions
5.1.1 Collision Resistance
5.1.2 Weaker Notions of Security
5.2 Domain Extension: The Merkle-Damgard Transform
5.3 Message Authentication Using Hash Functions
5.3.1 Hash-and-MAC
5.3.2 HMAC
5.4 Generic Attacks on Hash Functions
5.4.1 Birthday Attacks for Finding Collisions .
5.4.2 Small-Space Birthday Attacks .
5.4.3 *Time/Space Tradeoffs for Inverting Functions .
5.5 The Random-Oracle Model
5.5.1 The Random-Oracle Model in Detail
5.5.2 Is the Random-Oracle Methodology Sound?
5.6 Additional Applications of Hash Functions
5.6.1 Fingerprinting and Deduplication
5.6.2 Merkle Trees
5.6.3 Password Hashing
5.6.4 Key Derivation
5.6.5 Commitment Schemes
References and Additional Reading
Exercises
6 Practical Constructions of Symmetric-Key Primitives
6.1 Stream Ciphers
6.1.1 Linear-Feedback Shift Registers
6.1.2 Adding Nonlinearity
6.1.3 Trivium
6.1.4 RC4 . .
6.2 Block Ciphers
6.2.1 Substitution-Permutation Networks
6.2.2 Feistel Networks
6.2.3 DES - The Data Encryption Standard
6.2.4 3DES: Increasing the Key Length of a Block Cipher
6.2.5 AES - The Advanced Encryption Standard
6.2.6 *Differential and Linear Cryptanalysis
6.3 Hash Functions
6.3.1 Hash Functions from Block Ciphers .
6.3.2 MD5 .
6.3.3 SHA-0, SHA-1, and SHA-2
6.3.4 SHA-3 (Keccak)
References and Additional Reading
Exercises
7 *Theoretical Constructions of Symmetric-Key Primitives
7.1 One-Way Functions
7.1.1 Definitions .
7.1.2 Candidate One-Way Functions
7.1.3 Hard-Core Predicates
7 2 From One-Way Functions to Pseudorandomness
7 3 Hard-Core Predicates from One-Way Functions
7.3.1 A Simple Case
7.3.2 A More Involved Case
7.3.3 The FxiW Proof
7.4 Constructing Pseudorandom Generators . .
7.4.1 Pseudorandom Generators with Minimal Expansion
7.4.2 Increasing the Expansion Factor
7.5 Constructing Pseudorandom Functions
7.6 Constructing (Strong) Pseudorandom Permutations
7.7 Assumptions for Private-Key Cryptography
7.8 Computational Indistingtiishability
References and Additional Reading
Exercises
III Public-Key (Asymmetric) Cryptography
8 Number Theory and Cryptographic Hardness Assumptions
8.1 Preliminaries and Basic Group Theory
8.1.1 Primes and Divisibility
8.1.2 Modular Arithmetic .
8.1.3 Groups
8.1.4 The Group
8.1.5 *Isomorphisms and the Chinese Remainder Theorem .
8.2 Primes, Factoring, and RSA . . . .
8.2.1 Generating Random Primes .
8.2.2 *Primality Testing .
8.2.3 The Factoring Assumption .
8.2.4 The RSA Assumption . . . .
8.2.5 *Relating the RSA and Factoring Assumptions
8.3 Cryptographic Assumptions in Cyclic Groups
8.3.1 Cyclic Groups and Generators . . . .
8.3.2 The Discrete-Logarithm/Diffie-Hellman Assumptions
8.3.3 Working in (Subgroups of) Z*
8.3.4 Elliptic Curves . . . .
8.4 * Cryptographic Applications
8.4.1 One-Way Functions and Permutations .
8.4.2 Constructing Collision-Resistant Hash Functions
References and Additional Reading
Exercises
9 *Algorithms for Factoring and Computing Discrete Loga
rithms
9.1 Algorithms for Factoring
9.1.1 Pollard's p — 1 Algorithm
9.1.2 Pollard's Rho Algorithm .
9.1.3 The Quadratic Sieve Algorithm .
9.2 Algorithms for Computing Discrete Logarithms
9.2.1 The Pohlig-Hellman Algorithm . . . .
9.2.2 The Baby-Step/Giant-Step Algorithm
9.2.3 Discrete Logarithms from Collisions .
9.2.4 The Index Calculus Algorithm . . . .
9.3 Recommended Key Lengths
References and Additional Reading
Exercises
10 Key Management and the Public-Key Revolution
10.1 Key Distribution and Key Management
10.2 A Partial Solution: Key-Distribution Centers .
10.3 Key Exchange and the Diffie-Hellman Protocol
10.4 The Public-Key Revolution . .
References and Additional Reading
Exercises
11 Public-Key Encryption
11.1 Public-Key Encryption - An Overview
11.2 Definitions
11.2.1 Security against Chosen-Plaintext Attacks . .
11.2.2 Multiple Encryptions .
11.2.3 Security against Chosen-Ciphertext Attacks .
11.3 Hybrid Encryption and the KEM/DEM Paradigm .
11.3.1 CPA-Security
11.3.2 CCA-Security
11.4 CDH/DDH-Based Encryption
11.4.1 El Camal Encryption .
11.4.2 DDK-Based Key Encapsulation .
11.4.3 *A CDH-Based KEM in the Random-Oracle Model
11.4.4 Chosen-Ciphertext Security and DHIES/ECIES . . .
11.5 RSA Encryption
11.5.1 Plain RSA
11.5.2 Padded RSA and PKCS #1 vl.5
11.5.3 *CPA-Secure Encryption without Random Oracles .
11.5.4 OAEP and RSA PKCS #1 v2.0
11.5.5 *A CCA-Secure KEM in the Random-Oracle Model
11.5.6 RSA Implementation Issues and Pitfalls
References and Additional Reading . .
Exercises
12 Digital Signature Schemes
12.1 Digital Signatures - An Overview
12.2 Definitions
12.3 The Hash-and-Sign Paradigm . . .
12.4 RSA Signatures
12.4.1 Plain RSA
12.4.2 RSA-FDH and PRCS #1 v2.1
12.5 Signatures from the Discrete-Logarithm Problem
12.5.1 The Schnorr Signature Scheme
12.5.2 DSA and ECDSA
12.6 *Signatures from Hash Functions
12.6.1 Lamport's Signature Scheme
12.6.2 Chain-Based Signatures
12.6.3 Tree-Based Signatures .
12.7 *Certificates and Public-Key Infrastructures
12.8 Putting It All Together - SSL/TLS
12.9 *Signcryption
References and Additional Reading
Exercises .
13 *Advanced Topics in Public-Key Encryption
13.1 Public-Key Encryption from Trapdoor Permutations
13.1.1 Trapdoor Permutations
13.1.2 Public-Key Encryption from Trapdoor Permutations
13.2 The Paillier Encryption Scheme
13.2.1 The Structure of • •
13.2.2 The Paillier Encryption Scheme .
13.2.3 Homomorphic Encryption
13.3 Secret Sharing and Threshold Encryption
13.3.1 Secret Sharing
13.3.2 Verifiable Secret Sharing .
13.3.3 Threshold Encryption and Electronic Voting
13.4 The Goldwasser-Micali Encryption Scheme
13.4.1 Quadratic Residues Modulo a Prime
13.4.2 Quadratic Residues Modulo a Composite
13.4.3 The Quadratic Residuosity Assumption
13.4.4 The Goldwasser-Micali Encryption Scheme .
13.5 The Rabin Encryption Scheme
13.5.1 Computing Modular Square Roots
13.5.2 A Trapdoor Permutation Based on Factoring
13.5.3 The Rabin Encryption Scheme
References and Additional Reading
Exercises
9781466570269 (hardback)
Computer security.
Cryptography.
COMPUTERS / Operating Systems / General.
COMPUTERS / Security / Cryptography.
MATHEMATICS / Combinatorics.
005.82 / KAT/M