# Cryptography (SUAMI 2016)

**Thursday, June 2:** Introduction to Cryptography, Substitution Ciphers (1.1, 1.6)

For Friday, Read 1.2, Try 1.6, 1.10a, 1.11a.

**Friday, June 3:** Divisibility and the Euclidean Algorithm (1.2)

For Monday, Read 1.3, Try 1.14, 1.15, 1.16b,e, 1.25a.

**Monday, June 6:** Modular Arithmetic (1.3)

**HW due:** 1.2b, 1.4b, 1.38, 1.40

For Tuesday, Read 1.4, 1.5, Try 1.26, 1.28a, 1.30a, 1.32a

**Tuesday, June 7: **Unique Prime Factorization and Finite Fields (1.4, 1.5)

For Wednesday, Read 1.7, Try 1.41a

**Wednesday, June 8: **Symmetric and Asymmetric Ciphers (1.7)

The Original Diffie-Hellman Paper

Claude Shannon: A mathematical Theory of Communication

For Thursday, Read 2.1-2.3, Try 2.4a, 2.6

**Thursday, June 9: **Discrete Logarithm, Diffie Hellman, and Elgamal (2.1-2.4)

For Friday, Read 2.4-2.6, Try 2.16

**HW due:** 1.10a, 1.11, 1.14 (* only), 1.15, 1.16b,e, 1.17a-e, 1.23, 1.25a

Let a, b be positive integers. What positive integers can be expressed in the form au+bv where u and v are nonnegative integers

- If a=8, b=5?
- If a and b are relatively prime (i.e. gcd(a,b)=1).
- If a and b are not relatively prime?

Optional: 1.13, 1.18, 1.21

**Friday, June 10: **Order Notation and Computational Complexity (2.6)

Clay Mathematics Institute Millenium Problems

Animations for some sorting algorithms

For Monday, Read 2.6-2.7, Try 2.17a, 2.18d

**Monday, June 13: **Shanks’s Algorithm and CRT (2.7, 2.8)

For Tuesday: Read 2.9, Try 2.28

**HW due: **1.27, 1.31, 1.32d, 1.43, 1.46, 2.3, 2.4a,c, 2.6 (Computation of B and shared value only), 3.11a

Optional: 1.34, 1.41, 2.5

Use Euler’s Formula to find an integer between 0 and 15 congruent to 2^2016 (mod 15).

Modify Diffie-Hellman so more than two people can mutually share a secret.

**Tuesday, June 14:** Pohlig-Hellman (2.9)

For Wednesday: Read 3.1, 3.2. Try 3.6.

**Wednesday, June 15:** RSA (3.1, 3.2)

For Thursday, Read 7.1, 7.2, Try 7.1, 7.2.

**Thursday, June 16: **RSA Digital Signatures (7.1, 7.2)

For Friday, Read 7.3, Try 7.4, 7.5

**HW due: **2.8, 2.9, 2.17a, 2.23c,d, 2.25

Suppose in Shanks’s Algorithm instead of making each list of length n+1, one list is length c+1 and the other is length d+1. Show that the lists will have an entry in common if cd>N. Why do we choose c=d=n?

Assuming that for k-bit integers addition and subtraction require linear time (O(k)) and multiplication and division require quadratic time (O(k^2)), analyze the time complexity of the Euclidean Algorithm and the Fast Powering Algorithm where the inputs are k-bit integers.

Optional: 2.10, 2.24

**Friday, June 17:** Elgamal Digital Signatures (7.3)

For Monday, Read 3.4, Try 3.14a, 3.16a

**Monday, June 20: **Primality Testing (3.4)

For Tuesday, Read 3.5, Try 3.21a

Erdos-Selberg Dispute: Spencer and Graham

Erdos-Selberg Dispute: Goldfeld

Selberg’s Proof of the Prime Number Theorem

Gowers: Two cultures of mathematics

Lagarias: An elementary problem equivalent to the Riemann Hypothesis

**HW due: **2.26, 2.28a, 3.1a, 3.6, 3.7, 3.9b, 7.1, 7.2, 7.3

Optional: 3.2, 3.3, 3.4, 3.8a, 3.10

If p and q are 1000-bit primes, estimate the probability that a random message m (mod pq) will have gcd(m,pq)>1.

Prove: Let p be an odd prime and g be a generator in (**Z**/p**Z**)^*. Then either g or g + p is a generator in (**Z**/p^2**Z**)^*. If g is a generator in (**Z**/p^e**Z**)^* for e ≥ 2 then g is a generator in (**Z**/p^(e+1)**Z**)^*.

**Tuesday, June 21:** Pollard’s p-1 algorithm and Factoring by Difference of Squares (3.5, 3.6)

For Wednesday, Read 3.6, Try 3.23a, 3.25b

**Wednesday, June 22:** Factoring by Difference of Squares and Smooth numbers and sieves (3.6, 3.7)

Pomerance: A tale of two sieves

**Thursday, June 23:** Enigma

T.W. Korner: Chapter on Enigma

** Friday, June 24: **No class, Midterm due by 3pm

**Monday, June 27:** Index Calculus (3.8)

Weak Diffie-Hellman and the Logjam Attack

For Tuesday, Read 3.9, 3.10, Try 3.41

**Tuesday, June 28: **Quadratic Reciprocity and Goldwasser-Micali (3.9, 3.10)

**Wednesday, June 29: **Zero-Knowledge Proofs, Probability, and the Birthday “Paradox” (8.3, 4.3.1, 4.4.1)

**HW due: **3.13b (i), 3.14a, d (5 nonwitnesses are sufficient), 3.16a, 3.21a, 3.22c, 3.28g, 3.33a

Optional: 3.15, 3.17, 3.20, 3.22e, f, 3.31, 3.320

**Thursday, June 30: **Collision Algorithms and Pollard’s rho (4.4, 4.5)

**Friday, July 1: **Random Variables, Expectation and Pollard’s rho (4.3.4, 4.3.5, 4.5)

Teske: On Random walks for Pollard’s rho

On the Efficiency of Pollard’s rho

Subset-Restricted Random Walks for Pollard’s rho

**HW due: **3.35, 3.36, 3.41a,c, 4.22, 4.35

This problem concerns the Zero-knowledge proof protocol discussed in class (See p. 471)

- Explain why Peggy should never pick the same value of r twice.
- Suppose Peggy knows in advance which values of beta Victor will use. Explain how she can fool him into thinking that a NR (mod N) is actually a QR (mod N).

Optional: 3.40,

Find a zero-knowledge protocol whereby Peggy can convince Victor that she has a solution to a discrete log problem g^x=h mod p, where p is a large prime.

**Tuesday, July 5:** Elliptic Curves (5.1)

Stefan Friedl: An Elementary Proof of the Group Law for Elliptic Curves

For Wednesday: Read 5.2, 5.3. Try 5.6a, 5.8

**Wednesday, July 6: **Elliptic Curves Over Finite Fields and ECDLP (5.2, 5.3)

Andrea Corbellini: Visualization of EC addition

**Thursday, July 7: **Elliptic Curve Cryptography and Lenstra’s Factoring Algorithm (5.4, 5.6)

Lenstra’s paper on factoring with Elliptic Curves

Are strong primes needed for RSA?

**HW due: **4.36, 4.37, 4.38, 5.2 (ignore bonus), 5.3, 5.4d,e,

Assuming N is large, what is the probability that when you use the Pollard’s rho algorithm, T+M > 10*sqrt(N)? Evaluate numerically for N = 2^1000.

Regarding the coupon collector problem, if there were 100 different toys, how long would we expect to wait before collecting all 100? How long would we expect to wait before we had half of them? Find an expression for the expected waiting time before obtaining half of a set with n toys. Can you find a good asymptotic estimate for this quantity?

Optional: 4.31, 4.41

**Friday, July 8: **Is ECC still considered secure? NSA backdoor to the DUAL EC DRBG pseudorandom number generator

NSA 2009: The Case for Elliptic Curve Crypto (Archived)

Koblitz and Menezes: Why is NSA moving away from ECC?

Green: Discussion of Koblitz and Menezes

Shumow and Ferguson slides from 2007

On the Practical Exploitability of Dual EC in TLS Implementations

**Monday, July 11:** The DUAL EC DRBG backdoor and DLP reducibility to DLP-MSB

**HW due:** 5.6a, 5.10a, 5.12, 5.15b, 5.16, 5.18a

**Tuesday, July 12:** Conditional Probability, Bayes’ Formula, and Miller-Rabin (4.3.2)

**Wednesday, July 13:** Semantic Security, Indistinguishability, and RSA padding

Why Textbook ElGamal and RSA Encryption Are Insecure

RSA–OAEP is Secure under the RSA Assumption

Rogaway: The Moral Character of Cryptographic Work

**Thursday, July 14: **Bitcoin

Satoshi Nakamoto: Bitcoin: A Peer-to-Peer Electronic Cash System

NYT: A Bitcoin Believer’s Crisis of Faith

**Friday, July 15:**

Final Exam due