Modern Cryptography Principles and Protocols (by Katz (USA) and Lindel (Israel))

Cryptography plays a key role in ensuring the privacy and integrity of data and the security of computer networks. Modern Cryptography: Principles and Protocols provides a rigorous yet accessible introduction to modern cryptography, focusing on formal definitions, precise assumptions, and rigorous proofs. Modern Cryptography: Principles and Protocols introduces the core principles of modern cryptography, including modern, computationally complex security to overcome the limitations of perfect security. Symmetric key encryption and message authentication are also introduced in great detail. At the same time, the design principles of block ciphers such as DES and AES are illustrated, and the provably secure construction methods of block ciphers are demonstrated at the low-level primitive level. The second half of Modern Cryptography: Principles and Protocols introduces public key cryptography. First, the knowledge of number theory is introduced, which is needed to understand RSA, Diffie-Hellman, El Gamal, and other cryptographic systems. After exploring public key encryption and digital signatures, the random oracle model and its applications are introduced. Whether used as a textbook, reference book, or self-study book, this book presents readers with the tools they need to thoroughly understand the fascinating subject of modern cryptography. Part I Introduction to Classical Cryptography Chapter 1 Overview 1.1 Cryptography and Modern Cryptography 1.2 Basic Settings for Symmetric Key Cryptography 1.3 Classical Cryptography and Its Cryptanalysis 1.4 Basic Principles of Modern Cryptography 1.4.1 Principle 1 - Forming Precise Definitions 1.4.2 Principle 2 - Dependence on Precise Assumptions 1.4.3 Principle 3 - Rigorous Security Proofs References and Further Reading Introduction Exercises Chapter 2 Perfect Confidentiality Cryptography 2.1 Definition and Basic Properties 2.2 One-Time Pad (Vemam Cryptography) 2.3 Limitations of Perfect Confidentiality 2.4 Shannon\'s Theorem 2.5 Summary References and Further Reading Introduction Exercises Part II Symmetric Key Cryptography Chapter 3 Symmetric Key Cryptography and Pseudo-Randomness 3.1 Computational Methods in Cryptography 3.1.1 Basic Ideas of Computational Security 3.1.2 Efficient Algorithms and Negligible Probability of Success 3.1.3 Proofs of Specification 3.2 Definition of Computationally Secure Cryptography 3.2.1 Basic Definition of Security 3.2.2 Properties of Definition 3.3 Pseudo-Randomness 3.4 3.4.1 A Secure Fixed-Length Encryption Scheme 3.4.2 Handling Variable-Length Messages 3.4.3 Stream Ciphers and Multiple Encryptions 3.5 Security Against Chosen Plaintext Attacks (CPA) 3.6 Creating CPA-Secure Encryption Schemes 3.6.1 Pseudo-Random Functions 3.6.2 CPA-Secure Encryption Based on Pseudo-Random Functions 3.6.3 Pseudo-Random Permutations and Block Ciphers 3.6.4 Modes of Cryptographic Operation 3.7 Security of CCA References and Further Reading Introduction Exercises Chapter 4 Message Authentication Codes and Collision-Resistant Hash Functions 4.1 Secure Communications and Message Integrity 4.2 Comparison of Encryption and Message Authentication 4.3 Message Authentication Codes - Definition 4.4 Constructing Secure Message Authentication Codes 4.5 CBC.MAC 4.6 Collision-Resistant Hash Functions 4.6.1 Definition of Collision Resistance 4.6.2 A Weaker Definition of Hash Function Security 4.6.3 Universal \"Birthday\" Attack 4.6.4 Merkle-Damgard Transformation 4.6.5 4.7.1 The MAC-MMAC 4.7.2 The HMAC 4.8 Constructing CCA-secure encryption schemes 4.9 Obtaining privacy and message authentication References and further reading Introduction Exercises Chapter 5 Practical construction of pseudorandom permutations (block ciphers) 5.1 Substitute-permutation networks 5.2 Feistel networks 5.3 DES - the data encryption standard 5.3.1 The design of DES 5.3.2 Attacks on DES variants with reduced rounds 5.3.3 The security of DES 5.4 Increasing the key length of block ciphers 5.5 AES - the advanced encryption standard 5.6 Differential and linear cryptanalysis Introduction References and further reading Introduction Exercises Chapter 6 Theoretical construction of pseudorandom objects 6.1 One-way functions 6.1.1 Definition 6.1.2 Candidate one-way functions 6.1.3 Hard-core predicates 6.2 Overview: from one-way functions to pseudorandom permutations 6.3 6.3.1 The Simple Case 6.3.2 The Complex Case 6.3.3 The Complete Proof 6.4 Constructing Pseudorandom Generators 6.4.1 Pseudorandom Generators with Minimal Spread 6.4.2 Improving the Spread Factor 6.5 Constructing Pseudorandom Functions 6.6 Constructing (Strong) Pseudorandom Permutations 6.7 Necessary Assumptions for Symmetric Key Cryptography 6.8 Deviations—Computational Indistinguishability 6.8.1 Pseudorandomness and Pseudorandom Generators 6.8.2 Multiple Sampling References and Further Reading Introduction Exercises Part III Public (Asymmetric) Key Cryptography Chapter 7 Number Theory and Cryptographic Hardness Assumptions 7.1 Preliminaries and Basic Group Theory 7.1.1 Prime Numbers and Divisibility 7.1.2 Modular Arithmetic 7.1.3 Groups 7.1.4 Z*N Groups 7.1.5 Group Isomorphisms and the Chinese Remainder Theorem 7.2 Prime Numbers, Factorization, and RSA 7.2.1 7.2.2 Prime Determination 7.2.3 Factorization Assumption 7.2.4 RSA Assumption 7.3 Assumptions in Cyclic Groups 7.3.1 Cyclic Groups and Generators 7.3.2 Discrete Logarithms and the Diffie-Hellman Assumption 7.3.3 Working in (a Subgroup of) Zp 7.3.4 Elliptic Curve Groups 7.4 Cryptographic Applications of Number Theoretic Assumptions 7.4.1 One-Way Functions and Permutations 7.4.2 Constructing Collision-Resistant Hash Functions References and Further Reading Introduction Exercises Chapter 8 Factorization and Discrete Logarithm Algorithms 8.1 Factorization Algorithms 8.1.1 Pollard’s p-1 Method 8.1.2 Pollard’s Rho Method 8.1.3 Quadratic Sieve Algorithm 8.2 Algorithms for Computing Discrete Logarithms 8.2.1 “Small Step Big Step” Algorithm 8.2.2 Pohlig-Hellman Algorithm 8.2.3 Discrete Logarithm Problem in ZN 8.2.4 Index Algorithms References and Further Reading Introduction Exercises Chapter 9 Symmetric Key Management and the Public Key Revolution 9.1 Limitations of Symmetric Key Cryptography 9.2 Local Solutions—Key Distribution Centers 9.3 The Public Key Revolution 9.4 Diffe-Hellman Key Exchange References and Further Reading Introduction Exercises Chapter 10 Public Key Cryptography 10.1 Introduction to Public Key Cryptography 10.2 Definition 10.2.1 Security from Chosen Plaintext Attacks 10.2.2 Multiple Encryption 10.3 Hybrid Encryption 10.4 RSA Encryption 10.4.1 The “Textbook RSA” Encryption Scheme and Its Insecurity 10.4.2 Attacks on the “Textbook RSA” Encryption Scheme 10.4.3 Padding RSA 10.5 E1Gamal Encryption 10.6 Security from Chosen Ciphertext Attacks 10.7 Trapdoor Permutations 10.7.1 Definition 10.7.2 Public Key Cryptography from Trapdoor Permutations References and Further Reading Introduction Exercises Chapter 11 Other Public Key Cryptography Schemes 11.1 Goldwasser-Micali Encryption Scheme 11.1.1 Primes Modulo Quadratic Residues 11.1.2 Composites Modulo Quadratic Residues 11.1.3 Quadratic Residue Assumption 11.1.4 Goldwasser-Micali Encryption Scheme 11.2 Rabin Encryption Scheme 11.2.1 Computing Modular Square Roots 11.2.2 Factorization-Based Trapdoor Permutations 11.2.3 Rabin Encryption Scheme 11.3 Paillier Encryption Scheme 11.3.1 Z*N2 Structure 11.3.2 Paillier Encryption Scheme 11.3.3 Homomorphic Encryption References and Further Reading Introduction Exercises Chapter 12 Digital Signatures 12.1 Introduction to Digital Signatures 12.2 Definitions 12.3 RSA Signatures 12.3.1 The “Textbook RSA” Signature Scheme and Its Insecurity 12.3.2 The “Hashed RSA” Signature Scheme 12.4 The “Hash-and-Sign” Example 12.5 Lamport’s “One-Time Signature Scheme” 12.6 Signatures from collision-resistant hashes 12.6.1 Chain-based signatures 12.6.2 Tree-based signatures 12.7 Digital Signature Standard (DSS) 12.8 Digital Certificates and Public Key Infrastructure References and Further Reading Introduction Exercises 1 Chapter 13 Public Key Cryptography in the Random Oracle Model 13.1 Random Oracle Methodology 13.1.1 Random Oracle Model 13.1.2 Is the Random Oracle Method Reasonable 13.2 Public Key Cryptography in the Random Oracle Model 13.2.1 Chosen Plaintext Attack Security 13.2.2 Chosen Ciphertext Attack Security 13.2.3 OAEP 13.3 Signatures in the Random Oracle Model References and Further Reading Introduction Exercises Common Symbols Index Appendix Appendix A Mathematical Knowledge A.1 Identities and Inequalities A.2 Asymptotic Notation A.3 Introduction to Probability Theory A.4 The “Birthday” Problem Appendix B Algorithms Number Theory Supplementary Knowledge B.1 Integer Arithmetic B.2 Modular Arithmetic B.3 Finding Generators of a Cyclic Group References and Further Reading Introduction Exercises References