Math 75: Mathematical Cryptography
Spring 2016
Course Info:
- Lectures: Monday, Wednesday, Friday, block 2 (1:45 - 3:00 p.m.)
- x-period: Thursday 1:00 - 1:50 p.m.
- Dates: 28 March 2016 - 31 May 2016
- Room: 028 Haldeman Center
- Instructor: John Voight
- Office: 341 Kemeny Hall
- E-mail: jvoight@gmail.com
- Office hours: Monday 3:00 - 4:30 p.m. and Tuesday 10:00 - 11:30 a.m., or by appointment
- Course Web Page: http://www.math.dartmouth.edu/~m75s16/
- Prerequisites: Math 71, or Math 25 and 31, or instructor permission
- Required Texts:
- (HPS) Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman, An Introduction to Mathematical Cryptography, Second edition, 2014.
- (G) Paul Garrett, Making, Breaking Codes: Introduction to Cryptology, 2001.
- (S) Simon Singh, The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography, 2000.
- Recommended Texts: None
- Grading: Grade will be based on weekly homework (50%) and a takehome final cipher challenge (50%).
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 essential prerequisite is familiarity with abstract algebra and a healthy mathematical and computational appetite. Some experience with number theory would also be helpful. We will also be writing some simple computer programs in Python.
| 1 | 28 Mar | (M) | Introduction | ||
| 2 | 30 Mar | (W) | Shift ciphers | HPS 1.3; G 1.1 | HW 1: [PDF] [TeX] |
| 3 | 1 Apr | (F) | Substitution ciphers, permutations, statistics of English | HPS 1.1, 5.1; G 2.3, 2.4, 3.1, 3.3 | S Chapter 1 |
| 4 | 4 Apr | (M) | Affine ciphers, Euclidean algorithm | G 1.2, 1.4, 7.3, 7.4 | |
| 5 | 6 Apr | (W) | Algorithms, big Oh | G 9.1, 9.2, 9.4 | HW 2: [PDF] [TeX] |
| 6 | 7 Apr | (R) | Sage, ASCII | ||
| - | 8 Apr | (F) | No class, JV at CUNY | ||
| 7 | 11 Apr | (M) | Vigenere cipher | HPS 5.2; G 1.3 | S Chapter 2 |
| 8 | 13 Apr | (W) | Cryptanalysis of Vigenere cipher | HPS 4.1, 4.3, 4.4 | HW 3: [PDF] [TeX] |
| 9 | 15 Apr | (F) | Block (Hill) ciphers, inverting matrices | G 7.5, 8.1, 8.2 | |
| 10 | 18 Apr | (M) | Enigma | HPS 1.6 | S Chapters 3-4 Enigma simulators: Mac, WWW (choose Wehrmacht I), Windows |
| 11 | 20 Apr | (W) | Enigma | HW 4: [PDF + Reading] [TeX] | |
| 12 | 22 Apr | (F) | Feistel ciphers, SDES, DES | HPS 8.12; G 6.1, 6.2 | SDES |
| 13 | 25 Apr | (M) | Rijndael (AES) | G 6.3 | Rijndael animation |
| 14 | 27 Apr | (W) | Finite fields | HPS 2.10; G 26.1-26.5 | HW 5: [PDF] [TeX] |
| 15 | 29 Apr | (F) | Public key cryptography, RSA | HPS 2.1, 3.2 | S Chapter 6 |
| 16 | 2 May | (M) | RSA | HPS 3.4 | |
| 17 | 4 May | (W) | Primality testing | HPS 3.3 | HW 6: [PDF] [TeX] |
| 18 | 5 May | (R) | Sage, attacks on RSA | S Chapter 7 | |
| 19 | 6 May | (F) | Pollard rho | HPS 5.5; G 24.1 | |
| 20 | 9 May | (M) | Quadratic sieve | HPS 3.6; G 25.2, 25.4, 25.5 | |
| 21 | 11 May | (W) | Smooth numbers | HPS 3.7 | HW 7: [PDF] [TeX] |
| 22 | 13 May | (F) | Discrete logs | HPS 1.5, 2.2, 2.3; G 7.8 | |
| 23 | 16 May | (M) | Diffie-Hellman, Baby step-giant step | HPS 2.6, 2.7, 5.4; G 27.1, 27.2 | |
| 24 | 18 May | (W) | Pohlig-Hellman (index calculus), CRT | HPS 2.8, 2.9; G 27.3 | HW 8: [PDF] [TeX] |
| 25 | 20 May | (F) | Elgamal, signatures | HPS 4.1-4.3 | |
| 26 | 23 May | (M) | Elliptic curves | HPS 6.1, 6.2; G 28.3, 28.4, 28.5 | |
| 27 | 25 May | (W) | Elliptic curve cryptography, factoring with elliptic curves | HPS 3.5, 6.3, 6.4, 6.6; G 24.2, 28.1 | |
| 28 | 27 May | (F) | Quantum cryptography, wrap-up | HPS 6.5, 8.11 | S Chapter 8 |
| - | 30 May | (M) | No class, Memorial Day |
Homework:
The homework assignments will be assigned on a weekly basis and will be posted above. Homework is due in one week; no late homework will be accepted.
Reading out of Singh "The Code Book" is due the day listed (e.g., read Chapter 1 for Friday, 1 April).
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. Please acknowledge any cooperative work at the end of each assignment.
Plagiarism, collusion, or other violations of the Academic Honor Principle, after consultation, will be referred to the The Committee on Standards.
[PDF] Homework Submission Guidelines
Final cipher challenge:
A final cipher challenge was assigned in place of a final exam.