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 and passwords ✔
  • Birthday attacks ✔
  • Cryptography in current events, including NIST standardization ✔
  • Timing attacks   ✔
  • Pseudo-random number generators ✔
  • Implementation (e.g. how the internet uses cryptography, 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.

Suggested review problems for Module 3 test:  2nd Edition:  Section 8.8, #1, 2, 3, 4.  3rd Edition:  #1,3,5.

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✔
  • 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 (standard and extended)  ✔
  • Inverses modulo n  ✔
  • Chinese remainder theorem (many different statements, solving systems of equations)  ✔
  • Finding square roots using CRT  ✔
  • Euler phi function (proof of formula)  ✔
  • Primality testing (Fermat primality testing)  ✔
  • RSA cryptosystem (method, why you use an ephemeral key, basic security considerations)   ✔
  • RSA signature  ✔
  • short plaintext attack on RSA (daily due Oct 5 solns)  ✔
  • other attacks on RSA (didn’t cover)
  • the role of multiple square roots in factoring and Fermat factoring ✔
  • p-1 factoring  ✔
  • Quadratic sieve  ✔

Suggested review problems for Module 3 test:  Review the daily post exercises, and then consider 2nd Edition:  Section 3.13 #1, 2, 4,7, 8, 9, 10, and Section 6.8 # 1, 2, 3, 4, 5, 7, 8, 10, 11, 12, 13, 14.  3rd Edition:  Section 3.13 # 1,3,7, 13, 15, 17 and Section 9.8 # 1, 3, 5, 7, 9, 13, 15, 17, 21, 23, 25, 27. 

MODULE 4: Finite fields and elliptic curve cryptography

  • division algorithm and gcd, extended gcd in polynomial rings over $\ZZ/p\ZZ$  ✔
  • irreducible polynomials  ✔
  • finite fields: definition as a quotient (modding out by an irreducible polynomial)  ✔
  • listing the elements of a finite field in their simplest form and reducing more complicated expressions to these simplest forms  ✔
  • ability to do arithmetic in finite fields, including making an addition or multiplication table  ✔
  • number of elements in a finite field and which ones are units  ✔
  • possible sizes for finite fields (we did this just as a fact)  ✔
  • Finite field Fermat’s Little Theorem and the existence of a multiplicative generator (it always exists!)  ✔
  • finding the inverse of an element in a finite field  ✔
  • some general knowledge of the discrete logarithm in finite fields  ✔
  • ability to do DH key exchange and El Gamal encryption with a finite field  ✔
  • projective space (definition/elements over fields including finite fields)  ✔
  • elliptic curves and their group law, can compute
  • number of elements on an elliptic curve  ✔
  • putting an elliptic curve in projective coordinates  ✔
  • elliptic curve factoring method  ✔
  • discrete logarithm (DLP) on elliptic curves ✔
  • knowledge of attacks on DLP for elliptic curves ✔
  • turning a message into a point on an elliptic curve ✔
  • doing Diffie-Hellman key exchange or El Gamal encryption on an elliptic curve ✔
  • Dual_EC_DRBG (how it works and why a relationship between points is a problem) ✔
  • El Gamal Digital Signature on an elliptic curve (won’t test)
  • post-quantum cryptography:  isogeny-based cryptography (overview — won’t test)

Suggested review problems for Module 4 test:  Review the daily post exercises, and then consider 2nd Edition:  Section 3.13 # 33, 34; Section 16.7 #2, 5, 6 (more to come).  3rd Edition:  Section 3.13 #47, 48; Section 21.6 #3, 9,10 (additional in this edition only: 2, 4 for more practice).

MODULE 5: Quantum Aspects

  • single qubit state; Bloch sphere and change of basis✔
  • measurement (determine probabilities, collapse the state)✔
  • Quantum Key Exchange (BB84; the first one we did, not the entangled one mentioned later)✔
  • multiple qubits; how to measure multiple qubits, either one at a time or all together✔
  • how to detect entanglement✔
  • unitary operators (definition, ability to check if a matrix is unitary)✔
  • applying unitary operators as quantum gates to qubit states✔
  • big picture quantum computing:  we can compute classical functions/circuits “in parallel superposition”✔
  • quantum fourier transform (able to write down small cases, able to compute its action on small cases)✔
  • big picture QFT:  what it does to periodic states✔
  • how to reduce factoring to period finding ✔
  • Shor’s period-finding quantum algorithm ✔
  • Basic continued fractions (how to compute for Shor) ✔ 

Review problems here.

MODULE 6: Coding Theory & Lattice-Based Cryptography

  • error correcting codes and their terminology (length, information rate, number of errors detected/corrected etc.) ✔ 
  • Hamming distance and Hamming weight✔ 
  • linear codes ✔ 
  • decoding with syndromes (generating matrix, parity check matrix, cosets etc.) ✔ 
  • Lattices and how they are represented, basis change ✔ 
  • Shortest and closest vector problems ✔ 
  • lattice reduction in 2d (LLL) ✔ 
  • post-quantum cryptography:  Ring-LWE✔