Cryptography:
An Introduction to Cryptology

Math 348:01 - Spring 2013

TF 10:20-11:40am in ARC 207 (Busch campus)

Professor Stephen D. Miller

General Information

This is an upper level mathematics course. It is directed at students in mathematics, electrical engineering, or computer science who have strong interest in mathematics and want to learn about the exciting applications of algebra and number theory to cryptography and cryptanalysis.  The course will have two midterm exams, a final term paper assignment, and homework assignments (each comprising roughly 25% of the grade).

The due date for the final paper will be announced in class.

Prerequisites: Linear Algebra (Math 250) and one of Math 300, 356, or 477, or permission of department.
Part of the course will cover the needed background material on number theory (see below).

Textbook

Jeffrey Hoffstein, Jill Pipher, and Joseph Silverman, An introduction to Mathematical Cryptography, Springer-Verlag, ISBN 9781441926746.  Rutgers has an electronic site license for this book that is currently available here.  I have also placed the book on reserve in the Math library in the Hill Center (1st floor).

Dr. Ramarathnam Venkatesan, an eminent cryptographer from Microsoft Research, has agreed to allow us to use a draft of his new textbook "An invitation to mathematical aspects of cryptography".  Packets will be available for purchase from the mathematics department undergraduate office for $20 (exact change only, please).  

We will also draw from Wesley Pegden's course notes: click here for part 1, part 2, part 3, and errata.

Description

As the title indicates, this is an introduction to modern cryptography.  The course starts off with a discussion of cryptographic methods from ancient times through World War II.  We then turn to the amazing discoveries of public key cryptosystems in the mid- to late-1970s, and the mathematics that these algorithms depend on. The final part of the course covers attacks on these systems, e.g., modern techniques to factor large numbers.

Topics to be covered include:

Syllabus

Date Topic Supplementary Material
January 22 Section 1.1: Substitution ciphers and letter frequency Recap (pdf or Mathematica file)
January 25 Section 1.3: Caesar cipher and modular arithmetic
January 29 and February 1 Vigenere Cipher (Pegden's notes, p.14-36), Digraphs Recap (pdf or Mathematica file)
February 5 Trigraphs and the Kasiski attack on Vigenere Recap (pdf or Mathematica file)
February 8 Section 4.2: Index of coincidence and the Friedman attack Recap (pdf or Mathematica file)
February 12 Section 1.2: Modular arithmetic, GCDs
February 15 Sections 1.3, 1.4: Fast exponentiation, finite fields
February 19 Section 1.5: Powers in finite fields
February 22 and 26 Sections 2.1-2.3: The Diffie-Hellman key exchange, Discrete Logarithms
March 1 First Midterm
March 5 and 8 Section 2.5-2.7: Deterministic collision attacks on discrete logarithms, birthday paradox.
March 12 Sections 2.8-2.9: Chinese Remainder Theorem, Pohlig-Hellman attack for composite group orders Recap (pdf or Mathematica file)
March 15 Section 3.4: Making industrial strength primes
Spring Break
March 26 Section 3.4: Miller-Rabin primality test   Recap (pdf or Mathematica file)
March 29 and April 2 Sections 3.1-3.2: The RSA algorithm
April 5 and 9 Section 3.5: Pollard's factoring algorithms (supplementary handout) Recap (pdf or Mathematica file)
April 12 Section 3.6-7: Random Squares factorization (relations step)
April 16 Second Midterm
April 19 Section 3.6-7: Random Squares factorization (matrix step)
April 23 and 26 Section 3.8: Index calculus attack on Discrete Logarithms
April 30 and May 3 Section 4.4-4.5: Pollard rho for discrete logarithms Recap (pdf)

Homework Assignments

All assignments are due at the beginning of the class period on the day listed.  Listed problems are from the textbook, unless otherwise indicated.

Assignment 1 (due Feb. 15) 1.10, 1.13, 1.19, 1.20, 1.22, 1.25, 1.26, 1.28
Assignment 2 (due Feb. 22) 1.30, 1.32(a-d only), 1.34, 2.3, 2.4, 2.5, 2.6
Assignment 3 (due March 1) 2.16, 2.17, also solve "6x=n (mod 229)" for n=166,167, and 168.
Assignment 4 (due March 8) 2.18, 2.21, 2.28a).
Assignment 5 (due March 15) 3.13a, 3.13b, 3.14a, 3.14b, 3.14c, 3.16a, 3.20
Assignment 6 (due March 29) 3.1abc, 3.6, 3.7, 3.8, 3.9
Assignment 7 (due April 5) 3.21ab, 3.22acde, 3.23, 3.25
Assignment 8 (due April 12) 3.26, 3.28, 3.29
Assignment 9 (due April 19) 3.35 -- and also do part d for the following examples, replacing the "19": 119, 1119, 11119