Goals

The goals of this course are to:

  • Understand the mathematical underpinnings of coding theory and cryptography
  • Be able to encipher, decipher, cryptanalyse and use cryptography securely
  • Be able to code and decode
  • Understand the basics of elementary number theory
  • Program a computer (at an introductory level)
  • Improve your LaTeX skills
  • Improve your ability to communicate mathematics and write proofs
  • Improve your ability to think mathematically
  • Have fun

7 Modules (around 2 weeks each):

MODULE 1:  Paradigms, History and Application (distributed through semester; tested as accumulated)

  • Public and private key cryptography ✔
  • Keyspace and exhaustive search   ✔
  • Cryptographic “hard problems”  ✔
  • diffusion and confusion✔
  • computational complexity:
    • Big Oh notation  ✔
    • runtime analysis of algorithms  ✔
    • polynomial, subexponential, exponential  ✔
  • Classical cryptosystems: 
    • substitution ciphers, ✔
    • affine cipher including cryptanalysis,✔
    • Hill cipher including cryptanalysis, ✔
    • Vigenere cipher  ✔
    • frequency analysis and cryptanalysis of Vigenere
  • History:  ancient, world wars, advent of public key cryptography & computers (e.g. enigma machine)
  • Notions of security
  • Basics of programming in Python/Sage
  • Digital signatures
  • Hash functions
  • Cryptography in current events, including NIST standardization
  • Implementation (e.g. how the internet uses cryptography, timing attacks, famous hacks)
  • Miscellaneous topics (e.g. cryptocurrency, secret sharing, zero-knowledge proofs)

Suggested review problems for Module 2 test:  2nd Edition:  Section 2.13, #2, 3, 6, 13, 14.  3rd Edition:  Section 2.8, #3, 5, 11, Section 6.6 #1, 3.

MODULE 2: Modular arithmetic & discrete logarithm

  • modular arithmetic:✔
    • computations✔
    • reducing summands and factors but not exponents✔
    • no cancellation✔
    • equivalent conditions for invertibility with proofs✔
    • 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 and double-and-add)✔
    • multiplicative order (definition and computation)✔
    • Fermat/Euler theorems (including proof)✔
    • 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✔
  • Birthday attack (didn’t cover)
  • Index calculus✔
  • El Gamal encryption✔
  • El Gamal signature (didn’t cover)

Suggested review problems for Module 2 test:  Review the daily post exercises, and then consider 2nd Edition:  Section 3.13 #11, 13, 15, 18, 20, and Section 7.6 #1, 2, 3, 6, 7, 8, 11.  3rd Edition:  Section 3.13 #25, 27, 35, 39, 53 and Section 10.6 #1,2,3,7,9,11,16.  Warning:  the illegal epub 3rd ed is unusable as far as exercise numbering and math equations.

MODULE 3: Euclidean algorithm, primality testing & factoring

  • greatest common divisor
  • Euclidean algorithm
  • Inverses modulo n
  • Chinese remainder theorem
  • Euler phi function
  • Primality testing
  • RSA cryptosystem
  • RSA signature
  • p-1 factoring
  • Quadratic sieve

MODULE 4: Finite fields and elliptic curve cryptography

  • finite fields and their computations
  • projective space
  • elliptic curve cryptography
  • discrete logarithm in finite fields
  • discrete logarithm on elliptic curves
  • post-quantum cryptography:  isogeny-based cryptography (overview)

MODULE 5: Coding Theory

  • error correcting codes
  • bounds
  • linear and hamming codes
  • decoding
  • entropy and information theory
  • Huffman codes
  • coding-based cryptography

MODULE 6: Lattice-Based Cryptography

  • Shortest and closest vector problems
  • lattice reduction (LLL)
  • lattice attacks (e.g. on RSA)
  • post-quantum cryptography:  NTRU
  • post-quantum cryptography:  Ring-LWE

MODULE 7: Quantum Aspects

  • quantum key exchange
  • qubits
  • entanglement
  • measurement
  • unitary operators and quantum gates
  • basic quantum computing
  • quantum fourier transform
  • Shor’s algorithm