Computational Number Theory and Modern Cryptography

About the Author ix Preface xi Acknowledgments xiii Part I Preliminaries 1 Introduction 3 1.1 What is Number Theory? 3 1.2 What is Computation Theory? 9 1.3 What is Computational Number Theory? 15 1.4 What is Modern Cryptography? 29 1.5 Bibliographic Notes and Further Reading 32 References 32 2 Fundamentals 35 2.1 Basic Algebraic Structures 35 2.2 Divisibility Theory 46 2.3 Arithmetic Functions 75 2.4 Congruence Theory 89 2.5 Primitive Roots 131 2.6 Elliptic Curves 141 2.7 Bibliographic Notes and Further Reading 154 References 155 Part II Computational Number Theory 3 Primality Testing 159 3.1 Basic Tests 159 3.2 Miller-Rabin Test 168 3.3 Elliptic Curve Tests 173 3.4 AKS Test 178 3.5 Bibliographic Notes and Further Reading 187 References 188 4 Integer Factorization 191 4.1 Basic Concepts 191 4.2 Trial Divisions Factoring 194 4.3 rho and p . 1 Methods 198 4.4 Elliptic Curve Method 205 4.5 Continued Fraction Method 209 4.6 Quadratic Sieve 214 4.7 Number Field Sieve 219 4.8 Bibliographic Notes and Further Reading 231 References 232 5 Discrete Logarithms 235 5.1 Basic Concepts 235 5.2 Baby-Step Giant-Step Method 237 5.3 Pohlig-Hellman Method 240 5.4 Index Calculus 246 5.5 Elliptic Curve Discrete Logarithms 251 5.6 Bibliographic Notes and Further Reading 260 References 261 Part III Modern Cryptography 6 Secret-Key Cryptography 265 6.1 Cryptography and Cryptanalysis 265 6.2 Classic Secret-Key Cryptography 277 6.3 Modern Secret-Key Cryptography 285 6.4 Bibliographic Notes and Further Reading 291 References 291 7 Integer Factorization Based Cryptography 293 7.1 RSA Cryptography 293 7.2 Cryptanalysis of RSA 302 7.3 Rabin Cryptography 319 7.4 Residuosity Based Cryptography 326 7.5 Zero-Knowledge Proof 331 7.6 Bibliographic Notes and Further Reading 335 References 335 8 Discrete Logarithm Based Cryptography 337 8.1 Diffie-Hellman-Merkle Key-Exchange Protocol 337 8.2 ElGamal Cryptography 342 8.3 Massey-Omura Cryptography 344 8.4 DLP-Based Digital Signatures 348 8.5 Bibliographic Notes and Further Reading 351 References 351 9 Elliptic Curve Discrete Logarithm Based Cryptography 353 9.1 Basic Ideas 353 9.2 Elliptic Curve Diffie-Hellman-Merkle Key Exchange Scheme 356 9.3 Elliptic Curve Massey-Omura Cryptography 360 9.4 Elliptic Curve ElGamal Cryptography 365 9.5 Elliptic Curve RSA Cryptosystem 370 9.6 Menezes-Vanstone Elliptic Curve Cryptography 371 9.7 Elliptic Curve DSA 373 9.8 Bibliographic Notes and Further Reading 374 References 375 Part IV Quantum Resistant Cryptography 10 Quantum Computational Number Theory 379 10.1 Quantum Algorithms for Order Finding 379 10.2 Quantum Algorithms for Integer Factorization 385 10.3 Quantum Algorithms for Discrete Logarithms 390 10.4 Quantum Algorithms for Elliptic Curve Discrete Logarithms 393 10.5 Bibliographic Notes and Further Reading 397 References 397 11 Quantum Resistant Cryptography 401 11.1 Coding-Based Cryptography 401 11.2 Lattice-Based Cryptography 403 11.3 Quantum Cryptography 404 11.4 DNA Biological Cryptography 406 11.5 Bibliographic Notes and Further Reading 409 References 410 Index 413