Pre-Class Assignments
Math 302 Advanced Cryptography, Spring 2021
This page uses MathJax to display mathematical notation, so please let me know if any part isn't clear.
All section numbers refer to the text, An Introduction to Mathematical Cryptography, 2nd Edition by Hoffstein, Pipher, and Silverman.
All Echo360 videos are avaialable through onCourse.
Be sure to check back, because this page will be updated often during the semester.
Week 2: Due Sunday February 7 @ midnight
Fermat's Little Theorem
Primitive roots
To Read
- Section 1.1 Simple Substitution Ciphers (skim for background info)
- Section 1.2 Divisibility and Greatest Common Divisors
- Section 1.3 Modular Arithmetic
- Section 1.4 Prime Numbers, Unique Factorizations, and Finite Fields
- Section 1.5 Powers and Primite Roots in Finite Fields
- Section 1.6 Cryptography Before the Computer Age
Much of this should be review for you from the fall semester. Don't get too caught up in all of the details, but try to focus on the differences in notation from the fall. We'll hit the main points in the videos and during class.
To Watch
- A Little Number Theory (Echo360)
Pre-Class Questions
- Compute \( 2^{23\,425\,142} \mod 23\,425\,143 \). Using your answer and Fermat's Little Theorem, what can you conclude about \(23\,425\,143\)?
- Is 3 a primitive root of \( \mathbb{F}_{11} \)? How about 2? Explain.
Week 3: Due Sunday February 14 @ midnight
DLP vs DHP
Lagrange's Theorem
Introduction to big-\( \mathcal{O} \)
O
To Read
- Section 2.1 The Birth of Public Key Cryptography (skim for background)
- Section 2.2 The Discrete Logarithm Problem (for review)
- Section 2.3 Diffie-Hellman Key Exchange (for review)
- Section 2.5 An Overview of the Theory of Groups
- Section 2.6 How Hard is the Discrete Logarithm Problem?
As with last week's assignment, much of the first few sections will be review. There's a lot of information in Sections 2.5 & 2.6, and we'll hit the high points in the videos and during class.
To Watch
- Group Definition (Socratica)
- Asymptotic Bounding 101: Big O, Big Omega, & Theta (Back to Back SWE) - The first 15 minutes are most relevant
Pre-Class Questions
- Explain the difference between the Discrete Log Problem (DLP) and the Diffie-Hellman Problem (DLP).
- What is the order of (ℤ/8ℤ)*? What is the order of 3 in (ℤ/8ℤ)*? Explain.
- Why are we looking at big-\( \mathcal{O} \) notation now?
Week 4: Due Sunday February 21 @ midnight
Shanks Babystep-Giantstep algorithm
The Chinese Remainder Theorem
To Read
- Section 2.7 A Collision Algorithm fo the DLP
- Section 2.8 The Chinese Remainder Theorem
To Watch
- Shank's Babystep-Giantstep Algorithm (Echo360)
- The Chinese Remainder Theorem (Echo360)
Pre-Class Questions
- Consider the DLP 2x ≡ 21 mod 29. If you apply Shanks Babystep-Giantstep to solve this, how long will each list be?
- Why are we studying the Chinese Remainder Theorem now?
Week 5: Due Sunday February 28 @ midnight
The Pohlig-Hellman algorithm
To Read
- Section 2.9 The Pohlig-Hellman algorithm
To Watch
- The Pohlig-Hellman algorithm (Echo360)
Pre-Class Questions
- Consider the DLP \( g^x \equiv h \mod p \) where \( g=3 \), \( h=7\,065\,119\,811 \), and \( p=16\,665\,249\,401\).
Note that \( g \) is a primitive root of \( \mathbb{F}_p \) and that \( p-1=2^3\cdot5^2\cdot269\cdot307\cdot1009 \) is the prime factorization.
How many smaller DLPs will you solve when applying Pohlig-Hellman to this DLP? - Which algorithms/theorems that we have already learned are used when applying the Pohlig-Hellman algorithm?
At what point are these used? - How many times have you and your partner met to discuss Problem Set 2? How much progress has your group made?
Week 6: Due Sunday March 7 @ midnight
Pollard's \( \rho \) applied to DLP
To Read
- Section 5.5 Pollard's \( \rho \) Method
To Watch
- Pollard's \( \rho \) (Echo360)
Pre-Class Questions
- What is the advantage of using Pollard's \( \rho \) for solving the DLP over using Shank's?
- Pollard's \( \rho \) is a collision algorithm. What is the collision it looks for in the sequence \( \{x_i\} \)?
Week 7: Due Sunday March 14 @ midnight
More on Pollard's \( \rho \)
Primality testing
To Read
- Section 5.5 Pollard's \( \rho \) Method (re-read)
- Section 3.2 The RSA Public Key Cryptosystem (for review)
- Section 3.3 Implementation and Security Issues (for review)
- Section 3.4 Primality Testing (up to Proposition 3.17)
To Watch
- vth Roots mod p (Echo360)
Pre-Class Questions
- Suppose you have applied Pollard's \( \rho \) to the DLP \( g^x\equiv h\mod 1543 \) and your collision gives you \( g^{173}\equiv h^{30} \mod 1543 \). How long is the list of candidates for \( x \) that you'll form when taking the 30th root? Explain.
- Is 98 a witness for the compositeness of 441? How about 2? Explain.
Week 8: Due Sunday March 21 @ midnight
Miller-Rabin witnesses
Pollard's \( \rho \) applied to factoring
To Read
- Section 3.4 Primality Testing (finish the section)
- Exercise 5.44 (we'll go through the details during class)
To Watch
- The Miller-Rabin Test (Echo360)
- Factoring with Pollards \( \rho \) (Echo360)
Pre-Class Questions
- Is 38 a Miller-Rabin witness for 289? Explain.
- Is 36 a Miller-Rabin witness for 289? Explain.
- What is most surprising to you about the version of Pollard's \( \rho \) that can be used for factoring?
Week 9: Due Sunday March 28 @ midnight
Introduction to elliptic curves
To Read
- Section 6.1 Elliptic Curves
To Watch
- Elliptic Curves (Computerphile)
- Elliptic Curve Point Addition (Riverninj4)
- Theorem 6.6 Explained (Echo360)
Pre-Class Questions
- What's the advantage of using elliptic cuves in cryptography?
- Why do we include the point \( \mathcal{O} \) at infinity in our elliptic curves?
- If P1 ≠ P2 are points on the elliptic curve E, give a geometric description of the point P1 + P2 on E.
Week 10: Due Sunday April 4 @ midnight
Elliptic curves over \( \mathbb{F}_p \)
The elliptic curve DLP
To Read
- Section 6.2 Elliptic Curves over Finite Fields
- Section 6.3 The Elliptic Curve Discrete Logarthim Problem
To Watch
- Nothing for this week since these two sections are pretty short and are mostly elliptic curve analogs of topics we've covered in the mod p context.
Pre-Class Questions
- Consider the elliptic curve E: Y2 = X3 -5 X +6 over \( \mathbb{F}_{23} \). Verify that P=(1,5) and Q=(4,2) lie on E and find P+Q.
- If E: Y2= X3+AX+B is an elliptic curve over \( \mathbb{F}_{833} \), how many points lie on E?
Week 11: Due Sunday April 11 @ midnight
Elliptic curve DHKE
Elliptic curve DSA
To Read
- Section 6.4 Eliptic Curve Cryptography
To Watch
- ECDHKE & ECDSA (Echo360)
Pre-Class Questions
- A point on an elliptic curve has two coordinates (x,y). Why is it sufficient in ECDHKE to send only an x-component when exchanging keys?
- The DSA we studied in the fall used two modulii, p and q (look in the class material from early November if you need a reminder). In ECDSA, there is only one modulus, q. What serves the role of mod p in ECDSA?
Week 12: Due Sunday April 18 @ midnight
Introduction to lattices
The closest vector problem
To Read
- Section 7.3 A Brief Review of Vector Spaces
- Section 7.4 Lattices: Basic Definitions and Properties
- Section 7.5 Short Vectors in Lattices
To Watch
- Introduction to Lattices (Echo360)
Pre-Class Questions
Let \( \mathcal{L} \) be the lattice generated by \( v_1=\left\langle 2,3 \right\rangle \) and \( v_2=\left\langle 1,5 \right\rangle \)- Give two points other than \( v_1 \) and \( v_2 \) that lie in \( \mathcal{L} \). Explain.
- Does \( \left\langle \frac{1}{2}, \frac{5}{3} \right\rangle \) lie in \( \mathcal{L}\, \)? Explain.
Week 13: Due Sunday April 25 @ midnight
Lattice-based encryption
To Read
- Section 7.5 Short Vectors in Lattices (Re-read Section 7.5.1)
- Section 7.7 Cryptosystems Based on Hard Lattice Problems
No questions to submit for this week. I think you've got enough class responsibilities with the Kryptos challenge and the Group Presentation coming up.
Week 14: Due Sunday May 2 @ midnight
Student presentations
To Read
- Abstracts for presentations posted to onCourse