Pre-Class Assignments
Math 302 Advanced Cryptography, Spring 2023
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.
Be sure to check back, because this page will be updated often during the semester.
Week 2: Due Monday January 30 @ 11:59 pm
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.
Optional videos from Spring 2021
- A Little Number Theory - Echo360 video, link in onCourse
Pre-Class Questions
- Compute 223 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.
- Have you and your partner met to discuss the Problem Set? How much progress have you made?
Week 3: Due Monday February 6 @ 11:59 pm
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 during class.
Optional videos from Spring 2021
- 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 (DHP).
- 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?
- Have you and your partner met to discuss the Problem Set? How much progress have you made?
Week 4: Due Monday February 13 @ 11:59 pm
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
Optional videos from Spring 2021
- Shank's Babystep-Giantstep Algorithm - Echo360 video, link in onCourse
- The Chinese Remainder Theorem - Echo360 video, link in onCourse
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?
- Have you and your partner met to discuss the Problem Set? How much progress have you made?
Week 5: Due Monday February 20 @ 11:59 pm
The Pohlig-Hellman algorithm
To Read
- Section 2.9 The Pohlig-Hellman algorithm
Optional videos from Spring 2021
- The Pohlig-Hellman algorithm - Echo360 video, link in onCourse
Pre-Class Questions
- Consider the DLP gx ≡ 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=23⋅ 52⋅ 269⋅ 307⋅ 1009 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? - Have you and your partner met to discuss the Problem Set? How much progress have you made?
Week 6: Due Monday February 27 @ 11:59 pm
Pollard's \( \rho \) applied to DLP
To Read
- Section 5.5 Pollard's \( \rho \) Method
Optional videos from Spring 2021
- Pollard's \( \rho \) - Echo360 video, link in onCourse
- vth Roots mod p - Echo360 video, link in onCourse
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 Monday March 6 @ 11:59 pm
Miller-Rabin witnesses
To 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
Optional videos from Spring 2021
- The Miller-Rabin Test - Echo360 video, link in onCourse
Pre-Class Questions
- Is 38 a Miller-Rabin witness for 289? Explain.
- Is 36 a Miller-Rabin witness for 289? Explain.
Week 8: Due Monday March 20 @ 11:59 pm
Introduction to elliptic curves
Elliptic curves over \( \mathbb{F}_p \)
To Read
- Section 6.1 Elliptic Curves
- Section 6.2 Elliptic Curves over Finite Fields
Optional videos from Spring 2021
- Elliptic Curves (Computerphile)
- Elliptic Curve Point Addition (Riverninj4)
- Theorem 6.6 Explained - Echo360 video, link in onCourse
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.
- 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.
Week 9: Due Monday March 27 @ 11:59 pm
The elliptic curve DLP
Elliptic curve DHKE
To Read
- Section 6.3 The Elliptic Curve Discrete Logarthim Problem
- Section 6.4.1 Elliptic Diffie–Hellman Key Exchange
Pre-Class Questions
- If E: Y2= X3+AX+B is an elliptic curve over \( \mathbb{F}_{833} \), how many points lie on E?
- 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?
- Have you and your partner met to discuss the Problem Set? How much progress have you made?
Week 10: Due Monday April 3 @ 11:59 pm
Elliptic curve DSA
Shor's algorightm for DLP
To Read
- Section 6.4.3 Elliptic Curve Signatures
Optional videos from Spring 2021
- ECDHKE & ECDSA - Echo360 video, link in onCourse
Pre-Class Questions
- The DSA we studied in the fall used two modulii, p and q. In ECDSA, there is only one modulus, q. What serves the role of mod p in ECDSA?
- Give an example where ECDSA is used in real life.
Week 11: Due Monday April 11 @ 11:59 pm
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
Optional videos from Spring 2021
- Introduction to Lattices - Echo360 video, link in onCourse
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 12: Due Monday April 17 @ 11:59 pm
Babai's Algorithm
LLL Lattice Reduction Algorithm
To Read
- Section 7.6 Babai's Algorithm and Using a "Good" Basis to Solve apprCVP
- Section 7.13 Lattice Reduction Algorithms
No questions to submit for this week. I think you've got enough class responsibilities coming up.
Week 13: Due Monday April 25 @ 11:59 pm
Lattice-based post-quantum encryption
To Read
- Kyber - How does it work? at cryptopedia.dev
- Slides from the presentation Update on Post Quantum Encryption and Cryptographic Transitions on October 27, 2022 at NIST
- For reference, https://pq-crystals.org/ has the details of both CRYSTALS-Kyber and CRYSTALS-Dilithium
Week 14: Due Monday May 1 @ 11:59 pm
Student presentations
To Read
- Abstracts for presentations posted to onCourse