Cryptography for Secure Encryption (Universitext)

'This text is intended for a one-semester course in cryptography at the advanced undergraduate/Master's degree level. It is suitable for students from various STEM backgrounds, including engineering, mathematics, and computer science, and may also be attractive for researchers and professionals who want to learn the basics of cryptography. Advanced knowledge of computer science or mathematics (other than elementary programming skills) is not assumed. The book includes more material than can be covered in a single semester. The Preface provides a suggested outline for a single semester course, though instructors are encouraged to select their own topics to reflect their specific requirements and interests. Each chapter contains a set of carefully written exercises which prompts review of the material in the chapter and expands on the concepts. Throughout the book, problems are stated mathematically, then algorithms are devised to solve the problems. Students are tasked to write computer programs (in C++ or GAP) to implement the algorithms. The use of programming skills to solve practical problems adds extra value to the use of this text. This book combines mathematical theory with practical applications to computer information systems. The fundamental concepts of classical and modern cryptography are discussed in relation to probability theory, complexity theory, modern algebra, and number theory. An overarching theme is cyber security: security of the cryptosystems and the key generation and distribution protocols, and methods of cryptanalysis (i.e., code breaking). It contains chapters on probability theory, information theory and entropy, complexity theory, and the algebraic and number theoretic foundations of cryptography. The book then reviews symmetric key cryptosystems, and discusses one-way trap door functions and public key cryptosystems including RSA and ElGamal. It contains a chapter on digital signature schemes, including material on message authentication and forgeries, and chapters on key generation and distribution. It contains a chapter on elliptic curve cryptography, including new material on the relationship between singular curves, algebraic groups and Hopf algebras'. Sommario fornito dall'editore Preface Course Outlines What's Not in the Book Acknowledgments Contents 1 Introduction to Cryptography 1.1 Introduction to Cryptography 1.2 The Players in the Game 1.3 Ciphertext Only Attack: An Example 1.4 Exercises 2 Introduction to Probability 2.1 Introduction to Probability 2.1.1 Abstract Probability Spaces 2.2 Conditional Probability 2.3 Collision Theorems 2.4 Random Variables 2.5 2-Dimensional Random Variables 2.6 Bernoulli's Theorem 2.7 Exercises 3 Information Theory and Entropy 3.1 Entropy 3.1.1 Entropy and Randomness: Jensen's Inequality 3.2 Entropy of Plaintext English 3.2.1 ASCII Encoding 3.3 Joint and Conditional Entropy 3.4 Unicity Distance 3.5 Exercises 4 Introduction to Complexity Theory 4.1 Basics of Complexity Theory 4.2 Polynomial Time Algorithms 4.3 Non-polynomial Time Algorithms 4.4 Complexity Classes P, PP, BPP 4.4.1 Probabilistic Polynomial Time 4.4.2 An Example 4.5 Probabilistic Algorithms for Functions 4.6 Exercises 5 Algebraic Foundations: Groups 5.1 Introduction to Groups 5.2 Examples of Infinite Groups 5.3 Examples of Finite Groups 5.3.1 The Symmetric Group on n Letters Cycle Decomposition 5.3.2 The Group of Residues Modulo n 5.4 Direct Product of Groups 5.5 Subgroups 5.6 Homomorphisms of Groups 5.7 Group Structure 5.7.1 Some Number Theory 5.8 Exercises 6 Algebraic Foundations: Rings and Fields 6.1 Introduction to Rings and Fields 6.1.1 Polynomials in F[x] 6.2 The Group of Units of Zn 6.2.1 A Formula for Euler's Function 6.3 U(Zp) Is Cyclic 6.4 Exponentiation in Zn 6.4.1 Quadratic Residues 6.5 Exercises 7 Advanced Topics in Algebra 7.1 Quotient Rings and Ring Homomorphisms 7.1.1 Quotient Rings 7.1.2 Ring Homomorphisms 7.2 Simple Algebraic Extensions 7.2.1 Algebraic Closure 7.3 Finite Fields 7.4 Invertible Matrices over Zpq 7.5 Exercises 8 Symmetric Key Cryptography 8.1 Simple Substitution Cryptosystems 8.1.1 Unicity Distance of the Simple Substitution Cryptosystem 8.2 The Affine Cipher 8.2.1 Unicity Distance of the Affine Cipher 8.3 The Hill 22 Cipher 8.3.1 Unicity Distance of the Hill 22 Cipher 8.4 Cryptanalysis of the Simple Substitution Cryptosystem 8.5 Polyalphabetic Cryptosystems 8.5.1 The Vigenère Cipher 8.5.2 Unicity Distance of the Vigenère Cipher 8.5.3 Cryptanalysis of the Vigenère Cipher Key Length Is Known Key Length Is Not Known 8.5.4 The Vernam Cipher Perfect Secrecy 8.5.5 Unicity Distance of the Vernam Cipher 8.6 Stream Ciphers 8.7 Block Ciphers 8.7.1 Iterated Block Ciphers Feistel Ciphers The Data Encryption Standard (DES) The Advanced Encryption Standard (AES) 8.8 Exercises 9 Public Key Cryptography 9.1 Introduction to Public Key Cryptography 9.1.1 Negligible Functions 9.1.2 One-Way Trapdoor Functions 9.2 The RSA Public Key Cryptosystem 9.3 Security of RSA 9.3.1 Pollard p-1 9.3.2 Pollard ρ 9.3.3 Difference of Two Squares Fermat Factorization Modular Fermat Factorization 9.4 The ElGamal Public Key Cryptosystem 9.5 Hybrid Ciphers 9.6 Symmetric vs. Public Key Cryptography 9.7 Exercises 10 Digital Signature Schemes 10.1 Introduction to Digital Signature Schemes 10.2 The RSA Digital Signature Scheme 10.3 Signature with Privacy 10.4 Security of Digital Signature Schemes 10.5 Hash Functions and DSS 10.5.1 The Discrete Log Family 10.5.2 The MD-4 Family 10.5.3 Hash-Then-Sign DSS 10.6 Exercises 11 Key Generation 11.1 Linearly Recursive Sequences 11.2 The Shrinking Generator Sequence 11.3 Linear Complexity 11.4 Pseudorandom Bit Generators 11.4.1 Hard-Core Predicates 11.4.2 Hard-Core Predicates and the DLA 11.4.3 The Blum–Micali Bit Generator 11.4.4 The Quadratic Residue Assumption 11.4.5 The Blum–Blum–Shub Bit Generator 11.5 Exercises 12 Key Distribution 12.1 The Diffie–Hellman Key Exchange Protocol 12.2 The Discrete Logarithm Problem 12.2.1 The General DLP 12.2.2 Index Calculus 12.2.3 Efficiency of Index Calculus 12.2.4 The Man-in-the-Middle Attack 12.3 Exercises 13 Elliptic Curves in Cryptography 13.1 The Equation y2=x3+ax+b 13.2 Elliptic Curves 13.3 Singular Curves 13.4 The Elliptic Curve Group 13.4.1 Structure of E(K) 13.5 The Elliptic Curve Key Exchange Protocol 13.5.1 Comparing ECKEP and DHKEP 13.5.2 What Elliptic Curves to Avoid The MOV Attack Supersingular Curves Anomalous Curves 13.5.3 Examples of Good Curves 13.6 Exercises 14 Singular Curves 14.1 The Group Ens(K) 14.2 The DLP in Ens(K) 14.3 The Group Gc(K) 14.4 Ens(K).5-.5.5-.5.5-.5.5-.5Gc(K) 14.5 Exercises References Index