v
example) once security goals are clearly formulated, it often becomes easier
to understand the design choices made in a particular construction.
We have structured the book so that the only formal prerequisites are a
course in algorithms and a course in discrete mathematics. Even here we rely
on very little material: specifically, we assume some familiarity with basic
probability and big-O notation, modular arithmetic, and the idea of equating
efficient algorithms with those running in polynomial time. These concepts
are reviewed in Appendix A and/or when first used in the book.
Suggestions for course organization. The core material of this book,
which we strongly recommend should be covered in any introductory course
on cryptography, consists of the following (starred sections are excluded in
what follows; see further discussion regarding starred material below):
• Chapters 1–4 (through Section 4.6), discussing classical cryptography,
modern cryptography, and the basics of private-key cryptography (both
private-key encryption and message authentication).
• Chapter 7, introducing concrete mathematical problems believed to be
“hard”, providing the number-theoretic background needed to under-
stand RSA, Diffie-Hellman, and El Gamal, and giving a flavor of how
number-theoretic assumptions are used in cryptography.
• Chapters 9 and 10, motivating the public-key setting and discussing
public-key encryption (including RSA-based schemes and El Gamal).
• Chapter 12, describing digital signature schemes.
• Sections 13.1 and 13.3, introducing the random oracle model and the
RSA-FDH signature scheme.
We believe that this core material — possibly omitting some of the more
in-depth discussion and some proofs — can be covered in a 30–35-hour under-
graduate course. Instructors with more time available could proceed at a more
leisurely pace, e.g., giving details of all proofs and going more slowly when
introducing the underlying group theory and number-theoretic background.
Alternately, additional topics could be incorporated as discussed next.
Those wishing to cover additional material, in either a longer course or a
faster-paced graduate course, will find that the book has been structured to
allow flexible incorporation of other topics as time permits (and depending on
the instructor’s interests). Specifically, some of the chapters and sections are
starred (*). These sections are not less important in any way, but arguably
do not constitute “core material” for an introductory course in cryptography.
As made evident by the course outline just given (which does not include any
starred material), starred chapters and sections may be skipped — or covered
at any point subsequent to their appearance in the book — without affecting
the flow of the course. In particular, we have taken care to ensure that none of
