Modern Cryptography and Elliptic Curves: A Beginner's Guide (Student Mathematical Library) (Student Mathematical Library, 83)

This book offers the beginning undergraduate student some of the vista of modern mathematics by developing and presenting the tools needed to gain an understanding of the arithmetic of elliptic curves over finite fields and their applications to modern cryptography. This gradual introduction also makes a significant effort to teach students how to produce or discover a proof by presenting mathematics as an exploration, and at the same time, it provides the necessary mathematical underpinnings to investigate the practical and implementation side of elliptic curve cryptography (ECC). Elements of abstract algebra, number theory, and affine and projective geometry are introduced and developed, and their interplay is exploited. Algebra and geometry combine to characterize congruent numbers via rational points on the unit circle, and group law for the set of points on an elliptic curve arises from geometric intuition provided by Bézout's theorem as well as the construction of projective space. The structure of the unit group of the integers modulo a prime explains RSA encryption, Pollard's method of factorization, Diffie-Hellman key exchange, and ElGamal encryption, while the group of points of an elliptic curve over a finite field motivates Lenstra's elliptic curve factorization method and ECC. The only real prerequisite for this book is a course on one-variable calculus; other necessary mathematical topics are introduced on-the-fly. Numerous exercises further guide the exploration. -- Provided by publisher Cover Title page Contents Preface Introduction Chapter 1. Three Motivating Problems 1.1. Fermat’s Last Theorem 1.2. The Congruent Number Problem 1.3. Cryptography Chapter 2. Back to the Beginning 2.1. The Unit Circle: Real vs. Rational Points 2.2. Parametrizing the Rational Points on the Unit Circle 2.3. Finding all Pythagorean Triples 2.4. Looking for Underlying Structure: Geometry vs. Algebra 2.5. More about Points on Curves 2.6. Gathering Some Insight about Plane Curves 2.7. Additional Exercises Chapter 3. Some Elementary Number Theory 3.1. The Integers 3.2. Some Basic Properties of the Integers 3.3. Euclid’s Algorithm 3.4. A First Pass at Modular Arithmetic 3.5. Elementary Cryptography: Caesar Cipher 3.6. Affine Ciphers and Linear Congruences 3.7. Systems of Congruences Chapter 4. A Second View of Modular Arithmetic: \Z_{n} and U_{n} 4.1. Groups and Rings 4.2. Fractions and the Notion of an Equivalence Relation 4.3. Modular Arithmetic 4.4. A Few More Comments on the Euler Totient Function 4.5. An Application to Factoring Chapter 5. Public-Key Cryptography and RSA 5.1. A Brief Overview of Cryptographic Systems 5.2. RSA 5.3. Hash Functions 5.4. Breaking Cryptosystems and Practical RSA Security Considerations Chapter 6. A Little More Algebra 6.1. Towards a Classification of Groups 6.2. Cayley Tables 6.3. A Couple of Non-abelian Groups 6.4. Cyclic Groups and Direct Products 6.5. Fundamental Theorem of Finite Abelian Groups 6.6. Primitive Roots 6.7. Diffie–Hellman Key Exchange 6.8. ElGamal Encryption Chapter 7. Curves in Affine and Projective Space 7.1. Affine and Projective Space 7.2. Curves in the Affine and Projective Plane 7.3. Rational Points on Curves 7.4. The Group Law for Points on an Elliptic Curve 7.5. A Formula for the Group Law on an Elliptic Curve 7.6. The Number of Points on an Elliptic Curve Chapter 8. Applications of Elliptic Curves 8.1. Elliptic Curves and Factoring 8.2. Elliptic Curves and Cryptography 8.3. Remarks on a Post-Quantum Cryptographic World Appendix A. Deeper Results and Concluding Thoughts A.1. The Congruent Number Problem and Tunnell’s Solution A.2. A Digression on Functions of a Complex Variable A.3. Return to the Birch and Swinnerton-Dyer Conjecture A.4. Elliptic Curves over \C Appendix B. Answers to Selected Exercises B.1. Chapter 2 B.2. Chapter 3 B.3. Chapter 4 B.4. Chapter 5 B.5. Chapter 6 B.6. Chapter 7 Bibliography Index Back Cover This book offers the beginning undergraduate student some of the vista of modern mathematics by developing and presenting the tools needed to gain an understanding of the arithmetic of elliptic curves over finite fields and their applications to modern cryptography. This gradual introduction also makes a significant effort to teach students how to produce or discover a proof by presenting mathematics as an exploration, and at the same time, it provides the necessary mathematical underpinnings to investigate the practical and implementation side of elliptic curve cryptography (ECC). Elements of abstract algebra, number theory, and affine and projective geometry are introduced and developed, and their interplay is exploited. Algebra and geometry combine to characterize congruent numbers via rational points on the unit circle, and group law for the set of points on an elliptic curve arises from geometric intuition provided by Bézout's theorem as well as the construction of projective space. The structure of the unit group of the integers modulo a prime explains RSA encryption, Pollard's method of factorization, Diffie-Hellman key exchange, and ElGamal encryption, while the group of points of an elliptic curve over a finite field motivates Lenstra's elliptic curve factorization method and ECC. The only real prerequisite for this book is a course on one-variable calculus; other necessary mathematical topics are introduced on-the-fly. Numerous exercises further guide the exploration. -- Provided by publisher