# Cryptography (SUAMI 2016)

Syllabus

Errata for the textbook

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

Slides

Axioms for Integers

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

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

Slides

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

Monday, June 6: Modular Arithmetic (1.3)

Slides

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)

Slides

For Wednesday, Read 1.7, Try 1.41a

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

Slides

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)

Slides

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)

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)

Hardness of RSA vs. Factoring

Attacks on RSA

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)

NIST

Is Sign and Encrypt Secure?

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

Newman’s Proof

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/pZ)^*. Then either g or g + p is a generator in (Z/p^2Z)^*. If g is a generator in (Z/p^eZ)^*  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

Certicom ECC Challenge

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

Hales: NSA backdoor to NIST

Wired: NSA Backdoor

Shumow and Ferguson slides from 2007

DUAL EC DRBG information

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

Bleichenbacher Attack

Why Textbook ElGamal and RSA Encryption Are Insecure

Shoup: OAEP Reconsidered

Boneh: Simplified OAEP

RSA–OAEP is Secure under the RSA Assumption

Rogaway: The Moral Character of Cryptographic Work

Thursday, July 14: Bitcoin

Slides by Stefan Dziembowski

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

Bitcoin

NYT: A Bitcoin Believer’s Crisis of Faith

Friday, July 15:

Final Exam due