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)
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)
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
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)
Thursday, June 23: Enigma
Friday, June 24: No class, Midterm due by 3pm
Monday, June 27: Index Calculus (3.8)
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)
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).
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)
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)
Thursday, July 7: Elliptic Curve Cryptography and Lenstra’s Factoring Algorithm (5.4, 5.6)
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
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
Thursday, July 14: Bitcoin
Friday, July 15:
Final Exam due