Introduction to Modern Cryptography
Preview
Book Description
Cryptography is ubiquitous and plays a key role in ensuring data secrecy and integrity as well as in securing computer systems more broadly. Introduction to Modern Cryptography provides a rigorous yet accessible treatment of this fascinating subject.
The authors introduce the core principles of modern cryptography, with an emphasis on formal definitions, clear assumptions, and rigorous proofs of security. The book begins by focusing on private-key cryptography, including an extensive treatment of private-key encryption, message authentication codes, and hash functions. The authors also present design principles for widely used stream ciphers and block ciphers including RC4, DES, and AES, plus provide provable constructions of stream ciphers and block ciphers from lower-level primitives. The second half of the book covers public-key cryptography, beginning with a self-contained introduction to the number theory needed to understand the RSA, Diffie-Hellman, and El Gamal cryptosystems (and others), followed by a thorough treatment of several standardized public-key encryption and digital signature schemes.
Integrating a more practical perspective without sacrificing rigor, this widely anticipated Second Edition offers improved treatment of:
- Stream ciphers and block ciphers, including modes of operation and design principles
- Authenticated encryption and secure communication sessions
- Hash functions, including hash-function applications and design principles
- Attacks on poorly implemented cryptography, including attacks on chained-CBC encryption, padding-oracle attacks, and timing attacks
- The random-oracle model and its application to several standardized, widely used public-key encryption and signature schemes
- Elliptic-curve cryptography and associated standards such as DSA/ECDSA and DHIES/ECIES
Containing updated exercises and worked examples, Introduction to Modern Cryptography, Second Edition can serve as a textbook for undergraduate- or graduate-level courses in cryptography, a valuable reference for researchers and practitioners, or a general introduction suitable for self-study.
Table of Contents
Preface
I. Introduction and Classical Cryptography
Introduction
Cryptography and Modern Cryptography
The Setting of Private-Key Encryption
Historical Ciphers and Their Cryptanalysis
Principles of Modern Cryptography
Principle 1 – Formal Definitions
Principle 2 – Precise Assumptions
Principle 3 – Proofs of Security
Provable Security and Real-World Security
References and Additional Reading
Exercises
Perfectly Secret Encryption
Definitions
The One-Time Pad
Limitations of Perfect Secrecy
Shannon’s Theorem
References and Additional Reading
Exercises
II. Private-Key (Symmetric) Cryptography
Private-Key Encryption
Computational Security
The Concrete Approach
The Asymptotic Approach
Defining Computationally Secure Encryption
The Basic Definition of Security
Semantic Security
Constructing Secure Encryption Schemes
Pseudorandom Generators and Stream Ciphers
Proofs by Reduction
A Secure Fixed-Length Encryption Scheme
Stronger Security Notions
Security for Multiple Encryptions
Chosen-Plaintext Attacks and CPA-Security
Constructing CPA-Secure Encryption Schemes
Pseudorandom Functions and Block Ciphers
CPA-Secure Encryption from Pseudorandom Functions
Modes of Operation
Stream-Cipher Modes of Operation
Block-Cipher Modes of Operation
Chosen-Ciphertext Attacks
Defining CCA-Security
Padding-Oracle Attacks
References and Additional Reading
Exercises
Message Authentication Codes
Message Integrity
Secrecy vs. Integrity
Encryption vs. Message Authentication
Message Authentication Codes – Definitions
Constructing Secure Message Authentication Codes
A Fixed-Length MAC
Domain Extension for MACs
CBC-MAC
The Basic Construction
Proof of Security
Authenticated Encryption
Definitions
Generic Constructions
Secure Communication Sessions
CCA-Secure Encryption
Information-Theoretic MACs
Constructing Information-Theoretic MACs
Limitations on Information-Theoretic MACs
References and Additional Reading
Exercises
Hash Functions and Applications
Definitions
Collision Resistance
Weaker Notions of Security
Domain Extension: The Merkle–Damgård Transform
Message Authentication Using Hash Functions
Hash-and-MAC
HMAC
Generic Attacks on Hash Functions
Birthday Attacks for Finding Collisions
Small-Space Birthday Attacks
Time/Space Tradeoffs for Inverting Functions
The Random-Oracle Model
The Random-Oracle Model in Detail
Is the Random-Oracle Methodology Sound?
Additional Applications of Hash Functions
Fingerprinting and Deduplication
Merkle Trees
Password Hashing
Key Derivation
Commitment Schemes
References and Additional Reading
Exercises
Practical Constructions of Symmetric-Key Primitives
Stream Ciphers
Linear-Feedback Shift Registers
Adding Nonlinearity
Trivium
RC4
Block Ciphers
Substitution-Permutation Networks
Feistel Networks
DES – The Data Encryption Standard
3DES: Increasing the Key Length of a Block Cipher
AES – The Advanced Encryption Standard
Differential and Linear Cryptanalysis
Hash Functions
Hash Functions from Block Ciphers
MD5
SHA-0, SHA-1, and SHA-2
SHA-3 (Keccak)
References and Additional Reading
Exercises
Theoretical Constructions of Symmetric-Key Primitives
One-Way Functions
Definitions
Candidate One-Way Functions
Hard-Core Predicates
From One-Way Functions to Pseudorandomness
Hard-Core Predicates from One-Way Functions
A Simple Case
A More Involved Case
The Full Proof
Constructing Pseudorandom Generators
Pseudorandom Generators with Minimal Expansion
Increasing the Expansion Factor
Constructing Pseudorandom Functions
Constructing (Strong) Pseudorandom Permutations
Assumptions for Private-Key Cryptography
Computational Indistinguishability
References and Additional Reading
Exercises
III. Public-Key (Asymmetric) Cryptography
Number Theory and Cryptographic Hardness Assumptions
Preliminaries and Basic Group Theory
Primes and Divisibility
Modular Arithmetic
Groups
The Group Z□N
Isomorphisms and the Chinese Remainder Theorem
Primes, Factoring, and RSA
Generating Random Primes
Primality Testing
The Factoring Assumption
The RSA Assumption
Relating the RSA and Factoring Assumptions
Cryptographic Assumptions in Cyclic Groups
Cyclic Groups and Generators
The Discrete-Logarithm/Diffie–Hellman Assumptions
Working in (Subgroups of) Z□p
Elliptic Curves
Cryptographic Applications
One-Way Functions and Permutations
Constructing Collision-Resistant Hash Functions
References and Additional Reading
Exercises
Algorithms for Factoring and Computing Discrete Logarithms
Algorithms for Factoring
Pollard’s p − 1 Algorithm
Pollard’s Rho Algorithm
The Quadratic Sieve Algorithm
Algorithms for Computing Discrete Logarithms
The Pohlig–Hellman Algorithm
The Baby-Step/Giant-Step Algorithm
Discrete Logarithms from Collisions
The Index Calculus Algorithm
Recommended Key Lengths
References and Additional Reading
Exercises
Key Management and the Public-Key Revolution
Key Distribution and Key Management
A Partial Solution: Key-Distribution Centers
Key Exchange and the Diffie–Hellman Protocol
The Public-Key Revolution
References and Additional Reading
Exercises
Public-Key Encryption
Public-Key Encryption – An Overview
Definitions
Security against Chosen-Plaintext Attacks
Multiple Encryptions
Security against Chosen-Ciphertext Attacks
Hybrid Encryption and the KEM/DEM Paradigm
CPA-Security
CCA-Security
CDH/DDH-Based Encryption
El Gamal Encryption
DDH-Based Key Encapsulation
A CDH-Based KEM in the Random-Oracle Model
Chosen-Ciphertext Security and DHIES/ECIES
RSA Encryption
Plain RSA
Padded RSA and PKCS #1 v1.5
CPA-Secure Encryption without Random Oracles
OAEP and RSA PKCS #1 v
A CCA-Secure KEM in the Random-Oracle Model
RSA Implementation Issues and Pitfalls
References and Additional Reading
Exercises
Digital Signature Schemes
Digital Signatures – An Overview
Definitions
The Hash-and-Sign Paradigm
RSA Signatures
Plain RSA
RSA-FDH and PKCS #1 v
Signatures from the Discrete-Logarithm Problem
The Schnorr Signature Scheme
DSA and ECDSA
Signatures from Hash Functions
Lamport’s Signature Scheme
Chain-Based Signatures
Tree-Based Signatures
Certificates and Public-Key Infrastructures
Putting It All Together – SSL/TLS
Signcryption
References and Additional Reading
Exercises
Advanced Topics in Public-Key Encryption
Public-Key Encryption from Trapdoor Permutations
Trapdoor Permutations
Public-Key Encryption from Trapdoor Permutations
The Paillier Encryption Scheme
The Structure of Z□N2
The Paillier Encryption Scheme
Homomorphic Encryption
Secret Sharing and Threshold Encryption
Secret Sharing
Verifiable Secret Sharing
Threshold Encryption and Electronic Voting
The Goldwasser–Micali Encryption Scheme
Quadratic Residues Modulo a Prime
Quadratic Residues Modulo a Composite
The Quadratic Residuosity Assumption
The Goldwasser–Micali Encryption Scheme
The Rabin Encryption Scheme
Computing Modular Square Roots
A Trapdoor Permutation Based on Factoring
The Rabin Encryption Scheme
References and Additional Reading
Exercises
Index of Common Notation
Appendix A: Mathematical Background
Identities and Inequalities
Asymptotic Notation
Basic Probability
The "Birthday" Problem
Finite Fields
Appendix B: Basic Algorithmic Number Theory
Integer Arithmetic
Basic Operations
The Euclidean and Extended Euclidean Algorithms
Modular Arithmetic
Basic Operations
Computing Modular Inverses
Modular Exponentiation
Montgomery Multiplication
Choosing a Uniform Group Element
Finding a Generator of a Cyclic Group
Group-Theoretic Background
Efficient Algorithms
References and Additional Reading
Exercises
References
Index
Author(s)
Biography
Jonathan Katz is a professor of computer science at the University of Maryland, and director of the Maryland Cybersecurity Center. He has published over 100 articles on cryptography, and serves as an editor of the Journal of Cryptology, the premier journal of the field. Prof. Katz has been invited to give introductory lectures on cryptography for audiences in academia, industry, and government, as well as an on-line cryptography course through Coursera.
Yehuda Lindell is a professor of computer science at Bar-Ilan University. He has published more than 90 articles on cryptography and four books, and has considerable industry experience in deploying cryptographic schemes. Professor Lindell lectures widely in both academic and industry venues on both theoretical and applied cryptography, and has been recognized with two prestigious grants from the European Research Council.
Reviews
"The work is comprehensive, rigorous, and yet accessible for dedicated students."
—Computing Reviews, October 2015"… this book fills a significant gap among previous cryptography textbooks by explicitly discussing the philosophy behind this approach, gradually building up the relevant theory and giving a broad overview of the discipline conceived within this framework. The result is a coherent picture of the field that provides a pleasing clarity in its explanation of this perspective through a systematic, step-by-step development of important concepts. … The material from the first edition has been restructured and expanded, with an emphasis on practical aspects that provides a nice counterpoint to the theory and helps to highlight its real-world relevance. … This textbook is appropriate for use in teaching at either an advanced undergraduate or graduate level … a particularly valuable resource for graduate students with a computer science or mathematics background who are seeking a pathway to understanding the current cryptography research literature. In the preface, the authors mention their aim of treating modern cryptography through a unified approach that is rigorous yet accessible—Introduction to Modern Cryptography achieves this admirably."
—Mathematical Reviews, August 2015Praise for the First Edition:
"This book is a comprehensive, rigorous introduction to what the authors name ‘modern’ cryptography. … a novel approach to how cryptography is taught, replacing the older, construction-based approach. … The concepts are clearly stated, both in an intuitive fashion and formally. … I would heartily recommend this book to anyone who is interested in cryptography. … The exercises are challenging and interesting, and can benefit readers of all academic levels."
—IACR Book Reviews, January 2010"Over the past 30 years, cryptography has been transformed from a mysterious art into a mathematically rigorous science. The textbook by Jonathan Katz and Yehuda Lindell finally makes this modern approach to cryptography accessible to a broad audience. Readers of this text will learn how to think precisely about the security of protocols against arbitrary attacks, a skill that will remain relevant and useful regardless of how technology and cryptography standards change. The book uses just enough formalism to maintain precision and rigor without obscuring the development of ideas. It manages to convey both the theory's conceptual beauty and its relevance to practice. I plan to use it every time I teach an undergraduate course in cryptography."
—Salil Vadhan, Harvard University, Cambridge, Massachusetts, USA"The greatest attribute is the fact that the material is presented in such a unified way. This is not just a collection of topics from cryptography thrown together at random. One topic leads effortlessly to the next. As such, this is a virtually indispensable resource for modern cryptography."
—Donald L. Vestal, South Dakota State University, Brookings, USA, MAA Online, July 2008"… an excellent introduction to the theoretical background of cryptography. It would be a fine textbook for an advanced undergraduate (or graduate) course in theoretical computer science for students who have already seen the rudiments of cryptography. It will be a valuable reference for researchers in the field."
—Steven D. Galbraith, Mathematical Reviews, 2009"The book is highly recommended as a textbook in cryptography courses at graduate or advanced undergraduate levels. … covers, in a splendid way, the main notions of current cryptography from the point of view of information-theoretical security. This corresponds indeed to a modern cryptography approach."
—Guillermo Morales-Luna, Zentralblatt MATH, Vol. 1143