Introduction to Modern Cryptography, 3/Ed > 암호

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