A Course in Mathematical Cryptography

Description

Cryptography has become essential as bank transactions, credit card infor-mation, contracts, and sensitive medical information are sent through inse-cure channels. This book is concerned with the mathematical, especially algebraic, aspects of cryptography. It grew out of many courses presented by the authors over the past twenty years at various universities and covers a wide range of topics in mathematical cryptography. It is primarily geared towards graduate students and advanced undergraduates in mathematics and computer science, but may also be of interest to researchers in the area. Besides the classical methods of symmetric and private key encryption, the book treats the mathematics of cryptographic protocols and several unique topics such as Group-Based Cryptography Gröbner Basis Methods in Cryptography Lattice-Based Cryptography Focuses on the mathematics of cryptographic protocols. Discusses relevant ideas from computer science and complexity theory. Includes a chapter on noncommutative algebraic cryptography. Contents Preface 1 Basic Ideas of Cryptography 1.1 Mathematical Cryptography 1.2 Cryptography, Cryptanalysis and Cryptosystems 1.3 A Very Brief History of Cryptography 1.4 Encryption and Number Theory 1.5 Public Key Cryptography 1.6 Cryptosystems and the Key Space 1.7 Cryptographic Protocols 1.8 Exercises 2 Symmetric Key Cryptosystems 2.1 Mixed Encryption 2.2 Block Ciphers 2.3 Stream Ciphers 2.4 Feistel Networks, DES and AES 2.5 One-Way Functions and Trapdoors 2.6 Exercises 3 Cryptanalysis and Complexity 3.1 Cryptanalysis and Cryptanalytic Attacks 3.2 Statistical Methods 3.3 Cryptographic Security 3.3.1 Security Proofs 3.4 Perfect Security and the One-Time Pad 3.4.1 Vigènere Encryption and Polyalphabetic Ciphers 3.4.2 Breaking a Protocol 3.5 Complexity of Algorithms 3.6 Exercises 4 Cryptographic Protocols 4.1 Cryptographic Protocols 4.2 Cryptographic Hash Functions 4.3 Authentication Protocols 4.4 Digital Signatures 4.5 Secret Sharing Schemes 4.5.1 The Shamir Secret Sharing Scheme 4.5.2 Alternatives for Secret Sharing Protocols 4.5.3 Verifying Secret Sharing Protocols (VSS) 4.6 Zero-Knowledge Proofs 4.7 Exercises 5 Elementary Number Theoretic Techniques 5.1 Cryptography and Number Theory 5.2 Modular Arithmetic 5.3 Units and the Multiplicative Group Z*n 5.4 The Field Zp and Finite Fields 5.5 Finite Abelian Groups 5.6 Cyclic Groups and Primitive Elements 5.7 The Chinese Remainder Theorem 5.8 Exercises 6 Some Number Theoretic Algorithms 6.1 Algorithms for Public Key Cryptography 6.2 Quadratic Residues and Square Roots 6.3 Modular Square Roots 6.4 Products of Two Primes 6.5 The Discrete Log Problem 6.5.1 Shank’s Baby Step Giant Step Algorithm (BSGS) 6.5.2 Pollard’s ?-Algorithm 6.5.3 The Index Calculus Method 6.6 Primality Testing 6.6.1 Sieving Methods 6.6.2 Fermat’s Primality Testing 6.6.3 Pseudoprimes and Probabilistic Primality Testing 6.6.4 Miller-Rabin Primality Testing 6.6.5 Mersenne Primes and the Lucas-Lehmer Test 6.7 Exercises 7 Public Key Cryptography 7.1 Public Key Cryptography 7.2 Standard Model for Public Key Encryption 7.3 The Diffie-Hellman Key Exchange and Protocol 7.4 ElGamal Encryption 7.4.1 Generalizations of ElGamal 7.5 The RSA Algorithm and Protocol 7.5.1 The RSA Cryptosystem 7.5.2 RSA as a Block Cipher 7.5.3 Practical Implementation of RSA 7.5.4 Feasibility of the RSA Algorithm 7.5.5 Security of RSA 7.5.6 Cryptanalysis of RSA 7.6 Rabin Encryption 7.6.1 Quadratic residues and Rabin Encryption 7.6.2 The Rabin Cryptosystem 7.6.3 Security Equivalence of the Rabin Cryptosystem 7.7 Session Keys and Mixed Encryption 7.8 The RSA Signature Method 7.9 Exercises 8 Elliptic Curve Cryptography 8.1 The ElGamal and Elliptic Curve Encryption System 8.2 Elliptic Curves 8.2.1 Fields and Field Extensions 8.2.2 Elliptic Curves 8.2.3 Elliptic Curve Groups 8.2.4 The Order of an Elliptic Curve Group 8.2.5 Calculating Points in Elliptic Curve Groups 8.3 Elliptic Curve Cryptography 8.4 Cryptoanalysis of Elliptic Curve Cryptosystems 8.5 The MOV-Algorithm 8.6 The Elliptic Curve Digital Signature 8.7 Exercises 9 Basic Concepts from Group Theory 9.1 Groups and Group Theory 9.2 Cosets and Normal Subgroups 9.3 Examples of Groups 9.4 Generators and Group Presentations 9.5 Free Groups and Group Presentations 9.6 Group Presentations 9.6.1 The Modular Group 9.7 Presentations of Subgroups 9.8 Group Decision Problems 9.9 Group Amalgams 9.10 Exercises 10 Group Based Cryptography 10.1 Group Based Methods 10.2 The Magnus Method 10.2.1 The Wagner-Magyarik Method 10.3 Free Group Cryptosystems 10.3.1 An Implementation Within the Classical Modular Group 10.3.2 A Variation Using the Magnus Representation 10.4 Cryptographic Protocols Using Groups 10.5 Non-Abelian Digital Signatures 10.6 Password Security 10.6.1 The Strong Generic Free Group Property 10.6.2 Security Analysis of the Group Randomizer Protocols 10.6.3 Actual Implementation of a Group Randomizer System Protocol 10.7 A Secret Sharing Scheme 10.8 Exercises 11 Braid Group Cryptography 11.1 Cryptographic Platforms and Platform Groups 11.2 The Ko-Lee and AAG Protocols 11.2.1 The Ko-Lee Protocol 11.2.2 The Anshel-Anshel-Goldfeld Protocol 11.3 Some Other Group Based Cryptosystems 11.4 The Shamir Three-Pass 11.5 Hard Group Theoretic Properties 11.6 Braid Group Cryptography 11.7 The Braid Groups 11.7.1 The Artin Presentation 11.7.2 Normal Forms Within Bn 11.7.3 The Pure Braid Group for Bn 11.7.4 Linear Representations of Bn 11.8 Cryptanalysis of Braid Group Cryptosystems 11.8.1 Attacks on the Conjugacy Search Problem 11.8.2 Length Based Attacks 11.8.3 Representation Theoretic Attacks 11.8.4 Braid Group Security Summary 11.9 Some Other Braid Group Based Protocols 11.10 Exercises 12 Further Applications 12.1 Finitely Presented Groups and Cryptography 12.2 Group Theory for Access Control 12.3 Public Key Control Groups 12.4 Diophantine Control Security groups 12.5 The Social Security Control Groups 12.6 Further Extensions of Diffie-Hellman and RSA 12.7 Exercises 13 Commutative Gröbner Basis Methods 13.1 Commutative Gröbner Bases 13.2 Commutative Gröbner Basis Cryptosystems 13.3 Algebraic Attacks Using Gröbner Bases 13.3.1 The Gröbner Basis Attack 13.3.2 The Integer Programming Attack 13.3.3 The SAT Attack 13.4 Exercises 14 Non-Commutative Gröbner Basis Methods 14.1 Non-Commutative Gröbner Bases 14.2 Elimination and its Applications 14.3 Gröbner Bases of Modules 14.4 Non-Commutative GB Cryptosystems 14.5 Exercises 15 Lattice-Based Cryptography 15.1 Lattice-Based Cryptography 15.2 General Cryptoprimitives 15.3 Lattices and Their Properties 15.3.1 The Geometry of Numbers 15.4 Hard Lattice Problems 15.5 Lattice Reduction and Babai’s Algorithm 15.6 Main Lattice Based Cryptosystems 15.6.1 Ajtai’s Hash Function and Cryptosystem 15.6.2 The Ajtai-Dwork Cryptosystem 15.6.3 The GGH Cryptosystem 15.6.4 NTRU Cryptosystem 15.7 Security Proofs 15.8 Exercises Bibliography Index