All posts by profstange

Your friendly professor.

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.

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

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

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})^*$.