Computational Cryptography: Algorithmic Aspects of Cryptology

Description

The area of computational cryptography is dedicated to the development of effective methods in algorithmic number theory that improve implementation of cryptosystems or further their cryptanalysis. This book is a tribute to Arjen K. Lenstra, one of the key contributors to the field, on the occasion of his 65th birthday, covering his best-known scientific achievements in the field. Students and security engineers will appreciate this no-nonsense introduction to the hard mathematical problems used in cryptography and on which cybersecurity is built, as well as the overview of recent advances on how to solve these problems from both theoretical and practical applied perspectives. Beginning with polynomials, the book moves on to the celebrated Lenstra–Lenstra–Lovász lattice reduction algorithm, and then progresses to integer factorization and the impact of these methods to the selection of strong cryptographic keys for usage in widely used standards. Cover Series information Endorsements Title page Copyright information Contents List of Contributors Preface 1 Introduction 1.1 Biographical Sketch 1.2 Outline PART I CRYPTANALYSIS 2 Lattice Attacks on NTRU and LWE: A History of Refinements 2.1 Introduction 2.2 Notation and Preliminaries 2.3 Lattice Reduction: Theory 2.4 Practical Behaviour on Random Lattices 2.5 Behaviour on LWE Instances 2.6 Behaviour on NTRU Instances 3 History of Integer Factorisation 3.1 The Dark Ages: Before RSA 3.2 The Enlightenment: RSA 3.3 The Renaissance: Continued Fractions 3.4 The Reformation: A Quadratic Sieve 3.5 The Revolution: A Number Field Sieve 3.6 An Exquisite Diversion: Elliptic Curves 3.7 The Future: How Hard Can Factoring Be? 4 Lattice-Based Integer Factorisation: An Introduction to Coppersmith’s Method 4.1 Introduction to Coppersmith’s Method 4.2 Useful Coppersmith-Type Theorems 4.3 Applications in the Univariate Case 4.4 Multivariate Applications: Small Secret Exponent RSA 4.5 Open Problems and Further Directions 5 Computing Discrete Logarithms 5.1 Introduction 5.2 Elliptic Curves 5.3 Some Group Descriptions with Easier Discrete Logarithms 5.4 Discrete Logarithms for XTR and Algebraic Tori 5.5 Discrete Logarithms in Finite Fields of Fixed Characteristic 5.6 Conclusion 6 RSA, DH and DSA in the Wild 6.1 Introduction 6.2 RSA 6.3 Diffie–Hellman 6.4 Elliptic-Curve Diffie–Hellman 6.5 (EC)DSA 6.6 Conclusion 7 A Survey of Chosen-Prefix Collision Attacks 7.1 Cryptographic Hash Functions 7.2 Chosen-Prefix Collisions 7.3 Chosen-Prefix Collision Abuse Scenarios 7.4 MD5 Collision Attacks PART II IMPLEMENTATIONS 8 Efficient Modular Arithmetic 8.1 Montgomery Multiplication 8.2 Arithmetic for RSA 8.3 Arithmetic for ECC 8.4 Special Arithmetic 9 Arithmetic Software Libraries 9.1 Introduction 9.2 Long-Integer Arithmetic 9.3 Number-Theoretic Transforms 9.4 Arithmetic in Z[sub(p)][X] for Multi-Precision p 9.5 Arithmetic in Z[sub(p)][X] for Single-Precision p 9.6 Matrix Arithmetic over Z[sub(p)] 9.7 Polynomial and Matrix Arithmetic over Other Finite Rings 9.8 Polynomial and Matrix Arithmetic over Z 9.9 The Future of NTL 10 XTR and Tori 10.1 The Birth of XTR 10.2 The Magic of XTR 10.3 The Conservative Use of Tori 10.4 Pairings with Elliptic Curves 10.5 Over the Edge: Cyclotomic Subgroups Recycled 11 History of Cryptographic Key Sizes 11.1 Introduction 11.2 Attacking Symmetric Algorithms with Software and Hardware 11.3 Software Attacks on Factoring and Discrete Logarithms 11.4 Hardware for Factoring 11.5 Attacking Cryptosystems Based on Elliptic Curves 11.6 Post-Quantum Cryptography 11.7 Key-Size Recommendation References Index