Cryptography: Theory and Practice

Description

Through three editions, Cryptography: Theory and Practice, has been embraced by instructors and students alike. It offers a comprehensive primer for the subject’s fundamentals while presenting the most current advances in cryptography. The authors offer comprehensive, in-depth treatment of the methods and protocols that are vital to safeguarding the seemingly infinite and increasing amount of information circulating around the world. Key Features of the Fourth Edition: New chapter on the exciting, emerging new area of post-quantum cryptography (Chapter 9). New high-level, nontechnical overview of the goals and tools of cryptography (Chapter 1). New mathematical appendix that summarizes definitions and main results on number theory and algebra (Appendix A). An expanded treatment of stream ciphers, including common design techniques along with coverage of Trivium. Interesting attacks on cryptosystems, including: padding oracle attack correlation attacks and algebraic attacks on stream ciphers attack on the DUAL-EC random bit generator that makes use of a trapdoor. A treatment of the sponge construction for hash functions and its use in the new SHA-3 hash standard. Methods of key distribution in sensor networks. The basics of visual cryptography, allowing a secure method to split a secret visual message into pieces (shares) that can later be combined to reconstruct the secret. The fundamental techniques cryptocurrencies, as used in Bitcoin and blockchain. The basics of the new methods employed in messaging protocols such as Signal, including deniability and Diffie-Hellman key ratcheting. Cover Half Title Title Page Copyright Page Dedication Table of Contents 1: Introduction to Cryptography 1.1 Cryptosystems and Basic Cryptographic Tools 1.1.1 Secret-key Cryptosystems 1.1.2 Public-key Cryptosystems 1.1.3 Block and Stream Ciphers 1.1.4 Hybrid Cryptography 1.2 Message Integrity 1.2.1 Message Authentication Codes 1.2.2 Signature Schemes 1.2.3 Nonrepudiation 1.2.4 Certificates 1.2.5 Hash Functions 1.3 Cryptographic Protocols 1.4 Security 1.5 Notes and References 2: Classical Cryptography 2.1 Introduction: Some Simple Cryptosystems 2.1.1 The Shift Cipher 2.1.2 The Substitution Cipher 2.1.3 The Affine Cipher 2.1.4 The Vigenère Cipher 2.1.5 The Hill Cipher 2.1.6 The Permutation Cipher 2.1.7 Stream Ciphers 2.2 Cryptanalysis 2.2.1 Cryptanalysis of the Affine Cipher 2.2.2 Cryptanalysis of the Substitution Cipher 2.2.3 Cryptanalysis of the Vigenère Cipher 2.2.4 Cryptanalysis of the Hill Cipher 2.2.5 Cryptanalysis of the LFSR Stream Cipher 2.3 Notes and References Exercises 3: Shannon’s Theory, Perfect Secrecy, and the One-Time Pad 3.1 Introduction 3.2 Elementary Probability Theory 3.3 Perfect Secrecy 3.4 Entropy 3.4.1 Properties of Entropy 3.5 Spurious Keys and Unicity Distance 3.6 Notes and References Exercises 4: Block Ciphers and Stream Ciphers 4.1 Introduction 4.2 Substitution-Permutation Networks 4.3 Linear Cryptanalysis 4.3.1 The Piling-up Lemma 4.3.2 Linear Approximations of S-boxes 4.3.3 A Linear Attack on an SPN 4.4 Differential Cryptanalysis 4.5 The Data Encryption Standard 4.5.1 Description of DES 4.5.2 Analysis of DES 4.6 The Advanced Encryption Standard 4.6.1 Description of AES 4.6.2 Analysis of AES 4.7 Modes of Operation 4.7.1 Padding Oracle Attack on CBC Mode 4.8 Stream Ciphers 4.8.1 Correlation Attack on a Combination Generator 4.8.2 Algebraic Attack on a Filter Generator 4.8.3 Trivium 4.9 Notes and References Exercises 5: Hash Functions and Message Authentication 5.1 Hash Functions and Data Integrity 5.2 Security of Hash Functions 5.2.1 The Random Oracle Model 5.2.2 Algorithms in the Random Oracle Model 5.2.3 Comparison of Security Criteria 5.3 Iterated Hash Functions 5.3.1 The Merkle-Damgård Construction 5.3.2 Some Examples of Iterated Hash Functions 5.4 The Sponge Construction 5.4.1 SHA-3 5.5 Message Authentication Codes 5.5.1 Nested MACs and HMAC 5.5.2 CBC-MAC 5.5.3 Authenticated Encryption 5.6 Unconditionally Secure MACs 5.6.1 Strongly Universal Hash Families 5.6.2 Optimality of Deception Probabilities 5.7 Notes and References Exercises 6: The RSA Cryptosystem and Factoring Integers 6.1 Introduction to Public-key Cryptography 6.2 More Number Theory 6.2.1 The Euclidean Algorithm 6.2.2 The Chinese Remainder Theorem 6.2.3 Other Useful Facts 6.3 The RSA Cryptosystem 6.3.1 Implementing RSA 6.4 Primality Testing 6.4.1 Legendre and Jacobi Symbols 6.4.2 The Solovay-Strassen Algorithm 6.4.3 The Miller-Rabin Algorithm 6.5 Square Roots Modulo n 6.6 Factoring Algorithms 6.6.1 The Pollard p ̶ 1 Algorithm 6.6.2 The Pollard Rho Algorithm 6.6.3 Dixon’s Random Squares Algorithm 6.6.4 Factoring Algorithms in Practice 6.7 Other Attacks on RSA 6.7.1 Computing Ø(n) 6.7.2 The Decryption Exponent 6.7.3 Wiener’s Low Decryption Exponent Attack 6.8 The Rabin Cryptosystem 6.8.1 Security of the Rabin Cryptosystem 6.9 Semantic Security of RSA 6.9.1 Partial Information Concerning Plaintext Bits 6.9.2 Obtaining Semantic Security 6.10 Notes and References Exercises 7: Public-Key Cryptography and Discrete Logarithms 7.1 Introduction 7.1.1 The ElGamal Cryptosystem 7.2 Algorithms for the Discrete Logarithm Problem 7.2.1 Shanks’ Algorithm 7.2.2 The Pollard Rho Discrete Logarithm Algorithm 7.2.3 The Pohlig-Hellman Algorithm 7.2.4 The Index Calculus Method 7.3 Lower Bounds on the Complexity of Generic Algorithms 7.4 Finite Fields 7.4.1 Joux’s Index Calculus 7.5 Elliptic Curves 7.5.1 Elliptic Curves over the Reals 7.5.2 Elliptic Curves Modulo a Prime 7.5.3 Elliptic Curves over Finite Fields 7.5.4 Properties of Elliptic Curves 7.5.5 Pairings on Elliptic Curves 7.5.6 ElGamal Cryptosystems on Elliptic Curves 7.5.7 Computing Point Multiples on Elliptic Curves 7.6 Discrete Logarithm Algorithms in Practice 7.7 Security of ElGamal Systems 7.7.1 Bit Security of Discrete Logarithms 7.7.2 Semantic Security of ElGamal Systems 7.7.3 The Diffie-Hellman Problems 7.8 Notes and References Exercises 8: Signature Schemes 8.1 Introduction 8.1.1 RSA Signature Scheme 8.2 Security Requirements for Signature Schemes 8.2.1 Signatures and Hash Functions 8.3 The ElGamal Signature Scheme 8.3.1 Security of the ElGamal Signature Scheme 8.4 Variants of the ElGamal Signature Scheme 8.4.1 The Schnorr Signature Scheme 8.4.2 The Digital Signature Algorithm 8.4.3 The Elliptic Curve DSA 8.5 Full Domain Hash 8.6 Certificates 8.7 Signing and Encrypting 8.8 Notes and References Exercises 9: Post-Quantum Cryptography 9.1 Introduction 9.2 Lattice-based Cryptography 9.2.1 NTRU 9.2.2 Lattices and the Security of NTRU 9.2.3 Learning With Errors 9.3 Code-based Cryptography and the McEliece Cryptosystem 9.4 Multivariate Cryptography 9.4.1 Hidden Field Equations 9.4.2 The Oil and Vinegar Signature Scheme 9.5 Hash-based Signature Schemes 9.5.1 Lamport Signature Scheme 9.5.2 Winternitz Signature Scheme 9.5.3 Merkle Signature Scheme 9.6 Notes and References Exercises 10: Identification Schemes and Entity Authentication 10.1 Introduction 10.1.1 Passwords 10.1.2 Secure Identification Schemes 10.2 Challenge-and-Response in the Secret-key Setting 10.2.1 Attack Model and Adversarial Goals 10.2.2 Mutual Authentication 10.3 Challenge-and-Response in the Public-key Setting 10.3.1 Public-key Identification Schemes 10.4 The Schnorr Identification Scheme 10.4.1 Security of the Schnorr Identification Scheme 10.5 The Feige-Fiat-Shamir Identification Scheme 10.6 Notes and References Exercises 11: Key Distribution 11.1 Introduction 11.1.1 Attack Models and Adversarial Goals 11.2 Key Predistribution 11.2.1 Diffie-Hellman Key Predistribution 11.2.2 The Blom Scheme 11.2.3 Key Predistribution in Sensor Networks 11.3 Session Key Distribution Schemes 11.3.1 The Needham-Schroeder Scheme 11.3.2 The Denning-Sacco Attack on the NS Scheme 11.3.3 Kerberos 11.3.4 The Bellare-Rogaway Scheme 11.4 Re-keying and the Logical Key Hierarchy 11.5 Threshold Schemes 11.5.1 The Shamir Scheme 11.5.2 A Simplified (t, t)-threshold Scheme 11.5.3 Visual Threshold Schemes 11.6 Notes and References Exercises 12: Key Agreement Schemes 12.1 Introduction 12.1.1 Transport Layer Security (TLS) 12.2 Diffie-Hellman Key Agreement 12.2.1 The Station-to-station Key Agreement Scheme 12.2.2 Security of STS 12.2.3 Known Session Key Attacks 12.3 Key Derivation Functions 12.4 MTI Key Agreement Schemes 12.4.1 Known Session Key Attacks on MTI/A0 12.5 Deniable Key Agreement Schemes 12.6 Key Updating 12.7 Conference Key Agreement Schemes 12.8 Notes and References Exercises 13: Miscellaneous Topics 13.1 Identity-based Cryptography 13.1.1 The Cocks Identity-based Cryptosystem 13.1.2 The Boneh-Franklin Identity-based Cryptosystem 13.2 The Paillier Cryptosystem 13.3 Copyright Protection 13.3.1 Fingerprinting 13.3.2 Identifiable Parent Property 13.3.3 2-IPP Codes 13.3.4 Tracing Illegally Redistributed Keys 13.4 Bitcoin and Blockchain Technology 13.5 Notes and References Exercises A: Number Theory and Algebraic Concepts for Cryptography A.1 Modular Arithmetic A.2 Groups A.2.1 Orders of Group Elements A.2.2 Cyclic Groups and Primitive Elements A.2.3 Subgroups and Cosets A.2.4 Group Isomorphisms and Homomorphisms A.2.5 Quadratic Residues A.2.6 Euclidean Algorithm A.2.7 Direct Products A.3 Rings A.3.1 The Chinese Remainder Theorem A.3.2 Ideals and Quotient Rings A.4 Fields B: Pseudorandom Bit Generation for Cryptography B.1 Bit Generators B.2 Security of Pseudorandom Bit Generators B.3 Notes and References Bibliography Index