# 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

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