Math/CS 295: Mathematical Cryptography
Fall 2012
Course Info:
- Course: Mathematical Cryptography
- Lectures: Monday, Wednesday, Friday, 12:50 p.m. - 01:40 p.m.
- Dates: 27 August 2011 - 5 December 2012
- Room: Votey 209
- Instructor: John Voight
- Office: 16 Colchester Ave, Room 207C
- Phone: (802) 656-2271
- E-mail: jvoight@gmail.com
- Office hours: Mondays and Wednesdays, 2:00 - 3:30 p.m.; or just make an appointment!
- Course Web Page: http://www.cems.uvm.edu/~jvoight/295/
- Instructor's Web Page: http://www.cems.uvm.edu/~jvoight/
- Prerequisites: Math 52 (or Math 54) and Math 124 and one of the following: Math 251, Math 255, or permission. To get permission, all you need is some advanced coursework and a healthy dose of curiosity!
- Required Texts: Jeffrey Hoffstein, Jill Pipher, and J.H. Silverman, An Introduction to Mathematical Cryptography, 2010.
Simon Singh, The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography, 2000. - Grading: Weekly homework will count for 55% of the grade. Class participation and preparedness will count for 5% of the grade. A final cipher challenge will count for 40% of the grade.
Syllabus:
[PDF] Syllabus
We live an information age, with technology increasingly integrated into our daily lives. As a result, the security of our information is of the utmost concern, even as the interconnectedness of the Internet makes our data more vulnerable to attack. The ability to encrypt secrets and to conduct a trusted exchange of digital information, once a subject of interest primarily to governments and the military, is now a matter of necessity for us all.
At the end of the day, the foundation of modern cryptography relies upon the difficulty of solving certain mathematical problems; this course is intended to address them from both a mathematical and algorithmic point of view. We will cover some subset of the following topics: conventional encryption techniques, the Hill cipher, DES and SDES, RSA, the Rijndael cipher, discrete logarithms and the Diffie-Hellman key exchange, and elliptic curve cryptography.
All mathematical objects will be defined, so the prerequisites are minimal. Really, all one needs is a healthy mathematical and computational appetite. The class will be driven by applications and examples.
Homework:
Late homework will not be accepted. Standard weekly homework assignments, counting for 60% of the grade, will be due on Fridays.
Be sure to show your work and explain how you got your answer. Correct but incomplete answers will only receive partial credit. Part of the beauty of mathematics is in the elegance of its proofs, and one goal of this course is for you to learn to write mathematics excellently.
Cooperation on homework is permitted (and encouraged), but if you work together, do not take any paper away with you---in other words, you can share your thoughts (say on a blackboard), but you have to walk away with only your understanding. In particular, you must write the solution up on your own.
Plagiarism, collusion, or other violations of the Code of Academic Integrity will be referred to the The Center for Student Ethics and Standards.
[PDF] Homework Submission Guidlines
Homework is due on the same day as the row in which it appears. For an exercise with *, use of a computer is recommended.
| Chapter 1: An Introduction to Cryptography | ||||
| 1 | 27 Aug | (M) | Introduction | |
| 2 | 29 Aug | (W) | 1.1 | |
| 3 | 31 Aug | (F) | 1.2 | "Code Book", Chapter 1 |
| 3 Sep | (M) | No class, Labor Day | ||
| 4 | 5 Sep | (W) | Algorithms | 1.3, 1.4(a), 1.5 |
| 5 | 7 Sep | (F) | Sage | |
| 6 | 10 Sep | (M) | 1.3 | |
| 7 | 12 Sep | (W) | 1.4 | 1.2*, 1.9(a), 1.10(a), 1.11, 1.12* |
| 8 | 14 Sep | (F) | 1.5 | |
| 9 | 17 Sep | (M) | 1.6 | "Code Book", Chapter 3 |
| 10 | 19 Sep | (W) | Enigma | 1.22, 1.24, 1.25*, 1.33, 1.A, 1.B, 1.C |
| 11 | 21 Sep | (F) | Enigma | |
| 12 | 24 Sep | (M) | Enigma | |
| 13 | 26 Sep | (W) | 1.7-1.7.4 video | "Code Book", Chapter 4 |
| 14 | 28 Sep | (F) | 1.7.5, 1.7.6 | 1.D, 1.E |
| Chapter 2: Discrete Logarithms and Diffie-Hellman | ||||
| 15 | 1 Oct | (M) | 2.1, 2.2 | |
| 16 | 3 Oct | (W) | 2.3 | 1.40, 1.41, 1.45 |
| 17 | 5 Oct | (F) | 2.4, 2.5 | "Code Book", Chapter 6 |
| 18 | 8 Oct | (M) | 2.6 | |
| 19 | 10 Oct | (W) | 2.7 | 2.3(b)(c), 2.4, 2.6, 2.8, 2.A |
| 20 | 12 Oct | (F) | 2.9 | |
| Chapter 3: Integer Factorization and RSA | ||||
| 21 | 15 Oct | (M) | 3.1 | "Code Book", Chapter 7 |
| 22 | 17 Oct | (W) | 3.2 | 2.12, 2.16, 2.17(a), 2.17(b)(c)*, 2.28(a), 2.B |
| 23 | 19 Oct | (F) | 3.3 | |
| 24 | 22 Oct | (M) | 3.4 | |
| 25 | 24 Oct | (W) | 3.5 | 3.1(a), 3.1(e)*, 3.6*, 3.8(b), 3.9(a), 3.10, 3.A, 3.B |
| 26 | 26 Oct | (F) | 3.6 | |
| 27 | 29 Oct | (M) | 3.7 | |
| 28 | 31 Oct | (W) | Enigma | |
| 29 | 2 Nov | (F) | 3.7 | 3.13(a), 3.14(a)(b)*, 3.21(b)*, 3.23(a), 3.25(b)* |
| Chapter 4: Combinatorics, Probability, and Information Theory | ||||
| 30 | 5 Nov | (M) | 4.1 | |
| 31 | 7 Nov | (W) | 4.2 | 3.26(e), 3.C |
| 32 | 9 Nov | (F) | 4.2.2 | "Code Book", Chapter 2 |
| 33 | 12 Nov | (M) | 4.4 | |
| 34 | 14 Nov | (W) | 4.5 | 4.11(b), 4.15(a), 4.A*, 4.19 |
| 35 | 16 Nov | (F) | AES | |
| 19-23 Nov | (M-F) | No class, Thanksgiving Recess | ||
| Chapter 5: Elliptic Curves and Cryptography | ||||
| 36 | 26 Nov | (M) | 5.1 | |
| 37 | 28 Nov | (W) | 5.1 | |
| 38 | 30 Nov | (F) | 5.2 | |
| 39 | 3 Dec | (M) | 5.3, 5.4 | |
| 40 | 5 Dec | (W) | 5.5, 5.6 | 5.2, 5.6(a), 5.7, 5.8, 5.A* |
Computational Resources:
Certain problems will be computational in nature and the use of computer algebra packages is encouraged. Please print out and attach your work.
Sage is free software for algebra and number theory. See the download instructions to install it on your machine.
Alternatively, you can open a Sage worksheet by connecting to marykate.uvm.edu (link will only work on campus or on a machine with a VPN client installed); unfortunately, her sister ashley.uvm.edu is very sick right now, but as a backup you may use antigone.uvm.edu. Or just go to the Sage notebook, which is hosted by William Stein at the University of Washington.
Final Cipher Challenge:
There will be no exams in the course. In place of a final exam, there will be a final cipher challenge.
[TeX] [PDF] Final Cipher Challenge (due Thursday, 13 Dec, 10:30 a.m.)
Links:
There are additional resources on the 295 Fall 2010 website.
[PDF] Typos in An Introduction to Mathematical Cryptography
The Enigma simulator for Windows.
The Enigma sim manual.