CS 442: Cryptography

Spring 2024

General Information

Course Overview

This course is an undergraduate introduction to cryptography, whose aim is to present the theoretical foundations of cryptosystems used in the real world. This course covers the theory, application, and implementation of mathematical techniques used to secure modern communications. Topics include symmetric and public-key encryption, message integrity, hash functions, block-cipher design and analysis, number theory, and digital signatures.

The required textbook for this course is Introduction to Modern Cryptography by Katz and Lindell, 3rd edition.

Prerequisites: Programming skills equivalent to CS 111 (Introduction to Computer Science), CS 206 (Introduction to Discrete Structure II) and CS 344 (Design and Analysis of Computer Algorithms).

Course Requirements

There will be five assignments each given 2 weeks to complete. The assignments are designed to review what has been taught in class so far. The students will need to digest and reformulate the lecture content to successfully complete the assignments. The assignments consist of programming tasks, algorithm designs and cryptanalysis. The choice of language is flexible, but C/C++/java or python are recommended. Some assignments will have a networking component with the networking code provided for you in a particular language. It is assumed you can pick up what is needed to complete the assignments. students are expected to have "mathematical maturity" since many of the concepts will be abstract, rigorous definitions and proofs will be given, and some new mathematics (e.g., group theory, number theory) will be introduced. Basic background in discrete mathematics (probability, modular arithmetic) is assumed. Discussion about assignment problems on Canvas is encouraged.

To assess that students have acquired basic literacy in all the concepts, tools, and techniques they are taught, they will be given one midterm and one final exam in the semester. The exams will be "open book" with no electronic devices permitted.

The final course grade is not curved. What this means is that there is no predetermined percentage of students who will get As, Bs, Cs, etc. Instead, every student's final grade is determined by how well he or she can demonstrate his/her understanding of the material. This also means that students in the class are not competing with each other.

Schedule (subject to change, please see the Canvas course website for updated schedule)

Lecture Topic
Week 1 Introduction and overview. Private-key cryptography. The syntax of private-key encryption. The shift cipher. ASCII, hex, and the ASCII shift cipher. Elementary cryptanalysis and frequency analysis. The Vigenere cipher.
Week 2 Modern cryptography: definitions, assumptions, and proofs. Perfect secrecy. The one-time pad. Proving security of the one-time pad. Randomness generation and implementing the one-time pad. Limitations of perfect secrecy. Toward computational notions of security.
Week 3 A computational notion of security. Pseudorandomness and pseudorandom generators. The pseudo-OTP. Proofs by reduction, and a proof of security for the pseudo-OTP. Security for multiple encryptions.
Week 4 Drawbacks of deterministic encryption. Chosen-plaintext attacks and CPA-security. Pseudorandom functions. Pseudorandom permutations and block ciphers. CPA-security from pseudorandom functions.
Week 5 Block-cipher and stream-cipher modes of operation. Message integrity and message authentication codes (MACs). Defining security for MACs. A fixed-length MAC. MACs for arbitrary-length messages. CBC-MAC.
Week 6 CBC-MAC. Chosen-ciphertext attacks and CCA-security. Padding-oracle attacks. Authenticated encryption and generic constructions. Secure sessions
Week 7 Hash functions and collision resistance. Birthday attacks on hash functions. The Merkle-Damgard transform. HMAC. Hash functions as random oracles. Additional applications of hash functions.
Week 8 Practical constructions of stream ciphers. LFSRs. Adding non-linearity. Correlation attacks. Trivium. RC4. Practical constructions of block ciphers. Substitution-permutation networks (SPNs). Attacks on reduced-round SPNs.
Wekk 9 Feistel networks. The Data Encryption Standard (DES). 2DES and triple-DES. Meet-in-the-middle attacks. The Advanced Encryption Standard (AES). Practical constructions of hash functions: the Davies-Meyer construction. Basic number theory and algorithmic number theory. Modular arithmetic. Efficient exponentiation.
Week 10 Efficient exponentiation. Group theory. Primality testing, the factoring assumption, and the RSA assumption.
Week 11 The RSA assumption. Cyclic groups. The discrete-logarithm assumption and the Diffie-Hellman assumptions. Algorithms for factoring and computing discrete logarithms; concrete parameters. Drawbacks of private-key cryptography. Key exchange and the Diffie-Hellman key-exchange protocol.
Week 12 The public-key setting. Public-key encryption: syntax and definitions of security. Definitions of security for public-key encryption. El Gamal encryption. El Gamal encryption. Hybrid encryption and the KEM/DEM paradigm.
Week 13 RSA-based encryption. Padded RSA (PKCS #1 v1.5). RSA-OAEP (PKCS #1 v2). Digital signatures. The hash-and-sign paradigm. RSA-based signatures. (EC)DSA. Certificates and public-key infrastructures.
Week 14 Certificates and public-key infrastructures. SSL/TLS. Final review. Quantum computing and post-quantum cryptography.

Academic Honesty

You are free to discuss the problem sets with others. However, the actual writeup of your assignments must be done ONLY by yourself (and without copying from notes or other sources!). In addition, you must acknowledge your sources and the discussions in your submission. Please read the Academic Integrity Policy for full details. If you are having trouble with the course, come speak to me!for full details. If you are having trouble with the course, come speak to me!