# 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✔