CS 442  Introduction to Cryptography
Fall 2012
Course Overview
This course is an undergraduate introduction to modern cryptography. We'll dig
below the surface of cryptographic primitives and learn how to rigorously
evaluate their security. We'll look at symmetric and publickey encryption,
message authentication, digital signatures, hash functions, and more advanced
topics as time allows. This course will be mathematical in nature, and
while the needed background material on probability and number theory will be
covered in class, students must be comfortable with working to understand
new mathematics.
This course will not teach you everything about how to make your
computer secure. We will be looking at cryptography at a theoretical level
with a choice of topics that looks toward its practical usage. Interested
students should also consider taking CS 419, which gives an introduction to
general computer security.
General Information
Grading
Final grades in the course will be an average of homework grades (20%),
the midterm exam (35%) and comprehensive final exam (45%).
Homeworks
Homework assignments will be posted here roughly every 2 weeks. Students
should turn in neatly written or typeset solutions on time. Late homeworks
will not be accepted. Students are allowed to collaborate in teams of two, but
only in the capacity of discussing the problems. Solutions must be written up
individually, without collaboration, in your own words to show your
understanding. On each assignment, if you choose to collaborate with someone,
indicated the name of your collaborator on the homework you turn in.
Lecture Schedule
A brief summary of each lecture and the associated reading will be posted here.
 Thu Sept 6 (Lecture 1): Introduction
 Overview of cryptography. Basics of privatekey encryption. Classical
ciphers and how to break (cryptanalyze) them.
 Reading: Sections 1.1, 1.2, 1.3.
 Mon Sept 10 (Lecture 2): Provable security overview. Probability review.
 Security definitions, hardness assumptions, and security proofs. Uniform distribution, conditional probability, independence.
 Reading: Section 1.4. See also appendix A.3.
 Thu Sept 13 (Lecture 3): Perfect secrecy and the onetime pad.
 Definition of perfect secrecy and an equivalent definition. (Ours
are different from the book.) The onetime pad scheme and proof that it is
perfectly secret. Limitations of perfect secrecy.
 Reading: Sections 2.12.3 (note the differences between this definition
and ours), 2.5.
 Mon Sept 17 (Lecture 4): Computational Security.
 Making the onetime pad practical. Polynomial time and negligible
funcitons. Computational security of privatekey encryption. Pseudorandom
generators.
 Reading: Sections 3.1.1, 3.1.2, 3.2 (through 3.2.1), 3.3, 3.4 up to Theorem 3.16
 Thu Sept 20 (Lecture 5): Computational Security (cont.).
 Indistinguishability and semantic security. Generic attack against
Pseudorandom generators.
 Reading: Sections 3.2.2 and 3.3
 Mon Sept 24 (Lecture 6): Encryption and Security Proofs.

Security reductions. Proof that the generalized onetime pad is secure.
Security for multiple encryptions. The necessity of randomized or
stateful encryption. Some realworld PRGs.
 Reading: Sections 3.1.3, 3.4.1, 3.4.2 up to "Secure Multiple Encryptions
Using a Stream Cipher".
 Thu Sept 27 (Lecture 7): Pseudorandom Functions and Chosen Plaintext Attack Security.
 Definitions of pseudorandom functions and security against chosen plaintext attacks, and basic facts about the definitions.
 Reading: Sections 3.5 and 3.6.1.
 Mon Oct 1: Class canceled.
 Thu Oct 4 (Lecture 8): Constructing CPASecure Encryption Schemes
 Review definitions. A CPAsecure encryption scheme from any PRF
and its security proof.
 Reading: Section 3.6.2.
 Mon Oct 8 (Lecture 9): CPASecure Encryption Schemes For Long Messages
 Pseudorandom permutations. Modes of operation and their tradeoffs. Begin CCA security.
 Reading: Sections 3.6.3, 3.6.4, begin 3.7.
 Thu Oct 11 (Lecture 10): CCA Security and Message Authentication Codes
 CCA Security, CCA attacks and ciphertext malleability. Begin authentication and MACs.
 Reading: Sections 3.7, 4.1, 4.2, 4.3.
 Mon Oct 15: Class canceled.
 Thu Oct 18 (Lecture 11): Message Authentications Codes
 A MAC for short messages from a PRF. Begin MAC constructions for longer messages. Extra: the CRIME attack on compressthenencrypt.
 Reading: Sections 4.3, 4.4 through page 121. See also the question and first answer
here for a discussion about the principles behind the CRIME attack.
 Mon Oct 22 (Lecture 12): MACs for Long Messages
 MAC constructions for longer messages: CBCMAC. Security for variablelength messages.
 Reading: Sections 4.4, 4.5.
 Thu Oct 25 (Lecture 13): Combining Encryption and MACs
 EncryptthenMac, its security, and why variants are insecure.
 Reading: Sections 4.8, 4.9 to page 150.
See also this paper
about attacks on bad padding implementations.
 Mon Oct 29: Class canceled due to Sandy.
 Thu Nov 1: Class canceled due to Sandy.
 Mon Nov 5: Midterm review.
 Thu Nov 8 Midterm.
 Mon Nov 12 (Lecture 14): Practical PRP Constructions
 Practical security goals for blockciphers. Subsitutionpermutation
networks. Attacks on 1 and 2 rounds.
 Reading: Section 5.1.
 Thu Nov 15 (Lecture 15): Feistel Networks and DES
 Feistel networks, outline of DES. Theoretical result on Feistel networks. Double/triple encryption and meet in the middle attacks.
 Reading: Sections 5.25.4. See also Section 6.6 for the LubyRackoff result
on 3 and 4 round Feistel.
 Mon Nov 19 (Lecture 16): Number Theory I
 Primes, divisbility, modular operations.
 Reading: Sections 7.1.1, 7.1.2, B.1.1, B.2.1, and B.2.3 up to page 507.
 Tue Nov 20 (Lecture 17): Number Theory II
 Modular exponentiations and inverses. Groups and the group Z^{*}_{N}.
 Reading: Sections 7.1.3, 7.1.4.
 Mon Nov 26 (Lecture 18): Assumptions in Number Theory
 Primality testing and generating primes. Factoring and the RSA problem.
 Reading: Section 7.2 except 7.2.2.
 Thu Nov 29 (Lecture 19): PublicKey Encryption, Textbook RSA
 The need for publickey encryption (PKE). Security notions for PKE,
how they relate to privatekey notions and to each other. Textbook
RSA encryption and its insecurity.
 Reading: Sections 9.19.3, 10.1, 10.2 through page 341, 10.4 to
page 357.
 Mon Dec 3 (Lecture 20): Secure PKE Schemes
 Padded RSA and a standardized variant. Chosenciphertext security
and why it is important. The CCAinsecurity of textbook RSA.
 Reading: 10.4.3, 10.6 except for the "El Gamal" note at the end.
 Thu Dec 6 (Lecture 21): Digital Signatures
 Digital signature schemes and their security. Textbook
RSA and why it is not secure. Hashed RSA.
 Reading: Sections 12.112.3.