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