# Wednesday, November 9th

Quiz (the Fourth) topics:

• Euclidean algorithm (as always)
• Arithmetic in Z/nZ including inverses
• Arithmetic in explicit finite fields, including finding inverses (explicit means I tell you the integer and polynomial modulus)
• The size of finite fields
• Be able to create finite field examples by creating an integer and polynomial modulus; know the properties the integer and polynomial must have (i.e. integer is prime, polynomial is irreducible)
• Generalities on rings and fields (axioms)
• Know that there is exactly one finite field of size q^k
• Know the the invertible elements of a finite field have a multiplicative generator
• Be able to generalize the idea of discrete log, Diffie-Hellman and El Gamal to a finite field instead of Z/pZ
• Hash functions (3 basic properties, and example uses)
• El Gamal Digital Signature Algorithm (be able to implement it)
• Birthday attack for forging signatures
• Elliptic curves: what they are, how to add points (geometric algorithm), including special cases (P+P, point at infinity), how to find inverse of a point.
• be able to add points on an elliptic curve over the rationals, mod p or a finite field
• statement of Hasse’s theorem on number of points on an elliptic curve
• be able to find the number of points on an elliptic curve over finite field or mod p (don’t forget point at infinity)
• Elliptic Curve Discrete Logarithm problem — generalities (e.g. no subexponential known algorithms)
• be able to implement elliptic curve Diffie-Hellman Key Exchange, or explain how it works
• explain in theory how having a pairing gives you 3-party key exchange; no actual ability to implement required
• definition of a continued fraction, ability to compute using invert-and-take-integer-part.
• Birthday paradox: know how to compute the probability of a coincidence with n items (e.g. people) and N possibilities (e.g. days in the year)
• Know how to attack discrete log with birthday attack
• Projective space: definition, tell if elements are the same
• Projective space: whether functions or equations are well-defined and why
• Projective space: finding all solutions to a line or equation in projective space
• I won’t ask you to do elliptic curve computations in projective coordinates
• Basic terminology: SSL handshake, nonce, public key infrastructure, collision an collision-resistance, SHA-1, salt, dictionary attack on passwords, digital signature, irreducible polynomial
• Know, for all your algorithms, whether the runtime is exponential, sub-exponential or polynomial (no need for explicit formula memorization)
• No proofs on this one

# Monday, November 7th

Prepare for your quiz.  Please take a look ahead to Wednesday’s post listing the topics for the quiz.

Today in class we will introduce coding theory, but it won’t be on the quiz.

# Friday, November 4th

Assignment due today.

# Wednesday, November 2nd

I’m posting some suggested problems from the book to do with recent topics, you’ll want to use these to study over the next week:

• Chapter 3, Number Theory, Exercises 33, 34
• Chapter 8, Hash, Exercises 1, 3, 4
• Chapter 9, Signatures, Exercises 1, 2, 5, 6, Computer Problem 1
• Chapter 16, Elliptic Curves, Exercises 2, 3, 4, 5, 9, Computer Problem 2
• I suggest you also find the full multiplication table for \$y^2 + y = x^3\$ over \$\mathbb{F}_2\$ (where it has 3 points) and over \$\mathbb{F}_4\$ (where it has 9 points).  Notice that \$\mathbb{F}_2\$ is a subfield of \$\mathbb{F}_4\$, so you’ve done part of the work already.  Don’t do all the multiplications out by hand, that’s tedious.  Instead, use cleverness to use just a few computations to fill out the whole table (as we did in class).

# Monday, October 31st

Happy Halloween!  Please feel welcome to wear a math or cryptography-themed costume to class (non-math costumes are alright too, but who would do that?).

To do for class:

• Please get a head-start on your assignment due Friday, before you forget how finite fields work!!

# Friday, October 28th

To do for class:

• Start work on the mission while finite fields are fresh in your mind
• Check D2L for your grades and report if any are missing or incorrect

# Wednesday, October 26th

Note:  Mission #7 is posted, due Friday November 4th.  It is an individual mission, but you can collaborate on the problems or give each other feedback on the write-ups.

On Wednesday, we are doing a second finite fields worksheet (here).

# Monday, October 24

On Monday, we did this worksheet:  Finite Fields 1 (tex).

# Friday, October 21

On Friday, we talked about hash and signatures.

# Wednesday, October 19th

Quiz the Third

Note: Monday’s review on discrete log has solutions here.

Material for the quiz:

• Basic modular arithmetic
• Euclidean algorithm and inverses in modular arithmetic
• successive squaring for powers in modular arithmetic
• general ideas of feasibility (our discussion of powers of 2 and runtime)
• Pollard’s p-1 factorization (can explain and perform by hand)
• Sieve of Eratosthenes
• Sieving for smooth numbers
• Quadratic sieve factorization (can explain and perform by hand)
• Know what a continued fraction is and its principal properties
• Primitive roots
• Fact:  a primitive root exists modulo any prime p (no proof given)
• The proposition of Section 3.7 (understand and can use the statement).
• Discrete Logarithm Problem and notation \$L_g(h)\$
• Understand formula for probability of coincidences in Birthday Paradox
• Baby-Step-Giant-Step algorithm (can explain and perform by hand)
• Index Calculus (can explain and perform by hand)
• know that Pohlig-Hellman exists and what sort of primes it works on
• Diffie-Hellman Key Exchange (can explain and perform by hand)
• ElGamal Public Key Cryptosystem (can explain and perform by hand)
• considerations for security and implementation of the above
• ElGamal Digital Signature Scheme (if we get to it on Monday, Section 9.2)
• Proofs:
• novel proofs surrounding ideas of primitive roots and modular arithmetic
• proofs that DHE (Diffie-Hellman-Key-Exch) and ElGamal are correct, e.g. the decryption recovers the plaintext, or the shared secrets agree
• proof of Proposition of Section 3.7 or parts of that
• Terminology to know the basics of:  factor base, smooth number, smoothness bound, exponential and sub-exponential run-times, birthday paradox, man-in-the-middle attack, notation \$(\mathbb{Z}/p\mathbb{Z})^*\$.