In this introductory textbook the author explains the key topics in cryptography. He takes a modern approach, where defining what is meant by "secure" is as important as creating something that achieves that goal, and security definitions are central to the discussion throughout. The chapters in Part 1 offer a brief introduction to the mathematical foundations: modular arithmetic, groups, finite fields, and probability; primality testing and factoring; discrete logarithms; elliptic curves; and lattices. Part 2 of the book shows how historical ciphers were broken, thus motivating the design of modern cryptosystems since the 1960s; this part also includes a chapter on information-theoretic security. Part 3 covers the core aspects of modern cryptography: the definition of security; modern stream ciphers; block ciphers and modes of operation; hash functions, message authentication codes, and key derivation functions; the "naive" RSA algorithm; public key encryption and signature algorithms; cryptography based on computational complexity; and certificates, key transport and key agreement. Finally, Part 4 addresses advanced prot ocols, where the parties may have different or even conflicting security goals: secret sharing schemes; commitments and oblivious transfer; zero-knowledge proofs; and secure multi-party computation. The author balances a largely non-rigorous style — many proofs are sketched only — with appropriate formality and depth. For example, he uses the terminology of groups and finite fields so that the reader can understand both the latest academic research and "real-world" documents such as application programming interface descriptions and cryptographic standards. The text employs colour to distinguish between public and private information, and all chapters include summaries and suggestions for further reading. This is a suitable textbook for advanced undergraduate and graduate students in computer science, mathematics and engineering, and for self-study by professionals in information security. While the appendix summarizes most of the basic algebra and notation required, it is assumed that the reader has a basic knowledge of discrete mathematics, probability, and elementary calculus.
Author(s): Nigel P. Smart
Publisher: Springer
Year: 2015
Language: English
Pages: 481
Preface
Further Reading
Contents
Part 1 Mathematical Background
CHAPTER 1 Modular Arithmetic, Groups, Finite Fields and Probability
Chapter Goals
1.1. Modular Arithmetic
1.1.1. Groups
1.1.2. Rings
1.1.3. Euler’s f Function
1.1.4. Multiplicative Inverse Modulo N
1.1.5. The Set (Z/NZ)*
1.2. Finite Fields
1.2.1. Inversion in General Finite Fields
1.2.2. Isomorphisms of Finite Fields
1.2.3. Field Towers and the Frobenius Map
1.3. Basic Algorithms
1.3.1. Greatest Common Divisors
1.3.2. The Euclidean Algorithm
1.3.3. The Extended Euclidean Algorithm
1.3.4. Chinese Remainder Theorem (CRT)
1.3.5. The Legendre Symbol
1.3.6. Computing Square Roots Modulo p
1.3.7. The Jacobi Symbol
1.3.8. Squares and Pseudo-squares Modulo a Composite
1.3.9. Square Roots Modulo n = p·q
1.4. Probability
1.4.1. Bayes’ Theorem
1.4.2. Birthday Paradox
1.5. Big Numbers
Chapter Summary
Further Reading
CHAPTER 2 Primality Testing and Factoring
Chapter Goals
2.1. Prime Numbers
2.1.1. The Prime Number Theorem
2.1.2. Trial Division
2.1.3. Fermat’s Test
2.1.4. Miller–Rabin Test
2.1.5. Primality Proofs
2.1.6. AKS Algorithm
2.2. The Factoring and Factoring-Related Problems
2.3. Basic Factoring Algorithms
2.3.1. Trial Division
2.3.2. Smooth Numbers
2.3.3. Pollard’s P 1 Method
2.3.4. Difference of Two Squares
2.4. Modern Factoring Algorithms
Combining Relations
2.5. Number Field Sieve
2.5.1. The Linear Sieve
2.5.2. Higher-Degree Sieving
Chapter Summary
Further Reading
CHAPTER 3 Discrete Logarithms
Chapter Goals
3.1. The DLP, DHP and DDH Problems
3.2. Pohlig–Hellman
3.3. Baby-Step/Giant-Step Method
3.4. Pollard-Type Methods
3.4.1. Pollard’s Rho Algorithm
3.4.2. Pollard’s Lambda Method
3.4.3. Parallel Pollard’s Rho
3.5. Sub-exponential Methods for Finite Fields
Chapter Summary
Further Reading
CHAPTER 4 Elliptic Curves
Chapter Goals
4.1. Introduction
4.1.1. The Affine Form
4.1.2. Isomorphisms of Elliptic Curves
4.2. The Group Law
4.2.1. The Elliptic Curve Discrete Logarithm Problem (ECDLP)
4.3. Elliptic Curves over Finite Fields
4.3.1. Curves over Fields of Characteristic p > 3
4.3.2. Curves over Fields of Characteristic Two
4.4. Projective Coordinates
4.4.1. Large Prime Characteristic
4.4.2. Even Characteristic
4.5. Point Compression
4.6. Choosing an Elliptic Curve
Chapter Summary
Further Reading
CHAPTER 5 Lattices
Chapter Goals
5.1. Lattices and Lattice Reduction
5.1.1. Vector Spaces
5.1.2. The Gram–Schmidt Process
5.1.3. Lattices
5.1.4. LLL Algorithm
5.1.5. Continued Fractions
5.2. “Hard” Lattice Problems
5.2.1. Shortest Vector Problem
5.2.2. Closest Vector Problem
5.2.3. Bounded-Distance Decoding Problem
5.3. q-ary Lattices
5.4. Coppersmith’s Theorem
Chapter Summary
Further Reading
CHAPTER 6 Implementation Issues
Chapter Goals
6.1. Introduction
6.2. Exponentiation Algorithms
6.2.1. Binary Exponentiation
6.2.2. Window Exponentiation Methods
6.2.3. Sliding Window Method
6.2.4. Generalizations to Any Group
6.3. Special Exponentiation Methods
6.3.1. Small Exponents
6.3.2. Knowing p and q
6.3.3. Multi-exponentiation
6.4. Multi-precision Arithmetic
6.4.1. Addition
6.4.2. Schoolbook Multiplication
6.4.3. Karatsuba Multiplication
6.4.4. Division
6.4.5. Montgomery Arithmetic
6.5. Finite Field Arithmetic
6.5.1. Characteristic-Two Field Division
6.5.2. Characteristic-Two Field Multiplication
6.5.3. Karatsuba Multiplication
6.5.4. Squaring in Characteristic Two
Chapter Summary
Further Reading
Part 2 Historical Ciphers
CHAPTER 7 Historical Ciphers
Chapter Goals
7.1. Introduction
7.2. Shift Cipher
7.3. Substitution Cipher
7.4. Vigen`ere Cipher
7.5. A Permutation Cipher
Chapter Summary
Further Reading
CHAPTER 8 The Enigma Machine
Chapter Goals
8.1. Introduction
8.2. An Equation for the Enigma
8.3. Determining the Plugboard Given the Rotor Settings
8.3.1. Ciphertext Only Attack
8.3.2. Known Plaintext Attack
8.4. Double Encryption of Message Keys
8.5. Determining the Internal Rotor Wirings
8.6. Determining the Day Settings
8.7. The Germans Make It Harder
8.8. Known Plaintext Attack and the Bombes
8.8.1. The Turing/Welchman Bombe
8.8.2. Bombe Stop to Plugboard
8.8.3. Finding the Final Part of the Key
8.9. Ciphertext Only Attack
Chapter Summary
Further Reading
CHAPTER 9 Information-Theoretic Security
Chapter Goals
9.1. Introduction
9.2. Probability and Ciphers
9.2.1. Modified Shift Cipher
9.2.2. Vernam Cipher
9.3. Entropy
9.3.1. Properties of Entropy
9.3.2. Joint and Conditional Entropy
9.3.3. Application to Ciphers
9.4. Spurious Keys and Unicity Distance
9.4.1. Redundancy and Ciphertexts
Chapter Summary
Further Reading
CHAPTER 10 Historical Stream Ciphers
Chapter Goals
10.1. Introduction to Symmetric Ciphers
10.2. Stream Cipher Basics
10.3. The Lorenz Cipher
10.3.1. Baudot Code
10.3.2. Lorenz Operation
10.3.3. The Lorenz Cipher’s Wheels
10.3.4. Lorenz Cipher Operation
10.3.5. Example
10.3.6. Lorenz Key Size
10.4. Breaking the Lorenz Cipher’s Wheels
10.4.1. Ciphertext Only Method
10.4.2. Known Keystream Method
10.4.3. Both Methods Continued
10.4.4. Breaking the Other Wheels
10.5. Breaking a Lorenz Cipher Message
Chapter Summary
Further Reading
Part 3 Modern Cryptography Basics
CHAPTER 11 Defining Security
Chapter Goals
11.1. Introduction
11.2. Pseudo-random Functions and Permutations
11.3. One-Way Functions and Trapdoor One-Way Functions
11.4. Public Key Cryptography
11.5. Security of Encryption
11.5.1. Basic Notions of Security
11.5.2. Modern Notions of Security
11.6. Other Notions of Security
11.6.1. Many Time Security
11.6.2. Real-or-Random
11.6.3. Lunchtime Attacks
11.6.4. Nonce-Based Encryption
11.6.5. Data Encapsulation Mechanisms
11.6.6. Non-malleability
11.6.7. Plaintext Aware
11.6.8. Relations Between Security Notions
11.7. Authentication: Security of Signatures and MACs
11.7.1. Message Authentication Codes
11.7.2. Digital Signature Schemes
11.7.3. Security Definitions for MACs and Digital Signatures
11.8. Bit Security
11.8.1. Hard Predicates for Discrete Logarithms
11.8.2. Hard Predicates for the RSA Problem
11.9. Computational Models: The Random Oracle Model
Chapter Summary
Further Reading
CHAPTER 12 Modern Stream Ciphers
Chapter Goals
12.1. Stream Ciphers from Pseudo-random Functions
12.2. Linear Feedback Shift Registers
12.2.1. Linear Complexity
12.3. Combining LFSRs
12.3.1. Filter Generator
12.3.2. Alternating-Step Generator
12.3.3. Shrinking Generator
12.3.4. The A5/1 Generator
12.3.5. Trivium
12.4. RC4
Chapter Summary
Further Reading
CHAPTER 13 Block Ciphers and Modes of Operation
Chapter Goals
13.1. Introduction to Block Ciphers
13.2. Feistel Ciphers and DES
13.2.1. Overview of DES Operation
13.3. AES
13.3.1. AES Operations
13.4. Modes of Operation
13.4.1. ECB Mode
13.4.2. CBC Mode
13.4.3. OFB Mode
13.4.4. CFB Mode
13.4.5. CTR Mode
13.5. Obtaining Chosen Ciphertext Security
13.5.1. Encrypt-then-MAC
13.5.2. Encrypt-and-MAC
13.5.3. MAC-then-Encrypt
Chapter Summary
Further Reading
CHAPTER 14 Hash Functions, Message Authentication Codes and Key Derivation Functions
Chapter Goals
14.1. Collision Resistance
14.2. Padding
14.3. The Merkle–Damgård Construction
14.3.1. Theoretical Properties of the Merkle–Damgård Construction
14.4. The MD-4 Family
14.4.1. MD-4
14.4.2. SHA-1
14.4.3. SHA-2
14.5. HMAC
14.5.1. NMAC
14.5.2. Building HMAC from NMAC
14.6. Merkle–Damgård-Based Key Derivation Function
14.7. MACs and KDFs Based on Block Ciphers
14.7.1. Message Authentication Codes from Block Ciphers
14.7.2. Key Derivation Function from Block Ciphers
14.8. The Sponge Construction and SHA-3
14.8.1. The Sponge Construction
14.8.2. SHA-3
14.8.3. Sponges With Everything
Chapter Summary
Further Reading
CHAPTER 15 The “Naive” RSA Algorithm
Chapter Goals
15.1. “Naive” RSA Encryption
15.1.1. Rabin Encryption
15.2. “Naive” RSA Signatures
15.3. The Security of RSA
15.3.1. Knowledge of the Private Exponent and Factoring
15.3.2. Knowledge of f(N) and Factoring
15.3.3. Use of a Shared Modulus
15.3.4. Use of a Small Public Exponent
15.4. Some Lattice-Based Attacks on RSA
15.4.1. Håstad’s Attack
15.4.2. Franklin–Reiter Attack and Coppersmith’s Generalization
15.4.3. Wiener’s Attack on RSA
15.4.4. Extension to Wiener’s Attack
15.5. Partial Key Exposure Attacks on RSA
15.5.1. Partial Exposure of the MSBs of the RSA Decryption Exponent
15.5.2. Partial Exposure of Some Bits of the RSA Prime Factors
15.5.3. Partial Exposure of the LSBs of the RSA Decryption Exponent
15.6. Fault Analysis
Chapter Summary
Further Reading
CHAPTER 16 Public Key Encryption and Signature Algorithms
Chapter Goals
16.1. Passively Secure Public Key Encryption Schemes
16.1.1. Goldwasser–Micali Encryption
16.1.2. ElGamal Encryption
16.1.3. Paillier Encryption
16.2. Random Oracle Model, OAEP and the Fujisaki–Okamoto Transform
16.2.1. RSA-OAEP
16.2.2. The Fujisaki–Okamoto Transform
16.3. Hybrid Ciphers
16.3.1. Defining a Key Encapsulation Mechanism
16.3.2. Generically Constructing Hybrid Encryption
16.4. Constructing KEMs
16.4.1. RSA-KEM
16.4.2. The DHIES Encryption Scheme
16.5. Secure Digital Signatures
16.5.1. RSA-FDH
16.5.2. RSA-PSS
16.5.3. The Digital Signature Algorithm
16.5.4. Schnorr Signatures
16.5.5. Nyberg–Rueppel Signatures
16.6. Schemes Avoiding Random Oracles
16.6.1. The Cramer–Shoup Encryption Scheme
16.6.2. Cramer–Shoup Signatures
Chapter Summary
Further Reading
CHAPTER 17 Cryptography Based on Really Hard Problems
Chapter Goals
17.1. Cryptography and Complexity Theory
17.1.1. Decision and Search Problems
17.1.2. The class NP
17.1.3. Average vs Worst-Case Complexity
17.1.4. Random Self-reductions
17.2. Knapsack-Based Cryptosystems
17.3. Worst-Case to Average-Case Reductions
17.4. Learning With Errors (LWE)
17.4.1. Public Key System Based on LWE
17.4.2. Ring-LWE
17.4.3. Public Key System Based on Ring-LWE
17.4.4. Fully Homomorphic Encryption
Chapter Summary
Further Reading
CHAPTER 18 Certificates, Key Transport and Key Agreement
Chapter Goals
18.1. Introduction
18.2. Certificates and Certificate Authorities
18.2.1. Implicit Certificates
18.3. Fresh Ephemeral Symmetric Keys from Static Symmetric Keys
18.3.1. Wide-Mouth Frog Protocol
18.3.2. Needham–Schroeder Protocol
18.3.3. Kerberos
18.4. Fresh Ephemeral Symmetric Keys from Static Public Keys
18.4.1. Key Transport
18.4.2. Diffie–Hellman Key Exchange
18.4.3. Signed Diffie–Hellman
18.4.4. Station-to-Station Protocol
18.4.5. Blake-Wilson–Menezes Protocol
18.4.6. MQV Protocol
18.5. The Symbolic Method of Protocol Analysis
18.6. The Game-Based Method of Protocol Analysis
Chapter Summary
Further Reading
Part 4 Advanced Protocols
CHAPTER 19 Secret Sharing Schemes
Chapter Goals
19.1. Access Structures
19.2. General Secret Sharing
19.2.1. Ito–Nishizeki–Saito Secret Sharing
19.2.2. Replicated Secret Sharing
19.3. Reed–Solomon Codes
19.3.1. Data Recovery
19.3.2. Error Detection
19.3.3. Error Correction
19.3.4. The Berlekamp–Welch Algorithm
19.4. Shamir Secret Sharing
19.5. Application: Shared RSA Signature Generation
Chapter Summary
Further Reading
CHAPTER 20 Commitments and Oblivious Transfer
Chapter Goals
20.1. Introduction
20.2. Commitment Schemes
20.3. Oblivious Transfer
Chapter Summary
Further Reading
CHAPTER 21 Zero-Knowledge Proofs
Chapter Goals
21.1. Showing a Graph Isomorphism in Zero-Knowledge
21.2. Zero-Knowledge and NP
21.3. Sigma Protocols
21.3.1. Schnorr’s Identification Protocol
21.3.2. Formalizing Sigma Protocols
21.3.3. Associated Identification Protocol
21.3.4. Associated Signature Schemes
21.3.5. Non-interactive Proofs
21.3.6. Chaum–Pedersen Protocol
21.3.7. Proving Knowledge of Pedersen Commitments
21.3.8. “Or” Proofs
21.4. An Electronic Voting System
Chapter Summary
Further Reading
CHAPTER 22 Secure Multi-party Computation Chapter Goals
Chapter Goals
22.1. Introduction
22.2. The Two-Party Case
22.2.1. Garbled Circuit Construction
22.2.2. Garbled Circuit Evaluation
22.2.3. Yao’s Protocol
22.3. The Multi-party Case
22.3.1. Addition Gates
22.3.2. Multiplication Gates
22.4. The Multi-party Case
Chapter Summary
Further Reading
Appendix
Basic Mathematical Terminology
A.1. Sets
A.2. Relations
A.3. Functions
A.4. Permutations
A.5. Operations
A.6. Groups
A.7. Rings
A.8. Fields
A.9. Vector Spaces
Index
