Math 348 - Cryptography

Spring 2014


Instructor: Shubhangi Saraf


Timing:  TF 10:20- 11:40 am 

Location:  ARC 207 (Busch Campus)

Office hours:  Tuesday 1 pm – 2 pm (Hill 426)


Prerequisites: Linear Algebra (Math 250) and one of Math 300, 356, or 477, or permission of department.

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).

Description: This course is an introduction to modern cryptography. The course begins with a description of the evolution of cryptography and cryptanalysis from ancient times through World War II. We then turn to some of the amazing discoveries of public key crypto systems in the 1970s that completely revolutionized cryptography and we develop and discuss the mathematical tools that are used. We will also go on to discuss some of the more advanced topics such as digital signatures, one way functions, pseudorandom generators and zero-knowledge proofs. 

Recommended Text: Introduction to Cryptography with Coding Theory (Second Edition) by Wade Trappe and Lawrence C. Washington

Other Resources:

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

Another great resource: 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.

Lecture Notes by Brandon Bate available here

The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography by Simon Singh


Homework 1 (due Feb 7)

Homework 2 (due Feb 21)

Homework 3 (due March 14)

Homework 4 (due April 4)

Homework 5 (due April 18)


Some sample solutions to hw and midterm questions


MIDTERM 1: Scheduled for Feb 25 (in class)

MIDTERM 2: Scheduled for April 11 (in class)



§  Lecture 1 (Tuesday 01/21): Administrative details, course overview, Shift Cipher 

§  Lecture 2 (Friday 01/24):  Basic congruences, Multiplication cipher, Affine cipher  (See Wesley Pegden’s notes part 1)

§  Lecture 3 (Tuesday 01/28): Substitution cipher, frequency analysis   (See Wesley Pegden’s notes part 1)

§  Lecture 4 (Friday 01/31):  Primes, factoring, unique factorization  (See W-T or H-P-S )

§  Lecture 5 (Tuesday 02/04): Euclid’s algorithm for gcd, extended Euclid’s algorithm  (See W-T or H-P-S )

§  Lecture 6 (Friday 02/07): Vignere cipher, Kasiski attack (See Wesley Pegden’s notes part 1)

§  Lecture 7 (Tuesday 02/11): Fast exponentiation modulo n  (See W-T or H-P-S )

§  Lecture 8 (Friday 02/14): Fermat’s little theorem  (See W-T or H-P-S )

§  Lecture 9 (Tuesday 02/18): Enigma

§  Lecture 10 (Friday 02/21): Primitive roots, discrete log problem

§  Lecture 11 (Tuesday 02/25): Midterm 1

§  Lecture 12 (Friday 02/28): Diffie Hellman Key exchange

§  Lecture 13 (Tuesday 03/04):  Hardness of discrete log problem, complexity of various computational problems

§  Lecture 14 (Friday 03/07):  Public key cryptography

§  Lecture 15 (Tuesday 03/11):  RSA

§  Lecture 16 (Friday 03/14):  Sampling a random prime

§  (Tuesday 03/18): Spring Break

§  (Friday 03/21): Spring Break

§  Lecture 17 (Tuesday 03/25): Miller Rabin test for primality

§  Lecture 18 (Friday 03/28): Probability review

§  Lecture 19 (Tuesday 04/01): Digital signatures

§  Lecture 20 (Friday 04/04): Linear algebra and secret sharing

§  Lecture 21 (Tuesday 04/08): Review – univariate polynomials and their roots

§  Lecture 22 (Friday 04/11): Midterm 2