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
- Learn some 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
New plan of Modules (6 total; 15% each):
- Classical Cryptosystems
- Modular Arithmetic and Discrete Log Problem
- Euclidean algorithm, RSA, primality testing and factoring
- Finite fields and elliptic curve cryptography, as well a post-quantum cryptography proposals (including lattice-based cryptography and isogeny-based cryptography)
- Coding Theory
- Quantum Aspects
Original plan of 9 Modules (4-6 lecture days each):
Classical Cryptosystems
- Shift, affine, Vigenere, substitution ciphers, engima machine, etc., and classical cryptanalysis, such as frequency analysis; general concepts of cryptosystems; also modular arithmetic, introduction to Sage and LaTeX
Modular Arithmetic
- modular arithmetic in more depth, additive and multiplicative dynamics, discrete logarithms, Fermat/Euler theorems, primitive roots, efficient exponentiation
Discrete Log Cryptography
- Diffie-Hellman key exchange and El Gamal Encryption, public key cryptography, Discrete Logarithm Problem, Birthday attack, baby-step giant step, Pollard’s rho, index calculus, notions of security
The Euclidean Algorithm & primality testing
- greatest common divisor, Euclidean algorithm, inverses modulo n, Chinese remainder theorem, euler phi function, primality testing (Fermat, Miller-Rabin)
RSA & Factoring
- RSA cryptosystem, square roots mod n, p-1 factoring, quadratic sieve, timing attacks, other attacks, pohlig-hellman algorithm
Finite fields and elliptic curve cryptography
- finite fields and their computations, elliptic curve cryptography, discrete logarithm in finite fields
Coding Theory
- error correcting codes, bounds, linear and hamming codes, decoding, coding-based cryptography
Lattice-Based Cryptography
- hard lattice problems, NTRU, Ring-LWE
Quantum Aspects
- quantum key exchange, quantum computing, Shor’s algorithm
Fall 2020 – Professor Katherine Stange