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
5 Modules (around 3 weeks each; tested in class):
INTRO/AMBIENT: 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
 Pseudorandom number generators
 Implementation (e.g. how the internet uses cryptography, famous hacks)
 Miscellaneous topics (e.g. cryptocurrency, secret sharing, zeroknowledge proofs)
Suggested review problems (Trappe/Washington): 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 (Trappe/Washington): 2nd Edition: Section 8.8, #1, 2, 3, 4. 3rd Edition: #1,3,5.
MODULE 1: 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 doubleandadd)
 multiplicative order (definition and computation)
 Fermat/Euler theorems (including proof)
 Using Fermat/Euler to tackle $a^{b^c}$ style problems
 primitive roots (definition)
 Computational DiffieHellman problem
 Discrete logarithm problem
 DiffieHellman key exchange
 Babystep giant step
 Index calculus
 El Gamal encryption
 El Gamal signature
Suggested review problems(Trappe/Washington): 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 2: 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
 p1 factoring
 Quadratic sieve
Suggested review problems (Trappe/Washington): 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 3: 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 DiffieHellman 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)
 postquantum cryptography: isogenybased cryptography (only an overview)
Suggested review problems (Trappe/Washington): 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 4: 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 periodfinding quantum algorithm
 Basic continued fractions (how to compute for Shor)
MODULE 5: Coding Theory & LatticeBased 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)
 postquantum cryptography: RingLWE