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

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
• p-1 factoring

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 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 (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 period-finding quantum algorithm
• Basic continued fractions (how to compute for Shor)

## MODULE 5: 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