All posts by profstange

Your friendly professor.

Due Friday, Sept 8th, 2023:

  1. I’ve updated the discord link in canvas if anyone still needs it (it last one week each time).
  2. In what follows, hand in as much as you got done on canvas.  Remember, an hour of effective, useful work is all I ask.
  3. Quick review question:  What is the inverse of 7 mod 11?  What is the inverse of 7 mod 14?  (Watch for trick questions!)
  4. Compute the Euler phi functions $\varphi(12)$, $\varphi(26)$, $\varphi(27)$.  For each of these $n$, verify your answer by computing the set $(\mathbb{Z}/n\mathbb{Z})^*$.
  5. If the affine cipher key $(\alpha, \beta)$ is `badly chosen’ (i.e. $\alpha$ may not be invertible), then bad things can happen.  Find an example where two different plaintexts encrypt to the same ciphertext.
  6. Some abstract thinking about modular arithmetic.  Prove (explain your reasoning) that:
      1. If you take successive powers of $a$ mod $n$, i.e. $a,a^2,a^3,a^4,a^5,\cdots$, that eventually you will get a repeat (the same residue will appear more than once, e.g. $a^2$ might equal $a^7$). (Hint: finiteness)
      2. If $a$ is invertible, then some power of $a$ is $1$. (Hint: use the first part somehow.)
      3. Can you find an example residue $a$ modulo $n$ for some $a$ and $n$ where no power of $a$ is ever $1$?  You might want to mess around with the various Sage tools on this site.
  7. For remaining time (if any), you have two fun options, pick whichever seems like more fun to do first/at all:
      1. OPTION A:   Practice with modular arithmetic in the context of matrices, with a cryptography flavour.
          1. Read about Hill cipher.  (We mentioned it briefly Friday in class).
          2. Can you find the Hill cipher key?  The Hill cipher (with 2×2 matrices) was used to encrypt the plaintext SOLVED to get the ciphertext GEZXDS.
          3. Consider Hill cipher with the matrix $$\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}$$ modulo $26$.  Can you find two plaintexts that encrypt to the same ciphertext?  (The plaintexts don’t need to be english, they can just be any letters.)  What’s wrong with this matrix?
      2. OPTION B:  Learn a useful new algorithm!  The Double-And-Add algorithm allows for fast exponentiation, among other things; it’s a sort of refinement of successive squaring.
          1. First, watch this video (6:09) which gives a general algorithm.
          2. Use the double-and-add algorithm of the video (by writing 148 in binary) to demonstrate an efficient way to compute $2^{148}$.
          3. Program it if you feel like it.

Due on Wednesday September 6th:

  1. Check out this tool for drawing pictures of the function $f(x)=ax \pmod{n}$.  Try it for $n=5$ and $n=6$ with different $a$’s.  Figure out what it is doing.
  2. Check out this tool for making addition and multiplication tables modulo n.  Try it for n=5 and n=6.  Notice some patterns.  Keep it in mind as a useful tool for future.
  3. Our first ciphertext chain!!
    1. Come up with a short (one word) answer to the question “What’s the coolest math?”  This is your plaintext.
    2. Choose a key $(\alpha,\beta) \in (\mathbb{Z}/26\mathbb{Z})^2$ .   Make sure you choice is suitable as a key, as we discussed in class.
    3. Encrypt the plaintext with affine cipher (by hand, using the cryptography tools sheet if you like).  This gives you your ciphertext.
    4. Post your ciphertext on the discord channel #ciphertexts, along with the key.
    5. Choose the most recent user’s post (besides yours) from #ciphertexts, and decrypt it (by hand).
    6. Post the answer in the form “So-and-so thinks the coolest math is….”.  Use discord’s “spoiler” feature to hide your answer, in case other students want to practice, or end up using the same ciphertext (this never works quite perfectly).
  4. Suppose you eavesdrop on your little sister’s communications, and she is using affine cipher.  Her ciphertext is CRWWZ.  You know she starts every message she writes with “HA” (she’s weird that way).  Decrypt the message.  Explain how you did it.
  5. Come up with the fastest way to compute $3^{519}$ modulo $11$ by hand.  That is, count the multiplications you need to do, and try to minimize that number.  It should be doable by hand (i.e., don’t do 500+ multiplications!!) (Hint: think back to our puzzle at the end of class.)
  6. Hand items #4,5 in on canvas as your record for today’s daily post.
  7. If needed, review injective, surjective, bijective, invertible for functions.  Here’s a discussion that gets right to the point.  Know the definitions, know examples, know a function is invertible if and only if it is bijective, and know that for a function from a finite set to itself, injective, surjective and bijective are equivalent.  (To really see why this is true, try to build a function from $\mathbb{Z}/5\mathbb{Z}$ to itself that is only injective or only surjective.)
  8. The following video (17:26) I made discusses the proof of our “main theorem” from today that multiplication and addition “work” mod n.   The goal of this video for you, here and now, is to understand why it works, and how math formalism guarantees the math we are using is “safe and correct”.  If time remains, watch this; otherwise save for later when you have time.

For Friday, September 1st

Hi all, this is your first daily post with real math content.  Remember, you should set aside a studious hour for this.  If you don’t finish everything in one hour, continuing now or catching up later or skipping things is at your discretion.  Here’s what you should do with your hour before Friday’s class:

  1. Watch my video Modular Arithmetic User’s Manual.
  2. Do this worksheet.  We will take it up at the beginning of class.  (Here’s the LaTeX if you want.)
  3. For the course, we will use Sage Mathematics Software for computations.  Here’s a Sage worksheet that shows how to use Sage as a calculator for modular arithmetic.  Check it out (do each computation by hand and then compare to the computer output).  Note:  worksheets on the course website do not save your data.
  4. Download this daily post worksheet and fill out your info for today’s daily post.
  5. Upload your completed modular arithmetic worksheet (step 2 above) to canvas in the daily post dropbox which is open now, due at the beginning of Friday’s class.  Uploading your daily work helps both of us keep a record of your progress in the course, and allows for occasional feedback from me and the grader, but it will not be officially graded.
  6. Contact me if you have any concerns about the class being recorded.  I *do not* want this to discourage anyone from speaking in class, so talk to me, I can edit the audio if needed.
  7. If you just joined the class, catch up on the first day or two on the “archive” tab above and read all the tabs at the top of the website for syllabus info.
  8. Make it part of your daily (“lecturely”) routine to look over what has been done and catch up on anything missing.
  9. FYI:  The best way to contact me is discord.  If you want to meet in person just let me know.  I will set regular office hours when things settle down.

Prep for 2nd Day!

Hi all!  Thanks for attending class on the first day.  I will be posting recordings to canvas for the students in the class.  We’ll continue the “whirlwind tour” on Wednesday and also discuss class logistics.  I hope you are enjoying the beginning of your semester!

Please read through the tabs at the top of this website and let me know if you have any logistical concerns (particularly test dates).  Please also log into discord (link on canvas)!

Welcome to Fall 2023!

Welcome to Cryptography!

To get ready for day 1, please do the following:

  • Read through the tabs on the top bar of this website (that constitutes the course syllabus).
  • Log into our canvas site.
  • In the canvas site, please use the discord invite link to sign up for discord (please check your username for appropriateness _before_ using the link, and then set an alias on the server which is first name and last name/initial).
  • Please complete the lecture recording waiver in canvas.  I plan to record audio and screencast (not video) during lectures.

See you soon!