|
|
x | |
Preface |
|
xi | |
|
1 Introduction Joppe W. Bos and Martijn Stam |
|
|
1 | (14) |
|
|
1 | (8) |
|
|
9 | (6) |
|
|
|
2 Lattice Attacks on NTRU and LWE: A History of Refinements Martin R. Albrecht and Leo Ducas |
|
|
15 | (26) |
|
|
15 | (2) |
|
2.2 Notation and Preliminaries |
|
|
17 | (1) |
|
2.3 Lattice Reduction: Theory |
|
|
18 | (2) |
|
2.4 Practical Behaviour on Random Lattices |
|
|
20 | (9) |
|
2.5 Behaviour on LWE Instances |
|
|
29 | (5) |
|
2.6 Behaviour on NTRU Instances |
|
|
34 | (7) |
|
3 History of Integer Factorisation Samuel S. Wagstaff, Jr |
|
|
41 | (37) |
|
3.1 The Dark Ages: Before RS A |
|
|
41 | (6) |
|
3.2 The Enlightenment: RSA |
|
|
47 | (3) |
|
3.3 The Renaissance: Continued Fractions |
|
|
50 | (5) |
|
3.4 The Reformation: A Quadratic Sieve |
|
|
55 | (3) |
|
3.5 The Revolution: A Number Field Sieve |
|
|
58 | (4) |
|
3.6 An Exquisite Diversion: Elliptic Curves |
|
|
62 | (5) |
|
3.7 The Future: How Hard Can Factoring Be? |
|
|
67 | (11) |
|
4 Lattice-Based Integer Factorisation: An Introduction to Coppersmith's Method Alexander May |
|
|
78 | (28) |
|
4.1 Introduction to Coppersmith's Method |
|
|
79 | (1) |
|
4.2 Useful Coppersmith-Type Theorems |
|
|
80 | (5) |
|
4.3 Applications in the Univariate Case |
|
|
85 | (10) |
|
4.4 Multivariate Applications: Small Secret Exponent RSA |
|
|
95 | (5) |
|
4.5 Open Problems and Further Directions |
|
|
100 | (6) |
|
5 Computing Discrete Logarithms Robert Granger and vAntoine Joux |
|
|
106 | (34) |
|
|
106 | (4) |
|
|
110 | (8) |
|
5.3 Some Group Descriptions with Easier Discrete Logarithms |
|
|
118 | (4) |
|
5.4 Discrete Logarithms for XTR and Algebraic Tori |
|
|
122 | (8) |
|
5.5 Discrete Logarithms in Finite Fields of Fixed Characteristic |
|
|
130 | (9) |
|
|
139 | (1) |
|
6 RSA, DH and DSA in the Wild Nadia Heninger |
|
|
140 | (42) |
|
|
140 | (1) |
|
|
141 | (13) |
|
|
154 | (16) |
|
6.4 Elliptic-Curve Diffie--Hellman |
|
|
170 | (4) |
|
|
174 | (7) |
|
|
181 | (1) |
|
7 A Survey of Chosen-Prefix Collision Attacks Marc Stevens |
|
|
182 | (41) |
|
7.1 Cryptographic Hash Functions |
|
|
182 | (4) |
|
7.2 Chosen-Prefix Collisions |
|
|
186 | (4) |
|
7.3 Chosen-Prefix Collision Abuse Scenarios |
|
|
190 | (22) |
|
7.4 MD5 Collision Attacks |
|
|
212 | (11) |
|
|
|
8 Efficient Modular Arithmetic Joppe W. Bos, Thorsten Kleinjung and Dan Page |
|
|
223 | (28) |
|
8.1 Montgomery Multiplication |
|
|
224 | (1) |
|
|
225 | (12) |
|
|
237 | (6) |
|
|
243 | (8) |
|
9 Arithmetic Software Libraries Victor Shoup |
|
|
251 | (42) |
|
|
251 | (3) |
|
9.2 Long-Integer Arithmetic |
|
|
254 | (5) |
|
9.3 Number-Theoretic Transforms |
|
|
259 | (11) |
|
9.4 Arithmetic in Zp[ X] for Multi-Precision p |
|
|
270 | (12) |
|
9.5 Arithmetic in Zp[ X] for Single-Precision p |
|
|
282 | (4) |
|
9.6 Matrix Arithmetic over Zp |
|
|
286 | (3) |
|
9.7 Polynomial and Matrix Arithmetic over Other Finite Rings |
|
|
289 | (1) |
|
9.8 Polynomial and Matrix Arithmetic over Z |
|
|
289 | (2) |
|
|
291 | (2) |
|
10 XTR and Tori Martijn Stam |
|
|
293 | (21) |
|
|
293 | (4) |
|
|
297 | (7) |
|
10.3 The Conservative Use of Tori |
|
|
304 | (4) |
|
10.4 Pairings with Elliptic Curves |
|
|
308 | (3) |
|
10.5 Over the Edge: Cyclotomic Subgroups Recycled |
|
|
311 | (3) |
|
11 History of Cryptographic Key Sizes Nigel P. Smart and Emmanuel Thome |
|
|
314 | (21) |
|
|
314 | (1) |
|
11.2 Attacking Symmetric Algorithms with Software and Hardware |
|
|
315 | (3) |
|
11.3 Software Attacks on Factoring and Discrete Logarithms |
|
|
318 | (5) |
|
11.4 Hardware for Factoring |
|
|
323 | (2) |
|
11.5 Attacking Cryptosystems Based on Elliptic Curves |
|
|
325 | (4) |
|
11.6 Post-Quantum Cryptography |
|
|
329 | (3) |
|
11.7 Key-Size Recommendation |
|
|
332 | (3) |
References |
|
335 | (48) |
Index |
|
383 | |