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 efficiently; 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
Previous Page Next Page