Public Key Cryptography

Professor Lynn Batten holds the Deakin Chair in Mathematics and is the Director of the Information Security Research Group at Deakin University. Her research interests include combinatorial geometry, computer network security and computational chemistry. As Associate Dean for Academic and Industrial Research at the University of Manitoba, her former institution, she established a number of agreements between the University and various industry and government sectors.

• Preface xii 0 Introduction 10.1 The Meaning of the Word Cryptography 20.2 Symmetric Key Cryptography 20.3 Public Key (Asymmetric) Cryptography 50.4 Key Establishment 80.5 Cryptography — more than just Hiding Secrets 90.6 Standards 100.7 Attacks 111 Congruence Equations 131.1 Congruence Arithmetic 131.1.1 Computer Examples 171.1.2 Problems 181.2 The Euclidean Algorithm — Finding Inverses 191.2.1 Computer Examples 261.2.2 Problems 271.3 Discrete Logarithms and Diffie-Hellman Key Exchange 271.3.1 Computer Examples 341.3.2 Problems 351.4 Attacking the Discrete Logarithm 371.4.1 Computer Examples 451.4.2 Problems 462 The ElGamal Scheme 492.1 Primitive Roots 492.1.1 Computer Examples 552.1.2 Problems 552.2 The ElGamal Scheme 562.2.1 Computer Examples 582.2.2 Problems 602.3 Security of the ElGamal Scheme 622.3.1 Computer Examples 642.3.2 Problems 643 The RSA Scheme 673.1 Euler's Theorem 673.1.1 Computer Examples 713.1.2 Problems 713.2 The RSA Algorithm 713.2.1 Computer Examples 763.2.2 Problems 783.3 RSA Security 793.3.1 Computer Examples 853.3.2 Problems 873.4 Implementing RSA 883.4.1 Computer Examples 903.4.2 Problems 914 Elliptic Curve Cryptography 934.1 Elliptic Curves and Elliptic Curve Groups 934.1.1 Computer Examples 1024.1.2 Problems 1034.2 Elliptic Curve Cryptography 1044.2.1 Computer Examples 1094.2.2 Problems 1124.3 The Elliptic Curve Factoring Scheme 1134.3.1 Computer Examples 1154.3.2 Problems 1165 Digital Signatures 1175.1 Hash Functions 1175.1.1 Computer Examples 1295.1.2 Problems 1305.2 Digital Signature Schemes 1325.2.1 Computer Examples 1395.2.2 Problems 1415.3 Attacks on Digital Signatures 1425.3.1 Computer Examples 1505.3.2 Problems 1526 Primality Testing 1556.1 Fermat's Approach and Wilson's Theorem 1566.1.1 Computer Examples 1576.1.2 Problems 1586.2 The Miller-Selfridge-Rabin Primality Test 1586.2.1 Computer Examples 1646.2.2 Problems 1646.3 True Primality Tests  1656.3.1 Computer Examples 1686.4 Mersenne Primes and the Lucas-Lehmer Test 1696.4.1 Computer Examples 1716.4.2 Problems 1716.5 Primes is in P 1716.5.1 Computer Examples 1756.5.2 Problems 1767 Factoring Methods 1797.1 Fermat Again 1807.1.1 Computer Examples 1837.1.2 Problems 1857.2 The Quadratic Sieve 1857.2.1 Computer Examples 1877.2.2 Problems 1897.3 Pollard's p - 1 and rho Methods 1897.3.1 Computer Examples 1937.3.2 Problems1947.4 Continued Fractions and Factoring1947.4.1 Computer Examples 2007.4.2 Problems 203Appendix: Solutions to Problems 207References 231Index 236Notation 239

“This is a book of great pedagogical value. . . The book is a bright exposition of the mathematical methods most used in public key cryptography, and it is very motivating due to its numerous computational examples and rigorous treatment.”  (Zentralblatt  MATH, 1 August 2013)“The book is suitable as a university text for years three and above, and I recommend that every computer scientist read it. I would be inclined to describe this book as offering “what every computer scientist should know about public key cryptography.”  (Computing Reviews, 9 September 2013)