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.

Primitive roots

- 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.

- A Little Number Theory (Echo360)

- 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.

Lagrange's Theorem

Introduction to big-\( \mathcal{O} \) O

- 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.

- Group Definition (Socratica)
- Asymptotic Bounding 101: Big O, Big Omega, & Theta (Back to Back SWE) - The first 15 minutes are most relevant

- 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?

The Chinese Remainder Theorem

- Section 2.7 A Collision Algorithm fo the DLP
- Section 2.8 The Chinese Remainder Theorem

- Shank's Babystep-Giantstep Algorithm (Echo360)
- The Chinese Remainder Theorem (Echo360)

- Consider the DLP 2
^{x}≡ 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?

- Section 2.9 The Pohlig-Hellman algorithm

- The Pohlig-Hellman algorithm (Echo360)

- 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?

- Section 5.5 Pollard's \( \rho \) Method

- Pollard's \( \rho \) (Echo360) Coming by Friday, March 5

- Coming by Thursday, March 4

Primality testing

- 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 be determined. . .

- Coming soon. . .

Pollard's \( \rho \) applied to factoring

- Section 3.4 Primality Testing (finish the section)
- Exercise 5.44 (we'll go through the details during class)

- To be determined. . .

- Coming soon. . .

- Section 6.1 Elliptic Curves

- To be determined. . .

- Coming soon. . .

The elliptic curve DLP

- Section 6.2 Elliptic Curves over Finite Fields
- Section 6.3 The Elliptic Curve Discrete Logarthim Problem

- To be determined. . .

- Coming soon. . .

Elliptic curve DSA

- Section 6.4 Eliptic Curve Cryptography

- To be determined. . .

- Coming soon. . .

The closest vector problem

- 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 be determined. . .

- Coming soon. . .

- Section 7.7 Cryptosystems Based on Hard Lattice Problems
- Section 7.8 The GGH Public Key Crytposystem

- To be determined. . .

- Coming soon. . .

- Abstracts for presentations posted to onCourse

- Coming soon. . .