Archive

The following calendar will be populated with links to worksheets, videos, and activities, so you can catch up on anything you’ve missed and revisit important material.

Daily post solutions:  Aug 29, Aug 31Sept 2,  Sept 7, Sept 9, Sep 12, Sep 21, Sept 23, Sept 26, Sept 28, Sept 30, Oct 3. Oct 5, (Oct 14 see lecture notes below), (Oct 17 see lecture notes below), Oct 19, Oct 21. Nov 2. Nov 7. Nov 9. Nov 11, Nov 28, Dec 5. Dec 7th.

Monday, August 22nd, 2022:

  • We did an overview of the course today, including briefly Caesar cipher, Vigenere cipher, ADFGVX cipher, enigma, notions of keyspace, cryptanalysis, notions of public-key cryptography, Diffie-Hellman Key Exchange, hard cryptographic problems and quantum aspects.  All these topics will be revisited in detail.
  • Presentation slides here.
  • Course videos can be viewed on canvas (give time for uploading).  Today’s video is also available here.

Wednesday, August 24th, 2022:

  • We defined modular arithmetic and used it to formalize Caesar and affine cipher.
  • Lecture notes are here.
  • I forgot to record the lecture after all that (duh! sorry…)

Friday, August 26th, 2022:

  • We discussed the multiplicative inverse in modular arithmetic, used it to find the decryption key to an affine cipher, and proved that there’s at most one multiplicative inverse.  We discussed the intuition and conjecture that the inverse of $a \pmod n$ exists if and only if $\gcd(a,n)=1$.  (We’ll prove that next class.)
  • Lecture notes are here.
  • The lecture recording is on canvas.

Monday, August 29th, 2022:

  • We proved that the inverse of $a \pmod n$ exists if and only if $\gcd(a,n)=1$.   We discussed how to compute the set of invertible elements and its cardinality, and talked about Hill cipher.
  • Lecture notes are here.
  • The lecture recording is on canvas.

Wednesday, August 31st, 2022:

  • We defined the multiplicative order of an element, showed that it exists if and only if the element is invertible, and then proved Euler’s theorem and Fermat’s Little Theorem.  At the end of class, our TA Joe Macula did some example problems.
  • Lecture notes are here (not including Joe’s part).
  • The lecture recording is on canvas.

Friday, September 2nd, 2022:

Wednesday, September 7th, 2022:

  • We reviewed Diffie-Hellman Key Exchange in practice, and discussed Big-Oh notation and the beginning of runtimes.
  • Computer demo from class: Big Oh Notation.
  • Lecture notes are here.
  • The lecture recording is on canvas.

Friday, September 9th, 2022:

  • We discussed homework.  We finished talking about runtimes (polynomial, subexponential and exponential).  We analysed the runtime of modular exponentiation.  We introduced notation for the discrete logarithm and covered the Baby-Step Giant Step algorithm.
  • Lecture notes from class.
  • Runtimes computer demo.
  • Video is up on canvas.

Monday, September 12th, 2022:

  • We discussed an example of Baby-Step-Giant-Step and discussed its runtime, then introduced the index calculus.  We did an ill-fated example of index calculus, and then discussed the Logjam attack.  I reminded students they can ask for extra help on proofs and that we have a test on Friday.
  • Nice video example of index calculus (to replace the one from class that was messy).
  • Lecture notes from class consist of two lecture screenshots  and the replacement example.
  • Video on canvas.

Wednesday, September 14th, 2022:

  • We discussed the runtime of the index calculus, and the ElGamal encryption system.
  • Lecture notes here.
  • Video on canvas.

Friday, September 16th, 2022:

  • Module 2 Assesment

Monday, September 19th, 2022:

  • We covered the Euclidean algorithm and extended euclidean algorithm.
  • Lecture notes are here.
  • Video on canvas.

Wednesday, September 21st, 2022:

  • This was a Sage workshop day in class.
  • No notes or video.
  • The Sage workshop can be accessed on sage.colorado.edu with your identikey, and can also be downloaded as a worksheet from the Notes/Resources page (top bar of this site).

Friday, September 23rd, 2022:

  • We covered the Chinese Remainder Theorem, including proof and an example, as well as intuition.
  • Notes are here.
  • Video on canvas (I forgot the first few minutes, and the video didn’t work, only audio)

Monday, September 26th, 2022:

  • We used the Chinese Remainder Theorem to solve square roots by breaking apart the modulus.
  • We proved the euler phi function formula.
  • We introduced the RSA public key encryption algorithm, and began discussing its security.
  • Lecture notes are here.
  • Video on canvas.

Wednesday, September 28th, 2022:

  • We discussed primality testing and timing attacks on RSA.
  • Lecture notes are here.
  • Video will be up on canvas later.

Friday, September 30th, 2022:

  • Class was covered by Joseph Macula, who talked about p-1 factoring and gave two examples.
  • Lecture notes of mine (not exactly what was done in class probably) are here.
  • There is no video.

Monday October 3rd, 2022:

Wednesday October 5th, 2022:

  • We covered RSA signature and signatures in general and introduced hash functions.
  • Lecture notes from class.
  • The video is on canvas.

Friday October 7th, 2022:

  • We talked about hash functions and birthday attacks.
  • Lecture notes from class.
  • The video is on canvas.

Monday, October 10th, 2022:

  • Module 3 test.

Wednesday October 12th, 2022:

  • We introduced a couple of finite fields (size 9 and size 4).  Then we returned to the basics of how to “build” these things by learning to do arithmetic with polynomials with coefficients mod p.  We talked about irreducibles, division, gcd.
  • Lecture notes from class.
  • The video had no sound 🙁 :(.  BUT…. fortunately today I used notes from last time I taught on zoom (the first time I did this!) so I can actually just post the zoom recording from then and it is almost the same as today’s lecture!  So that’s on canvas.

Friday October 14th, 2022:

  • We took up the daily post questions and did the extended euclidean algorithm to find an inverse in a finite field.  We did a “big picture” overview of how we are “redoing” modular arithmetic with polynomials.  We defined a ring and field for context.
  • Lecture notes from class.
  • The video is on canvas.

Monday October 17th, 2022:

  • We did a summary and discussion of applications of finite fields.  Then we introduced elliptic curves and the group law on elliptic curves.
  • Lecture notes from class.
  • The video is on canvas.

Wednesday October 19th, 2022:

  • We talked about the curve addition law, and projective space and put an elliptic curve into projective space.  We talked briefly about how many points there are on an elliptic curve over a finite field.
  • Lecture notes from class Part A (most of it) and a few more pages in Part B.
  • The video is on canvas.

Friday October 21st, 2022:

  • We talked about using elliptic curves to factor.
  • Lecture notes.
  • Video is on canvs.

Monday October 24th, 2022:

  • Elliptic curve discrete log problem, why elliptic curves in cryptography, how to take a square root mod p, how to do diffie-hellman and el-gamal on an elliptic curve, and elliptic curve digital signature
  • Lecture notes.
  • Video is on canvas.

Wednesday October 26th, 2022:

Friday October 28th, 2022:

  • Module 4 Test

Monday October 31st, 2022:

  • Happy Hallowe’en!
  • We defined qubits and their states and measurements.
  • Lecture Notes
  • Video on canvas.

Wednesday November 2nd, 2022:

  • We covered Quantum Key Distribution
  • Lecture Notes
  • Video on canvas.

Friday November 4th, 2022:

  • We discussed security of QKD, entanglement, and a Bell-state-based version of QKD.
  • Lecture Notes
  • Video on canvas.

Monday, November 7th, 2022:

  • We discussed quantum gates and how a quantum computer can compute a classical reversible circuit.
  • Lecture Notes
  • Video on canvas.

Wednesday, November 9th, 2022:

  • We discussed the massive parallelism “paradox” of the quantum computer, then the quantum fourier transform, which is a change of basis.
  • Lecture Notes
  • Video on canvas.

Friday, November 11th, 2022:

Monday, November 14th, 2022:

  • Shor’s algorithm!  Everything except the final phase that involves a continued fraction.
  • Lecture Notes
  • Video on canvas.

Wednesday, November 16th, 2022:

  • Continued fractions to finish off Shor’s algorithm!
  • Lecture Notes
  • Video on canvas.

Friday, November 18th, 2022:

  • Module 5 test.

Monday, November 28th, 2022:

  • Lattices, change of basis, and the basis reduction algorithm.
  • Lecture Notes
  • Video on canvas.

Wednesday, November 30th, 2022:

Friday, December 2nd, 2022:

  • The basic parameters of coding theory (q-ary, length, code, rate, etc.)
  • Lecture Notes.
  • Video on canvas.

Monday, December 5th, 2022:

  • Linear codes and their decoding (syndromes, etc.)
  • Lectures Notes.
  • Video on canvas.

Wednesday, December 7th, 2022:

  • Student Presentation!