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.
Author(s): Joppe Bos (editor), Martijn Stam (editor)
Series: London Mathematical Society Lecture Note Series, Series Number 469
Edition: 1
Publisher: Cambridge University Press
Year: 2022
Language: English
Pages: 398
Tags: Cryptography; Cryptanalysis; RSA; DH; DSA
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
