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

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.

The course is designed for students with no prior experience in abstract algebra or programming. It serves as an introduction to those topics, meant to prepare students for more advanced courses. Students with prior experience are welcome, however.

You can find materials from previous offerings of this course here: 2020, 2019, 2016, 2015. The 2015 and 2016 courses, taught at Brown, were sligtly different in style and emphasis.

Time and location

• Monday, Tuesday, Wednesday, and Friday: 3:00-3:50pm in SMUD 205.
• See Moodle page for the Zoom link during the first week.

Help hours

• My office hours in SMUD 401:
  • Tuesday 12:30-1:50
  • Wednesday 10:30-12:00
  • Friday 9:30-10:30
• Our math fellow, Luka Duranovic, will have office hours at the following times.
  • Sunday 7:30-9:00pm in SMUD 006 (likely on Zoom on 2/13)
  • Tuesday 7:30-9:00pm in SMUD 006

Handouts

• Syllabus
• Boardwork from the my tablet can be found at this Dropbox link.
• Desmos demo on elliptic curve addition
• Desmos demo on associativity of EC addition

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 or order a $25 paperback copy. If you are off the campus network, try this link, or look up “springerlink” (one word) in the Amherst College library catalog.
• Starter code and testing notebooks
• CS Circles python tutorial (most relevant sections for our purposes: 0 through 10 and 13, except 2X, 7A, and 8)

Homework

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

• Gradescope submission information for all written assignments.
• PSet 1. Due Wednesday 2/16 (written part), and Friday 2/18 (code) at 10pm on Gradescope.
• PSet 2. Due Wednesday 2/23 (both written and code).
• PSet 3. Due Wednesday 3/2 Friday 3/4.
• PSet 4. Due Wednesday 3/9.
• (No problem set the week 3/21-25, due to Midterm 1)
• PSet 5. Due Friday 4/1.
• PSet 6. Due Wednesday 4/6.
• PSet 7. Due Wednesday 4/13.
• PSet 8. Due Wednesday 4/20.
• PSet 9. Due Wednesday 4/27.
• PSet 10 (now complete). Due Friday 5/13.

Exams

• Midterm 1 will be on Friday 3/25 in class.
  • Exam / Solutions
  • Remember to make a one-page note-sheet (front and back)! Tables 2.2 and 2.3 from the textbook (summary of Diffie-Hellman and Elgamal) will be included in the exam packet, so you do not need to copy any of that information to your note sheet.
  • Coverage: anything discussed in class up to Friday 3/11. This includes the following textbook sections: 1.2, 1.3, 1.4, 1.5, 2.1, 2.2, 2.3, 2.4, 2.6, 2.7.
  • Some old exams, for review. Note that coverage and emphasis differs on these exams, and in particular the 2015 and 2016 exams are somewhat more difficult that ours is likely to be.
    • 2020 midterm 1 / Solutions
    • 2019 midterm 1 / Solutions
    • 2016 midterm 1 / Solutions
    • 2015 midterm 1 / Solutions
• Midterm 2 will be Wednesday 5/4 in class.
  • Exam / Solutions
  • Remember to make a one-page note-sheet (front and back)! Summary tables for all cryptosystems we’ve studied will be included in the exam packet, so you do not need to copy any of that information to your note sheet.
  • Coverage: anything discussed in class between Monday 3/14 and Wednesday 4/27. This includes the following textbook sections: 2.8-9, 3.1-4, 4.1-3, 6.1-4.
  • Some old exams, for review. Note that coverage and emphasis differs on these exams, and in particular the 2015 and 2016 exams are somewhat more difficult that ours is likely to be. The 2015 and 2016 exams were earlier in the semester than our midterm 2, so they do not include content on elliptic curves. Solutions will be posted early next week.
    • 2015 midterm 2 / Solutions
    • 2016 midterm 2 / Solutions
    • 2019 midterm 2 / Solutions
  • Some old final exams. You may wish to consult these for problems about elliptic curves.
    • 2015 final exam (problems 1, 4, 6, 9, 11 concern elliptic curves) / Solutions
    • 2016 final exam (problems 3, 6, 10 concern elliptic curves) / Solutions
    • 2019 final exam (problem 2 concerns elliptic curves) / Solutions
• The final exam will be Monday 5/23, 2-5pm in SMUD 014.
  • Remember to make a one-page note-sheet (front and back)! Summary tables for all cryptosystems we’ve studied will be included in the exam packet, so you do not need to copy any of that information to your note sheet.
  • Coverage: cumulative, up to class on Tuesday 5/10. In particular, the last two class meetings, about lattice reduction to attack NTRU, will not appear on the exam. The material after Midterm 2 will have slightly higher weight, since it has not yet been covered on an exam.
  • Some old final exams are linked above, under Midterm 2 materials.
  • Exam / Solutions