**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

§