Math 252: Mathematics of Public-Key Cryptography (Spring 2019)

This course concerns the mathematical problems underlying public-key ciphers and digital signatures, as well as algorithms to solve them. Topics include discrete logarithms, integer factorization, elliptic curves, and lattices. These topics provide an appealing introduction to several topics in number theory, abstract algebra, and algorithms.

Help hours

• My office hours in SMUD 401 (tentative):
  • Tuesday 1:45-3:15
  • Wednesday 1:45-3:15
  • Friday 1:30-2:30

Handouts

• 1/28: Syllabus
• 3/1: Console Output (Pohlig-Hellman discussion)
• 5/3: NTRU Cryptanalysis challenge (in case you want to try implementing LLL).

Textbook and other links

• The course text is An Introduction to Mathematical Cryptography, 2nd edition. Use this link to download the book in pdf for free (with Amherst credentials) or order an inexpensive paperback copy.
• Starter code and testing notebooks for programming assignments.
• Jupyter hub is a convenient way to develop and test your code from a web browser.<li>CS Circles python tutorial (most relevant sections for our purposes: 0 through 10 and 13, except 2X, 7A, and 8)</li>

Homework

Problem sets will be posted here. All problem sets are due at 10pm, via Gradescope.

• Course Survey / Gradescope instructions (due 1/30)
• Problem Set 1 (written part due 2/6) / Solutions
• Problem Set 2 (due 2/13written 2/15, code 2/18) / Solutions
• Problem Set 3 (written due 2/20; code due 2/22) / Solutions
• Problem Set 4 (due 3/1) / Solutions
• Problem Set 5 (due 3/20) / Solutions
• Problem Set 6 (due 3/27) / Solutions
• Problem Set 7 (due 4/3) / Solutions
• Problem Set 8 (due 4/10) / Solutions
• Problem Set 9 (due 4/17) / Solutions
• Problem Set 10 (due Friday 5/3) / Solutions

Exams

• Midterm 1: Wednesday 3/6

  • Remember to make a one-page note-sheet (front and back)!
  • Practice Exam 1 / Solutions
  • Practice Exam 2 / Solutions (Note: the solution to Problem 4 uses an alternative notation for modular arithmetic, where [a]_p refers to a mod p)
  • Exam / Solutions

• Midterm 2: Wednesday 4/24

  • Remember to make a one-page note-sheet (front and back)!

  • Some exams from previous versions of the course:

    • NOTE: in past versions, midterm 2 came earlier in the semester, before elliptic curves. Therefore I’ve included some previous final exams here, with the elliptic curve problem identified, so you can try those specific problems for review.
    • 2015 Midterm 2 / Solutions (skip #5, since we didn’t discuss groups in general)
    • 2016 Midterm 2 / Solutions
    • 2015 Final exam / Solutions (problems 1, 4, 6, 9, 11 concern elliptic curves)
    • 2016 Final exam / Solutions (problems 3, 6, 10 concern elliptic curves)
    • (solutions to these old exams will be posted early next week)
  • Exam / Solutions

• Final Exam: Monday, May 13 at 9am, in SMUD 206.

  • Remember to make a one-page note-sheet (front and back)!
  • Please bring a calculator if you have one. You should only use the four arithmetic functions.
  • 2015 Final exam / Solutions (skip problems 7(b) and 12, which concern material we didn’t cover this year)
  • 2016 Final exam / Solutions (skip problem 1(h))
  • The final exam will cover content from the entire course, with slightly higher emphasis on material from after the second midterm.
  • Exam / Solutions