Cryptography:
An Introduction to Cryptology

Math 348:01 - Spring 2011

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

Professor Stephen D. Miller

General Information

This is an upper level MATH 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 one midterm exam, a term paper assignment, homework assignments (20% each of the total grade), and a final exam (40%).

The term paper is due in class on the last day of class, Friday April 29th.

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 reserved in the Math library in the Hill Center (1st floor).

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:

Symmetric Cryptography: Classical Cryptography: Simple Ciphers and Cryptograms. Vigenère Cipher;
Public Key/Private Key Cryptography: Ciphers: Rivest-Shamir-Adleman (RSA), El Gamal, Diffie-Hellman and trapdoors.
Number Theory:
- Congruences and Finite fields,
- Primitive roots and discrete logarithms.
- Finding large primes, pseudoprimes and primality testing.
- Square root algorithms, factoring techniques.
- Legendre and Jacobi symbols.

Syllabus

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

According to http://www.math.rutgers.edu/home/final_schedules/FinalExamSpring2011.pdf, our final is Thursday May 5 from 12-3pm in ARC-207 (the usual classroom).

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

Last updated: April 21, 2011

Cryptography: An Introduction to Cryptology