Cryptography Made Simple (Information Security and Cryptography)

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 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