Preface xii -- 0 Introduction 1 -- 0.1 The Meaning of the Word Cryptography 2 -- 0.2 Symmetric Key Cryptography 2 -- 0.3 Public Key (Asymmetric) Cryptography 5 -- 0.4 Key Establishment 8 -- 0.5 Cryptography - more than just Hiding Secrets 9 -- 0.6 Standards 10 -- 0.7 Attacks 11 -- 1 Congruence Equations 13 -- 1.1 Congruence Arithmetic 13 -- 1.1.1 Computer Examples 17 -- 1.1.2 Problems 18 -- 1.2 The Euclidean Algorithm - Finding Inverses 19 -- 1.2.1 Computer Examples 26 -- 1.2.2 Problems 27 -- 1.3 Discrete Logarithms and Diffie-Hellman Key Exchange 27 -- 1.3.1 Computer Examples 34 -- 1.3.2 Problems 35 -- 1.4 Attacking the Discrete Logarithm 37 -- 1.4.1 Computer Examples 45 -- 1.4.2 Problems 46 -- 2 The ElGamal Scheme 49 -- 2.1 Primitive Roots 49 -- 2.1.1 Computer Examples 55 -- 2.1.2 Problems 55 -- 2.2 The ElGamal Scheme 56 -- 2.2.1 Computer Examples 58 -- 2.2.2 Problems 60 -- 2.3 Security of the ElGamal Scheme 62 -- 2.3.1 Computer Examples 64 -- 2.3.2 Problems 64 -- 3 The RSA Scheme 67 -- 3.1 Euler's Theorem 67 -- 3.1.1 Computer Examples 71 -- 3.1.2 Problems 71 -- 3.2 The RSA Algorithm 71 -- 3.2.1 Computer Examples 76 -- 3.2.2 Problems 78 -- 3.3 RSA Security 79 -- 3.3.1 Computer Examples 85 -- 3.3.2 Problems 87 -- 3.4 Implementing RSA 88 -- 3.4.1 Computer Examples 90 -- 3.4.2 Problems 91 -- 4 Elliptic Curve Cryptography 93 -- 4.1 Elliptic Curves and Elliptic Curve Groups 93 -- 4.1.1 Computer Examples 102 -- 4.1.2 Problems 103 -- 4.2 Elliptic Curve Cryptography 104 -- 4.2.1 Computer Examples 109 -- 4.2.2 Problems 112 -- 4.3 The Elliptic Curve Factoring Scheme 113 -- 4.3.1 Computer Examples 115 -- 4.3.2 Problems 116 -- 5 Digital Signatures 117 -- 5.1 Hash Functions 117 -- 5.1.1 Computer Examples 129 -- 5.1.2 Problems 130 -- 5.2 Digital Signature Schemes 132 -- 5.2.1 Computer Examples 139 -- 5.2.2 Problems 141 -- 5.3 Attacks on Digital Signatures 142 -- 5.3.1 Computer Examples 150 -- 5.3.2 Problems 152 -- 6 Primality Testing 155 -- 6.1 Fermat's Approach and Wilson's Theorem 156.

6.1.1 Computer Examples 157 -- 6.1.2 Problems 158 -- 6.2 The Miller-Selfridge-Rabin Primality Test 158 -- 6.2.1 Computer Examples 164 -- 6.2.2 Problems 164 -- 6.3 True Primality Tests 165 -- 6.3.1 Computer Examples 168 -- 6.4 Mersenne Primes and the Lucas-Lehmer Test 169 -- 6.4.1 Computer Examples 171 -- 6.4.2 Problems 171 -- 6.5 Primes is in P 171 -- 6.5.1 Computer Examples 175 -- 6.5.2 Problems 176 -- 7 Factoring Methods 179 -- 7.1 Fermat Again 180 -- 7.1.1 Computer Examples 183 -- 7.1.2 Problems 185 -- 7.2 The Quadratic Sieve 185 -- 7.2.1 Computer Examples 187 -- 7.2.2 Problems 189 -- 7.3 Pollard's p - 1 and rho Methods 189 -- 7.3.1 Computer Examples 193 -- 7.3.2 Problems194 -- 7.4 Continued Fractions and Factoring194 -- 7.4.1 Computer Examples 200 -- 7.4.2 Problems 203 -- Appendix: Solutions to Problems 207 -- References 231 -- Index 236 -- Notation 239.