Instructor: Poorvi Vora, poorvi@gwu.edu, 706 Philips Hall. Office Hours: 1-4 pm, Wed.

TA: Yu-An Sun, ysun.hosp@gmail.com, 720G, Philips Hall. Office Hours: 5:30-8:30pm, Tues; 4-7 pm, Thurs.

Text: Douglas Stinson, "Cryptography: Theory and Practice", Third Edition, 2005.

Course Content: Classical ciphers and cryptanalysis, Shannon's perfect secrecy, Feistel ciphers and DES, SPN's and AES, linear and differential cryptanalysis, public-key crypto (RSA, Discrete Log), hash functions, digital signatures, authentication.

Prerequisites: Discrete Mathematics, some complexity theory

Grading: HWs (30%), Quizzes (15%), two tests (15% each), a final exam (25%).
Late HWs are allowed till the HW solution is made available, but will be multiplied by a factor of (1.0 - n*0.1) where n is the number of days the submission is delayed. So, for example, if you submit your HW two days late, your grade on that HW will be multiplied by 0.8.

284 and 162 will be graded separately. If you are an undergrad, please consult your adviser before choosing to take 284; graduate credit for 284 is not automatic for undergrads, but all those enrolled in 284 will be graded together.

Course Outline

Planned Schedule

14 January 2008, Lecture 1: Classical Ciphers and their cryptanalysis. Slides All of chapter 1 from the text except sections 1.1.5, 1.1.7, 1.2.3, 1.2.4, 1.2.5 and theorems in section 1.1.3. We will not be covering Hill Ciphers (sections 1.1.5 and 1.2.4) or cryptanalysis of the Vigenere Cipher (section 1.2.3) in this course, but we will cover stream ciphers and their cryptanalysis (sections 1.1.7 and 1.2.5) in lecture 4, and the theorems from section 1.1.3 in lectures 2 and 10. Further Reading (not necessary, and you do not need any of the proofs) Modular Arithmetic Class Notes, CSCI 124 Groups Class Notes, CS 124 (the theorem in this will be covered next week)

21 January 2008, Holiday: Martin Luther King Jr. Day

28 January 2008, Lecture 2: GCD and basic Euclidean Algorithm. Notes: GCD Basic Euclidean Algorithm Euclidean Algorithm for Inverse Slides: GCD Basic Euclidean Algorithm Euclidean Algorithm for Inverse Theorem 1.1 from section 1.1.3 with a proof not in the book. Section 5.2.1 (pages 163-164). HW1 assigned: Due on 4 February Quiz 1 GCD Practice Problems Modular Inverse Practice Problems

4 February 2008, Lecture 3: Block Ciphers: Substitution-Permutation Networks, Feistel Ciphers. Slides 3.1. 3.2 from text, section 2 from Heys' report. Quiz 2 References H. M. Heys, Section 2, "A Tutorial on Linear and Differential Cryptanalysis", Technical Report CORR 2001-17, Centre for Applied Cryptographic Research, Department of Combinatorics and Optimization, University of Waterloo, Mar. 2001. (Also appears in Cryptologia, vol. XXVI, no. 3, pp. 189-221, 2002.)

11 February 2008, Lecture 4: AES, DES. Slides Sections 3.5-3.7 from text. HW2 assigned: Due February 25 Sample Input File, SPN; Sample Output File, SPN; Sample Input File, Feistel; Sample Output File, Feistel Quiz 3 References DES Standard AES Standard Animation of AES Encryption

18 February 2008, Holiday: Presidents' Day

25 February 2008, Note Test Postponed to March 3 Lecture 5: Probability Theory Slides Section 2.2 from text

3 March 2008, Lecture 6: Test 1: Classical, Block Ciphers, some number theory (modulo m arithmetic, inverses, GCD, Euclidean algorithms for gcd and inverse), probability theory, Lectures 1-5, except Bayes' theorem. Quiz 4

10 March 2008, Lecture 7: Shannon Secrecy. Slides Sections 2.1-2.3 from text. HW3 assigned: Due March 28 Quiz 5 References Claude E. Shannon, "Communication Theory of Secrecy Systems", Bell System Technical Journal, vol.28-4, page 656--715, 1949.

17 March 2008,Spring Break Practice Problems: 1.11, 3.1-3.4, 3.7

24 March 2008 Lecture 8: Complete Shannon Secrecy. Product Cryptosystems Sections 2.2, 2.3, 2.7 from text. Quiz 6 References Claude E. Shannon, "Communication Theory of Secrecy Systems", Bell System Technical Journal, vol.28-4, page 656--715, 1949.

31 March 2008, Lecture 9: Stream Ciphers. Linear Cryptanalysis. Slides: Stream Ciphers Cryptanalysis Sections 1.1.7, 3.3 from text. 2.4 (no Huffman encodings), HW4 assigned (only for 284. 162 students may do it for extra credit). Due April 21 Quiz 7 References Coppersmith, Krawczyk, Mansour. "The Shrinking Generator", Crypto '93, LNCS 773, pages 22-39. Springer-Verlag, 1994. Beth and Piper, "The stop-and-go-generator" in Advances in Cryptology: Proceedings of Eurocrypt 84, Lecture Notes in Computer Science, Berlin: SpringerVerlag 1985, vol. 209, pp. 88-92. H. M. Heys, Section 2, "A Tutorial on Linear and Differential Cryptanalysis", Technical Report CORR 2001-17, Centre for Applied Cryptographic Research, Department of Combinatorics and Optimization, University of Waterloo, Mar. 2001. (Also appears in Cryptologia, vol. XXVI, no. 3, pp. 189-221, 2002.)

7 April 2008, Lecture 10: Differential Cryptanalysis, Entropy. Slides: Cryptanalysis Entropy Sections 2.4 (no Huffman encodings), 3.4 from text. Quiz 8 References H. M. Heys, Section 2, "A Tutorial on Linear and Differential Cryptanalysis", Technical Report CORR 2001-17, Centre for Applied Cryptographic Research, Department of Combinatorics and Optimization, University of Waterloo, Mar. 2001. (Also appears in Cryptologia, vol. XXVI, no. 3, pp. 189-221, 2002.)

14 April 2008, Lecture 11: Test 2. Shannon Secrecy, Product Ciphers, Stream Ciphers, Entropy, Cryptanalysis. Lectures 7-10.

21 April 2008, Lecture 12: Efficient Exponentiation, RSA Slides: Efficient Exponentiation, RSA Sections 5.1 and 5.3 from text. See also Fast Exponentiation notes and practice examples. Quiz 9 Extra Credit: HW 5 Due May 12

28 April 2008, Lecture 13: Number theory: Lagrange theorem on group order, CRT, RSA Correctness Proof. Sections 5.2.2 and 5.2.3 (only Thm. 5.4) from text Quiz 10

30 April 2008, Wednesday, Lecture 14 El Gamal. Hash Functions. Digital Signatures. Slides: El Gamal. Hash Functions. Digital Signatures. Quiz 11

12 May 2008, Monday, 5:20-7:20 pm, 2020 K St. Room 7. Final Exam. Comprehensive: Lectures 1-14.