Tests

  • There will be module assessments on:
      • Wed September 20th (Module 1)
      • Wed October 11th (Module 2)
      • Wed November 1st (Module 3)
      • Wed November 29th (Module 4)
  • Final Exam Sunday December 17th, 7:30 pm

Format

My tests typically have some short answer concept type questions, e.g. true false, fill in the blank, and some longer questions where you might demonstrate how to do an algorithm or compute something.

Wednesday, September 20th, 2023:

  • Public and private key cryptography
  • Keyspace and exhaustive search
  • Cryptographic “hard problems”
  • computational complexity:
    • Big Oh notation
    • runtime analysis of algorithms
    • polynomial, subexponential, exponential
  • Classical cryptosystems:
    • substitution ciphers,
    • affine cipher including cryptanalysis,
  • modular arithmetic:
    • computations
    • reducing summands and factors but not exponents
    • no cancellation (unless invertible)
    • equivalent conditions for invertibility
    • set of invertible elements $(\mathbb{Z}/n\mathbb{Z})^*$ (definition and computation)
    • euler’s phi function, definition and formula
    • linear algebra mod n (invertibility of matrices)
    • efficient exponentiation (successive squaring)
    • multiplicative order (definition and computation)
    • Fermat/Euler theorems
    • Using Fermat/Euler to tackle $a^{b^c}$ style problems
    • primitive roots (definition)
  • Computational Diffie-Hellman problem
  • Discrete logarithm problem
  • Diffie-Hellman key exchange
  • Baby-step giant step (including runtime)
  • Index calculus (excluding runtime)
  • El Gamal Cryptosystem (including what happens if you re-use the ephemeral key)

For some review problems, I’ve posted a folder of exercises and examples here.  Solutions are not included, but for computations, they can generally be verified by Sage.  Do not hesitate to reach out to me on discord to check work.