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