Cryptanalytic Attacks on RSA

0387487417......Page 1
Table of Contents......Page 6
Preface......Page 9
Notations......Page 13
1.1 Introduction......Page 19
1.2 Computability, Complexity and Intractability......Page 22
1.3 Effcient Number-Theoretic Algorithms......Page 33
1.4 Intractable Number-Theoretic Problems......Page 59
1.5 Chapter Notes and Further Reading......Page 72
2.1 Introduction......Page 73
2.2 Public-Key Cryptography......Page 78
2.3 RSA Public-Key Cryptography......Page 84
2.4 RSA Problem and RSA Assumption......Page 89
2.5 RSA-Type Crytposystems......Page 91
2.6 Chapter Notes and Further Readings......Page 106
3.1 Introduction......Page 108
3.2 Fermat Factoring Attack......Page 110
3.3 The \"p ± 1\" and ECM Attacks......Page 111
3.4 Quadratic Sieve Attack......Page 115
3.5 Successful QS Attack......Page 120
3.6 Number Field Sieve Attack......Page 122
3.7 Chapter Notes and Further Reading......Page 127
4.1 Introduction......Page 128
4.2 Baby-Step Giant-Step Attack......Page 132
4.3 Silver–Pohlig–Hellman Attack......Page 135
4.4 Index Calculus Attacks......Page 139
4.5 Xedni Calculus Attack......Page 144
4.6 Chapter Notes and Further Reading......Page 149
5.1 Introduction......Page 151
5.2 Order Finding Problem......Page 153
5.3 Quantum Order Finding Attack......Page 155
5.4 Quantum Integer Factorization Attack......Page 158
5.5 Quantum Discrete Logarithm Attack......Page 162
5.6 Chapter Notes and Further Reading......Page 164
6.1 Introduction......Page 165
6.2 Guessing Plaintext Attacks......Page 166
6.3 Blinding Attack on RSA Signatures......Page 167
6.4 Guessing ø(N) Attack......Page 168
6.5 Guessing d Attack......Page 171
6.6 eth Root Attack......Page 175
6.7 Common Modulus Attack......Page 177
6.8 Fixed-Point Attack......Page 180
6.9 Chapter Notes and Further Readings......Page 182
7.1 Introduction......Page 184
7.2 A Theorem of Coppersmith......Page 185
7.3 Short e Attacks for Same Messages......Page 188
7.4 Short e Attacks for Related Messages......Page 192
7.5 Lattice Attack for Stereotyped Messages......Page 198
7.6 Chapter Notes and Further Reading......Page 202
8.1 Introduction......Page 204
8.2 Diophantine Attack......Page 205
8.3 Extended Diophantine Attacks......Page 210
8.4 Small Private CRT-Exponent Attacks......Page 213
8.5 Partial Private Key Exposure Attacks......Page 216
8.6 Chapter Notes and Further Reading......Page 220
9.1 Introduction......Page 222
9.2 Modular Exponentiation Revisited......Page 223
9.3 Timing Attacks......Page 224
9.4 Time Attacks on RSA in OpenSSL......Page 227
9.5 Power (Analysis) Attacks......Page 230
9.6 Random Fault Attacks......Page 231
9.7 Chapter Notes and Further Reading......Page 237
10.1 Introduction......Page 238
10.2 Elliptic Curve-Based Cryptography......Page 239
10.3 Coding-Based Cryptography......Page 240
10.4 Lattice-Based Cryptography......Page 242
10.5 Quantum Cryptography......Page 244
10.6 Conclusions......Page 245
10.7 Chapter Notes and Further Reading......Page 247
Bibliography......Page 248
E......Page 266
P......Page 267
T......Page 268
W......Page 269
About the Author......Page 270