# 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