Math 5248: Cryptology and Number Theory (Spring 2015)

Lectures: MW 1:00-2:15 in Vincent Hall 113.

Instructor: Gregg Musiker (musiker "at" math.umn.edu)
(To ensure faster responses to emails, please include the course number 5248 in the subject line in email correspondences.)

NEW Office Hours: (In Vincent Hall 251) M 2:30-3:20, W 10:10-11:00, Th 1:00-1:50, or by appointment.

Course Syllabus: 5248

Course Description:

This is an introductory course in the mathematics of cryptography, the subject of how to make ciphers and break them, and related areas of number theory. Both symmetric and public key cryptosystems will be introduced. The math used in this course will be heavy on modular arithmetic, which will be introduced and covered in some depth. It also makes some use of elementary counting and probability, plus a tiny bit of linear algebra and matrices.

Prerequisites: Two semesters of sophomore level mathematics (or the equivalent). Students will be expected to have some familiarity with proof techniques, such as mathematical induction.

Textbook:

"Cryptology and Number Theory" by Paul Garrett, available at Alpha Print in Dinkytown (next to McDonald's), 1407 4th St SE., 612-379-8535. Used copies from previous years, produced by Alpha Print, are fine to use, as they are the same. However, the first edition, printed by the publisher, has substantial differences, and would not suffice.

You might also find useful textbooks that are available freely (and legally) online, including William Stein's "Elementary Number Theory: Primes, Congruences, and Secrets", Stein book.

For popular historical accounts of cryptology, highly recommended sources are Simon Singh, "The Code Book" and (for much more detail) David Kahn, "The Codebreakers".

Computer algebra systems (very helpful, but not essential):

Sage, Maple, Mathematica, available in Math computer labs, and also (for CSE undergrads) for free downloads at CSE Labs. Some systems available on the Web, in particular the Sage Cell Server and Wolfram Alpha, are sufficient. A calculator is advisable, even if you use a computer algebra system, to reduce the tedium of computations.

Participation in class is encouraged. Please feel free to stop me and ask questions during lecture. Otherwise, I might stop and ask you questions instead.

Grading:

  • Homework (25%): There will be 6 homework assignments due approximately every other week (tentatively) mostly on Wednesdays. The first homework assignment is due on February 4th.

    I encourage collaboration on the homework, as long as each person understands the solutions, writes them up in their own words, and indicates on the homework page their collaborators. Late homework will not be accepted. Early homework is fine, and can be left in my mailbox in the School of Math mailroom in Vincent Hall 107. Homework solutions should be well-explained-- the grader is told not to give credit for an unsupported answer. Complaints about the grading should be brought to me.

    Solutions will be made available via Moodle

  • Exams (approx. 25% each): There will be 3 in-class exams (the first one is worth 20%, the second is worth 25%, the third is worth 30%), each of which will be open book, open notes, and with scientific or graphing calculators allowed, but no smart phones, iPads, or other communication devices can be used, and you have to do all the work yourself. Missing an exam is permitted only for the most compelling reasons. You should obtain my permission in advance to miss an exam. Otherwise you will be given a 0. If you are excused from taking an exam, your other exam scores will be prorated.

    The exams will be on Monday February 16th, Monday April 6th, and Wednesday May 6th.

  • Tentative Lecture Schedule (with related reading from Garrett)

  • (W Jan 21) Lecture 1: Introduction to the Course and Caesar Ciphers (1.1, 2.3, 3.1, 7.1 (including intro to Chap 7))
    Print your own Caesar Wheel (courtesy of Science by Email)      Shift Encryptor and Frequency Analysis (courtesy of Braingle)      More on ADFGVX (courtesy of Practical Cryptography)
  • (M Jan 26) Lecture 2: One-Time Pads, Public Key Cryptography and Euclid's Theorem (1.3, 7.4, 8.1, 8.3)
  • (W Jan 28) Lecture 3: Euclidean Algorithm and Fundamental Theorem of Arithmetic (1.2, 1.4)
  • (M Feb 2) Lecture 4: Modular Arithmetic, Affine Ciphers and Known Plaintext attack on Affine Cipher (1.5, 1.6, 1.7, 4.2)
  • (W Feb 4) Lecture 5: The Extended Euclidean Algorithm, Solving Congruences (6.3)
  • (M Feb 9) Lecture 6: Chinese Remainder Theorem, Probability and Binomial Coefficients (2.1, 2.2, 4.4, 10.1, 10.2, 10.3)
  • (W Feb 11) Lecture 7: The Vigenere Cipher and Attacks on it (2.3, 2.4, 4.1, 4.3)
  • (M Feb 16) Exam 1
  • (W Feb 18) Lecture 8: Expectation and Attacks on Vigenere (4.1, 4.3, 4.4)
    Applet for Breaking Vigenere (courtesy of David Little and Adriano Garsia)
    Vigenere Toolkit (by Helmut Saueregger)
  • (M Feb 23) Lecture 9: Index of Coincidence and the Euler Phi Function (4.5, 10.6, 11.1)
  • (W Feb 25) Lecture 10: Fermat's Little Theorem and the Diffie-Helman Key Exchange (7.4, 9.1, 9.5)
  • (M Mar 2) Lecture 11: Proof of Euler-Fermat's Theorem and RSA (7.1, 7.2, 9.1)
  • (W Mar 4) Lecture 12: Primitive roots, Discrete logs, and El Gamal (7.2, 7.3, 7.5)
  • (M Mar 9) Lecture 13: Primitive root testing and Cyclotomic Polynomials (9.2, 15.3, 15.5, 15.9)
  • (W Mar 11) Lecture 14: Mobius inversion and Proof that primitive roots exist mod p (11.2, 11.3, 15.5)
  • (M Mar 16) Spring Break
  • (W Mar 18) Spring Break
  • (M Mar 23) Lecture 15: Fermat pseduo-primes and Carmichael Numbers (13.1, 13.2)
  • (W Mar 25) Lecture 16: More on Carmichael Numbers (17.1, 17.2)
  • (M Mar 30) Lecture 17: Strong pseduo-primes and the Miller-Rabin test (13.5, 13.6)
  • (W Apr 1) Lecture 18: The Prime Number Theorem and Attacks on RSA (7.2, 8.2)
  • (M Apr 6) Exam 2
  • (W Apr 8) Lecture 19: Continued Fractions and RSA (18.3)
  • (M Apr 13) Lecture 20: Pocklington-Lehmer (18.3, 18.5)
  • (W Apr 15) Lecture 21: Pocklington-Lehmer II and Principal Square Roots (9.6, 18.3, 18.5)
  • (M Apr 20) Lecture 22: Square Root Oracles and Quadratic Reciprocity (10.5, 10.8, Chapter 12)
  • (W Apr 22) Lecture 23: Quadratic Reciprocity proof and Euler Psedoprimes (Chapter 12, 25.1, 25.2, 13.3, 13.4)
  • (M Apr 27) Lecture 24: Pollard's Rho and p-1 Methods for Factoring and the Birthday Problem 18.1, 18.2) Kruskal Count Magic Trick
  • (W Apr 29) Lecture 25: Discrete Log Attacks: Baby Step, Giant Step; and Pollard Rho (20.1, 20.2)
  • (M May 4) Lecture 26: Final Review
  • (W May 6) Exam 3


  • Homework assignments
    Assignment Due date Problems from Garrett text,
    unless otherwise specified
    Homework 1 Wednesday Feb 4 1.1 # 5, 10
    1.2 # 4
    1.3 # 3
    1.5 # 2, 7, 9
    1.6 # 4, 12
    1.6 # 15 (Make sure to explain your work)
    1.7 # 3, 7
    1.7 # 14 (BONUS)
    4.2 # 3, 8
    6.2 # 3
    Exam 1 Monday Feb 16
    Homework 2 Wednesday Feb 25 EXAM 1 will also cover the topics related to the following problems:
    1.6 # 17
    1.7 # 18
    2.1 # 2, 11
    2.2 # 5, 6, 12
    6.3 # 6
    10.2 # 7
    10.3 # 7

    Part 2 of HW2:
    2.4 # 2
    4.1 # 1
    4.4 # 7
    4.5 # 2 (see 4.5.1)
    Homework 3 Wednesday March 11 6.2 # 8
    7.2 # 1, 7, 9
    7.3 # 10, 11
    7.5 # 1, 2
    9.1 # 3, 7
    11.1 # 1, 3, 5 (Hint: Read Section 11.1)
    Homework 4 Wednesday April 1 10.6 # 1, 3 (Compute the Euler Phi Functions however you wish)
    11.3 # 1, 3, 4
    13.1 # 1, 3
    13.2 # 1, 2
    13.6 # 1, 5
    15.3 # 2, 3, 4
    15.5 # 1, 3, 4
    Homework 5 Wednesday April 22 Download Here
    Homework 6 Monday May 4 18.1 # 1, 2
    18.2 # 2, 4
    20.1 # 5, 11
    20.2 # 3