CS 442 - Introduction to Cryptography
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 public-key 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
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.
Final grades in the course will be an average of homework grades (20%),
the midterm exam (35%) and comprehensive final exam (45%).
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.
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 private-key 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 one-time pad.
- Definition of perfect secrecy and an equivalent definition. (Ours
are different from the book.) The one-time pad scheme and proof that it is
perfectly secret. Limitations of perfect secrecy.
- Reading: Sections 2.1-2.3 (note the differences between this definition
and ours), 2.5.
- Mon Sept 17 (Lecture 4): Computational Security.
- Making the one-time pad practical. Polynomial time and negligible
funcitons. Computational security of private-key encryption. Pseudorandom
- 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
- Reading: Sections 3.2.2 and 3.3
- Mon Sept 24 (Lecture 6): Encryption and Security Proofs.
Security reductions. Proof that the generalized one-time pad is secure.
Security for multiple encryptions. The necessity of randomized or
stateful encryption. Some real-world 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 CPA-Secure Encryption Schemes
- Review definitions. A CPA-secure encryption scheme from any PRF
and its security proof.
- Reading: Section 3.6.2.
- Mon Oct 8 (Lecture 9): CPA-Secure 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 compress-then-encrypt.
- 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: CBC-MAC. Security for variable-length messages.
- Reading: Sections 4.4, 4.5.
- Thu Oct 25 (Lecture 13): Combining Encryption and MACs
- Encrypt-then-Mac, 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. Subsitution-permutation
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.2-5.4. See also Section 6.6 for the Luby-Rackoff 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): Public-Key Encryption, Textbook RSA
- The need for public-key encryption (PKE). Security notions for PKE,
how they relate to private-key notions and to each other. Textbook
RSA encryption and its insecurity.
- Reading: Sections 9.1-9.3, 10.1, 10.2 through page 341, 10.4 to
- Mon Dec 3 (Lecture 20): Secure PKE Schemes
- Padded RSA and a standardized variant. Chosen-ciphertext security
and why it is important. The CCA-insecurity 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.1-12.3.