Math 158: Cryptography (Fall 2015)

This course will focus on the mathematics of public-key cryptography. This subject presents an appealing introduction to several topics from both mathematics and computer science. Throughout the course, we will discuss both cryptography (encryption and signing algorithms) and cryptanalysis (algorithms to break cryptosystems), in order to illustrate the mistakes that must be avoided in implementing these systems, and the vulnerabilities that may arise as technology improves.

Announcements

  • The final exam has been graded. The mean and median were both 83, with a standard deviation of 19.8.

  • I’m making a small change to the notes policy for the final exam.

    • You may bring one sheet of paper, front and back, with whatever you want on it (handwritten, typed, or photograph of your dog are all acceptable formats). It’s fine to photocopy the same sheet and share it among several people.
    • I will include this document at the back of the exam packet. It includes the textbook’s summary tables of all of the cryptosystems and signature schemes that I will consider to be on the exam syllabus. So there is no need to print this information on your note sheet.

  • Some scheduling remarks for the rest of the term:

    • Problem set 8 will be due in two parts: written on F 11/20 and code on W 11/25. It will be longer than usual due to the extra time. Problem set 9 will be due on F 12/4, and Problem set 10 (the last assignment) will be due on Friday 12/11.
    • Class on W 11/25 will be optional; there will be one optional programming problem based on the day’s content. The topic will be Lenstra’s elliptic curve integer factorization algorithm (section 6.6).
    • We will have class on the first day of reading week, M 11/7. This will be the last day of class.
    • The final exam is on Thursday, 11/17.
  • For the week of November 9-13, my office hours will be Monday 1:30-2:30 and Tuesday 11:30-12:30, due to the exam on Wednesday. There will be no office hours or section on Wednesday or Thursday.
  • The second midterm exam will be held in class on Wednesday, November 11. Topics may include material from: Chapter 2 sections 5,8,9; Chapter 3 sections 1,2,3,4; Chapter 4 sections 1,2,3; and Chapter 5 section 1.
  • My weekly office hours are changing to the following: Wednesday 1:30-2:30 and Thursday 11:30-12:30. During the week September 28-October 2, I will also be available during my originally posted office hours.
  • The first midterm exam will be held in class on Wednesday, October 7. It will cover: Chapter 1 sections 2,3,4,5 and Chapter 2 sections 2,3,4,6,7. Some problems will involve writing algorithms similar to the programming assignments; reasonably precise pseudocode will be sufficient.
  • There is no problem set due on Friday October 9, due to the midterm exam. Problem set 4 will be due on Friday October 16.
  • There will be no class on Wednesday, October 14. Since October 12 is a University holiday, this means that class will only meet on Friday that week.

Textbook and readings

  • The course text is An Introduction to Mathematical Cryptography, Second Edition by Hoffstein, Pipher, and Silverman. The link above will allow you to download the entire book in pdf for free (you must log in with your Brown credentials), and also to buy a discount paperback copy.
  • Python crash course covering many of the basic keywords and syntax to get started with the programming assignments.
  • Suite B Cryptography The NSA’s list of algorithms approved for “Top Secret” communications, with minimum key sizes for each.
  • Python for Non-Programmers contains a number of useful resources and links.
  • Learn Python the Hard Way is a (despite the title) very well-suited to beginners and is quite comprehensive. For our purposes, I suggest focusing on the exercises 0-4, 11, 18, 19, 21, and 29-33 (but read and consider the author’s warning at the end of exercise 0).
  • repl.it is a convenient website to code in Python (and other languages) straight through a web browser, with no installation needed.

Problem sets

  • Problem Set 1 (due 18 September). Reading: Textbook sections 1.1 and 1.2.
  • Problem Set 2 (due 25 September). Reading: textbook sections 1.3-1.5, 2.1-2.3.
  • Problem Set 3 (due 2 October). Reading: textbook sections 2.4,2.6,2.7.
  • Problem Set 4 (due 16 October). Reading: textbook sections 2.5,2.8.
  • Problem Set 5 (due 23 October). Reading: textbook sections 3.1,3.2,3.3.
  • Problem Set 6 (due 30 October). Reading: textbook sections 3.4,4.1,4.2.
  • Problem Set 7 (due 6 November). Reading: textbook sections 4.3,5.1,5.3.
  • Problem Set 8 (written due 20 November; code due 25 November). Reading: textbook sections 5.4,6.1,6.2.
  • Problem Set 9 (due 4 December). Reading: sections 6.3,6.4,6.5 (and 6.6 for extra credit problem).
  • Problem Set 10 (due 11 December). Reading: sections 7.1,7.9,7.10.1.

Exams