| |
| |
| |
Classical Cryptography | |
| |
| |
| |
Introduction: Some Simple Cryptosystems | |
| |
| |
| |
The Shift Cipher | |
| |
| |
| |
The Substitution Cipher | |
| |
| |
| |
The Affine Cipher | |
| |
| |
| |
The Vigenere Cipher | |
| |
| |
| |
The Hill Cipher | |
| |
| |
| |
The Permutation Cipher | |
| |
| |
| |
Stream Ciphers | |
| |
| |
| |
Cryptanalysis | |
| |
| |
| |
Cryptanalysis of the Affine Cipher | |
| |
| |
| |
Cryptanalysis of the Substitution Cipher | |
| |
| |
| |
Cryptanalysis of the Vigenere Cipher | |
| |
| |
| |
Cryptanalysis of the Hill Cipher | |
| |
| |
| |
Cryptanalysis of the LFSR Stream Cipher | |
| |
| |
| |
Notes | |
| |
| |
Exercises | |
| |
| |
| |
Shannon's Theory | |
| |
| |
| |
Introduction | |
| |
| |
| |
Elementary Probability Theory | |
| |
| |
| |
Perfect Secrecy | |
| |
| |
| |
Entropy | |
| |
| |
| |
Huffman Encodings | |
| |
| |
| |
Properties of Entropy | |
| |
| |
| |
Spurious Keys and Unicity Distance | |
| |
| |
| |
Product Cryptosystems | |
| |
| |
| |
Notes | |
| |
| |
Exercises | |
| |
| |
| |
Block Ciphers and the Advanced Encryption Standard | |
| |
| |
| |
Introduction | |
| |
| |
| |
Substitution-Permutation Networks | |
| |
| |
| |
Linear Cryptanalysis | |
| |
| |
| |
The Piling-up Lemma | |
| |
| |
| |
Linear Approximations of S-boxes | |
| |
| |
| |
A Linear Attack on an SPN | |
| |
| |
| |
Differential Cryptanalysis | |
| |
| |
| |
The Data Encryption Standard | |
| |
| |
| |
Description of DES | |
| |
| |
| |
Analysis of DES | |
| |
| |
| |
The Advanced Encryption Standard | |
| |
| |
| |
Description of AES | |
| |
| |
| |
Analysis of AES | |
| |
| |
| |
Modes of Operation | |
| |
| |
| |
Notes and References | |
| |
| |
Exercises | |
| |
| |
| |
Cryptographic Hash Functions | |
| |
| |
| |
Hash Functions and Data Integrity | |
| |
| |
| |
Security of Hash Functions | |
| |
| |
| |
The Random Oracle Model | |
| |
| |
| |
Algorithms in the Random Oracle Model | |
| |
| |
| |
Comparison of Security Criteria | |
| |
| |
| |
Iterated Hash Functions | |
| |
| |
| |
The Merkle-Damgard Construction | |
| |
| |
| |
The Secure Hash Algorithm | |
| |
| |
| |
Message Authentication Codes | |
| |
| |
| |
Nested MACs and HMAC | |
| |
| |
| |
CBC-MAC and Authenticated Encryption | |
| |
| |
| |
Unconditionally Secure MACs | |
| |
| |
| |
Strongly Universal Hash Families | |
| |
| |
| |
Optimality of Deception Probabilities | |
| |
| |
| |
Notes and References | |
| |
| |
Exercises | |
| |
| |
| |
The RSA Cryptosystem and Factoring Integers | |
| |
| |
| |
Introduction to Public-key Cryptography | |
| |
| |
| |
More Number Theory | |
| |
| |
| |
The Euclidean Algorithm | |
| |
| |
| |
The Chinese Remainder Theorem | |
| |
| |
| |
Other Useful Facts | |
| |
| |
| |
The RSA Cryptosystem | |
| |
| |
| |
Implementing RSA | |
| |
| |
| |
Primality Testing | |
| |
| |
| |
Legendre and Jacobi Symbols | |
| |
| |
| |
The Solovay-Strassen Algorithm | |
| |
| |
| |
The Miller-Rabin Algorithm | |
| |
| |
| |
Square Roots Modulo n | |
| |
| |
| |
Factoring Algorithms | |
| |
| |
| |
The Pollard p - 1 Algorithm | |
| |
| |
| |
The Pollard Rho Algorithm | |
| |
| |
| |
Dixon's Random Squares Algorithm | |
| |
| |
| |
Factoring Algorithms in Practice | |
| |
| |
| |
Other Attacks on RSA | |
| |
| |
| |
Computing [phi] (n) | |
| |
| |
| |
The Decryption Exponent | |
| |
| |
| |
Wiener's Low Decryption Exponent Attack | |
| |
| |
| |
The Rabin Cryptosystem | |
| |
| |
| |
Security of the Rabin Cryptosystem | |
| |
| |
| |
Semantic Security of RSA | |
| |
| |
| |
Partial Information Concerning Plaintext Bits | |
| |
| |
| |
Optimal Asymmetric Encryption Padding | |
| |
| |
| |
Notes and References | |
| |
| |
Exercises | |
| |
| |
| |
Public-key Cryptography and Discrete Logarithms | |
| |
| |
| |
The ElGamal Cryptosystem | |
| |
| |
| |
Algorithms for the Discrete Logarithm Problem | |
| |
| |
| |
Shanks' Algorithm | |
| |
| |
| |
The Pollard Rho Discrete Logarithm Algorithm | |
| |
| |
| |
The Pohlig-Hellman Algorithm | |
| |
| |
| |
The Index Calculus Method | |
| |
| |
| |
Lower Bounds on the Complexity of Generic Algorithms | |
| |
| |
| |
Finite Fields | |
| |
| |
| |
Elliptic Curves | |
| |
| |
| |
Elliptic Curves over the Reals | |
| |
| |
| |
Elliptic Curves Modulo a Prime | |
| |
| |
| |
Properties of Elliptic Curves | |
| |
| |
| |
Point Compression and the ECIES | |
| |
| |
| |
Computing Point Multiples on Elliptic Curves | |
| |
| |
| |
Discrete Logarithm Algorithms in Practice | |
| |
| |
| |
Security of ElGamal Systems | |
| |
| |
| |
Bit Security of Discrete Logarithms | |
| |
| |
| |
Semantic Security of ElGamal Systems | |
| |
| |
| |
The Diffie-Hellman Problems | |
| |
| |
| |
Notes and References | |
| |
| |
Exercises | |
| |
| |
| |
Signature Schemes | |
| |
| |
| |
Introduction | |
| |
| |
| |
Security Requirements for Signature Schemes | |
| |
| |
| |
Signatures and Hash Functions | |
| |
| |
| |
The ElGamal Signature Scheme | |
| |
| |
| |
Security of the ElGamal Signature Scheme | |
| |
| |
| |
Variants of the ElGamal Signature Scheme | |
| |
| |
| |
The Schnorr Signature Scheme | |
| |
| |
| |
The Digital Signature Algorithm | |
| |
| |
| |
The Elliptic Curve DSA | |
| |
| |
| |
Provably Secure Signature Schemes | |
| |
| |
| |
One-time Signatures | |
| |
| |
| |
Full Domain Hash | |
| |
| |
| |
Undeniable Signatures | |
| |
| |
| |
Fail-stop Signatures | |
| |
| |
| |
Notes and References | |
| |
| |
Exercises | |
| |
| |
| |
Pseudo-random Number Generation | |
| |
| |
| |
Introduction and Examples | |
| |
| |
| |
Indistinguishability of Probability Distributions | |
| |
| |
| |
Next Bit Predictors | |
| |
| |
| |
The Blum-Blum-Shub Generator | |
| |
| |
| |
Security of the BBS Generator | |
| |
| |
| |
Probabilistic Encryption | |
| |
| |
| |
Notes and References | |
| |
| |
Exercises | |
| |
| |
| |
Identification Schemes and Entity Authentication | |
| |
| |
| |
Introduction | |
| |
| |
| |
Challenge-and-Response in the Secret-key Setting | |
| |
| |
| |
Attack Model and Adversarial Goals | |
| |
| |
| |
Mutual Authentication | |
| |
| |
| |
Challenge-and-Response in the Public-key Setting | |
| |
| |
| |
Certificates | |
| |
| |
| |
Public-key Identification Schemes | |
| |
| |
| |
The Schnorr Identification Scheme | |
| |
| |
| |
Security of the Schnorr Identification Scheme | |
| |
| |
| |
The Okamoto Identification Scheme | |
| |
| |
| |
The Guillou-Quisquater Identification Scheme | |
| |
| |
| |
Identity-based Identification Schemes | |
| |
| |
| |
Notes and References | |
| |
| |
Exercises | |
| |
| |
| |
Key Distribution | |
| |
| |
| |
Introduction | |
| |
| |
| |
Diffie-Hellman Key Predistribution | |
| |
| |
| |
Unconditionally Secure Key Predistribution | |
| |
| |
| |
The Blom Key Predistribution Scheme | |
| |
| |
| |
Key Distribution Patterns | |
| |
| |
| |
Fiat-Naor Key Distribution Patterns | |
| |
| |
| |
Mitchell-Piper Key Distribution Patterns | |
| |
| |
| |
Session Key Distribution Schemes | |
| |
| |
| |
The Needham-Schroeder Scheme | |
| |
| |
| |
The Denning-Sacco Attack on the NS Scheme | |
| |
| |
| |
Kerberos | |
| |
| |
| |
The Bellare-Rogaway Scheme | |
| |
| |
| |
Notes and References | |
| |
| |
Exercises | |
| |
| |
| |
Key Agreement Schemes | |
| |
| |
| |
Introduction | |
| |
| |
| |
Diffie-Hellman Key Agreement | |
| |
| |
| |
The Station-to-station Key Agreement Scheme | |
| |
| |
| |
Security of STS | |
| |
| |
| |
Known Session Key Attacks | |
| |
| |
| |
MTI Key Agreement Schemes | |
| |
| |
| |
Known Session Key Attacks on MTI/A0 | |
| |
| |
| |
Key Agreement Using Self-certifying Keys | |
| |
| |
| |
Encrypted Key Exchange | |
| |
| |
| |
Conference Key Agreement Schemes | |
| |
| |
| |
Notes and References | |
| |
| |
Exercises | |
| |
| |
| |
Public-key Infrastructure | |
| |
| |
| |
Introduction: What is a PKI? | |
| |
| |
| |
A Practical Protocol: Secure Socket Layer | |
| |
| |
| |
Certificates | |
| |
| |
| |
Certificate Life-cycle Management | |
| |
| |
| |
Trust Models | |
| |
| |
| |
Strict Hierarchy Model | |
| |
| |
| |
Networked PKIs | |
| |
| |
| |
The Web Browser Model | |
| |
| |
| |
Pretty Good Privacy | |
| |
| |
| |
The Future of PKI? | |
| |
| |
| |
Alternatives to PKI | |
| |
| |
| |
Identity-based Cryptography | |
| |
| |
| |
The Cocks Identity-based Encryption Scheme | |
| |
| |
| |
Notes and References | |
| |
| |
Exercises | |
| |
| |
| |
Secret Sharing Schemes | |
| |
| |
| |
Introduction: The Shamir Threshold Scheme | |
| |
| |
| |
A Simplified (t, t)-threshold Scheme | |
| |
| |
| |
Access Structures and General Secret Sharing | |
| |
| |
| |
The Monotone Circuit Construction | |
| |
| |
| |
Formal Definitions | |
| |
| |
| |
Information Rate and Construction of Efficient Schemes | |
| |
| |
| |
The Vector Space Construction | |
| |
| |
| |
An Upper Bound on the Information Rate | |
| |
| |
| |
The Decomposition Construction | |
| |
| |
| |
Notes and References | |
| |
| |
Exercises | |
| |
| |
| |
Multicast Security and Copyright Protection | |
| |
| |
| |
Introduction to Multicast Security | |
| |
| |
| |
Broadcast Encryption | |
| |
| |
| |
An Improvement using Ramp Schemes | |
| |
| |
| |
Multicast Re-keying | |
| |
| |
| |
The Blacklisting Scheme | |
| |
| |
| |
The Naor-Pinkas Re-keying Scheme | |
| |
| |
| |
Logical Key Hierarchy | |
| |
| |
| |
Copyright Protection | |
| |
| |
| |
Fingerprinting | |
| |
| |
| |
Identifiable Parent Property | |
| |
| |
| |
2-IPP Codes | |
| |
| |
| |
Tracing Illegally Redistributed Keys | |
| |
| |
| |
Notes and References | |
| |
| |
Exercises | |
| |
| |
Further Reading | |
| |
| |
Bibliography | |
| |
| |
Index | |