TY - BOOK AU - Katz,Jonathan TI - Introduction to modern cryptography SN - 9781466570269 (hardback) U1 - 005.82 KW - Computer security KW - Cryptography KW - COMPUTERS / Operating Systems / General KW - COMPUTERS / Security / Cryptography KW - MATHEMATICS / Combinatorics N1 - 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 ER -