Math 348 - Cryptography
Spring 2014
Instructor:
Shubhangi Saraf
Email: shubhangi.saraf@rutgers.edu
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)
Schedule:
§ 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
§