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