xiv PREFACE We encounter a problem that we’ll face again and again in later chapters: an encryption method which seems hard to break is ac- tually vulnerable to a clever attack. All is not lost, however, as the very fast methods of this chapter can be used in tandem with the more powerful methods we discuss later. • Chapters 7 and 8 bring us to the theoretical and practical high point of the book, a complete description of RSA (its name comes from the initials of the three people who described it publicly for the first time—Rivest, Shamir, and Aldeman). For years this was one of the most used encryption schemes. It allows two people who have never met to communicate quickly and securely. Before describing RSA, we first discuss several simpler methods. We dwell in detail on why they seem secure but are, alas, vulnerable to simple attacks. In the course of our analysis we’ll see some ideas on how to improve these methods, which leads us to RSA. The mathematical content of these chapters is higher than earlier in the book. We first intro- duce some basic graph theory and then two gems of mathematics, the Euclidean algorithm and fast exponentiation. Both of these methods allow us to solve problems far faster than brute force sug- gests is possible, and they are the reason that RSA can be done in a reasonable amount of time. Our final needed mathematical ingre- dient is Fermat’s little Theorem. Though it’s usually encountered in a group theory course (as a special case of Lagrange’s theorem), it’s possible to prove it directly and elementarily. Fermat’s result allows the recipient to decrypt the message eﬃciently without it, we would be left with just a method for encryption, which of course is useless. In addition to describing how RSA works and proving why it works, we also explore some of the implementation issues. These range from transmitting messages quickly to verifying the identity of the sender. • In Chapter 9 we discuss the need to detect and correct errors. Often the data is not encrypted, and we are just concerned with ensuring that we’ve updated our records correctly or received the correct file. We motivate these problems through some entertaining riddles. After exploring some natural candidates for error detecting and correcting codes, we see some elegant alternatives that are able to transmit a lot of information with enough redundancy to catch many errors. The general theory involves advanced group theory and lattices, but fortunately we can go quite far using elementary counting. • We describe some of the complexities of modern cryptography in Chapter 10, such as quantum cryptography and steganography. • Chapter 11 is on primality testing and factorization algorithms. In the RSA chapters we see the benefits of the mathematicalization of messages. To implement RSA, we need to be able to find two large

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2013 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.